Synthesis of Minimal Threshold Logic Networks

Abstract

An algorithm is developed for synthesizing networks which realize Boolean switching functions through the use of a minimum number of threshold logic elements. A switching function is represented by a matrix and the algorithm is based on the principle that the removal of the positive linear dependences from the rows of this matrix results in a linearly separable function. The positive linear dependences are removed by adding columns to the matrix, each column representing the output of a threshold logic element in the network. The added columns in effect transform a nonseparable function into a sparable function a higher dimensional space. The algorithm is illustrated with examples of the synthesis of both single and multiple output networks. The technique is not restricted to completely specified functions.