Authors : Mohamed Raseen and K. Thanushkodi
Abstract: For decades, the storage of Boolean functions using Binary Decision Diagrams (BDD) has been popular. Efficiency of representing a Boolean function by BDD depends upon the size of the BDD (Number of nodes). Evaluating time on Boolean function using BDD depends upon the path lengths of the BDD. The efficiency of manipulating Boolean function depends upon the BDD parameters such as Longest Path Length (LPL), Average Path Length (APL) and Shortest Path Length (SPL). Lesser the value of the parameters, lesser will be the computational time. This study describes a new mathematical model for the estimation of the complexity of Binary Decision Diagrams (BDDs) for simplified Boolean functions. This study provides a mathematical model for estimation of Number of Nodes, APL, LPL and SPL for a given set of values such as number of nodes/number of product terms. The mathematical model precisely matches the experimental values obtained from CUDD (Colorado university decision diagram package). This mathematical model works for any type of variable ordering method. The model enables the system to find the number of BDD nodes and path lengths (APL, LPL, SPL) without building the BDD. Hence, a great reduction in time complexity for VLSI and CAD designs can be achieved. It can also offer very useful clues to tackle BDD optimization problems in the design of digital circuits.
Mohamed Raseen and K. Thanushkodi , 2008. ROBDD�s Parameter Estimation for Simplified Boolean Functions. International Journal of Soft Computing, 3: 451-460.