Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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
1993

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},
    URL = {http://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1993/2479.html
%F Swamy:M93/94