Journal of Computer Science

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

A. Assi, P. W.C. Prasad, B. Mills and A. Elchouemi

DOI : 10.3844/jcssp.2006.236.244

Journal of Computer Science

Volume 2, Issue 3

Pages 236-244

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.

Copyright

© 2006 A. Assi, P. W.C. Prasad, B. Mills and A. Elchouemi. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.