结合ATPG和SAT的无界模型检验前像计算方法

提出一种无界模型检验的前像计算方法,该方法有效地结合ATPG和SAT引擎,充分利用引擎各自的优点.SAT用来判断是否已经穷尽所有解;每次SAT枚举出一个前像解后,采用一个专门的ATPG过程减少状态变量上的赋值,从而减少前像解的总个数,加快后面的不动点迭代处理.最后通过在ISCAS89和ITC99电路上的实验证明了文中方法的有效性.

无界模型检验中融合电路信息的SAT算法研究

针对从电路转化而来的SAT问题,通用SAT求解器存在一个缺陷——电路互连信息的缺失,这是造成很多无关推导的根源.文中提出了一个统一的基于CNF数据结构的电路SAT无界模型检验框架.首先作者提出了定值子句的概念,利用这一概念可以在CNF结构中保存电路的互连信息,在搜索过程中更早地识别可满足解,减少不必要的搜索.其次,文中提出了在CNF结构上的状态变量赋值精简方法,摆脱了以往基于SAT的无界模型检验中这一步骤对门级电路结构的依赖.实验数据表明,利用文中方法进行前像计算能够取得明显的加速.同时,文章比较了两种搜索顺序在多时帧搜索中的效果.实验结果表明利用文中方法可以验证传统模型检验方法难以验证的复杂电路属性.