Gary J. Shannon
Created: Mar. 3, 2003
Last updated: Mar. 12, 2003
| Random Explorations in Automata
Theory Gary J. Shannon Created: Mar. 3, 2003 Last updated: Mar. 12, 2003 |
|
Bead Racer: Logic Circuits in a Two-Dimensional CA
An early cellular automata (CA) called Wire World, was designed by Brian Silverman in 1987 to simulate the operation of electronic logic gates. Working independantly and without knowing about Wire World, I devised a set of rules that were quite similar to the Wire World rule set. Playing around with both the Wire World rule set and my own rule set I came up with a rule set that I believe is better than either of them for implementing logic circuits. Named after the appearance of the graphics I choose for the program I wrote to explore this rule set, I called my CA, Bead Racer.
[Want to to come out and play? Brian Prentice has kindly provided an MCell user DLL that you can download here, or you can try my own (not quite ready for prime time) Win/95/98/2000 BeadRacer program here. The Bead Racer progam will run either this rule set or the Pipline rule set described here.]
The Rules
The rules of bead racer govern what cells turn to what states depending on the states of their neighbors. Bead Racer has 5 states. These are: WALL, EMPTY, RED PHOTON, BLUE PHOTON, and PHOTON TAIL. The rules controlling the next states are:
This rule set is similar enough to my original rule set that all the devices I discovered and those that were sent to be by others still work correctly with this improved rule set.
The Basic Concepts
There are two kinds of photons, red and blue. For the most part the rules governing them are identical and they move and behave the same way in tracks of empty cells. Because these photons turn to tails when they die the tails block the path behind them forcing them to move in one direction only. Take a look at figure 1 just to get an idea of how these beads race around the tracks we can make for them.
Fig 1. Follow the beads around the race track.
The first simple component we'll take a look at is the battery. This component emits a continuous stream of photons of either color, one every third clock tick. (See figure 2.) This stream of photons should not be thought of as a stream of binary ones and zeroes, or even as a stream of binary ones. Instead, it is a continuous logic state of one, like the continous supply voltage from a real battery. It will only become ones and zeroes when we define a specific pulse width to represent a binary one or zero in a particular circuit. This will make more sense when we start building circuits, but for now just think of it as a steady battery voltage that we can use to makes ones and zeroes with.
Fig. 2. The battery.
The battery itself consists of a three cell loop; the 2 vertical cells and the first cell to the right of that column. It is charged by placing, a head at the end of the path and a tail in the junction cell. From that point on it will continue to emit photons forever.
A second type of battery emits both colors of photons alternately. The two-color battery will come in handy if we ever need a source of both kinds of photons.
Fig. 2.1. The two-color battery.
Playing With Colors
The reason for the two different colors of beads will become apparent when we start to investigate complex logic circuits, but for now lets take a look at a few components that can alter the color of a photon.
As you recall from the rule set if an empty cell has 3 neighbors of either color it will change to the opposite color. The color flipper component is nothing more than a wide spot in the track where 3 photons of like color can spawn side by side. Once they spawn they follow the rule and give rise to one cell of the opposite color
Fig. 3. The color changer.
There will be times when we must take a stream of mixed-color photons and insure that they are all the same color before inserting them into the next stage of the machine. The color normalizer performs this function.
Fig. 4. The color normalizer.
The normalizer works its magic by making a clone of the photon (See the photon cloner in figure 4.2) and simultanesouly changing the color of the original. These two opposite-color photons are then brought back together and since the rule states that two unlike colors will give birth to a red photon, only red photons emerge.
Another color-related component is the color filter. This device will pass blue photons only, and block all red photons from passing through. It can be changed to a filter that passes red photons only by putting one color flipper in front of it and another at the output.
Fig. 4.1. The color filter.
Finally, here's a color cloner. It simultaneously copies a photon and makes an opposite color copy too. This is the heart of both the color normalizer and the the color filter.
Fig. 4.2 The cloner.
Getting the Wires Crossed
There will be times when one stream of photon will need to cross over another stream of photons without either interfering with the other. The theory behind the design was posted to the newsgroup comp.theory.cell-automata by Paul Chapman in response to a question I posted about how to accomplish this. Here is Paul's 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. 4.3 Crossover diagram.
This path-crossing circuit was sent to me on the same day by two different contributors to the comp.theory.cell-automata newsgroup. One was posted on the newsgroup and was arrived in my personal email. Frank Buss of Germany and Ilmari Karonen of Finland can both take credit for this circuit. I call this the Buss-Karonen crossover network in honor of this elegant piece of design work.
Fig. 5. The Buss-Karonen crossover network.
Although one of the contributors showed me the circuit with square corners and the other with the corners clipped as show in the figure, clipped or squared corners will normally have no effect on the operation of a circuit. One limitation of any crossover circuit is that it will only work with same-color photons. This is simply because the crossover uses multiple exclusive OR circuits (see logic gates below) and it is in the nature of Bead Racer that XOR circuits only work with photons of matching color. This is one of those cases when we want to be sure to use a color normalizer before the crossover if there's any doubt about the color of the incoming stream.
For Historical interest only, here is my early attempt at a crossover component. While it does work it is no where near as elegant as the newer Buss-Karonen circuit.
Fig. 5.1. My own crossover
Let's Get Logical -- The Exclusive OR
Since we've already mentioned the exlusive OR circuit in passing, let's take a closer look at it. The exclusive or (XOR) is designed to accept two input streams of photons. The input streams must be matching color photons, so take care to normalize the colors if necessary. The circuit will produce an output stream of photons such that whenever either of the inputs, but not both of them have photons only then will the output have photons. This logic gate is constructed out of a simple T-joint. Since the rules forbid any new photon head to form in an empty cell that has two like-colored neighbors if there are two incoming photons they will cancel each other out. If only one input stream has a photon in it then that photon will spawn two heads in the juntion of the T preventing it from crossing the T (no head spawns where there are 2 red neighbors) and it will simply turn the corner and continue on it's way down the stem of the T.
Fig. 6. The exclusive OR gate.
The OR Gate
Consider what would happen in the XOR if one of the incoming photons was blue and the other was red. The rules state that one red and one blue neighbor will cause a red photon to spawn in any cell they both touch. This is why it is important that the inputs to the XOR be all the same color. But it is also the secret behind the logical OR gate. This gate will produce an output photon whenever there is a photon in either OR both of them. By color flipping one of the inputs the XOR becomes an ordinary OR gate.
Fig. 7. The OR gate.
Notice that the output from the OR gate has mixed color photons. If later stages of the machine requires monchromatic photons only it is important to remember to put a color normalizer after the OR gate.
The Inverter
Another handy component is the inverter, or NOT gate. This component needs to emit a photon whenever there is no photon in the input stream and not emit a photon when there is. In other words, to put out an output stream that has gaps for every input photon and photons for every input gap. This is easily accomplished by attaching a battery to one of the inputs of the exclusive OR gate.
Fig. 8. The Inverter.
The AND Gate and DeMorgan's Law
The logical AND gate will, as the name implies, produce an output photon only when both input A, AND input B contains a photon. If we examine the rules of Bead Racer state generation we will find that the the only rule that spawns a photon for two neighbors is the rule that applies to the case where there is one red and one blue neighbor. We might think that this rule could form the basis of an AND gate. But this is not the case. For every case where only one photon arrives at the junction of the gate the rules insist that a photon head spawns and the photon gets through the gate alone.
Since the rules do not give us what we need to build an AND gate, how do we accomplish this task? In formal logic there is a law known as DeMorgan's law which, simply stated, is that NOT( NOT ( A ) OR NOT ( B ) ) is equivalent to A AND B. If that sounds confusing don't worry about it. Just trust that it works and your trust will be repaid.
So the secret to the AND gate is to invert both inputs, push them through an OR gate and then invert the output. This makes the AND gate a bit more complicated than the logic gates we've looked at so far, but it is an important logic component to have.
Fig. 9. The AND gate.
Notice that at the beginning of the animation sequence there is one photon in the upper track and two in the lower track. At the end, only where the two photons entered together is there an output photon. Notice also the color normalizer embedded in the middle of the circuit. Without this it would not work properly.
The NAND Gate
A comonly used gate in practical applications is the NAND, or NOT-AND. So important is the NAND gate that any logic circuit built from all the other kinds of gates can actually be built using nothing but NAND gates! In Bead Racer the NAND gate is easy now that we have the AND. We simply remove the invertor from the end of the AND and voila. There's no need to animate the NAND since the internal operation is exactly like the AND in figure 9.
Fig. 10. The NAND gate.
Flipping and Flopping
A flip-flop is a bistable component that can be set to either one of two states, and will remember that state until it is switched to the opposite state. In our case the two states are emitting a stream of photons and not emitting a stream of photons. We could, of course, build a flip-flop out of NAND gates, and that would work perfectly fine. But as it turns out in Bead Racer there is a basic bi-stable component that is very much simpler than that. I call it the memory gate or M-gate.
Fig. 11. The M-gate.
There are a lot of different kinds of flip-flops in the world with names like "D-flop", "T", "R-S", and "JK" just to mention a few. Some of them are activated by a "level" and some are activated by an "edge". We'll get into that in more detail when we start looking at pulses, timing and sequential logic a bit later. But for now notice that the M-gate is activated by a single photon. If we send it a pulse that is two photons wide the first photon will turn the memory on and the second one will immediately turn it off. For this reason we need to be sure that when we send an on/off signal to an M-gate that it is only one photon long.
That's rather a fussy requirement. It would be better to have a flip-flop that could be set or reset by a pulse of any length. But before we can accomplish that task we need to take a look at pulses, and the various things we can do with them.
Before we leave M-gates here are a couple of intersting facts. When the gate is turned on by a red photon it must be turned off by a red photon. A blue photon will have no effect. When a gate is turned on by a blue photon it can only be turned off by a blue photon, but in this case a red photon, instead of turning the gate off, will switch its color to red.
Manipulating Pulses
In real world logic circuits signals usually come and go on a regular schedule. When we talk about a 1 gigahertz microprocessor we are saying that the master clock that governs the flow of pulses in the computer runs at 1 billion pulses per second. Even at such speeds the pulses in your computer obviously consist of more than one electron just as pulses in a Bead Racer machine can consist of more than one photon.
The defining characteristic of a pulse is that unlike the stream of photons coming from the battery component of figure 2, a pulse has a definite beginning and a definite end. Photons are not data until the timing of the data pulses has been defined.
Fig. 12. Level vs. Pulses
In figure 13 notice that we have the same stream of data in both the upper and lower half of the illustration, but that the clock pulses are different. What that stream of data means depends entirely on the timing of the clock pulses. In this diagram when the line in is the upper position that indicates that photons are flowing and when it is in the lower position that means that no photons are flowing. How many photons are in each pulse we don't know. It might be one or it might be a million, and as far as desigining pulse manipulation circuits it shouldn't matter.
Figure 13. The clock defines what the data means.
Later when we get into counters, shift registers and adders we'll be taking a closer looked at clocked logic, but for now it is enough to be aware that pulses exist and that they have a beginning and an end.
The Differentiator or Edge Detector
Here's a handy little component that will tell us when a pulse begins and ends. Notice that the output from the differentiator or edge detector is one photon when the first photon of the pulse arrives and one more photon when the first gap arrives. The original pulse is shown in the lower track for comparason.
Fig. 14. The differentiator or edge detector.
If we wish to reconstruct the original pulse we can send the two edge dector pulses into an M-gate and the first pulse will turn the stream on while the second will turn it off and the output from the M-gate will reconstruct the original pulse exactly.
Pulse Detector
The edge detector gave us two photons for every pulse, one for the leading edge and one for the trailing edge. The following circuit gives us one photon for the leading edge of the pulse only. The circuit is shown stretched out to make it easier to see how it works. In the first section the lower loop is one photon longer than the upper loop so when the two branches are OR'd together they produce a pulse that is one photon longer than the original. However, because of the way the OR gate works the first photon in the new pulse is a blue photon.
Fig. 15. One photon per pulse of any length.
By using the color filter to discard all but the first photon we create a single photon marking the leading edge of the original pulse, no matter how long that pulse is. We've also added a color flipper after the filter to insure that the output photon is always a red one.
By moving the color flipper in the first section to the lower path we change the circuit to a trailing edge detector that only emits a single photon when the incoming pulse turns off.
Fig. 16. Changing from leading edge
to trailing edge detection.
We can now put a pulse detector in front of the M-gate and have a memory element that can be turned on with one pulse and later turned off with a second pulse, and those pulses can be of any length.
Pulse Generator
As we saw earlier the M-gate will turn on when it receives a photon and then turn off with the next photon input. What that means is that if we hook a battery up to the input the M-gate will turn on and off with every other photon and create a series of pulses one photon wide. If we Put this series of pulses through another M-gate it turns the flow on and off again, but half as fast, giving us a train of pulses that are 2 photons wide.
Fig. 17. The binary pulse generator.
Now it should be easy to predict what we will see when we put more than one M-gate in a row. By letting each photon in the output turn the following M-gate on and off we should see a series like this:
11111111111111111111111111111111111 -- Input pulses 10101010101010101010101010101010101 After 1 M-gate. 11001100110011001100110011001100110 After 2 M-gates 10001000100010001000100010001000100 After 3 M-gates 11110000111100001111000011110000111 After 4 M-gates ... 11111111000000001111111100000000111 After 8 M-gates
The pattern tells us that after 8 M-gates 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 a total of 8 M-gates by the last stage we see the results in figure 17.
Phase Matching and Propagation Delay
There's one important aspect of logic circuit design that we've glossed over until now. In case you haven't noticed the logic circuits we've looked at so far all require that the photons arrive at the logic gate in perfect step with each other. Since the photon cycles every 3 clock ticks there are two ways to get this wrong and only one way to get it right.
Fig. 18. Two wrongs and a right.
Notice that the head of each photon must arrive at the same logic gate at the same time. Now there are some advanced design tricks you can use that deliberately use out of phase photons, but we'll leave that for later.
Even after we take care to match up the phase of the photons our troubles may not be over. There is also the matter of making sure that pulses that are supposed to work together actually stay together. Figure 19 illustrates what would be a perfectly innocent procedure in real world electronics; turning a corner with a wire or printed circuit trace. But in a Bead Racer machine this corner has disasterous consequences. The perfectly matched pulses on the top leg are completely out of step after rounding the corner.
Fig. 19. The not-so-innocent corner.
There are two ways to solve this problem. The first is to pay particular attention to path lengths to make sure that pulses stay in step with each other, and the second is to make the pulses longer so that they still overlap to some extent. In figure 20 we show the same corner with pulses of four photons each. After rounding the corner there is still some overlap in the pulses and this may be good enough for our purposes in some cases.
Fig. 20. Overlapping pulses.
In a real-world logic circuit the pulse travelling down the wires may be billions of electrons long and so it makes little difference if we introduce a few electrons worth of delay into one of the pulses. But in a Bead Racer machine we would rather not deal with pulses a billion photons long. The problem then becomes one of finding a pulse length that is long enough to work properly but short enough that it doesn't take forever to get anything done.
In general, the faster pulse rate you wish to run your Bead Racer machine with the more critical it is to pay attention to path lengths.
In the example of figure 20 if we fed these two inputs into an AND gate we would still see a single pulse output but that pulse would be only 2 photons long. If we went to a pulse length of 8 photons on the input then we would have 6 of those photons still overlapping. A pulse length of 65,536 photons would emerge with 65,534 of the photons still overlapping, so the longer the pulse length the less significant is the loss from propagation delay.
In some cases there are other problems created by non-overlapping pulses. The XOR gate, for example, should have an output of no photons at all for two perfectly matched pulses. Instead we will get a brief 2-photon pulse before the overlapping section and another 2-photon pulse after the overlapping section. Only the center of this stream of photons is correct data.
Fig 20.1. Data glitches caused by propagation delay before the XOR.
If our pulse length is 4 that's a big problem. But with a pulse length of 65,536 those two extraneous pulses at the beginning and end are transients that represent only 3/1000th of a percent of the total pulse length. By re-sychronizing the output to the clock pulses these transients are discarded. This kind of transient response or jitter is sometimes seen in real-life logic circuits but the glitches can be removed by re-synchronization.
Fig. 21. Resynchronizing for glitch-free pulses.
In the top waveform in figure 21 we see pulses with glitches introduced by propagation delay, just as in figure 20.1. The second pulse train is the sychronizing pulse that tells when it is safe to sample the incoming dirty pulses. The bottom trace shows how by AND'ing the dirty input with the clocking pulse and by using the result to reconstruct pulses of standard length we have eliminated the transient noise and reconstructed the data pulses clean and glitch-free.
Since re-synchronization is a complicated procedure and since we want our Bead Runner machines to run as fast as posisble we will, for the most part, be building machine where careful attention is given to path lengths so our pulses will stay in step with each other.
Building a Working Model of the Pentium® Chip
Just kidding. But seriously, we already have a lot of the pieces we would need to build quite a few working digital devices. But before we do let's take a brief side trip into the world of batteries. Up till now we have used a battery that emits photons every three clock ticks. Many of the components we have investigated so far depend on this standard. But other types of "supply voltages" are possible. Here, for example, is a battery that emits a photon every four clock ticks.
Fig. 22. The 4-cell battery.
While most of the components we have investigated so far will work just as well with the 4-cell battery some of them will not, and others will work, but differently than they do with the 3-cell battery. For example, the M-gate requires photons that arrive on a 3-phase schedule to turn off and since only every 4th photon from the 4-cell battery arrives at the right time, the output is a pulse of four 3-phase photons followed by a 4-phase gap. This kind of photon spacing will mess up both 3-phase circuits and 4-phase circuits. However, other components, including a 4-phase M-gate, are possible that would work only with a 4-cell battery. These remain to be investigated in the future.
Fig. 23. The 4-cell battery with the 3-phase M-gate.
Coming up on Page Two
On the next page we will build some real flip-flops of the S-R, T, and JK varieties. Then we will investigate binary counters and shift registers along with frequency-resonant components and various circuits that generate random numbers.
Page two under construction. Check back soon. (Mar. 9, 2003)