Implementation of arbitrary Boolean functions on a CNN Universal Machine

The demand for implementing arbitrary N-variable logic functions on percept ron-like structures arises quite often in practice. It is well known, that only the linearly separable class of Boolean functions can be implemented i n a single step on these structures. This class however, constitutes only a small (and with the increasing N exponentially decreasing) part of all log ic functions. All Boolean functions can be trivially decomposed into at mos t 2(N-1) sub-functions by implementing the minterm or maxterm formulation o f the function. This approach, however, becomes rather impractical with the increasing number of variables. In this paper an algorithm is proposed for decomposing arbitrary, linearly non-separable Boolean functions into a ser ies of separable functions, which can be then efficiently implemented as a program for the CNN Universal Machine(1-3) assuming the simplest and most r obust hardware architecture. The decomposition is achieved by finding the c losest linearly separable compact functions. Robustness issues of the imple mentation are also addressed. (C) 1998 John Wiley & Sons, Ltd.