Title :
ESPRESSO-SIGNATURE: a new exact minimizer for logic functions
Author :
McGeer, Patrick C. ; Sanghavi, Jagesh V. ; Brayton, Robert K. ; Sangiovanni-Vicentelli, A.L.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA
Abstract :
An algorithm for exact two-level logic optimization that radically improves the Quine-McCluskey (QM) procedure is presented. The new algorithm derives the covering problem directly and implicitly without generating the set of all prime implicants. It then generates only those prime implicants involved in the covering problem. A set of primes is represented by the cube of their intersection. Therefore, the unique set of sets of primes that forms the covering problem can be implicitly represented by a set of cubes that forms a minimum canonical cover. The minimum canonical cover starting from any initial cover is obtained and then the covering problem is derived. The method is effective; it improves on the runtime and memory usage of ESPRESSO-EXACT by average factors of 1.78 and 1.19, respectively, on the 114 of 134 benchmark examples that could be completed by ESPRESSO-EXACT. Of the remaining 20 hard problems, 14 are solved exactly. For three of the remaining six, the covering problem is derived but it can not be solved exactly.<>
Keywords :
VLSI; integrated logic circuits; logic CAD; minimisation of switching nets; ESPRESSO-SIGNATURE; Quine-McCluskey procedure; benchmark examples; covering problem; exact minimizer; hard problems; logic functions; logic synthesis; memory usage; minimum canonical cover; prime implicants; runtime; two-level logic optimization; Circuits; Concrete; Logic functions; Minimization methods; Modems;
Journal_Title :
Very Large Scale Integration (VLSI) Systems, IEEE Transactions on
