An Algorithm for NAND Decomposition Under Network Constraints
作者： E.S. Davidson
关键词:
摘要: A branch-and-bound algorithm is presented for the synthesis of multioutput, multilevel, cycle-free NAND networks to realize an arbitrary given set partially or completely specified combinational switching functions. In a programmed version algorithm, fan-in, fan-out, and level constraints may be specified. Cost as nonnegative integer linear combination gates gate inputs. Further cost criteria are compatible with algorithm. first solution constructed by sequence local decisions, backtracking executed find improved solutions prove optimality final solution.
sci-hub.se 参考文章(13)
Edward Steinberg Davidson, An algorithm for nand decomposition of combinational switching functions Coordinated Science Laboratory, University of Illinois at Urbana-Champaign. ,(1968)
R. W. House, T. Rado, Erratum: `` On a Computer Program for Obtaining Irreducible Representations for Two-Level Multiple Input-Output Logical Systems'' Journal of the ACM. ,vol. 10, pp. 256- ,(1963) , 10.1145/321150.321154
E.S. Davidson, G. Metze, Comments on "An Algorithm for Synthesis of Multiple-Output Combinational Logic" IEEE Transactions on Computers. ,vol. C-17, pp. 1091- 1092 ,(1968) , 10.1109/TC.1968.226866
P.R. Schneider, D.L. Dietmeyer, An Algorithm for Synthesis of Multiple-Output Combinational Logic IEEE Transactions on Computers. ,vol. C-17, pp. 117- 128 ,(1968) , 10.1109/TC.1968.227399
Eugene L. Lawler, An Approach to Multilevel Boolean Minimization Journal of the ACM. ,vol. 11, pp. 283- 295 ,(1964) , 10.1145/321229.321232
B. B. Gordon, R. W. House, A. P. Lechler, L. D. Nelson, T. Rado, Simplification of the Covering Problem for Multiple Output Logical Networks IEEE Transactions on Electronic Computers. ,vol. EC-15, pp. 891- 897 ,(1966) , 10.1109/PGEC.1966.264471
Richard M. Karp, Functional Decomposition and Switching Circuit Design Journal of The Society for Industrial and Applied Mathematics. ,vol. 11, pp. 291- 335 ,(1963) , 10.1137/0111022
Leo Hellerman, A Catalog of Three-Variable Or-Invert and And-Invert Logical Circuits IEEE Transactions on Electronic Computers. ,vol. 12, pp. 198- 223 ,(1963) , 10.1109/PGEC.1963.263531
R. M. Karp, F. E. McFarlin, J. P. Roth, J. R. Wilts, A computer program for the synthesis of combinational switching circuits foundations of computer science. pp. 182- 194 ,(1961) , 10.1109/FOCS.1961.1
James F. Gimpel, The Minimization of TANT Networks IEEE Transactions on Electronic Computers. ,vol. EC-16, pp. 18- 38 ,(1967) , 10.1109/PGEC.1967.264603