The Cellular Automata of John von
Coders, decoders and
The coders are the most
common type of automaton organs. A coder is a quiescent-cell assembly that, once activated
by a single pulse, generates an activation
train to be interpreted as
a bit sequence. The following figure shows a coder as designed by von Neumann.
On the left, the coder
is shown in the moment of its activation. On the right, it is shown just after the generation of the activation train propagating along the output
line (the pulse sequence corresponds to the bit sequence
10101001 in reverse order). The
coding procedure exploits four basic properties common to both JVN and EVN transition rules:
1) The bifurcation of an activation
train at a confluent-state.
2) The relative delays of activation
trains propagating along transmission lines of different length. 3) The one-step delay
caused by the transit of an activation train across a confluent-state. 4) The logical
OR of activation trains converging to a transmission line.
Von Neumann's coders
were used by Pesavento and the Author to implement automata
now saved in files whose names are often marked as _OLD. Actually, the simplest general method to build coders
is that exemplified in the following figure
which shows how isolated confluent states aligned in the input line can be exploited to space at desired positions the pulse sequence generated by the coder.
Sometime, however, the
Author, found it often preferable to exploit various informal tricks to create coders
of irregular shape minimum size. The automaton-file CODER_COLLECTION.EVN and the fragment-file CODER_COLLECTION.EFR contain a wide repertoire
of such informal coders with their
trains indicated aside.
The decoders are
another important class of automaton organs. Their role is detecting whether a given activation train contains a certain bit sequence as a subsequence. This process is often sufficient
to discriminate different activation
trains, for instance when working with multiplexers. To
perform the filtering function,
the decoder exploits the logical
AND property of two activation trains converging
to a confluent state working as a coincidence device. The figure here below shows a decoder
as designed by von Neumann.
At input, the activation train carrying the bit sequence 10101001 enters the coder. At output, a single pulse
is emitted. Were there only a single 1 missing from the bit-sequence, the decoder
would not emit the output pulse. The cell assembly reported above evidences the decoding procedure. The
propagating along the input line bifurcates at 4 confluent states equally spaced along
the input-line continuation. Note that there are as many bifurcations as there are ones in the bit
sequence. The upward transmission
lines stemming from these bifurcations have
different lengths, in order to cause suitable delays, and converge to the output line through confluent states working as logical ANDs. Thus, an activation
pulse reaches the output line
only when two pulses target
simultaneously all logical ANDs. The time delays are chosen so that: (1) the pulse
transmitted by the first upward-line reaches the first logical
AND (second confluent state in the output line) in coincidence with the pulse coming from the second upward-line. (2) The pulse
transmitted by this confluent state reaches the next logical
AND (third confluent state in the output line) in
coincidence with that coming from the third upward-line, etc. Note that
the relative delays between
consecutive upward-lines (from left to right) are exactly 2, 2, 3, which correspond one-to-one
to the numbers of zeros in the sequence
10101001, i.e., 2-1, 2-1, 3-1.
This property can be
generalized to decode activation
trains of any sort. As with coders, there are alternative ways to implement decoders. The automaton-file
DECODERS.EVN and the fragment-file DECODER.EFR contain a few examples of coder-decoder pairs with their
respective characteristic activation
trains indicated underneath the connection lines.
A decoder simply
checks whether an activation
train contains a given bit-sequence as a subsequence, but not whether
it carries a precise bit sequence.
The organs capable of performing the latter operation are called recognizers. Since a bit sequence has more "ones" than any one of its
proper subsequences, to build a recognizer it suffices that the pulse released by the decoder
is cancelled if the activation
train contains more pulses
than expected. Indeed, the recognizers described in von Neumann & Burks' book, are nothing else but decoders provided with a secondary organ that do just
this. The cancellation of the pulse
at output is usually performed by exploiting a property of the special transmission states (red
arrows): a pulse delivered by a red arrow annihilates any ordinary transmission state (blue arrow) that it points to, no matter whether quiescent or not. Actually, the
cancellation is caused by the annihilation
of a right blue-arrow in the output line before the arrival of the pulse
released by the decoder.
Thus, when the pulse meets this vacuum state, instead of passing, a sensitized-state sequence restores the missing right arrow.
The recognizers used in several EVN automata implemented by the Author, however, exploit a different method
exemplified by the recognizer of the bit-sequence
101001 shown in the figure here below.
The secondary organ (underneath the
input-line level) is not a pulse counter but a coder
that generates a repetitive sequence of pulses (of
input-depending length) if the
input train has the expected number of pulses, otherwise a sequence with at least one gap if the number
of pulses. The device must then work so that the pulse
at output disappears unless the activation
train generated by the coder
has at least one gap. The propagation of this secondary train is timed in such a way that at a gap
reaches the confluent state near the red
arrow in coincidence with the pulse emitted by the decoder. Since this confluent state behaves as a logical
AND, the red arrow releases a pulse
only if the activation train has a gap.
RECOGNIZERS.EVN and the fragment-file RECOGNIZERS.EFR contain several examples of such recognizers with their characteristic
bit-sequences indicated aside. These organs are used in the universal constructors and self-reproducing
automata described in the EVN-automaton
gallery to control the
actions of the C-arm in correspondence with particular activation
train working as specific