Return to search

Characteristic polynomials of one-dimensional linear hybrid cellular automata

A one-dimensional linear hybrid cellular automaton (CA) is a specialised form of
linear finite state machine. These machines are of interest, both for their theoretical
properties and for their applications in VLSI built-in-self-test, random number
generation, cryptography, coding theory, and other areas. This work is a study of
the algebraic properties of the characteristic polynomials of CA, primarily for machines
defined over GF(2). Several problems, previously open, are solved: the efficient
synthesis of a CA from an irreducible polynomial, the existence and uniqueness of
CA for irreducible polynomials, the reducibility of the characteristic polynomial of a
cyclic-boundary CA, and the form of a similarity transform between CA and linear
feedback shift registers. A probabilistic algorithm for the synthesis of CA over finite
fields other than GF(2) is presented. Various other results concerning the characteristic
polynomial of CA are derived, and possible directions for future research are
discussed. / Graduate

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/9439
Date12 June 2018
CreatorsCattell, Kevin Michael
ContributorsMuzio, Jon C.
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
Formatapplication/pdf
RightsAvailable to the World Wide Web

Page generated in 0.002 seconds