Universal CNN cells

A cellular neural/nonlinear network (CNN) [Chua, 1998] is a biologically in spired system where computation emerges from a collection of simple nonline ar locally coupled cells. This paper reviews our recent research results be ginning from the standard uncoupled CNN cell which can realize only linearl y separable local Boolean functions, to a generalized universal CNN cell ca pable of realizing arbitrary Boolean functions. The key element in this evo lutionary process is the replacement of the linear discriminant (offset) fu nction w(sigma) = sigma in the "standard" CNN cell in [Chua, 1998] by a pie cewise-linear function defined in terms of only absolute value functions. A s in the case of the standard CNN cells, the excitation sigma evaluates the correlation between a given input vector u formed by the outputs of the ne ighboring cells, and a template vector b, which is interpreted in this pape r as an orientation vector. Using the theory of canonical piecewise-linear functions [Chua & Kang, 1977], the discriminant function w(sigma) = z + z(o )sigma - s Sigma(k=1)(m) (-1)(k)\sigma - z(k)\ is found to guarantee univer sality and its parameters can be easily determined. In this case, the numbe r of additional parameters and absolute value functions m is bounded by m < 2(n) - 1, where n is the number of all inputs (n = 9 for a 3 x 3 template) . An even more compact representation where m < n -1 is also presented whic h is based on a special form of a piecewise-linear function; namely, a mult i-nested discriminant: w(sigma) = s(z(m) + \z(m-1) + ...\z(1) + \z(0) + sig ma \\\) Using this formula, the "benchmark" Parity function with an arbitra ry number of inputs n is found to have an analytical solution with a comple xity of only m = O(log(2)(n)).