Efficient Realization of Boolean Functions by Pruning NAND(NOR) Trees

摘要

A combinatorial tree structure composed entirely of NAND(NOR) blocks is pruned in a non-exhaustive fashion to yield minimal or near-minimal networks. It is assumed that complemented variables are not available and that there are no fan-in or fan-out limitations. The cost of a network is taken as being primarily determined by the number of logic blocks with the number of inputs and logic levels as secondary factors. The pruning algorithm lends itself to both hand methods and machine computation, although the synthesis procedure has not been programmed. Of the 68 nondegenerate functional equivalence classes of 3 variables, the minimum number of blocks results in 63 cases; only one more block in excess of the minimum is required in each of the other 5 cases. (Author)