Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 30308
BDD Package Based on Boolean NOR Operation

Authors: M. Raseen, A. Harb, P.W. C. Prasad, A.Assi


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.

Keywords: boolean function, Binary Decision Diagram (BDD), ITE Operation, NOR operation

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1551


[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