Title :
Analysis of one-dimensional linear hybrid cellular automata over GF(q)
Author :
Cattell, Kevin ; Muzio, Jon C.
Author_Institution :
Dept. of Comput. Sci., Victoria Univ., BC, Canada
fDate :
7/1/1996 12:00:00 AM
Abstract :
The paper studies theoretical aspects of one dimensional linear hybrid cellular automata over a finite (Galois) field. General results concerning the characteristic polynomials of such automata are presented. A probabilistic synthesis algorithm for determining such a linear hybrid cellular automaton with a specific characteristic polynomial is given, along with empirical results and a theoretical analysis. Cyclic boundary cellular automata are defined and related to the more common null boundary cellular automate. An explicit similarity transform between a cellular automaton and its corresponding linear feedback shift register is derived
Keywords :
Galois fields; cellular automata; polynomials; characteristic polynomial; characteristic polynomials; common null boundary cellular automata; cyclic boundary cellular automata; finite Galois field; linear feedback shift register; one dimensional linear hybrid cellular automata; probabilistic synthesis algorithm; theoretical analysis; theoretical aspects; Algorithm design and analysis; Automata; Circuits; Cryptography; Galois fields; Linear algebra; Linear feedback shift registers; Pattern analysis; Polynomials; Test pattern generators;
Journal_Title :
Computers, IEEE Transactions on