Empirical Analysis and Mathematical Representation of the Path Length Complexity in Binary Decision Diagrams

Abstract

Information about the distribution of path-lengths in a Binary Decision Diagrams (BDDs) representing Boolean functions is useful in determining the speed of hardware and software implementations of the circuit represented by these Boolean functions. This study presents expressions produced from an empirical analysis of a representative collection of Boolean functions. The Average Path Length (APL) and the Shortest Path Length (SPL) have simple behavior as function of the number of variables and the number of terms used in the construction of the Sum of Products (SOPs) in Boolean expressions. We present a generic expression that is uniformly adaptable to each curve of path-length versus number of terms over all the empirical data. This expression makes it possible to estimate the performance characteristics of a circuit without building its BDD. This approach applies to any number of variables, number of terms, or variable ordering method.