A new approach for minimization of binary decision diagrams

Shun-Shii Lin, Chun Jen Wei

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Pages (from-to)207-214
Number of pages8
JournalCanadian Journal of Electrical and Computer Engineering
Volume30
Issue number4
DOIs
Publication statusPublished - 2005 Sep 1

Keywords

  • BDD
  • Exact algorithm
  • Minimization
  • Randomized algorithm
  • Sifting
  • Variable ordering

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A new approach for minimization of binary decision diagrams'. Together they form a unique fingerprint.

  • Cite this