![](https://csdnimg.cn/release/download_crawler_static/1960775/bg6.jpg)
local rules has been one of the driving forces. To present an overview of the methodologies developed by
researchers, we broadly divide CA into two categories: additive/linear CA - that is, CA following the
constraints of xor/xnor logic for its next state function; and non-linear CA - CA which do not possess
such constraints.
A. Linear/Additive CA
Analysis of linear/additive CA is amenable to algebraic methods. Since the next state function applied
at each cell follows the operations of a Galois field, the properties of the field can be applied to characterize
its state transition behavior. Consequently, the linear/additive CA are also termed as GF(q) CA where
q is a prime number. The GF(2) CA - the most popular variant of GF(q) CA [71], [72] has attracted
considerable attention in recent years since it can be applied in the field of V LSI design and test. There
have been several attempts to characterize GF(q) CA through a suitable algebraic tool. It has been
characterized using dipolynomials [123], [140]; but hybrid CA cannot be represented by dipolynomials.
CA state transition behavior has also been represented on arbitrary graphs and its behavior has been
studied based on graph-theoretic properties [237] . There are some abstract realizations of linear CA in
which the cell space is termed as an Abelian group and the state space is represented by a commutative
ring [10]. However, after this initial phase, characterization of GF(q) CA by a characteristic matrix
became a de facto standard [68], [72].
The matrix algebraic tool employing minimal and characteristic polynomials of the characteristic matrix
showed various interesting features of CA behavior. The first important finding is the categorization of
additive CA into group and non-group CA. In a group CA each of the states has a single predecessor
which is not true for non-group CA. However, it is found that the non-group CA show uniform behavior
in which trees rooted at any cycle state are isomorphic [140]. A detailed review regarding analysis of
group and non-group CA follows.
Group CA : The most effective application of null boundary group CA has been proposed in the field
of pseudo-random pattern generation. Serra et al. [217] showed that maximum length CA - group CA
with all non-zero states lying in a single cycle - produces high quality pseudo-random patterns. It has
been established that the maximum length cycle can be produced only if the characteristic polynomial is
primitive as well as only if rule 90 and/or rule 150 is used to construct the CA [36] (rule 90 = xor(left
neighbor, right neighbor); rule 150 = xor(left neighbor, self, right neighbor)). A maximum length CA
cannot be generated by periodic boundary CA since its characteristic polynomial can be factorized [20]; a
formal proof of this was provided by Nandi [165]. The next important theoretical hurdle was the synthesis
of a CA with rule 90/150 from a given irreducible/primitive polynomial. Serra et al. used a version of
6