Two Level Realization of Switching Functions with a Minimum Number of Threshold Gates

摘要

The paper deals with the synthesis of networks of threshold gate logic elements which realize non-linearly separable switching functions and which contain two levels of logic and a minimum number of logic elements. An algorithm is developed which can be used to obtain the desired network for a given switching function. The function may be incompletely specified. The algorithm is based on the realization procedures of Coates and Lewis. Necessary and sufficient conditions for removing an inconsistency are developed. A Boolean function technique for applying the removal rules to a set of inconsistencies is given. This technique consists of defining a Boolean function called a constraint function for each inconsistency that has been encountered. The product of constraint functions indicates the possibilities for defining gates to remove the inconsistencies. A zero product of constraint functions indicates that the set of inconsistencies cannot be removed with the number of gates being used. (Author)