2-by-n hybrid cellular automata with regular configuration: theory and application

Author

Cattell, Kevin ; Zhang, Shujian ; Serra, Micaela ; Muzio, Jon C.

Author_Institution

Hewlett-Packard, Rohnert Park, CA, USA

Volume

48

Issue

3

fYear

1999

fDate

3/1/1999 12:00:00 AM

Firstpage

285

Lastpage

295

Abstract

This paper introduces a new class of two-dimensional linear cellular automata and derives a number of their properties. A recursive relation is proved which enables the characteristic polynomial to be efficiently calculated, and minimal cost, maximal length generators of this type are listed for sizes up to 500. A theoretical analysis of the two vector transition properties of the cellular automata is given and it is shown that, for testing sequential faults over a set of standard benchmarks, the two-dimensional cellular automata perform, on average, better than one-dimensional linear hybrid cellular automata, and much better than linear finite shift registers

Keywords

cellular automata; finite state machines; 2-by-n hybrid cellular automata; characteristic polynomial; maximal length generators; recursive relation; regular configuration; standard benchmarks; vector transition properties; Automatic testing; Benchmark testing; Character generation; Costs; Performance analysis; Performance evaluation; Polynomials; Sequential analysis; Shift registers; Vectors;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.754995

Filename

754995