Simple cellular automata as pseudorandom m -sequence generators for built-in self-test
Makoto Matsumoto · ACM Transactions on Modeling and Computer Simulation · 1998
We propose an extremely simple and explicit construction of cellular automata (CA) generating pseudorandom m -sequences, which consist of only one type of cells. This construction has advantages over the previous researches in the following points. (1) There is no need to search for primitive polynomials; a simple sufficient number-theoretic condition realizes maximal periodic CA with periods 2 m − 1, m =2, 3, 5, 89, 9689, 21701, 859433. (2) The configuration does not require hybrid constructions. This makes the implementation much easier. This is a modification of the Rule-90 by Wolfram. We list our CAs with maximal period, up to the size 300. We also discuss the controllability of the CA, randomness of the generated sequence, and a two-dimensional version.