支持大规模变量集的最小覆盖迭代搜索算法  

Iterative Search Algorithm of Minimum Coverage for Large Size Literal Set

作　　者：于磊[1] 叶静[1] 郭毅[1] 李清宝[1] 

机构地区：[1]信息工程大学信息工程学院,郑州450002

出　　处：《计算机辅助设计与图形学学报》2008年第6期737-741,共5页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家"八六三"高技术研究发展计划(2006AA01Z404)

摘　　要：两级逻辑综合中的多输出逻辑电路最小覆盖的求解是一个NP难解问题,在输出变量集合和质蕴含项集合规模较大的情况下,会出现空间需求过大、处理时间太长等问题,影响多输出最小覆盖求解的可行性.在精选法的基础上,提出一种多输出最小覆盖迭代求解算法.将一次性求解最小覆盖的模式转换为多次迭代逼近最优解的过程,使得在有限的时间和空间范围内获得尽可能优化的最小覆盖结果.同时,对影响算法复杂度的单输出到多输出函数的阵列合并、极值的选择这2个主要环节进行了改进,大幅度降低了多输出最小覆盖求解算法的时间和空间复杂度.There is a NP-hard problem that derive the minimum coverage of multi-output logic circuit in two-level logic synthesis. When the number of output variables and the prime implicants grow up, the excessively long processing time and large memory space requirement are the major problem, which affect the possibility of coping with the problem of coverage minimization. An iterative algorithm for coverage minimization is presented based on the extract algorithm, which changes the one-time computing process into iterative searching mode of the optimum result. In contrast to the classical approaches, the proposed method can handle complex problem in reasonable time while the result is near by the optimum. At the same time, two major phases were improved, array union from singleoutput to multi-output and the selection of external value, which mainly affect the algorithm complexity. Experimental results show that the new algorithm superior to the others especially for decreasing the time-space complexity.

关 键 词：逻辑综合 最小覆盖 阵列合并 极值 迭代算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]