An Efficient Mathematical Estimation of the BDD's Complexity

A. Assi (Lebanon), M. Raseen, P.W.C. Prasad, and A. Harb (UAE)


Binary Decision Diagram (BDD), Reduced Ordered Binary Decision Diagram (ROBDD), Boolean Function, ROBDD complexity


This paper describes a new mathematical model for the estimation of the complexity of Binary Decision Diagrams (BDDs) for any Boolean function and with different degrees of variables complexity. This model is also capable of predicting the number of product terms in the Boolean function that will correspond to the maximum complexity. This mathematical model works for any type of variable ordering method, which will enable the system performance to be analyzed without building the BDD. A great reduction in time complexity for VLSI and CAD designs can be achieved and the model can also offer very useful clues to tackle BDD optimization problems in the design of digital circuits.

Important Links:

Go Back