BDD-based two variable sharing extraction

It has been shown that Binary Decision Diagram (BDD) based logic synthesis enjoys faster runtime than the classic logic synthesis systems based on Sum of Product (SOP) form. However, its synthesis quality has not been on par with the classic method due to the lack of an effective sharing extraction strategy. In this paper, we present the first sharing extraction algorithm that directly exploits the structural properties of BDD. While our sharing extraction algorithm is limited to two-variable, disjunctive factors, and therefore may miss sharing opportunities, we show that it can be made exact, incremental and polynomial.