This paper describes a novel logic decomposition theory and a practical logic synthesis system, BDS. It is based on a new binary decision diagrams (BDD) decomposition technique which supports all types of decomposition structures, including AND, OR, XOR, and complex MUX, both algebraic and Boolean. As a result, the method is very efficient in synthesizing both AND/OR and XOR-intensive functions. It also has a capability to handle very large circuits, as it employs the BDD decomposition in the partitioned Boolean network environment. The experimental results show that BDD-based logic decomposition is a promising alternative to the existing logic optimization approaches. In particular, it offers a superior runtime advantage over traditional logic synthesis systems.

This paper describes a new BDD-based logic optimization system, BDS. It is based on a recently developed theory for BDD-based logic decomposition, which supports both algebraic and Boolean factorization. New techniques, which are crucial to the manipulation of BDDs in a partitioned Boolean network environment, are described in detail. The experimental results show that BDS has a capability to handle very large circuits. It offers a superior runtime advantage over SIS, with comparable results in terms of circuit area and often improved delay.

Summary form only given. High noise immunity and level-restoring capabilities of static CMOS gates, combined with small area and low power of PTL cells, make a mixed CMOS/PTL design style an ideal alternative to the all-CMOS technology. However, the synthesis of mixed CMOS/PTL circuits imposes a great challenge to the existing synthesis methodology. Neither traditional techniques based on algebraic factorization nor methods based on direct BDD mapping are applicable to this new circuit style. We have recently proposed a new BDD-based logic optimization method for static CMOS. It is based on iterative BDD decomposition using various dominators which correspond to decomposable BDD structures leading to AND, OR, XOR and MUX decompositions. Synthesis results show that the method is very efficient for both AND/OR- and XOR-intensive functions. Since PTL structures can be easily identified on a BDD, our method can be readily extended to perform logic decomposition leading to mixed CMOS/PTL logic implementation. In contrast to other PTL synthesis techniques, based on direct BDD mapping, our method is not limited to decomposition onto PLTs only; its logic decomposition and optimization is driven by the capabilities of both the static CMOS and PTL logic. Our BDD decomposition method can also account for various parameters associated with circuit performance, thus avoiding drawbacks of direct BDD mapping-based synthesis, such as large fanouts and long transistor chains.

A unified logic optimization method efficient at handling both AND/OR-intensive and XOR-intensive functions is proposed. The method is based on iterative BDD decomposition using various dominators. Detail analysis of decomposable BDD structures leading to AND/OR, XOR and MUX decompositions are presented. Experiment shows that our synthesis results for AND/OR-intensive functions are comparable to those of SIS, and results for XOR-intensive functions are comparable to those of techniques targetting specifically XOR decomposition.