A cellular automaton (CA)
is specified by a regular lattice of sites or cells,
a set of possible cell states, and a
deterministic local
rule which is used to update the state of each of the sites on the lattice.
All cellular automata considered here operate on the 1-dimensional
lattice. The cardinality of the set of states possible at each lattice site
is a power of 2.
A cellular automaton, 
, can
be described formally as follows. Let r be the radius of the
cellular automaton rule. r gives the range of sites to the left
and right of a given site whose values at time t could
influence the value of the given site at time t+1. Let
be the array of values of all of the sites in the lattice at
time t, and let i index the sites. Then,
For example, consider a nearest-neighbor 2-state per cell rule. The
neighborhood of a state
can be represented by a binary triple {left neighbor, cell, right neighbor }.
There are eight possibilities:
.
A cellular automaton rule table specifies the cell state at time t+1
resulting from each possible neighborhood configuration at
time t. There are 256 different rules of radius 1. One of them
states that the neighborhoods {001}, {100}, {010}, and {101} lead to 1, and all
other neighborhoods lead to 0. This rule is known in the
CA literature as rule 54 [13] . The pattern generated by this rule
starting from a random initial configuration is shown in figure 2.1.
Its rule table is found in column 1 of table 1.
The evolution of the nearest-neighbor rule 54. An initial 256-bit block was chosen randomly, and iterated for 256 generations, with periodic boundary conditions imposed. Time runs from top to bottom of the page.
Rule 54 is an irreversible rule. Under a general irreversible rule, some blocks have many preimages, while others have none. The irreversible rules used in CA-1.0 are such that all blocks have preimages. How this property is used to advantage in cryptography is explained in the next section.