New cellular automata design based on transformation sequence programming

Abstract

Cellular automata based pseudorandom number generators (CA PRNG) are widely used in various fields. CA that generate highly random sequences have register transformation functions with more inputs over a non-local neighborhood while time-varying transformations are also used. These sequences are shown to pass all DIEHARD statistical tests, however their complex designs are difficult to analyze and desirable sequence properties such as period and distribution are not guaranteed. We propose the design of analyzable CA PRNG that uses transformations from a novel set generated by a maximum length CA. The two characteristics yielding highly random sequences are used in our CA PRNG while guaranteeing desirable statistical properties such as balanced distribution, maximum period length etc. Nonlinearity can also be indirectly introduced into the generated sequences without the usual high cost of nonlinear Boolean functions. Simulation and experimental results have been provided to show improvement in the randomness quality of sequences over existing CA designs.