CA Explorations -- More Circuits

Random Explorations in Automata Theory
Gary J. Shannon
Created: Mar. 4, 2003
Last Updated: Mar. 4, 2003

CA Logic Circuits Continued - Defining Logic States

If we have a steady stream of photons that will represent the logic state "1". Wherever there is a photon missing that will represent logic state "0". Notice that the photons come in streams with one photon every 3 ticks. The spaces between these photons are not binary zeros. A binary zero only exists where a whole photon (or more) is actually missing from the stream. That being the case our generator does not create a stream of ones and zeros, but instead it creates a solid stream binary ones that lasts forever. In order to create pulses of ones and zeros we need to chop out some of the photons from the stream created by the generator.

This can be accomplished with a memory circuit, but before we see how, lets look at the operation of the memory circuit. In figure 1 you will see an offset pair of notches in the pipe. This notched area works like a generator in that it continues to send out photons forever. However, unlike a regular generator this generator can be turned on and off. If one single photon comes down the input pipe from the left the generator will stop generating and be left empty.

Fig. 1. The memory device.

But how do we turn the generator back on? Simple. Send another single photon down the input channel and the the generator will once again start generating a stream of pulses. In other words, the memory device is like a switch that remembers if it has been switched off or switched on.

Stream Choppers and Pulsewidth Doublers

Now what happens if we send a continuous stream of binary ones to the memory device (MD)? The first photon turns the generator on long enough to emit one photon before the second photon comes along and turns it off again. We should expect to see that the MD generate half as many photons as it receives, and looking at figure 2, that is precisely what we observe.

Fig. 2. Generating pulses one photon wide.

Now it should be easy to predict what we will see when we put more than one MD in a row. If each 1 turns it on and off we should see a series like this:

11111111111111111111111111111111111 Input stream
10101010101010101010101010101010101 After one MD
11001100110011001100110011001100110 After 2 MD's
10001000100010001000100010001000100 After 3 MD's
11110000111100001111000011110000111 After 4 MD's
...
11111111000000001111111100000000111 After 8 MD's

The pattern tells us that after 8 MD's we should see a pulse 8 photons longs followed by 8 photons worth of empty space and then repeating 8 on, 8 off. Running the experiment with 8 MD's we see the results in figure 4.

Fig. 4. The 8-on, 8-off pulse train.

Differentiators and Integrators

A differentiator delivers one photon whenever the incoming pulse changes from 1 to 0 or from 0 to 1. In other words it detects the edges of the pulse, and is frequently called an edge detector for that reason. The circuit of figure 5 performs this function. The input pulse is 5 photons long and the output is only 2 photons, one marking the first 1 in the stream and another marking the first 0 after all the ones have gone by.

Fig. 5 With the inset showing the original pulse.

Now suppose we want to put the original pulse back together just from the two edge-marking photons. How can this be done? As it turns out, that is exactly the function performed by the memory device we looked at above. The first photon will turn the MD on and it will continue to generate photons until the second photon turns it off. The result will be an exact reconstruction of the orignal pulse.

Getting the Wires Crossed

Crossing one pipe over another is easy in 3 dimensions, but how can we cross one pipe "over" another when there is no "over" in 2 dimensions? How can we mix the two streams of photons together in the middle and then take them back apart again so that the data in them is preserved? Thanks to Paul Chapman on the comp.theory.cell-automata newsgroup for the suggestion on how to accomplish this. Here's Paul's circuit diagram:

    |->----A---->-|
    ^             v
A->-|             |->-A xor (A xor B) = B
    v             ^
    |->-A xor B->-|
    ^             v
B->-|             |->-(A xor B) xor B = A
    v             ^
    |->----B---->-|

       Fig. 6 Crossover diagram.

Figure 7 shows the same circuit built out of the components we've already seen. The spots marked "S" are the splitters where one photon is split into two photons. The original B photon, for example, is sent to the "A xor B" gate and its clone is sent around back to the "(A xor B) xor B)" gate. The two loop-like structures marked "D" are there to increase the distance the photon must travel in order to delay the photon so that it reaches the second XOR gate at the same instant that its clone also reaches the same gate through the first gate. "X" marks the spot where the exclusive OR gates are placed. When we looked at the XOR gate on the previous page it looked a lot larger than what we see here. But the heart of the XOR is only 4 cells arranged in a short T-joint. There is no need to spread things out just for the sake of clarity when building a real circuit, so we've packed devices as close together as possible and still allow them to work.

Fig 7 The Crossover.

This circuit is a good example of how the devices we've looked at so far can be packed together to do something genuinely useful. It also demonstrates the importance of phase and timing. For the XOR gate to work properly the two incoming photons must be timed to arrive on precisely the same tick of the clock. Not only that, but in this circuit after we've cloned a photon we have to be very careful that it is the very same photon that later interacts with its clone in the final stage of the process. That's the reason for the delay loops, and one of the reason the whole device is so large.

The crossover can probably be designed to be somewhat smaller than this, and visitors to this page are invited to tackle the challenge if they are so inclined.

{Update: See smaller and more elegant crossover here. This is in the section for the Bead Racer CA but it works in this CA as well.)

Frank Buss has worked out some nice logic gates using a generator that supplies one photon every 4 ticks instead of the 3 tick per photon style that I've used here. It may be that this slower pulse rate is more versatile than my original 3 tick pulse rate. Have a look at what he's done.