One- and two-dimensional maximum length cellular automaton sequences and their applications

Abstract

A cellular automaton (CA) is a discrete time dynamical system and consists of uniform array of memory called a cell. The states of cells in the array are updated according to a rule: the state of a cell at a given time depends only on its own state and the states of its nearby neighbors at the previous step. Since a CA has a simple, regular, modular, and cascadable structure, it is useful for hardware implementation for VLSI. Applications of CA``s in various fields have been proposed. In this dissertation, maximum length CA is considered as an alternative to linear feedback shift registers. In some applications, linear feedback shift registers of long period are required. Hence we are interested in finding configurations of maximum length CA sequences with large sizes of cells for possible applications. First, the maximum length linear binary CA sequence is considered. It is shown that all possible maximum length linear binary CA sequences can be constructed using linear simple CA``s and that the maximum length linear binary CA sequences are equivalent to the maximum length binary LFSR sequences. A procedure for finding the configurations of the maximum length linear simple CA is described. Configurations are found for cell length from 4 through 299 for immediate application using the procedure. Secondly, we consider two dimensional maximum length cellular automaton sequences, which is an extension of the one dimensional ones. The difference between the one and two dimensional CA sequences is the physical configuration of cells. We rearranged the two dimensional cells to one dimensional CA, and then the procedure of the one dimensional case is applied. Some configurations of the two dimensional maximum length CA are found. Lastly, we consider the two dimensional CA as a pseudorandom number generators. The two dimensional CA is similar to the generalized feedback shift registers. The $k$-distributivity of the two dimensional maximum length CA sequence is conside...