BDD Path Length Minimization Based on Initial Variable Ordering

Abstract

A large variety of problems in digital system design, combinational optimization and verification can be formulated in terms of operations performed on Boolean functions. The time complexity of Binary Decision Diagram (BDD) representing a Boolean function is directly related to the path length of that BDD. In this paper we present a method to generate a BDD with minimum path length. The Average Path Length (APL) and Longest Path Length (LPL) of the BDD are evaluated and discussed. The proposed method analyses the essentiality of a given variable order based on the complexity of sub functions derived from variable substitution. The variable that produces minimal cumulative complexity for the sub-functions is given priority over other variables. The experimental results and comparisons using benchmark circuits show that the proposed method is an encouraging approach towards minimizing the evaluation time of Boolean functions, consequently minimizing the time complexity of BDDs.