This invention relates to random sequence generators and in particular to a one-dimensional cellular automaton for generating random sequence signals.
Sequences that seem random are needed for a wide variety of purposes. They are used for unbiased sampling in the Monte Carlo method, and to imitate stochastic natural processes. They are used in implementing randomized algorithms on digital computers, and their unpredictability is used in games of chance. Random sequence generators are used as repeatable noise sources for electronic testing purposes.
To generate a random sequence on a digital computer, one starts with a fixed length seed, then iteratively applies some transformation to it, progressively extracting a random sequence which is as long as possible. In general, a sequence is considered "random" if no patterns can be recognized in it, no predictions can be made about it, and no simple description of it can be found. However, even if the sequence can be generated by iteration of a definite transformation it can nevertheless seem random if no computations done on it reveal this simple description. The original seed must be transformed in such a complicated way that the computations cannot recover it.
The fact that acceptably random sequences can be generated efficiently by digital computers is a consequence of the fact that quite simple transformations, when iterated, can yield extremely complicated behavior. Simple computations are able to produce sequences whose origins can apparently be deduced only by much more complex computations.
Most current practical random sequence generation computer programs are based on linear congruence relations (of the form x'=ax+b mod n), or linear feedback shift registers of the type discussed in "Shift Register Sequences", S. W. Golomb, Holden-Day (1967). The linearity and simplicity of these systems has made complete algebraic analysis possible, and has allowed certain randomness properties to be proved. But these characteristics also lead to efficient algebraic algorithms for predicting the sequences (or deducing their seeds), and limits their degree of randomness.
There are many standard mathematical processes which are simple to perform, yet produce sequences so complicated that they seem random. An example is taking square roots of integers. Many physical processes also yield seemingly random behavior and, in some cases, the randomness can be attributed to the effects of an external random input. Thus for example "analog" random sequence generators such as noise diodes work by sampling thermal fluctuations associated with a heat bath containing many components. Coin tossings and Roulette wheels produce outcomes that depend sensitively on initial velocities determined by complex systems with many components. It seems however that in all such cases, sequences extracted sufficiently quickly can depend on only a few components of the environment, and must eventually show definite correlations.
I have found that randomness in many physical systems may not arise from external random inputs, but rather through intrinsic mathematical processes. This invention makes use of such a process employing a one-dimensional cellular automaton.