BDD Path Length Minimization Based on Initial Variable Ordering | Science Publications

Journal of Computer Science

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

关键词: Binary decision diagram;    boolean function;    average path length;    longest path length;   

DOI  :  10.3844/jcssp.2005.521.529

学科分类：计算机科学（综合）

来源: Science Publications

【 摘 要 】

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.

【 授权许可】

Unknown