BDD Package Based on Boolean NOR Operation

Binary Decision Diagrams (BDDs) are useful data structures for symbolic Boolean manipulations. BDDs are used in many tasks in VLSI/CAD, such as equivalence checking, property checking, logic synthesis, and false paths. In this paper we describe a new approach for the realization of a BDD package. To perform manipulations of Boolean functions, the proposed approach does not depend on the recursive synthesis operation of the IF-Then-Else (ITE). Instead of using the ITE operation, the basic synthesis algorithm is done using Boolean NOR operation.

Authors:

• M. Raseen
• A.Assi
• P.W. C. Prasad
• A. Harb

Keywords:

• Binary Decision Diagram (BDD)
• ITE Operation
• Boolean Function
• NOR operation.

References:

[1] R. E. Bryant, "On the complexity of VLSI
implementations and graph representations of Boolean
functions with application to integer multiplication,"
IEEE Trans. Computers, Vol. 40, pp. 203¶ÇÇÉ213, 1991
.[2] R. E. Bryant, "Graph¶ÇÇÉBased Algorithm for Boolean
Function Manipulation," IEEE Trans. Computers, Vol.
35, pp. 677-691, 1986.
[3] H. Andreas, R. Drechsler and B. Becker, "MORE: An
Alternative Implementation of BDD-Packages by Multi-
Operand Synthesis," IEEE European Design Automation
Conference, pp. 164-169, 1996.
[4] A. Gupta and P. Ashar, "Integrating a Boolean
satisfability checker and BDDs for combinational
equivalence checking," Proc. of the International
Conference on VLSI Design, 1998.
[5] B. Bollig and I. Wegener, "Improving the Variable
Ordering of OBDDs is NP¶ÇÇÉComplete," IEEE Trans.
Computers, Vol. 45, pp. 993-1002, 1996.
[6] R. Drechsler and M. Thornton, "Fast and Efficient
Equivalence Checking based on NAND-BDDs,"
Proceedings of IFIP International Conference on Very
Large Scale Integration, pp. 401-405, 2001.
[7] J. Marques-Silva and T. Glass, "Combinational
Equivalence Checking Using Satisfability and Recursive
Learning," International Conference on Design,
Automation and Test in Europe, pp.145-164, 1999.
[8] A. Kuehlmann, M. Ganai and B. Paruthi, "Circuit-based
Boolean Reasoning," International Design Automation
Conf., pp. 232-237, 2001.
[9] H. Hulgaard, P. Williams and H. Andersen, "Equivalence
checking of combinational circuits using Boolean
expression diagrams," IEEE Transaction on Computer
Aided Design, Vol. 18, 1999.
[10]R. Drechsler and B. Becker, "Binary Decision
Diagrams¶ÇÇÉTheory and Implementation," Kluwer
Academic Publishers, 1998.
[11] S. Christoph and R. Drechsler, "BDD minimization using
Symmetric," IEEE transaction on CAD of IC and
systems, Vol. 18, no. 2, pp. 81-100, 1999.
[12] S. B. Akers, "Binary Decision Diagram," IEEE Trans.
Computers, Vol. 27, pp. 509-516, 1978