An Algorithm for NAND Decomposition of Combinational Switching Systems

摘要

A branch-and-bound algorithm is presented for the synthesis of multi-output, multi-level, cycle-free NAND networks, to realize an arbitrary given set of partially or completely specified combinational switching functions. Minimum cost solutions are obtained under a specified cost function which may be any non-negative integer linear combination of the number of gate inputs and gates of a solution network. Other solutions, not necessarily of minimum cost, are produced by the algorithm during the search for a minimum cost solution. A wide variety of network constraints are compatible with the algorithm and can easily be introduced. The completeness, consistency, and finite convergence of the algorithm are proven. Several versions of the algorithm are implemented in computer programs. Strategies for the final version of the algorithm are selected both on the basis of experimental results with these implementations and on the basis of more theoretical justification. Finally, the effectiveness of the approach and its relative effectiveness with respect to other approaches are tested with a set of broadly varied synthesis problems. (Author)