11. Practical Implementation

The simplicity and intrinsic parallelism of the cellular automaton rule (3.1) makes possible efficient implementation on many kinds of computers.

On a serial-processing computer, each site could be updated in turn according to (3.1). But in practice, site values can be represented by single bits in say a 32-bit word, and updated in parallel using standard word-wise Boolean operations. (Additional bit-wise operations are often needed for boundary conditions.)

On a synchronous parallel-processing computer, different sites or groups of sites in the cellular automaton can be assigned to different processors. They can then be updated independently (though synchronously), using the same instructions, and with only local communications.

Very efficient hardware implementations of (3.1) should also be possible. For short registers, explicit circuitry can be included for each site. And for long registers, a pipelined approach analogous to a feedback shift register can be used (cf. [39]).

The evidence presented above suggests that the cellular automaton of Eq. (3.1) can serve as a practical random sequence generator. The most appropriate detailed choices of parameters depend on the application intended. The most obvious constraint is one of cycle length. To obtain a cycle length larger than , Table 9.2 shows that a circular register of length can be used. Cycle lengths tend to increase with , but Table 9.2 shows some irregularities. Thus it is not clear, for example, how large need be to obtain a cycle length larger than . But based on Eq. (9.1), a value should certainly suffice.

Random sequences can be obtained by sampling the sequence of values of a particular site in a register updated according to Eq. (3.1). The theoretical and statistical studies described above support the contention that such sequences show no regularities. For some critical applications, it may be best however, to sample site values only say on alternate time steps. While this method generates a sequence more slowly, it should foil prediction procedures along the lines discussed in Section 7.

[ Figure 11.1 ] Patterns obtained by various procedures in registers of size . CA30 stands for the cellular automaton of Eq. (3.1), with periodic boundary conditions. CA60 is the linear cellular automaton of Eq. (2.4), again with periodic boundary conditions. LFSR is a linear feedback shift register with size and period . For the taps are at positions 14 and 17; for , they are at positions 27 and 29. LCG is a linear congruential sequence generator, operating on the 32-bit integers whose binary digit sequences are given. The seed in all cases consists of a single nonzero bit in the center of the register. Statistical properties of the sequences produced are given in Tables 10.1 and 10.2.

Sequences could potentially be obtained more quickly by extracting the values of several sites in the register at each time step. But Eq. (4.6) implies that some statistical correlations must exist between these values. The correlations are probably minimized if the sites sampled are equally spaced around the register. Nevertheless, in some applications where only a low degree of randomness is needed, it may even be satisfactory to use all site values in the register. (An example appears to be approximation of partial differential equations, where randomness can be used to emulate additional low-order digits.)

The random sequences obtained from Eq. (3.1) have an equal fraction of 0 and 1. Many applications, however, involve random binary choices with unequal probabilities. There is nevertheless a simple algorithm [40] to obtain digits with arbitrary probabilities. First write the probability for outcome 1 as a binary number. Then generate a random binary sequence with a length equal to this number. The output is obtained by an iterative procedure. Begin with a ``current result'' of 1. Then, starting from the least significant digit in , successively find a new result by combining the old result with the corresponding digit of , using a function AND or OR, depending on whether the digit in is 0 or 1, respectively. The final result thus obtained is equal to 1 with probability exactly .

Configurations in two length registers with slightly different seeds should become progressively less correlated under the action (3.1) as a result of the instability discussed in Section 5. The characteristic time for this process is governed by Eqs. (5.1) and (5.2), and should be . Thus, if several sequences are to be generated with seeds that differ only slightly (obtained for example from addresses of computer elements), then (3.1) should be applied at least times to the seeds before beginning to extract random sequences.

One may compare the scheme for random sequence generation described here with the linear methods now in common use (e.g., [1]). Figure 11.1 shows patterns produced by these various schemes. The primary feature of linear schemes is that they can be analysed by algebraic methods. As a consequence, certain randomness properties can be proved for the sequences they generate, and cases that give long cycles can be identified. But the simplicity in structure which underlies this analysis also limits the degree of randomness that such schemes can produce. The nonlinear scheme described here is not readily amenable to complete analysis, and no significant limits on the degree of randomness it yields are known. But on the other hand, no conventional mathematical proofs for particular randomness properties can be given, and it must be investigated by largely empirical methods.

previous  l  next