An Exact Logic Minimizer Using Implicit Binary Decision Diagram Based Methods

G.M. Swamy

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

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

We present an exact method for minimizing logic functions using BDD's. In this method the function is mapped to an extended space which gives it special properties that can be exploited to compute the function Primes and Minterms. The next step consists of conceptually creating a covering table whose rows represent the minterms and whose columns represent the primes. We formulate conditions for row and column dominance and remove dominated rows and columns iteratively until no more reduction is possible. The final step consists of finding minimum column cover for the remaining cyclic core of the problem. All functions are implemented using implicit BDD operations.

BibTeX citation:

@techreport{Swamy:M93/94,
    Author = {Swamy, G.M.},
    Title = {An Exact Logic Minimizer Using Implicit Binary Decision Diagram Based Methods},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2479.html},
    Number = {UCB/ERL M93/94},
    Abstract = {We present an exact method for minimizing logic functions using BDD's.  In this method the function is mapped to an extended space which gives it special properties that can be exploited to compute the function Primes and Minterms.  The next step consists of conceptually creating a covering table whose rows represent the minterms and whose columns represent the primes.  We formulate conditions for row and column dominance and remove dominated rows and columns iteratively until no more reduction is possible.  The final step consists of finding minimum column cover for the remaining cyclic core of the problem.  All functions are implemented using implicit BDD operations.}
}

EndNote citation:

%0 Report
%A Swamy, G.M.
%T An Exact Logic Minimizer Using Implicit Binary Decision Diagram Based Methods
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/ERL M93/94
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1993/2479.html
%F Swamy:M93/94