🚀 go-pugleaf

In article <1992Dec15.024904.22554@amd.com> roberts@angelo.amd.com (Dave Roberts) writes:
>
> 
> I couldn't think of a more appropriate news group to post this in, so
> here goze:
> 
	comp.lsi.cad would be a more appropriate newsgroup.

> What sort of algorithms are typically used to minimize logic equations
> specified in high level hardware description languages (PAL software,
> Verilog, etc.)?
> 
> I've read and understand Quine-McClusky, and doodled around with
> implementing my own versions.  It seems to work well except for the
> final step: choosing a set of prime implicants from the set that you
> just produced (by reductions of the form x * y + x * ~y = x, for those
> of you who don't remember.  Prime implicants are those product terms
> that can't be reduced any further by the application of the above
> identity).
> 
...
> 
> So I guess my question is, how are these problems overcome?  Do people
> use other algorithms than Quine-McClusky instead that don't suffer
> these problems?  If so, what are they?
> 
> Does someone have references of articles that describe this stuff?
> Articles themselves?
> 


QM uses enumeration to achieve optimum. A number of heuristics
achieve near optimal solutions using algebraic methods. Most common
being the espresso-style heuristics which attempts to utilize implicit 
don't-cares (either by tautology-checking or by using approximate
don't-care sets) to perform logic minimization. 

Two-level logic synthesis is a fairly well-developed field. You may 
want to check out the following monograph 

Brayton, Sangiovanni et al
	"Logic Minimization Algorithms for VLSI", Kluwer Academic, 1984 (I think)


or there is a tutorial paper in IEEE Proceedings Feb 1990.


> What about publicly available source code that implements the various
> algorithms?

Espresso and its cousins are publicly available. (Espresso: UCB, 
Bold: Colorado, Boulder).

> 
> Thanks for any help people can give to satisfy my curiousity.
> 
> Dave Roberts



Rajesh Gupta

725-3647 CIS 18					rgupta@momus.stanford.edu