Heuristic Minimization of BDDs, Using Don't Cares

T.R. Shiple, R. Hojati, Alberto L. Sangiovanni-Vincentelli and Robert K. Brayton

EECS Department
University of California, Berkeley
Technical Report No. UCB/ERL M93/58
July 1993

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/ERL-93-58.pdf

We present heuristic algorithms for finding a minimum BDD size cover of an incompletely specified function, assuming the variable ordering is fixed. In some algorithms based on BDDs, incompletely specified functions arise for which any cover of the function will suffice. Choosing a cover which has a small BDD representation may yield significant performance gains. We present a systematic study of this problem, establishing a unified framework for heuristic algorithms,, proving optimality in some cases, and presenting experimental results.

BibTeX citation:

@techreport{Shiple:M93/58,
    Author = {Shiple, T.R. and Hojati, R. and Sangiovanni-Vincentelli, Alberto L. and Brayton, Robert K.},
    Title = {Heuristic Minimization of BDDs, Using Don't Cares},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Jul},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2404.html},
    Number = {UCB/ERL M93/58},
    Abstract = {We present heuristic algorithms for finding a minimum BDD size cover of an incompletely specified function, assuming the variable ordering is fixed.  In some algorithms based on BDDs, incompletely specified functions arise for which any cover of the function will suffice.  Choosing a cover which has a small BDD representation may yield significant performance gains.  We present a systematic study of this problem, establishing a unified framework for heuristic algorithms,, proving optimality in some cases, and presenting experimental results.}
}

EndNote citation:

%0 Report
%A Shiple, T.R.
%A Hojati, R.
%A Sangiovanni-Vincentelli, Alberto L.
%A Brayton, Robert K.
%T Heuristic Minimization of BDDs, Using Don't Cares
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/ERL M93/58
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2404.html
%F Shiple:M93/58