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

Ali Assi | Zendy; P. W. C. Prasad | Zendy; Bruce Mills | Zendy; Amr Elchouemi | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Ali Assi,

P. W. C. Prasad,

Bruce Mills,

Amr Elchouemi

Publication year - 2006

Publication title -

journal of computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.161

H-Index - 28

eISSN - 1552-6607

pISSN - 1549-3636

DOI - 10.3844/jcssp.2006.236.244

Subject(s) - computer science , binary decision diagram , representation (politics) , binary number , path (computing) , theoretical computer science , influence diagram , algorithm , artificial intelligence , decision tree , mathematics , arithmetic , programming language , politics , political science , law

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research