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.

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.

This paper presents a method for the synthesis of a one-dimensional linear hybrid cellular automaton (CA) from a given irreducible polynomial. A detailed description of the algorithm is given, together with an outline of the theoretical background. It is shown that two CA exist for each irreducible polynomial, solving the previously open CA existence conjecture. An in-depth example of the synthesis is presented, along with timing benchmarks and an operation count. The algorithm solves the previously open problem of synthesizing CA for all practical applications.