  Cellular automata (CA) have been found as an attractive modeling tool for
various applications, such as, pattern recognition, image processing, data
compression, encryption, and specially for VLSI design & test. For such
applications, mostly a special class of CA, called as linear/additive CA, have
been utilized. Since linear/additive CA refer a limited number of candidate CA,
while searching for solution to a problem, the best result may not be expected.
The nonlinear CA can be a better alternative to linear/additive CA for
achieving desired solutions in different applications. However, the nonlinear
CA are yet to be characterized to fit the design for modeling an application.
This work targets characterization of the nonlinear CA to utilize the huge
search space of nonlinear CA while developing applications in VLSI domain. An
analytical framework is developed to explore the properties of CA rules. The
characterization is directed to deal with the reversibility, as the reversible
CA are primarily targeted for VLSI applications. The reported characterization
enables us to design two algorithms of linear time complexities -- one for
identification and nother for synthesis of nonlinear reversible CA. Finally,
the CA rules are classified into 6 classes for developing further efficient
synthesis algorithm.
