Journal of Computer Science

BDD Path Length Minimization Based on Initial Variable Ordering

P. W.C. Prasad, M. Raseen, A. Assi and S. M.N.A. Senanayake

DOI : 10.3844/jcssp.2005.521.529

Journal of Computer Science

Volume 1, Issue 4

Pages 521-529

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.

Copyright

© 2005 P. W.C. Prasad, M. Raseen, A. Assi and S. M.N.A. Senanayake. 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.