A New Exact Minimizer for Two-Level Logic Synthesis

摘要: We present a new algorithm for exact two-level logic optimization. It differs from the classical approach; rather than generating set of all prime implicants function, and then deriving covering problem, we derive problem directly implicitly, generate only those primes involved in problem. represent by cube their intersection. some properties sets which form this prove that forms an incompletely-specified function.F. is unique. Hence corresponding cubes minimum canonical cover F. give successive reduction finding any initial cover. Using cover, at least one minimal discuss two related heuristic minimization procedures; relaxed procedure, improved ESPRESSO-II procedure. experimental results minimizer. The method effective; solutions 10 20 hard examples ESPRESSO benchmark are derived proved minimum. In addition, 5 remaining derived, but remains to be solved exactly.