Thumbnail
Access Restriction
Open

Author Mcgeer, Patrick ♦ Sanghavi, Jagesh ♦ Brayton, Robert ♦ Vincentelli, Alberto Sangiovanni
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Covering Problem ♦ Logic Function ♦ Canonical Cover ♦ Essential Signature Set ♦ Initial Cover ♦ Level Logic Synthesi ♦ Prime Implicants ♦ Hard Example ♦ Corresponding Set ♦ New Algorithm ♦ Espresso Benchmark Set ♦ Exact Two-level Logic Optimization ♦ Minimal Cover ♦ Successive Reduction Algorithm ♦ Cube Form ♦ Classical Approach
Abstract 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...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study