caa a22 4500 47709709X CHVBK 20180405111530.0 cr unu---uuuuu 170330e19960501xx s 000 0 eng 10.1007/BF01182592 doi (NATIONALLICENCE)springer-10.1007/BF01182592 Using ordered binary decision diagrams to factorize multi-level logic [Elektronische Daten] [Pei-Yung Hsiao, Ruey-Tzer Liaw, Jeong-Yuan Su] A novel approach that employs ordered binary decision diagrams (OBDDs) is contributed to factorize multi-level logic functions by requiring as few literals as possible. A logic function with PLA format is represented as an OBDD form first. A heuristic decision method of variable ordering, called theorder lookahead method, is derived for the construction of OBDDs. This method is based on the constant cofactor and the number of erasable logic terms for each input variable. The total execution time of the OBDD construction by the above ordering decisions is very fast for some MCNC benchmarks. With the above OBDDs, we introduce a simple yet effective graph manipulation, calledEXT, to obtain a minimal number of literals in the Boolean function. This greedyEXT algorithm consists mainly of two phases. The first phase, calledgraph analysis, identifies the similarities between nodes on the same level in the OBDD. The second phase, calledtree analysis, utilizes the above features to extract the common parts of the nodes. TheEXT procedure runs from the bottom level up to the top level of the OBDD. The computational complexity depends on the number of nodes in the OBDD. The results of simulations show thatEXT has a very fast CPU execution time and a competitive literal ratio with other methods for some MCNC benchmarks.EXT will produce the smallest literal number, especially for structured or symmetric circuits. Birkhäuser Boston, 1996 Hsiao Pei-Yung Department of Computer and Information Science, National Chiao Tung University, 1001 Ta Hsueh Road, Hsinchu, Taiwan 300, Republic of China aut Liaw Ruey-Tzer Department of Computer and Information Science, National Chiao Tung University, 1001 Ta Hsueh Road, Hsinchu, Taiwan 300, Republic of China aut Su Jeong-Yuan Department of Computer and Information Science, National Chiao Tung University, 1001 Ta Hsueh Road, Hsinchu, Taiwan 300, Republic of China aut Circuits, Systems and Signal Processing Birkhäuser-Verlag 15/3(1996-05-01), 361-376 0278-081X 15:3<361 1996 15 34 https://doi.org/10.1007/BF01182592 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01182592 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hsiao Pei-Yung Department of Computer and Information Science, National Chiao Tung University, 1001 Ta Hsueh Road, Hsinchu, Taiwan 300, Republic of China aut NATIONALLICENCE 700 1- Liaw Ruey-Tzer Department of Computer and Information Science, National Chiao Tung University, 1001 Ta Hsueh Road, Hsinchu, Taiwan 300, Republic of China aut NATIONALLICENCE 700 1- Su Jeong-Yuan Department of Computer and Information Science, National Chiao Tung University, 1001 Ta Hsueh Road, Hsinchu, Taiwan 300, Republic of China aut NATIONALLICENCE 773 0- Circuits, Systems and Signal Processing Birkhäuser-Verlag 15/3(1996-05-01), 361-376 0278-081X 15:3<361 1996 15 34 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer