Implementation of arbitrary Boolean functions on a CNN Universal Machine

✍ Scribed by Nemes, L.; Chua, L. O.; Roska, T.

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 836 KB
• Volume: 26
• Category: Article
• ISSN: 0098-9886
• DOI: 10.1002/(sici)1097-007x(199811/12)26:6<593::aid-cta35>3.0.co;2-l

✦ Synopsis

The demand for implementing arbitrary N-variable logic functions on perceptron-like structures arises quite often in practice. It is well known, that only the linearly separable class of Boolean functions can be implemented in a single step on these structures. This class however, constitutes only a small (and with the increasing N exponentially decreasing) part of all logic functions. All Boolean functions can be trivially decomposed into at most 2,\ sub-functions by implementing the minterm or maxterm formulation of 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 series of separable functions, which can be then efficiently implemented as a program for the CNN Universal Machine\ assuming the simplest and most robust hardware architecture. The decomposition is achieved by finding the closest linearly separable compact functions. Robustness issues of the implementation are also addressed.