An Algorithm for NAND Decomposition Under Network Constraints
- 1 December 1969
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-18 (12), 1098-1109
- https://doi.org/10.1109/t-c.1969.222593
Abstract
A branch-and-bound algorithm is presented for the synthesis of multioutput, multilevel, cycle-free NAND networks to realize an arbitrary given set of partially or completely specified combinational switching functions. In a programmed version of the algorithm, fan-in, fan-out, and level constraints may be specified. Cost may be specified as a nonnegative integer linear combination of gates and gate inputs. Further constraints and cost criteria are compatible with the algorithm. A first solution is constructed by a sequence of local decisions, and backtracking is executed to find improved solutions and to prove the optimality of the final solution.Keywords
This publication has 12 references indexed in Scilit:
- Comments on "An Algorithm for Synthesis of Multiple-Output Combinational Logic"IEEE Transactions on Computers, 1968
- An Algorithm for Synthesis of Multiple-Output Combinational LogicIEEE Transactions on Computers, 1968
- The Minimization of TANT NetworksIEEE Transactions on Electronic Computers, 1967
- Simplification of the Covering Problem for Multiple Output Logical NetworksIEEE Transactions on Electronic Computers, 1966
- Backtrack ProgrammingJournal of the ACM, 1965
- An Approach to Multilevel Boolean MinimizationJournal of the ACM, 1964
- An Algorithm for the Traveling Salesman ProblemOperations Research, 1963
- Functional Decomposition and Switching Circuit DesignJournal of the Society for Industrial and Applied Mathematics, 1963
- A Catalog of Three-Variable Or-Invert and And-Invert Logical CircuitsIEEE Transactions on Electronic Computers, 1963
- A computer program for the synthesis of combinational switching circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1961