Research Article Open Access

BDD Path Length Minimization Based on Initial Variable Ordering

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

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.

Journal of Computer Science
Volume 1 No. 4, 2005, 521-529

DOI: https://doi.org/10.3844/jcssp.2005.521.529

Submitted On: 25 May 2005 Published On: 31 December 2005

How to Cite: Prasad, P. W., Raseen, M., Assi, A. & Senanayake, S. M. (2005). BDD Path Length Minimization Based on Initial Variable Ordering. Journal of Computer Science, 1(4), 521-529. https://doi.org/10.3844/jcssp.2005.521.529

  • 2,369 Views
  • 2,258 Downloads
  • 4 Citations

Download

Keywords

  • Binary decision diagram
  • boolean function
  • average path length
  • longest path length