Efficient implementation of neighborhood logic for cellular automata via the Cellular Neural Network Universal Machine

The main difficulty in implementing cellular automata on the Cellular Neural Network Universal Machine (CNNUM) is the need to perform arbitrary logic functions of the input neighborhood. Since the architecture computes weighted sums of this neighborhood, by using a "B-template," it is limited to threshold logic, i.e., a logical operation to be computed by a single transient must be in the class of linearly separable Boolean functions. It was shown previously how a general logic function can be implemented on the CNNUM by cascading component functions from this class-namely by the direct implementation of the minterm or maxterm formulation of the desired function. However, for functions of a 3/spl times/3 input neighborhood this method may require up to 256 stages. We propose a more efficient method for implementing general logic functions on the CNNUM and other hardwares capable of performing a threshold logic function of an input neighborhood. The class of considered component functions is a superset of the minterms and maxterms but, for purposes of searchability, ease of implementation, and robustness, a subset of the general linearly separable Boolean functions. We have formulated an algorithm that will find a sequence of weight-restricted threshold logic functions (B-templates with weights from {-1, 0, +1} and a bias) that, when cascaded together using two-input logical operations, will result in the desired Boolean function. Two examples are given to exhibit the algorithm.