Using ordered binary decision diagrams to factorize multi-level logic

Abstract

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 the order 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, called EXT, to obtain a minimal number of literals in the Boolean function. This greedy EXT algorithm consists mainly of two phases. The first phase, called graph analysis,, identifies the similarities between nodes on the same level in the OBDD. The second phase, called tree analysis, utilizes the above features to extract the common parts of the nodes. The EXT 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 that EXT 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.