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

Volume

45

Issue

7

fYear

1996

fDate

7/1/1996 12:00:00 AM

Firstpage

782

Lastpage

792

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;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.508317

Filename

508317