A new approach for minimization of binary decision diagrams

Shun Shii Lin*, Chun Jen Wei


研究成果: 雜誌貢獻期刊論文同行評審


This paper proposes a new approach that successfully finds the optimal variable orderings for almost all reduced ordered binary decision diagrams (BDDs) in the LGSynth91 benchmark circuits with up to 500 variables. All previously known approaches can solve only functions with less than 64 variables. The progress of the new approach is attributable to the concept of randomized algorithms, which significantly reduce the influence of the initial variable ordering on the minimization performance. Furthermore, the features of different BDD minimization algorithms can also be measured as a result. The results are gradually refined during the minimization progress, such that valid approximate results can be derived before a time-consuming process terminates. The performance of the proposed approach is illustrated through its application on LGSynth91 benchmark circuits. Experimental results demonstrate that the randomized algorithm is properly incorporated; thus the performance remains consistent for a large set of benchmark circuits. In addition to providing a feasible BDD minimization algorithm, this paper presents statistical results and analyses that could be helpful for related research.

頁(從 - 到)207-214
期刊Canadian Journal of Electrical and Computer Engineering
出版狀態已發佈 - 2005 9月

ASJC Scopus subject areas

  • 硬體和架構
  • 電氣與電子工程


深入研究「A new approach for minimization of binary decision diagrams」主題。共同形成了獨特的指紋。