home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / arch / 11676 < prev    next >
Encoding:
Text File  |  1992-12-15  |  2.4 KB  |  78 lines
  1. Newsgroups: comp.arch
  2. Path: sparky!uunet!stanford.edu!nntp.Stanford.EDU!rgupta
  3. From: rgupta@leland.Stanford.EDU (Rajesh Gupta)
  4. Subject: Re: Logic Minimization Algorithms
  5. Message-ID: <1992Dec15.225625.23933@leland.Stanford.EDU>
  6. Sender: rgupta@momus.Stanford.EDU (Rajesh Gupta)
  7. Organization: CIs, Stanford University, CA 94305, USA
  8. References: <1992Dec15.024904.22554@amd.com>
  9. Distribution: world 
  10. Date: Tue, 15 Dec 92 22:56:25 GMT
  11. Lines: 65
  12.  
  13. In article <1992Dec15.024904.22554@amd.com> roberts@angelo.amd.com (Dave Roberts) writes:
  14. >
  15. > 
  16. > I couldn't think of a more appropriate news group to post this in, so
  17. > here goze:
  18. > 
  19.     comp.lsi.cad would be a more appropriate newsgroup.
  20.  
  21. > What sort of algorithms are typically used to minimize logic equations
  22. > specified in high level hardware description languages (PAL software,
  23. > Verilog, etc.)?
  24. > 
  25. > I've read and understand Quine-McClusky, and doodled around with
  26. > implementing my own versions.  It seems to work well except for the
  27. > final step: choosing a set of prime implicants from the set that you
  28. > just produced (by reductions of the form x * y + x * ~y = x, for those
  29. > of you who don't remember.  Prime implicants are those product terms
  30. > that can't be reduced any further by the application of the above
  31. > identity).
  32. > 
  33. ...
  34. > 
  35. > So I guess my question is, how are these problems overcome?  Do people
  36. > use other algorithms than Quine-McClusky instead that don't suffer
  37. > these problems?  If so, what are they?
  38. > 
  39. > Does someone have references of articles that describe this stuff?
  40. > Articles themselves?
  41. > 
  42.  
  43.  
  44. QM uses enumeration to achieve optimum. A number of heuristics
  45. achieve near optimal solutions using algebraic methods. Most common
  46. being the espresso-style heuristics which attempts to utilize implicit 
  47. don't-cares (either by tautology-checking or by using approximate
  48. don't-care sets) to perform logic minimization. 
  49.  
  50. Two-level logic synthesis is a fairly well-developed field. You may 
  51. want to check out the following monograph 
  52.  
  53. Brayton, Sangiovanni et al
  54.     "Logic Minimization Algorithms for VLSI", Kluwer Academic, 1984 (I think)
  55.  
  56.  
  57. or there is a tutorial paper in IEEE Proceedings Feb 1990.
  58.  
  59.  
  60. > What about publicly available source code that implements the various
  61. > algorithms?
  62.  
  63. Espresso and its cousins are publicly available. (Espresso: UCB, 
  64. Bold: Colorado, Boulder).
  65.  
  66. > 
  67. > Thanks for any help people can give to satisfy my curiousity.
  68. > 
  69. > Dave Roberts
  70.  
  71.  
  72.  
  73. Rajesh Gupta
  74.  
  75. 725-3647 CIS 18                    rgupta@momus.stanford.edu
  76.  
  77.  
  78.