人工蜂群优化非鲁棒路径时滞故障测试生成算法

赵 莹，孟 祥，李艳娟，王一帆，赵彦超

(1.北华大学 电气信息工程学院，吉林 吉林 132021;2.东北林业大学 计算机学院，黑龙江 哈尔滨 150040)

0 引言

路径时滞故障［1］广泛存在于数字电路中，其中最主要的是非鲁棒路径时滞故障。当数字电路中存在非鲁棒路径时滞故障时，将导致电路不能正常工作甚至完全瘫痪。非鲁棒路径时滞故障测试生成算法旨在找出能够测试这种故障的矢量对，使故障在输出端能够表现出来。对此，国内外学者进行了深入研究，提出了众多算法，S.Ohtake 提出了基于固定故障测试生成算法的路径时滞故障测试生成［2］，该算法故障覆盖率能够达到91%以上，但平均测试时间较长;Hiroshi Takahashi 等人提出了基于Ni 判定测试集的路径时滞故障测试生成算法［3］，该算法平均测试生成时间较短，但故障覆盖率较低，且故障测试集大。本文提出的算法首先应用电路转换法则把数字电路转换成为其等效电路，然后用Hopfield 神经网络构建等效电路单固定故障的约束网络，并得到能量函数，再应用人工蜂群优化算法计算能量函数的最小值以得到等效电路单固定故障的测试矢量，最后根据对应关系得到原电路非鲁棒路径时滞故障的测试矢量对。

1 非鲁棒路径时滞故障相关知识

定义1:一个数字电路的路径P 由一系列的门{G1，G2，…，Gn}以及门的输入线和输出线组成，G1是第一个门，Gn是最后一个门，Gi的输出是Gi+1的输入。

定义2:当路径P 的输入端出现电平跳变，路径P 的输出端也会出现跳变，当输出端的电平跳变时间超出规定的限度，则称路径P 存在路径时滞故障，上升沿和下降沿路径时滞故障分别用P ↑和P↓表示。

定义3:当数字电路的路径P 存在路径时滞故障，且在这条路径上所有门的其它输入端的值都是非控制值时(与门和与非门的非控制值是1，或门和或非门的非控制值是0)，这种路径时滞故障称为非鲁棒路径时滞故障。

对图1 所示数字电路，cG1G2G3y 是一条路径P，如果G1门的d 输入为0，G2门的e 输入为1，G3门的f 输入为0，且cG1G2G3y 存在路径时滞故障，则这种故障就是非鲁棒路径时滞故障。

图1 非鲁棒路径时滞故障电路Fig.1 Non-robust path delay fault circuit

2 数字电路等效转换

为了把非鲁棒路径时滞故障转换称为等效的单固定故障，首先需要把数字电路按照电路转换法则转换称为其等效电路。方法如下:

(1)使用反演律把路径P 上的所有非门(包括与非门中的非门)移到输入端(路径P 除了输入端不允许再出现非门)。

图2 把非门移到输入端Fig.2 Removing to input end

按照这种方法，把图1 中路径cG1G2G3y 上的非门移到输入端的电路如图3 所示(G2门路径P 上的非门与G1门输出的非门正好抵消，所以G1门变为或门)。

图3 路径cG1G2G3y 上的非门移到输入端的电路Fig.3 Removing not-gate of cG1G2G3y’s to input

(2)把路径P 上所有门的扇出移到输入端

对图1 所示电路，G1门有两个扇出e 和g，G2门有两个扇出h 和i，为了把扇出移到输入端，可以通过增加门的方法。这里G2需要增加一个门;G1需要增加两个门，变换后的电路如图4 所示，可以看出电路的逻辑功能并未改变，但路径P 上的扇出已经移到输入端。

图4 图1 的等效电路Fig.4 Equivalent circuit of Fig.1

注意，非路径P 上的门保持不变，例如路径cG1gG2h G4j G3y 是非路径P，所以在变换时，G1门和G2门都不用变换，如图4 中的G12门和G21门所示。

可以证明等效电路中的固定0(固定1)故障与原电路中的上升沿时滞故障(下降沿时滞故障)相对应。对图1 电路，如果路径cG1G2G3y存在上升沿时滞故障，当在输入端施加测试矢量对＜000，001 ＞，故障可在输出端y 测试出来。如图5 所示，当在t0时刻，输入abc 由000 变为001，如果电路无故障，则在t1时刻可测得输出值为1，如果有故障在t1时刻可测得输出值为0。而对图4 所示电路，当输入c 存在固定0 故障时，当输入测试矢量001 时，电路无故障，可测得输出值为1，如果有故障输出值为0，可见图1 非鲁棒路径时滞故障的波形测试结果与图4 单固定固定故障的波形测试结果一致。这样变换后的等效电路中的单固定故障与原电路中的非鲁棒路径时滞故障一一对应，这样就可以把非鲁棒路径时滞故障的测试生成问题转换为单固定故障的测试生成。

图5 路径时滞故障的输出反应Fig.5 The output response of path delay fault

3 等效电路单固定故障神经网络模型的构建

本文采用Hopfield 神经网络构建等效电路单固定故障的模型［4］，Hopfield 神经网络模型的能量函数为:

其中Vi和Vj是神经元i 和j 的状态值(0 或1)，神经元的数目是N，神经元i 的内部参数是Ii，即阈值，神经元i 和j 之间的权值是Tij，K 是常数，保证能量函数为非负值。

基本门电路的神经网络模型可以根据文献［4］中的方法得到，数字电路由基本门电路组成，因此可以方便地得到数字电路的神经网络模型，并得到其对应的能量函数。

对数字电路相容状态(符合数字电路逻辑功能)，神经网络能量函数的值为0，否则大于0。为了得到符合相容状态的电路，需要构建待测电路的约束电路，单输出和多输出电路的约束电路如图6 和图7 所示［5－8］。当输入某个测试矢量时，无故障电路和有故障电路的输出肯定相异，所以约束电路处于相容状态。

图6 单输出电路的约束电路Fig.6 Single-output constraint circuit

图7 多输出电路的约束电路Fig.7 Multiple-output constraint circuit

这样通过计算约束电路对应能量函数的最小值点(也是零点)就可得到单固定故障的测试矢量。

4 算法描述

人工蜂群算法［9］于2005 年由土耳其学者karaboga 提出，是一种模拟蜜蜂找寻最优蜜源的仿生优化算法，该算法在每次迭代中都进行局部和全局搜索，因此能够减小进入局部最优解的概率。具体算法的流程图如图8 所示。在使用人工蜂群算法求解优化问题时，食物源的位置被抽象为最优解，待优化问题的适应度函数值决定了食物源的优劣。人工蜂群主要包括引领蜂、跟随蜂和侦查蜂。假设该算法有N 个初始种群［xi］(i=1，2，…，N)，［xi］含有m 个量(m为电路输入端的个数)，每个量的取值为0 或1。引领蜂首先随机对某个食物源进行邻域搜索，并按式(1)对食物源位置进行更新［10］:

其中δi为［－ 1，0，1］中的一个随机数;［Ii］为修正矩阵。

图8 算法流程图Fig.8 Flowchart of algorithm

适值函数定义为

其中E(x)为约束电路能量函数。f(x)的取值范围在0 与1 之间，食物源xi的适值f(xi)越大，说明xi的性能越好，f(xi)为1 时的［xi］即为给定单固定故障的一个测试矢量。当所有的引领蜂搜索完毕后，会通过跳摇摆舞的方式把信息传递给跟随蜂，跟随蜂采用轮盘赌规则选择食物源，保留收益率大的食物源。

在算法中，设置搜寻控制参数为L，它表示某个食物源未被更新的上限。如果某个食物源经过L 次搜寻后均未得到改善，说明该食物源进入了局部最优，这个食物源应该被放弃，相应的引领蜂变为侦查蜂，这时要按式(2)随机产生一个新的食物源位置代替原来的食物源［10］。

5 实验结果

ISCAS’85 电路集是为电路测试生成算法提供的国际标准电路集合，算法的优劣通常要在这些电路上测试，ISCAS’85 电路集中的C17 电路如图9 所示，该电路有5 个输入端，2 个输出端，由6 个与非门构成。

图9 ISCAS’85 中的C17 电路Fig.9 Circuit C17 of ISCAS’85

本文算法与其它文献算法比较的实验结果表1，根据本文算法，得到C17 电路的实验结果见表2。由结果可知，本文算法在故障覆盖率明显提高的情况下，故障平均测试时间明显缩短，说明本文算法较其它文献算法优越。

表1 不同算法测试实验结果Tab.1 Test experiment results of different algorithms

表2 C17 电路实验结果Tab.2 Experiment results of circuit C17

6 结论

本文将神经网络和人工蜂群算法应用于数字电路非鲁棒路径时滞故障的测试生成，充分利用了神经网络和人工蜂群算法解决优化问题的优越性，避免进入局部最优解。实验结果表明本文算法的故障覆盖率能够达到98%以上，平均测试生成时间低于0.8 μs，与其它文献算法相比具有明显的优越性。但本文算法应用于大规模时序逻辑电路时，会出现迭代次数大，故障覆盖率低和测试生成时间长等缺点，因此该算法不适用于大规模时序逻辑电路。

［1］G.L.Smith.Model for delay faults upon paths［C］//Int.Test Conference，1985:342－345.

［2］S.Ohtake，K.Ohtani，H.Fujiwara.A method of test generation for path delay faults using stuck-at fault test generation algorithms［C］//Proceeding design，automation and test in Europe，2003:310－315.

［3］Hiroshi Takahashi，Kewal K.Saluja，Yuzo Takamatsu.An Alternative Method of Generating Tests for Path Delay Faults Using Ni-Detection Test sets［C］//Proceedings of the 2002 Pacific Rim International Symposium on Dependable Computing，2002:23－24.

［4］T.Chakrdhar，M.L.Bushnell，V.D.Agrawal.Toward Massively Parallel Automatic Test Generation［J］.IEEE Trans.Computer_ Aided Design.1990，(9):981－993.

［5］吴丽华，王旭东.遗传优化三值神经网络多故障测试生成算法［J］.仪器仪表学报，2010，31(8).

［6］陈朝阳，丁明跃.基于神经网络测试码生成的一个鲁棒算法［J］.华中理工大学学报，1999，27(9):90－91.

［7］徐建斌，李智.神经网络在组合电路故障模拟测试生成算法中的应用［J］.电路与系统学报，2001，6(4):109－110.

［8］刘晓东，孙圣和.基于神经网络的组合电路测试生成算法［J］.哈尔滨工业大学学报，2002，34(2):256－257.

［9］Karaboga D.An idea based on honey bee swarm for numerical optimization［D］.Kayseri:Erciyes University，2005.

［10］易正俊，韩晓晶.增强寻优能力的改进人工蜂群算法［J］.数据采集与处理，2013，28(6):761－767.