ESPRESSO-SIGNATURE: A New Exact Minimizer for Logic Functions

We present a new algorithm for exact two-level logic optimization which radically improves the Quine-McCluskey (QM) procedure. 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. We represent a set of primes by the cube of their intersection. Therefore, the unique set of sets of primes which forms the covering problem can be implicitly represented by a set of cubes which forms a minimum canonical cover. We obtain the minimum canonical cover starting from any initial cover and then derive the covering problem. 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, we solve 14 exactly. For 3 of the remaining 6 the covering problem is derived but it could not be solved exactly.