Variable ordering of binary decision diagrams for multi-level logic minimization

Binary Decision Diagram (BDD) is now widely used in CAD fields, especially in formal verification and logic synthesis. In this paper, variable ordering methods of BDD for the application of multi-level logic minimization are presented. The variable ordering algorithm for sum-of-products representation is based on cover patterns and selects most binary variables first, and the one for multi-level logic representation is based on depth first traversal of circuits. In both cases, the obtained variable orderings are optimized by exchanging a variable with its neighbor in the ordering. Experimental results show the effectiveness of our methods.