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
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/9439 |
| Date | 12 June 2018 |
| Creators | Cattell, Kevin Michael |
| Contributors | Muzio, Jon C. |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Format | application/pdf |
| Rights | Available to the World Wide Web |
Page generated in 0.0023 seconds