Using Essential Signature Set in Logic Minimization

A new algorithm for exact two-level logic optimization is presented．It differs from the classical approach of generating the set of all prime implicants of function and then deriving a covering problem，we derive the covering problem directly，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 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，then generate only those primes involved in at least one minimal cover．The method is effective，solutions for 10 of 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．