串扰时延故障的SAT-ATPG算法研究

尚玉玲，钱 尚，刘 鹏

(桂林电子科技大学 电子工程与自动化学院, 广西 桂林 541004)

串扰时延故障的SAT-ATPG算法研究

尚玉玲，钱 尚，刘 鹏

(桂林电子科技大学 电子工程与自动化学院, 广西 桂林 541004)

随着芯片运行速度不断提高,对串扰时延的测试已成为一个迫切需要解决的问题；文中提出一种面向多条攻击线的受害线上最大串扰噪声的测试生成方法；此方法建立了串扰通路时延故障模型、分析了布尔可满足性问题、讨论了七值逻辑，研究了串扰时延故障测试转换为CNF的逻辑表达式，在非鲁棒测试条件下约简CNF范式，并提出了串扰时延故障的SAT-ATPG算法；最后通过实例分析，对本文算法进行验证；结果表明:该算法对串扰时延故障的测试矢量的生成是有效的。

串扰时延故障；布尔可满足性；时延测试

0 引言

随着电子信息技术不断发展，高速电路中信号频率的增加、边沿变陡、电路板的尺寸变小和布线密度的增大，这些因素使得在高速电路的设计中，信号完整性[1](Singnal Integrity，SI)问题越发突出。串扰引起的时延故障是信号完整性问题中一个突出问题，它是指相邻信号线同时发生跳变瞬间，攻击线对受害线所产生的传输时间的变化的故障类型。对串扰故障模型的研究方面，国内外研究者取得了一些成果，文献[2]用无耗传输线的串扰为对象，提出了最大攻击者模型，文献[3]提出多跳变故障模型，虽然使故障覆盖率增加，但是大大降低了测试的效率。文献[4]在最大攻击者模型的基础上，提出了最大信号完整性模型，它的优点是克服了最大攻击者模型的缺点，此外在串扰时延的测试方面，它也提出了串扰时延故障，最终得出串扰时延自动测试图形生成(Automatic Test Pattern Generation)算法。前人基于D算法、PODEM算法、FAN算法等进行了大量研究，但是这些传统的ATPG，很难求解串扰引起的瞬态故障并检测问题。本文主要针对串扰通路时延故障模型进行测试，以跳变通路时延故障模型为基础并引入串扰机制从而形成的一种串扰时延故障新模型，其特点是在跳变时延故障模型主体上引入串扰信号，将其转化成对应逻辑值从而对整个系统进行测试。近年来，随着布尔可满足性 (Boolean -Satisfiability)，SAT求解技术的发展及其广泛应用，基于SAT的ATPG技术已经成为一种新的故障测试矢量的生成方法，被应用于电路时延故障测试的自动测试生成中，如Chen[5]等人对电路的时延故障探究出了生成鲁棒测试集的具体方法，李玲[6]等人将增量式SAT技术应用到时延故障测试中。

1 布尔可满足性问题

布尔可满足性问题(SAT),它是第一个被证明的经典NP完全问题，有着非常重要的理论意义和应用意义。是用来判断以合取范式(Conjunctive Normal Form，简称CNF)形式给出的命题逻辑公式是否存在一个真值指派，使得该逻辑公式的逻辑值为真。在解决SAT问题的过程中采用DPLL(Davis-Putnam-Logemann-Loveland)算法[7]，基本DPLL算法采用深度优化策略去遍历所有的数，来找到一组赋值并使其满足这个问题的要求。当找到这组赋值的时候，搜索就会停止，或者遍历了所有的空间也没有找到满足条件的赋值，搜索也会停止。经典的DPLL算法来判断公式的布尔可满足性一般求解思路如下。

Input:输入一个待判定公式K；

Output：输出公式K的满足性判定。

Function DPLL-K

{ while(l

{

从公式K中选择子句M；若选不到，则跳出此循环；否则，利用子句M，化简公式K，得到新公式Kt；如果Kt为空，那么输出公式K就是满足条件的，停止； 否则，输出公式K是不满足的，停止；

}

}

2 基于SAT的串扰时延的ATPG测试方法

2.1 串扰通路时延故障模型

串扰通路时延故障模型是以跳变通路时延为基础，引入串扰形成的模型。在进行测试时候应该同时满足：1)与通路时延故障模型测试相比，它不仅需要在原始输入端加入一个跳变信号，而且在测试路径上每一个逻辑门的输入都需要一个跳变信号。2)每个门输入的跳变信号必须保持一致。在经过非门、与非门、或非门等逻辑门取反时，下个门跳变输入值也要取反。3)通路敏化：在测试通路上，要求旁路输入的第二个信号的输入值为非控制值，这样能够在非鲁棒测试条件下将每一个时延故障都能够通过测试路径传输到输出端，即检测出一个串扰通路时延故障。4)对于攻击线和受害线，将其转换成逻辑信号值，作为限定条件进行测试矢量的求解。5)采用单路径敏化测试方法，不能同时测试多条敏化路径。

2.2 多值逻辑

表1 七值逻辑表

2.3CNF范式表达

因为自动测试矢量的生成是一个NP完全问题，所以我们能用SAT矢量生成算法对此类问题求解。但是由于SAT算法是在CNF范式表达式的基础上进行求解的，因此我们需要将电路串扰时延故障测试转换为CNF的数学逻辑表达式形式。电路转换成SAT求解器能处理的CNF范式表达形式，可分为两步：

(1)用逻辑门的输入输出关系的功能函数，考虑信号的时序，进行该逻辑门特定逻辑的求解，计算出输入输出的逻辑表达式。

(2)根据蕴涵公式和等价公式计算逻辑表达式得出该门的合取范式，也就是CNF逻辑表达式。我们可以用一个二元组(ZS,ZV)来表示测试通路中门的输出，二元组(XS,XV)表示门的输入。从而按照蕴含关系和门的功能函数和，用逻辑门的输入来表示逻辑门的输出，最终转换成CNF表达式。例如与非门[9]有：

(ZS,ZV) =NAND[(XS,XV),(YS,YV)]⟹

(1)

2.4 非鲁棒性测试条件

在时延故障模型测试中,引入非鲁棒测试条件，设输入的测试矢量为，如果它能将单时延故障沿着测试路径即敏化通路传播到输出端,并且在规定的时间内检测到跳变信号，同时输出的结果由跳变信号所决定，那么我们就称这次非鲁棒测试是成功的。

同单通路敏化一样，非鲁棒性测试具有两个条件。

1)在输入端必须输入一个跳变信号，使其沿着测试路径传播。

2)在测试通路上,要求逻辑门的旁路输入的第二个向量设定为非控制值ncv,称之为通路敏化。在非鲁棒测试条件下，与门和与非门的第二个非控制量为1，或门、或非门第二个向量的非控制量为0，旁路输入表如表2所示。

表2 旁路输入表

其中:X1是终值为1的跳变，X0是终值为0的跳变。 根据旁路输入表以及激活通路上跳变引起时延故障条件，可以确定一些输入输出值，代入标准的CNF范式中，最终可得到CNF的最简形式。

2.5 测试生成算法

将抽象门的数字电路转化成CNF合取范式，并对故障模型进行建模以及转化,将ATPG问题转化成SAT问题,最后由SAT求解器进行求解。测试矢量生成主要包括4个步骤：

STEP1:提取电路信息建立有向循环图。

STEP2:分析每一个逻辑门，将对应的每个门电路按公式1转换成CNF范式表达式。

STEP3:在处理所有门的逻辑转换后，找出其中一条故障路径，指出攻击线和受害线，根据输入的跳变，将对应逻辑值代入到CNF公式中去；并根据非鲁棒测试的旁路敏化条件来敏化旁路输入，并加入串扰时延触发条件，同样转换到CNF范式中。

STEP4:将STEP3作为STEP2的约束条件进行CNF范式的最终化简，然后将最终范式作为串扰时延故障的最终数学描述，输入到SAT求解器中进行求解，由此可以得到测试矢量，否则该故障就不可测试。

3 实例及算法性能分析

3.1 实例分析

下面以ISCAS’85BenchmarksC17为例，对串扰时延故障进行分析，逻辑图如图1所示。

图1 实例电路图

其中故障点在X7处，攻击线X2的障类型为下降减速时延，信号采样在X10，其中被测通路为X4→X7→X8→X10。本电路的CNF范式表达式为：QC=NANDG1·NANDG2·NANDG3·NANDG4·NANDG5·NANDG6因此串扰故障时延模型情况下的组合电路的CNF表达式为：

(2)

(X8V+X10V)

(X9V+X11V)X11V

(3)

再次重复操作STEP3得到CNF最简式：

(4)

最后令最简范式等于1，则所有的真值按照一定的赋值顺序构成了一个搜索空间的集合,即V={X1S,X3S,X5S,X5V,X6S,X9S,X9V,X11S}，经过反复赋值和回溯，最终可得到测试向量V的空间。存在两种情况：V1={11011001}，V2={10011001}综合上面各个输入量得到Vtotal={1X1SX2S1X3S11001111110001101},故最终得到8组测试矢量X1,X2,X3,X4,X5如表3所示。

表3 测试矢量表

将X3,X4,的向量组带入到与非门的CNF范式中，并且使与非门范式值为1，即可得到故障点X7的变化，即(X7S,X7V)=(1,1),又因为(X2S,X2V)=(1,1)。那么指定的故障点是由攻击线X2和受害线X7同时同向跳变引起的下降时延减速故障。由以上测试向量可以求得该故障电路。

3.2 算法性能分析

[10]可以发现，本文引用的SAT方法相对于传统的ATPG算法(例如FAN算法)效率更高。在linux系统CPU2.93 GHz，内存512M的PC机上，对标准电路ISCAS’85电路进行了验证。对比FAN算法如文献[11]中的CPU时钟，本算法具有明显的优势。如表4所示，随机注入20个故障得出相应测试矢量所耗时间的平均值。

表4 实验结果与文献[11]对比

4 结论

在高速互联电路中，串扰作为影响信号完整性问题中的一重要因素严重影响信号传输的质量，为了确保电路的正确，需要对电路引起的故障进行检测，传统的ATPG算法无法满足求解规模较大的问题，文章提出的在串扰通路时延迟故障模型下使用布尔可满足性求解技术求解，能够有效的、省时的解决时延故障的测试问题。

参考文献：

[1] 石光耀, 尚玉玲, 曲 理. BGA焊点形态和布局对信号完整性的影响[J]. 桂林电子科技大学学报, 2013, 33(4):279-283.

[2] Ahmed N, Tehranipour M, Nourani M. Extending JTAG for Testing Signal Integrity in SoCs[C]. Conference on Design, Automation and Test in Europe. IEEE Computer Society, 2003:218-223.

[3] 张 月，李华伟，宫月战等,针对串扰引起的时延故障的测试产生[J].计算机辅助设计图形学学报，2004：1448-1553.

[4] Chen W Y, Gupta S K, Breuer M A. Test Generation for Crosstalk-Induced Delay in Integrated Circuits[C]. IEEE, 1999:191-200.

[5] Cheng KT，Chen CH. Generation of high quality non-robust test for Path dealy fsults .Proceedings of design automation conference,1994,PP.365-369.

[6] 李 玲.基于SAT的数字电路测试生成算法研究[D].哈尔滨：哈尔滨工程大学,2012.

[7] 付 宇，吴为民，姜 升,等.基于SAT的组合电路自动测试向量生成[J]微电子学:2011,14(2):230-234.

[8] 杨德才，谢永乐，陈光禹.基于布尔可满足性的层次化通路时延故障测试[J].电子测量与仪器学报:2008,22(3):6-10.

[9] 姜 升. 基于SAT的通路时延故障测试生成技术的研究[D]. 北京交通大学, 2011.

[10] Drechsler S. Acceleration of SAT-Based ATPG for industrial designs[J].IEEE Transactions on Computer-Aided Design of Integrated Circ-uits and Systems:2008,27(7):1329-13.

[11] 颜学龙，梁晓琳,尚玉玲.基于MAF模型的串扰时延故障的测试矢量生成.计算机工程与应用:2009(19).

Study on SAT-ATPG Algorithm for Time Delay Fault of Crosstalk

Shang Yuling，Qian Shang，Liu Peng

(Guilin University of Electronic Technology School of Electronic Engineering and Automation, GuiLin 541004,China)

As the improvement of chip operating speed, so it is high time to consider and take some measures to solve the problem. A test-generation method based on multiple crosstalk-induced glitch fault model is proposed. In this method ,it discusses Boolean satisfiability problem and analyse the crosstalk path delay fault model as well as Seven value logic of test vectors. It also analyse the mathematical logical expression converted by the crosstalk path delay fault model. And simplified CNF expression under the condition of non robust test,then a SAT-ATPG test algorithm of crosstalk delay fault is proposed.Finally,the algorithm is verified by specific example and the performance of the algorithm is effective for crosstalk-induced delay faults.

crosstalk delay fault;Boolean Satisfiability;delay faults testing

2016-07-25；

2016-11-08。

尚玉玲(1977-)，女，广西桂林人，博士，副研究员，主要从事高速电路信号完整性测试研究。

1671-4598(2017)03-0018-04

10.16526/j.cnki.11-4762/tp.2017.03.006

TP3

A