Simple Cellular Automata as Pseudorandom m-Sequence Generators for Built-In Self-Test

Matsumoto Makoto

ACM Transactions on Modeling and Computer Simulation

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 2m - 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.

Cellular automata

Finite fields

M-sequence

Pseudorandom number generation

VLSI

Mathematics [ 410 ]

eng

ACM

Copyright (c) 1998 ACM. This is the author version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Transactions on Modeling and Computer Simulation,Vol.8 No.1 ; http://dx.doi.org/10.1145/272991.273007

[ISSN] 1049-3301

[DOI] 10.1145/272991.273007

[NCID] AA10779230

[DOI] http://dx.doi.org/10.1145/272991.273007 isVersionOf