DocumentCode
1101519
Title
An Algorithm for NAND Decomposition Under Network Constraints
Author
Davidson, Edward S.
Author_Institution
IEEE
Issue
12
fYear
1969
Firstpage
1098
Lastpage
1109
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
Branch-and-bound algorithm, circuit constraints, combinational logic synthesis, decomposition, logic design automation, NAND synthesis.; Algorithm design and analysis; Costs; Design automation; Fabrication; Flip-flops; Integrated circuit synthesis; Large scale integration; Logic design; Logic functions; Network synthesis; Branch-and-bound algorithm, circuit constraints, combinational logic synthesis, decomposition, logic design automation, NAND synthesis.;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/T-C.1969.222593
Filename
1671186
Link To Document