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

Volume

1

Issue

4

fYear

1993

Firstpage

432

Lastpage

440

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;

fLanguage

English

Journal_Title

Very Large Scale Integration (VLSI) Systems, IEEE Transactions on

Publisher

ieee

ISSN

1063-8210

Type

jour

DOI

10.1109/92.250190

Filename

250190