Minimum average path length in BDDs based on static variable ordering

A large variety of problems in digital system design, combinational optimization and verification can be formulated in terms of operations on Boolean functions. Minimizing the average path length (APL) in binary decision diagrams (BDDs) can reduce the evaluation time of Boolean functions represented by these BDDs. This paper presents a novel method to generate a BDD with better APL, which reduces the evaluation time, based on a good static variable ordering. The method analyses the importance of the given variable order based on the complexity of the sub functions derived from variable substitutions. The variable that produces the minimum cumulative complexity for the sub-functions is given priority over other variables. Experimental results using benchmark circuits show that the proposed method is an encouraging approach towards minimizing the evaluation time of Boolean functions