home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / arch / 11702 < prev    next >
Encoding:
Internet Message Format  |  1992-12-16  |  1.8 KB
  1. Path: sparky!uunet!spool.mu.edu!yale.edu!qt.cs.utexas.edu!cs.utexas.edu!sun-barr!news2me.EBay.Sun.COM!exodus.Eng.Sun.COM!sun!amdcad!weitek!weaver
  2. From: weaver@jetsun.weitek.COM (Michael Gordon Weaver)
  3. Newsgroups: comp.arch
  4. Subject: Re: Logic Minimization Algorithms
  5. Message-ID: <1992Dec16.175805.5015@jetsun.weitek.COM>
  6. Date: 16 Dec 92 17:58:05 GMT
  7. References: <1992Dec15.024904.22554@amd.com>
  8. Organization: WEITEK Corporation, Sunnyvale CA
  9. Lines: 31
  10.  
  11. In article <1992Dec15.024904.22554@amd.com> roberts@angelo.amd.com (Dave Roberts) writes:
  12. >
  13. >I couldn't think of a more appropriate news group to post this in, so
  14. >here goze:
  15. >
  16. >What sort of algorithms are typically used to minimize logic equations
  17. >specified in high level hardware description languages (PAL software,
  18. >Verilog, etc.)?
  19. >
  20. >I've read and understand Quine-McClusky, and doodled around with
  21. >implementing my own versions.  It seems to work well except for the
  22. >final step: choosing a set of prime implicants from the set that you
  23. >just produced (by reductions of the form x * y + x * ~y = x, for those
  24. >of you who don't remember.  Prime implicants are those product terms
  25. >that can't be reduced any further by the application of the above
  26. >identity).
  27. >
  28. Quine-McClusky is not used in CAD because you cannot handle logic
  29. equations of the size that people want to do. Current methods 
  30. are called algebraic, implying that the equations are never
  31. fully expanded. 
  32.  
  33. Automatic translation from logic equations to gates has become popular
  34. in the last few year and you will find a number of papers on the
  35. subject in conference proceedings. Try Design Automation Conference
  36. (DAC) proceedings, or International Conference on Computer Aided
  37. Design (ICCAD) proceedings. Keywords to look for are Logic Synthesis,
  38. Logic Minimization.
  39.  
  40.  
  41. Michael Weaver.
  42.