|
Articles Computation Theory Random Sequence Generation by Cellular Automata (1986)
Random Sequence Generation by Cellular Automata (1986) |
|
The cellular automaton of Eq. (3.1) is one of the simplest that seems good for random sequence generation. But other cellular automata may also be considered, and some potentially have certain advantages.
Among 
, 
cellular automata, Eq. (3.2) is the only other serious contender. No direct equivalence between this rule and that of Eq. (3.1) is known, but their properties are very similar. Equation (3.2) gives however [45]
slightly smaller than the corresponding result (5.2) for Eq. (3.1). In addition, it gives a slightly smaller invariant entropy 
. It seems to have no advantages over (3.1).
Cellular automata with 
or 
may also be studied. (Here 
is defined as the total number of sites in the neighbourhood for the rule.) Any class 3 (chaotic) cellular automaton rule can be considered a candidate random sequence generator. Autoplectic rules which produce complex patterns even from simple initial conditions are probably best. Some of these rules have larger Lyapunov exponents and invariant entropies than Eq. (3.1), but they are also more difficult to compute. In addition, many rules that seem to produce chaotic overall patterns nevertheless yield sequences that show definite regularities, resulting, for example, in non-maximal temporal entropies. Permutive chaotic rules avoid such problems, but are very similar in character to the rule of Eq. (3.1), and so potentially share any of its possible deficiencies.
possible values for each site and depending on strictly previous site values. The rules given are ``totally quiescent,'' so that 
for all 
. The rules are specified by giving the values of 
as digits in a binary number indexed by a number formed from the arguments of . The binary number is then stated in base 32, with letters of the alphabet representing successive digits greater than 9. Leading zeroes are not truncated. Long specifications correspond to rules with larger values of .One possibility is to consider bijective cellular automaton rules, which are invertible, so that each configuration has both a unique successor in time, and a unique predecessor. The state transition diagrams for such cellular automata in finite regions with periodic boundary conditions can contain only cycles, and no transients. But only a very small fraction of all cellular automaton rules are bijective, and very few of those that are exhibit chaotic behaviour. Table 12.1 gives some non-trivial bijective cellular automaton rules with and 
(cf. [41]). None of those with 
are chaotic.
, cellular automata with rules of the form (12.2).With larger effective , it is nevertheless possible to construct chaotic bijective rules explicitly. One method [42] yields cellular automaton rules that are most easily stated in terms of dependence on second-to-last as well as immediately preceding site values:
Such rules may be stated in the standard form (2.1) by considering sites with 
possible values. Some examples of patterns generated by rules of the form (12.2) are shown in Fig. 12.1. The rules are bijective, so that all states lie on cycles. However, there are often many distinct cycles, each quite short, making the system unsuitable for random sequence generation.
