结合结构特征基于测试集重排序的故障诊断方法

欧阳丹彤，刘 扬，宋金彩，王浩然，张立明

（1.吉林大学计算机科学与技术学院，吉林长春 130012；2.吉林大学软件学院，吉林长春 130012；3.符号计算与知识工程教育部重点实验室（吉林大学），吉林长春 130012；4.中国科学院大学计算机科学与技术学院，北京 100000）

1 引言

随着现代半导体工业的迅猛发展，如今集成电路已经发展到由数十亿个晶体管组成的规模.电路的规模不断增大但电路尺寸却不断缩小，使得电路故障检测与诊断的难度和成本也随之不断增加.为了解决故障诊断效率相对低下的问题，学者们开始研究如何能够快速、有效地诊断出电路中发生的故障［1，2］.根据电路的实际输出响应，学者们主要使用基于模型的诊断方法［3～5］和基于测试的诊断方法［6～8］对错误的输出响应进行分析，从而得到该集成电路的候选故障信息.基于模型的诊断方法通过建立集成电路对应的模型，利用电路输入得到电路的预期行为，然后以预期行为与观测行为的差异作为诊断方法的输入，进而计算能够解释这种差异的候选诊断解.基于测试的故障诊断方法则是利用测试激励集对单故障的实际输出响应与该电路的故障输出响应进行比较，匹配得到与故障输出响应最契合的故障，并将这些故障作为候选诊断解，组成候选故障集合.

近几年，许多学者对基于测试激励集的故障诊断方法进行了研究.Pomeranz［9］提出了SCOR 方法和DD方法：SCOR 方法通过比较电路在测试激励集下单故障与真实故障输出响应之间相同的端口个数，将该值作为该故障的评分，选取评分最高的故障组成候选故障诊断解；DD 方法在SCOR 方法的基础上通过对比同一测试激励集下同一输出端口的单故障与真实故障输出响应，将输出响应相同的故障添加到Fsame集合中，再根据SCOR 方法从Fsame中选取评分最高的候选故障组成候选故障诊断解.Pomeranz［10］提出了ADD方法，通过调用DD 方法得到一个初始候选故障集，逐个删除测试激励集中的每个测试激励，将每次删除测试激励后的测试激励集作为DD 方法的新测试激励集，在上一次候选故障集基础上再次调用DD 方法得到新的候选故障集，迭代求解直到得到最小的候选故障集.Pomeranz［11］随后提出了一种两阶段故障诊断方法：首先，使用完整的测试激励集作为故障诊断测试激励集调用DD 方法得到一组候选故障集，将该候选故障集与故障诊断测试激励集作为ADD 方法的输入得到一组新的候选故障集和新的故障诊断测试激励集，针对新的候选故障集中的无法区分故障对，使用诊断测试生成方法，产生可以区分故障对的新的测试激励，并将该测试激励添加到当前故障诊断测试激励集当中，形成新的故障诊断测试激励集；其次，将第一阶段得到的新故障诊断测试激励集与新候选故障集作为第二阶段DD 方法的输入，之后的过程与第一阶段相同，将最后得到的候选故障集作为候选故障诊断解.

为进一步提高基于测试激励集的方法的故障诊断准确性，国内外学者通过分析测试激励与故障之间的关系，开展了关于通过调整测试激励集顺序来提高故障诊断准确性的研究.Bernardi等学者［12］提出通过对测试激励集进行重新排序的故障诊断方法，通过建立一个基于树的故障字典，从根节点到叶节点遍历诊断树来识别每个故障，测试重新排序用于最小化根节点到叶节点路径的长度，以减少故障诊断所需识别的故障信息.Bolchini等学者［13］通过数据挖掘技术提取测试与故障之间的规则，并结合已有的系统模型建立测试与故障之间的关系，根据该关系对测试激励集重排序，在保证故障诊断准确性的前提下较大程度减少了故障诊断过程所需的测试激励数目.Huang 等学者［14］为了提高有限故障信息下的扫描链故障诊断分辨率，提出诊断覆盖率的概念，利用诊断覆盖率度量测试激励的诊断准确性，对测试激励按照诊断覆盖率大小进行降序重新排序，在保证诊断准确性的情况下有效缩减了测试激励集规模.Xue 等学者［15］提出一种结合诊断特征的测试激励重排序方法，根据测试激励集对诊断结果的影响程度的大小对测试激励集进行排序，当遍历至对诊断结果无影响的测试激励时便停止诊断过程，得到候选故障集，将最终的候选故障集作为候选故障诊断解，进一步得到最终的诊断解.Bodhe 等学者［16］提出了N-Cover 方法，该方法使用贪婪算法选择故障数据，每次选择包含故障位最多的故障数据加入当前解中，直到达到特定的覆盖要求为止，尽量在满足覆盖要求的情况下有效缩减故障数据.Bodhe等学者［17］在N-Cover方法基础上提出了结合测试激励集重排序的GTreord方法，该方法在不影响诊断质量的情况下对测试激励重新排序，然后调用N-Cover 方法，进而较大程度提高了故障诊断方法的准确性.

文献［9～11］提出的方法主要结合测试激励集与输出响应以有效提高故障诊断效率.文献［12～17］中提出的方法则是利用基于测试激励集重排序的方法，提高故障诊断的准确率、分辨率以及诊断效率.本文在对以GTreord 为代表的基于测试激励集重排序的方法深入研究的基础上，依据每个测试激励对生成该故障诊断解集合的影响程度的不同，提出了测试分数概念，在此基础上提出基于测试激励集重排序的故障诊断方法（Reordering Test Default Diagnosis，RTDD）.RTDD 方法依据测试激励与候选故障诊断解之间的结构特征，得到每个测试激励的测试分数，根据测试分数对测试激励进行重新排序，并将重排序后的测试激励集用于故障诊断.RTDD 方法相较于GTreord 方法，主要有以下优点：

（1）RTDD 方法有效缩短了测试激励集重排序时间，提高了测试激励集重排序效率；

（2）RTDD 方法中的重排序测试激励集方法，在保证同样故障诊断准确性的情况下能有效减少测试激励个数.

2 GTreord方法

本节先介绍基于测试激励集重排序的故障诊断方法中用到的相关概念和定义，随后结合相关诊断实例详细介绍GTreord方法［17］.

2.1 基本概念

下面介绍GTreord方法中所使用概念的基本定义.

定义1电路中单模型故障为fk，所有可能发生的模型故障集合为F，电路中真实发生的故障集合为fobs，用于诊断过程的单个测试激励为ti，测试激励集合为T，记为F={f0,f1,f2,…,fn-1,fn}，fobs={fk|fk∈F}，T={t0,t1,t2,…,tm-1,tm}，其中fobs⊂F.

定义2电路在T下发生fobs中故障时电路的实际输出响应为Robs，电路在T下无故障发生时的预期输出响应为Rff，电路在T下发生fk时电路的实际输出响应为Rk.

定义3电路的第j位（0≤j＜输出端口总数）输出端口为zj.在电路在ti激励下，发生fobs中故障时电路zj的实际输出响应为Robs(i,j)，发生fk时电路zj的实际输出响应为Rk(i,j)，无故障发生时电路zj的预期输出响应为Rff(i,j).

定义4候选故障诊断解的集合为CND.

定义5用于诊断fk时保证CND 中候选故障诊断解数量不变的最小测试子集为T(sub,k)，满足T(sub,k)⊂T.称最小测试子集的集合为TSUB，记为TSUB={T(sub,0),T(sub,1),T(sub,2),…,T(sub,n-1),T(sub,n)}.

定义6GTreord 方法重排序测试激励集为Treord.使用Treord作为N-Cover 方法输入时，N-Cover 方法返回的诊断测试激励集为Tcover.

2.2 GTreord方法

GTreord 方法的两个过程是测试激励删除过程和测试激励集重排序过程.测试激励删除过程通过删除ti得到每个fk对应的T(sub,k)，并由所有T(sub,k)组成TSUB；测试激励集重排序过程根据每个ti在TSUB中出现的次数，由高到低对T进行重排序.排序后调用N-Cover 方法得到Tcover.GTreord方法伪代码如算法1所示.

根据伪代码步骤2 至步骤18 为测试激励删除过程，该过程通过模拟每个fk的发生，将fk作为fobs.并将Robs，Rk，T，F作为DD 方法［9］的输入进行故障诊断，得到初始CND.之后从T的末尾开始逐个删除ti，将删除ti后的T(sub,k)代替T作为DD 方法的输入得到CNDnew，若删除ti后CNDnew中的候选诊断解的数量不变则接受ti的删除，否则将ti重新加入T并将其置于T的首部，对T中ti的下标进行更新.遍历T后得到最终该fk对应的T(sub,k).依照该过程遍历F后得到TSUB.下面结合例1 对测试激励删除过程进行详细描述.

例1本实例中使用的电路为c17基准化电路.c17实例具体信息：电路中有2 个可观测输出端口z0和z1，F={f0,f1,f2,…,f12,f13}，T={t0,t1,t2,…,t5,t6}，具体信息如图1（a）所示.本实例中电路模拟f0为真实故障时，使用T进行故障诊断得到的CND={f0,f2,f5,f11}，|CND|=4.

下面详细介绍GTreord 方法测试激励删除过程.如图1 所示，首先令Tsub=T，随后从图1（a）中删除t6，得到图1（b）所示的Tsub，使用该测试激励集进行故障诊断得到CNDnew={f0,f2,f4,f5,f11}，与CND相比，|CNDnew| ≠|CND|，所以将t6加入到图1（b）中所示的Tsub首部，如图1（c）所示，并更新Tsub的顺序.随后将图1（c）中t6删除，得到图1（d）所示的Tsub，用该测试激励集进行故障诊断，得到CNDnew={f0,f1,f3,f11}，此时|CNDnew|=|CND|，所以彻底删除t6，随后删除t5，得到图1（e）中所示的Tsub，用该测试激励集进行故障诊断，得 到 CNDnew={f0,f4,f9,f11,f13}，此 时|CNDnew| ≠|CND|，所以将t5加入到图1（e）中所示的Tsub首部，如图1（f）所示，并更新Tsub的顺序.以此类推，得到针对该模型故障的Tsub.

图1 GTreord方法测试激励删除过程

步骤19 至步骤29 为测试激励集重排序过程，该过程在测试激励删除过程模拟F中所有的fk，在得到Tsub的基础上，计算每个ti在Tsub中出现的次数，依据出现次数的高低对T进行排序得到最终的Treord.随后将Treord、F、Rk作为N-Cover方法的输入，得到最终的Tcover.

在例1的基础上，介绍GTreord方法的重排序过程，例1中得到的部分T(sub,k)如图2所示.

图2 GTreord方法部分T(sub,k)

下面详细介绍GTreord 方法测试激励集重排序过程.以图2 所示部分Tsub为例，T中t0=10100，在T(sub,0)和T(sub,2)中均有出现，所以此时t0的分数为2.以此类推，遍历Tsub得到所有ti分数后进行排序，最终排序后的Treord如图3 所示.随后将Treord用于N-Cover 方法得到Tcover，Tcover={t0,t1,t2,t3,t4}.

图3 GTreord方法测试激励集重排序结果

3 RTDD方法

本节将首先介绍RTDD 方法在测试激励集重排序过程中所使用概念的基本定义，然后结合伪代码与具体实例详细介绍RTDD方法.

3.1 基本概念

下面介绍RTDD方法相关定义.

定义7在RTDD 方法中，将模型故障的集合记为Fnew，Fnew={fK|fK∈F}，且满足Fnew⊂F.将Fnew中fK的个数记为|Fnew|.

定义8将Fnew中在ti的激励下满足Rk≠Rff的fk组成的故障集合称为候选单故障集合CanF(ti).将CanF(ti)中fk的个数记为||CanF(ti) ||.且当对fk进行诊断时，将候选单故障集合称为CanF(ti,k).

定义9在ti的激励下，将||CanF(ti) ||与|Fnew|的比值称为ti的故障检测评分det(ti)，记为det(ti)=且当对fk进行诊断时，将故障检测评分称为det(ti,k)，记为det(ti,k)=

定义10在ti的激励下，将Fnew中所有fk满足Rk(i,j)=Robs(i,j)的所有元素个数称为ti的故障诊断评分dia(ti)，记 为dia(ti)=且当对fk进行诊断时，将故障诊断评分称为dia(ti,k)，记为dia(ti,k)=

定义11当对fk进行诊断时，将ti的故障检测评分与故障诊断评分的乘积称为测试分数s(ti,k)，记为s(ti,k)=det(ti,k) ×dia(ti,k)，且将F中所有fk对应的s(ti,k)的和记为s(ti).

定义12将RTDD 方法重排序测试激励集记为RTreord.将使用RTreord作为N-Cover 方法输入时返回的诊断测试激励集记为RTcover.

3.2 RTDD方法

RTDD 方法考虑到每个ti对生成该故障诊断解集合的影响程度不同，提出了测试分数概念，依据ti与候选故障诊断解之间的对应关系，通过比较在ti的激励下电路的Rk、Robs以及Rff，得到每个ti对得到该故障诊断解集合的影响程度，即为测试分数，根据测试分数对ti进行重新排序得到测试激励影响程度从高到低排列的新的测试激励集.得到重排序测试激励集之后，将其用于N-Cover 方法，得到N-Cover 方法返回的诊断测试激励集.

在测试集重排序过程中，s(ti)能够作为ti的测试分数的原因有以下几点：首先，根据ti与fk之间的对应关系，一个ti可以检测到多个fk，一个fk也可以被多个ti检测，但一个ti并不能检测到所有fk.且在ti激励下满足Rff≠Rk的fk更可能是故障诊断解，det(ti)表示ti在CND中能够检测的fk占候选故障诊断解的比重，即det(ti)可以表示该T的故障检测能力对生成该CND 的影响程度；其次，在故障诊断方法中证明了若fk的Rk与Robs具有相同输出端口的个数越多，则该fk更可能是故障诊断解，dia(ti)为Fnew中所有fk在ti激励下满足Rk=Robs的端口个数之和，代表着该ti在故障诊断过程中对生成CND的影响程度.因此本文提出一个观点：若一个ti能够检测到的fk占候选故障诊断解比重越大且在该ti激励下所有候选故障的Rk与Robs相同输出端口个数之和越大，那么该ti对生成该CND 的影响程度越大.所以本文结合ti的det(ti)与dia(ti)来计算ti的测试分数.

RTDD方法的伪代码如算法2所示.

根据伪代码，RTDD 方法对F中每一个fk进行故障诊断.首先，令fobs=fk，Robs=Rk，使用T、F、Robs作为故障诊断程序DD 方法的输入，得到初始CND，将该CND 作为测试激励集重排序过程的故障集合Fnew；其次，比较Fnew中的fk在T中的每一个ti激励下，电路的Rk与Rff，将满足Rff≠Rk条件的fk组成针对ti激励下的CanF(ti,k)；然 后，计 算 det(ti,k)，即计算 det(ti,k)=的值；接下来，计算dia(ti,k)，即计算满足ti的激励下，Fnew中所有fk满足Rk(i,j)=Robs(i,j)条件的输出端口的个数之和；然后，计算ti的s(ti,k)，即计算det(ti,k)与dia(ti,k)的乘积；下一步，遍历F中每一个fk得到所有的s(ti,k)，将同一ti的s(ti,k)相加，得到该ti的s(ti)；随后根据s(ti)由高到低对测试激励进行重新排序，得到新的测试激励集RTreord；最后，将RTreord，F，Rk作为N-Cover 方法的输入，得到满足N-Cover 方法终止条件时所需ti组成的RTcover.

复杂性分析：设测试激励对电路进行故障检测的复杂度为o(t)，故障诊断和故障检测都是通过对比电路输出是否相同来实现，即故障诊断复杂度也为o(t).设故障个数为n，测试激励个数为m，GTreord 方法中故障fi对应的测试激励个数为di，0 ＜di＜m.所有测试激励个数平均值记为d=，则测试激励总数为n×d.GTreord 方法需对每个故障检测每个测试激励是否可以删除，其求解复杂度为n×d×o(t)；其最坏情况下，不存在可以删除的测试激励时，其时间复杂度为n×(m-1)×o(t).RTDD 方法对m个测试激励求解故障检测和故障诊断分数，求解复杂度为m×(o(t)+o(t))，即2×m×o(t).随着电路规模的增大，n×d和n×(m-1)的增加速度远高于2×m，RTDD 方法比GTreord 方法的求解优势更明显.

下面结合例1中c17电路详细介绍RTDD 方法具体过程.电路模拟f0为真实故障时，部分Robs和Rk与T对应的具体细节如表1所示.

下面详细介绍RTDD 方法测试激励集重排序过程.在 例1 中fobs=f0，经DD 方法得到CND={f0,f2,f5,f11}.令Fnew=CND，以表1中的信息为例，此时仅考虑故障集合Fnew中的故障，以t0的激励下计算过程为例，首先计算得到CanF(t0,0)，Rff=10，R0=00，R2=10，其中Rff=R2，所以R2不能添加到CanF(t0,0)中，以此类推遍历Fnew中所有模型故障得到CanF(t0,0)={f0,f11}；接下来计算det(ti,0)，根据已经得到的CanF(t0,0)与Fnew，det(t0,0)==0.5；然后计算dia(t0,0)，在t0的激励下Robs=00，R0=00，R2=10，由 于Robs(0,0)=R0(0,0)，Robs(0,1)=R0(0,1)，Robs(0,0)≠R2(0,0)，Robs(0,1)=R2(0,1)，此时dia(t0,0)=1+1+1=3，以此类推最终dia(t0,0)=5；下一步计算s(t0,0)，根据计算得到的t0对应 的det(t0,0) 和dia(t0,0)，计 算s(t0,0)=det(t0,0)×dia(t0,0)=0.5×5=2.5；遍历T中所有的ti，得到fobs=f0时所有ti的s(ti,0)；遍历F中所有fk，将同一ti的s(ti,k)相加，得到最终的s(ti)；最后依据s(ti)的大小进行测试激励集重排序，得到RTreord；在得到RTreord之后，将RTreord，F，Rk作为N-Cover 方法的输入，得到N-Cover 方法返回的RTcover.RTreord与RTcover如图4所示.

表1 c17部分Rk和Robs对照表

图4 c17实例RTreord，RTcover

以上便是RTDD 方法的具体实现过程.从以上实例可知，本文提出的RTDD 方法相较于GTreord 方法能够更加高效地完成测试激励集重排序过程，且使用更少的ti即可达到与GTreord 方法同样的诊断要求.下一节将介绍RTDD 方法和GTreord 方法在ISCAS-85［18］和ISCAS-89［19］基准电路上的实验结果.

4 实验

本节将从测试激励集重排序效率和排序后测试激励集诊断准确性两个方面对RTDD 方法的性能进行实验分析.

4.1 实验环境

实验环境如下：Windows 10，CPU Intel（R）Core（TM）i7-7700HQ 2.80GHz，16GB RAM，python3.使用商业工具Synopspy Tetramax2018 生成T，使用商业工具Modelsim SE 10.4 进行故障模拟仿真，得到电路模拟发生故障时的实际输出响应Rk与Robs.

4.2 故障类型

本文所使用的故障是Stuck-at 故障（固定型故障），使用该故障的原因有以下几点：

（1）多数其他类型故障都可以转换为Stuck-at 故障或用不同Stuck-at故障的组合表示；

（2）一个故障诊断方法若对Stuck-at 故障进行诊断得到较高的分辨率和准确率时，对于电路中的其他类型故障进行诊断也有较高的分辨率和准确率；

（3）其易于生成故障列表，且故障总数随着电路中的逻辑门的个数线性增长，故障列表的规模容易控制.

4.3 实验结果

本文采用的集成电路为国际测试领域中广泛使用的基准化集成电路ISCAS-85［18］和ISCAS-89［19］基准电路.因为RTDD 方法和GTreord 方法的测试激励集重排序结果仅与测试激励集相关，不会受到其他因素的影响，所以仅进行一次对比实验.下面对GTreord 方法和本文提出的RTDD 方法在完全一致的条件下的实验结果进行分析.

表2 表示ISCAS-85 基准下所有电路使用RTDD 方法的测试激励集重排序过程与GTreord 方法的结果对比.其中第1 列Circuit Name 表示电路名称；第2 列Fnum表示该电路用于RTDD 方法与GTreord 方法的fk的数量；第3 列Tnum表示电路初始T中ti的个数；第4 列和第5 列分别表示RTDD 方法和GTreord 方法调用DD 方法的次数；第6 列Rtest表示RTDD 方法中RTcover中ti个数与RTreord中ti个数的比值；第7 列Gtest表示将GTreord 方法中Tcover中ti个数与Treord中ti个数的比值.

表3 表示ISCAS-89 基准下所有电路使用RTDD 方法的测试激励集重排序过程与GTreord 方法的结果对比，各列内容与表2相同.

从表2和表3中的RTDD方法测试激励集重排序过程与GTreord方法的实验结果分析如下.

表2 ISCAS-85实例测试激励集重排序结果

表3 ISCAS-89实例测试激励集重排序结果

（1）针对ISCAS-85 基准电路和ISCAS-89 基准电路，在达到同样诊断准确性情况下，比较RTDD 方法的RTreord与GTreord 方法的Treord，虽然RTcover中ti的个数在电路c432，c3540，c6288，s298，s349，s386，s444，s526n，s832，s953，s35932 电路上多于Tcover中ti的个数，但是在ISCAS-85和ISCAS-89基准下，72.5%的电路上少于Tcover中ti的个数.结果表明，针对大多数电路，RTDD 方法测试激励集重排序过程得到的RTreord与GTreord 方法测试激励集重排序得到的Treord相比，达到同样诊断准确性时需要用于诊断的测试激励个数更少，RTDD 方法测试激励集重排序过程得到的RTreord确实具有更好的诊断准确性.

（2）针对ISCAS-85 基准电路和ISCAS-89 基准电路，RTDD 方法相较于GTreord方法调用DD方法的次数更少，节省了大量的时间成本.根据两种方法的算法流程可以得到以下推论：每个电路进行测试激励集重排序时，RTDD 方法的测试激励集重排序过程需要调用DD 方法的次数等于其Fnum；GTreord 方法需要调用DD方法的次数等于其Fnum×（Tnum+1）.尽管RTDD 方法测试激励集重排序过程调用DD 方法之后需要进行一系列的计算过程，但该过程所需时间与调用一次DD 方法的时间相比而言是可以完全可以接受的.表4表示在ISSCAS-85 和ISCAS-89 基本电路中，RTDD 方法计算一次s(ti)的过程所需时间，以及使用完整T调用一次DD 方法的时间，其中Circuit Name 表示电路名称；rtime表示RTDD方法计算过程的时间，dtime表示调用一次DD方法的时间，时间单位均为s.尽管GTreord 方法在调用DD方法时的T不断减小，DD方法所需时间在不断减小，但是相较于RTDD 方法的计算过程的时间仍然很长.总之，结果表明，RTDD 方法测试激励集重排序过程具有更好的测试激励集重排序效率.

表4 RTDD方法测试激励集重排序过程时间对比

综上所述，本文提出的RTDD 方法与Gtreord 方法相比有以下两点优势：

（1）RTDD 方法能够更加高效地对测试激励集进行重排序，时间缩短最多可达到4个数量级；

（2）RTDD 方法在保障同样诊断准确性的情况下，72.5%的电路所需ti更少，平均减少3.645%，具有更强的诊断准确性.

5 总结

本文提出的RTDD 方法根据测试激励与候选故障诊断解之间的关系计算测试激励的测试分数，依据测试分数对测试激励集进行重排序，并将用重排序后的测试激励集用故障诊断.在标准测试用例上的实验表明：RTDD 方法的测试激励集重排序过程与GTreord 方法相比，调用DD 方法的次数更少，能够更加高效地进行测试激励集重排序，求解速度有1～4 个数量级的提高；此外，RTDD 方法重排序后测试激励集用于故障诊断时，在保证同样诊断准确性情况下所需测试激励集个数更少.