On variable ordering of binary decision diagrams for the application of multi-level logic synthesis

Abstract

We have developed multi-level logic minimization programs using Binary Decision Diagram (BDD). Here we present variable ordering methods of BDD. The variable ordering algorithm for two-level circuits is based on cover patterns and selects most binate variables first, and the one for multi-level circutis is based on depth first traverse of circuits. In both cases, the acquired variable orderings are optimized by exchanging a variable with its neighbor in the ordering.