next up previous contents
Next: Four tables for Up: The Margolus neighborhood Previous: The neighborhood

Rule of evolution

The fundamental construction is a mapping of a square, consisting of four cells, into itself; in each halfCAM the cells have four states, gotten by combining the two binary bitplanes. Each cell therefore requires a function of four four-state variables to describe its evolution. One way to represent the situation would be to use four tables. The result is more manageable than using a single matrix, but still requires the manipulation of quite a bit of data.

As with other automata, selections can be simplified by introducing totalistic rules or other specialized combinations. However, the Margolus neighborhood seems to have been designed with the specific intention of emulating a lattice gas, and moreover, reversibly so.

Therefore, when the CAM is operating in Margolus mode, the lookup table in the CAM as well as the circuitry required to implement it, has been arranged to favor this particular application. To the user, it appears that the same rule by which one single cell evolves from four neighbors has been applied differently according to the parity of the coordinates, albeit in a very symmetric way --- by rotating the neighborhood.

Just for that reason it is recommended that the neighbors not be thought of as lying to the north, south, east, or west; rather they are situated clockwise, counterclockwise or diagonally opposite, all relative to the cell itself which occupies the corner required by parity.

If this were all there were to the matter, rules could be defined with great ease. Indeed, it is a good arrangement for creating Moore automata, giving each corner a rotated version of the same rule. The rule need not always be the same, of course.

However, as originally conceived, the CAM lookup table had twelve address lines, whose meanings could be varied somewhat by both software and hardware switches. Without worrying about variants, for von Neumann neighborhoods, five neighbors with four states (two bits each) in one half-CAM plus the center cells in the other half-CAM fills the quota. For Moore neighborhoods, nine cells in one plane together with three more center cells gives the pertinent dispensation of twelve bits.

Margolus neighborhoods require only eight bits to achieve four states in each of four cells, leaving four bits free. These free bits can be assigned to two parity bits (four parity combinations) and two phase bits, giving four distinct tables (phase bit combinations) each of which distinguishes the parity of the coordinates in the square sublattice. The tables can be completely separate, rotated versions of a single table, or a combination of the two.

But the additional addresses could also have been given over completely to the phase bits, leaving sixteen different tables to be applied uniformly to all the cells.

Finally, custom configurations can be brought in by invoking the user options and hardware jumpers.



next up previous contents
Next: Four tables for Up: The Margolus neighborhood Previous: The neighborhood



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx