Minimization of Logic Functions using Essential Signature Sets

We present a new algorithm for exact two-level logic optimization. It differs from the classical approach; rather than generating the set of all prime implicants of a function, and then deriving a covering problem, we derive the covering problem directly and implicitly, and then generate only those primes involved in the covering problem. We represent a set of primes by the cube of their intersection. The set of sets of primes which forms the covering problem is unique. Hence the corresponding set of cubes forms a canonical cover. We give a successive reduction algorithm for finding the canonical cover from any initial cover, we then generate only those primes involved in at least one minimal cover. The method is effective; solutions for 10 of the 20 hard examples in the Espresso benchmark set are derived and proved minimum. For 5 of the remaining examples the canonical cover is derived, but the covering problem remains to be solved exactly. 1 Introduction The two level logic synthesi..