AN ALGORITHM FOR NAND DECOMPOSITION OF COMBINATIONAL SWITCHING SYSTEMS,
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1968
- Accession Number
- AD0678558
Entities
People
- Edward S. Davidson
Organizations
- University of Illinois Urbana–Champaign