用关键特征集对逻辑进行优化

Using Essential Signature Set in Logic Minimization

提出了一个两级逻辑优化的新算法 .与通过函数质蕴涵集求解覆盖的传统算法不同 ,文中将求解逻辑函数的质蕴涵项与推导覆盖问题相结合 ,直接得出覆盖问题的解 .算法的主要问题可以简化为 :对于立方描述的单元 ,求解最小覆盖 .在这个过程中又提出了一种改进的覆盖吸收算法 :基于关键特征集合的选拔吸收算法 .此算法不用求所有的立方 ,通过标准的测试例子与原来的 Espresso算法作比较 ,对于大电路 ,在计算时间上 。

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.