基于人工蜂群算法的数字电路多故障测试生成算法

赵 莹，马占辉，李艳娟

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

·新技术新设备·

基于人工蜂群算法的数字电路多故障测试生成算法

赵 莹1，马占辉1，李艳娟2

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

针对数字电路多固定故障测试生成故障覆盖率低和平均测试生成时间长的问题，提出了人工蜂群和神经网络优化的数字电路多固定故障测试生成算法。该算法首先通过等效的方法得到多固定故障的单固定故障模型，再使用Hopfield二值神经网络的方法得到单固定故障的约束电路模型，最后使用人工蜂群优化方法求解故障约束电路接口电路的能量函数的零值点获得原电路的多固定故障的测试生成矢量。实验结果(在ISCAS’85国际标准测试电路上)表明该算法的故障覆盖率可达98.5%以上，平均测试生成时间小于0.25μs。

神经网络；人工蜂群算法；约束电路；能量函数

0 前言

飞速发展的微电子技术使数字集成电路的集成度和复杂性越来越高，这就使数字电路故障诊断的一个重要环节 数字电路故障的测试生成愈发困难。近些年，国内外众多学者对此进行了大量的研究，取得了很多成果，但这些研究成果仍然存在着测试时间长，故障覆盖率低等问题，而且多数的研究模型为单固定故障模型，对多固定故障模型的研究非常少。Javier Ferrer等人提出了功能测试中测试序列生成的多故障搜索算法[1]，该算法平均故障覆盖率能够到达97%，但平均测试生成时间为0.5μs；Stelios Neophytou等人提出了多元化故障分解的多故障测试生成算法[2]，平均测试生成时间较短，但故障覆盖率只能达到95%，而且随着电路复杂度的提高，存在迭代次数大的问题。由于多固定故障广泛存在于数字电路中，因此对多固定故障测试生成进行研究具有重要的意义。本文使用等效的方法得到多固定故障的单固定故障模型，通过对单固定故障模型应用Hopfield二值神经网络和人工蜂群算法的方法获得原电路的多固定故障测试生成矢量。实验结果表明该算法能够快速地得到多固定故障的测试生成矢量，与其它文献相比，测试生成效率得到明显提高。

1 多固定故障与单固定故障的等效转换

在把多固定故障转换成为等效的单固定故障过程中，需要插入两种门电路，一种称为线上门，另一种称为多输入故障门。在图1a所示电路中，V1,V2,V3,V4为输入，V5,V6,V7,V8为输出。该电路存在一组多固定故障，V1,V3线路上存在固定0(s-a-0)故障，V2,V4线路上存在固定1(s-a-1)故障。外加两种门电路分别为：

线上门。线上门是一个二输入的门电路，插入在每一条故障线路上，固定1故障插入或门，固定0故障插入与门，插入的线上门的一个输入端是故障线路的输入端，原电路故障线路的输出就是线上门的输出。

多输入故障门。插入的多输入故障门是与门，其输入端个数是多故障的个数。多输入故障门输入端的连接方式与故障类型有关，如果故障线上存在s-a-1故障，故障线直接连接到多输入故障门的输入端，如果故障线上存在的是s-a-0故障，则故障线通过一个非门连接到多输入故障门的输入端。多输入故障门输出端的连接方式与线上门类型有关，如果线上门是或门，故障门的输出直接与线上门相连，如果线上门是与门，那么故障门通过一个非门与线上门相连。转换后的多输入故障门的输出端的单固定故障与原电路的多固定故障等价[2]。例如，图1b中f处的s-a-1故障与图1a中的多固定故障等价。

图1 多固定故障与单固定故障等效转换Fig.1 The equivalent transformation of multiple and single stuck-at fault

下面证明该方法的正确性。

两个电路功能的等价

对图1b,根据电路可得：

上面的表达式与图1a的功能完全相同。

两个电路故障的等价

对图1a存在的多固定故障，可以得出：

V5=0；V6=1；V7=0；V8=1

对图1b等价的单固定故障，可以得出：

V5=0·V1=0；V6=1+V2=1

V7=0·V3=0;V8=1+V4=1

由此可见，转换后的单固定故障与原电路的多固定故障等价。

2 单固定故障测试生成的神经网络模型

本文使用Hopfield二值神经网络建立等效电路单固定故障的模型[3-4]，Hopfield二值神经网络模型的能量函数表示为如下：

(1)

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

表1 常用基本门电路的Hopfield神经网络能量函数

数字电路由基本门电路组成，因此可以通过合并神经元，并把神经元的状态值和连接权值相加的方法得到数字电路的神经网络模型，并得到其对应的能量函数。可以证明，各基本门电路能量函数之和即为数字电路对应神经网络模型的能量函数[5-6]。例如，图2是一个简单的数字电路，可以分别得到或门和与门的神经网络模型，见图3a、b、c，按上述方法可以得到图2数字电路的神经网络模型如图2d所示，最终得到该数字电路神经网络模型的能量函数为

E=-4V4(V1+V2)-4V5(V2+V4)-4V6

(V3+V5)+2V1V2+2V2V4+2V3V5+

2V1+2V2+2V4+6V5+6V6

(2)

图2 一个简单数字电路Fig.2 A simple digital circuit

图3 图2电路的Hopfield神经网络模型Fig.3 Hopfield neural network model of Fig.2

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

图4 单输出电路的约束电路Fig.4 Constraint circuit of single-output circuit

图5 多输出电路的约束电路Fig.5 Constraint circuit of multiple-output circuit

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

3 算法的实现

3.1 简化约束电路能量函数

从前面分析可知，求解单固定故障的测试矢量可以通过计算约束电路的能量函数的最小值点(也是零点)得到，但是约束电路的能量函数通常比较复杂，尤其是复杂的数字电路。所以简化约束电路能量函数非常有必要[11-14]。对图4所示的单输出电路的约束电路，无故障电路与故障电路输出肯定相异，因此接口电路(即非门)肯定处于相容状态，所以可以通过求解接口电路能量函数的最小值点的方法得到单固定故障的测试矢量。

按照表1非门的能量函数，可以得到单输出电路约束电路的能量函数为:

E=4V(i)V(j)-2V(i)-2V(j)+2

(3)

其中V(i) 和V(j)分别为无故障电路和故障电路的输出。

例如如果图2所示电路在V5处存在s-a-1故障，则该电路的约束电路如图6所示。

图6 图2电路的约束电路Fig.6 Constraint circuit of fig.2

图6电路的接口电路是一个非门，则该接口电路的能量函数为

(4)

多输出电路约束电路的简化能量函数也是只写出接口电路的能量函数即可。

3.2 人工蜂群算法求解能量函数的零点

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

[xi+1]=[xi]+{[xi]-[xi-1]}δi+[Ii]

(5)

其中δ为[-1,0,1]中的一个随机数，[Ii]为修正矩阵，其内部数字也为[-1,0,1]中的一个随机数。

首先随机取一个食物源，再根据式(5)得到新的食物源，代入能量函数E(x)，使E(x)为0时的[xi]即为给定单固定故障的一个测试矢量，否则继续搜索。当所有的引领蜂搜索完毕后，会通过跳摇摆舞的方式把信息传递给跟随蜂，跟随蜂采用轮盘赌规则选择食物源，保留能量函数值小的食物源。

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

[xi+1]=[xi]+rand(0,1)[xi-1]

(6)

具体算法的流程图如图7所示。

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

下面举例说明。如果某一电路的多固定故障与图2中V5处的s-a-1故障等价，下面就用本文算法求解V5处的s-a-1故障的测试矢量。

则根据式(5)

[x2]=[x1]+{[x1]-[x0]}δ1+[I1]=

[x3]=[x2]+{[x2]-[x1]}δ2+[I2]=

4 实验结果

ISCAS’85电路集是为电路测试生成算法提供的国际标准电路集合，算法的优劣通常要在这些电路上测试，ISCAS’85电路集中的C17电路如图8所示，该电路有5个输入端，2个输出端，由6个与非门构成。根据本文算法，用C++语言编程，在C17电路上的实验结果如图9所示。本文算法在C432和C499上的部分实验结果如表2和表3所示。本文算法与其它文献算法比较的实验结果如表4所示，由结果可知，本文算法在故障覆盖率明显提高的情况下，故障平均测试时间明显缩短，说明本文算法较其它文献算法优越。

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

图9 C17电路实验结果

多故障(故障点/故障类型)测试生成时间/μs测试矢量1/1,2/1,5/0,12/0,20/1,32/0,45/1,80/05/0,8/1,9/0,10/0,25/0,30/1,55/0,90/0,105/0,121/12/1,3/0,6/1,14/0,26/0,42/1,49/1,180/0,251/1,316/010/1,21/0,50/0,62/0,75/1,82/0,95/1,108/0,288/0,313/17/1,10/1,15/0,32/0,40/1,92/0,105/1,180/0,188/0,213/1,310/00.2010.2210.2240.2010.25100111010110100011101111000011101001111011011010100011101010100110100001001000101101010111010110010111010010101110110101010100011110100101011111101010100101011001011001100101010000

表3 C499实验结果

表4 不同算法测试实验结果

5 结论

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

[1] Javier Ferrer, Peter M. Kruse.Search based algorithms for test sequence generation in functional Testing[J]. Information and Software Technology,2014,7(14):4-10.

[2] Stelios Neophytou, Maria K. Michael.Multiple detection test generation with diversified fault partitioning paths[J]. Microprocessors and Microsystems,2014,38(4):585-590.

[3] 韦翠荣，颜学龙，尚玉玲.边界扫描测试生成与故障诊断的研究与实现[J]. 计算机工程，2015,41(1):303-306.

[4] YONG Chang Kim,V.D.Agrawal.Multiple faults:modeling,simulation and test[C]. Proc.of 15th International Conference on VLSI Design,2012:55-58.

[5] Nachiketa Das, Pranab Roy, Hafizur Rahaman.Bridging fault detection in cluster based FPGA by using Muller C element[J]. Computers and Electrical Engineering,2013,28(9): 2469-2482.

[6] 李鹏，颜学龙，孙元.基于多配置的LFSR的测试生成结构设计[J].计算机工程与科学，2014,36(5):43-48.

[7] I. Voyiatzis, C. Efstathiou.An effective two-pattern test generator for Arithmetic BIST[J]. Computers and Electrical Engineering,2013,39(10):398-409.

[8] 罗汉青，梁利平，叶甜春.基于遗传算法的随机测试生成技术探讨[J].电子测试，2013,45(13):75-78

[9] Reza Nourmandi-Pour a,n, NafisehMousavian .A fully parallel BIST-based method to test the crosstalk defects on the inter-switch links in NOC[J]. Microelectronics Journal,2013,35(1):248-257.

[10]Jiri Balcarek, Petr Fiser, Jan Schmidt. Techniques for SAT-based constrained test pattern generation[J]. Microprocessors and Microsystems.2012,9(10):185-189.

[11]吴丽华，王旭东.遗传优化三值神经网络多故障测试生成算法[J].仪器仪表学报，2010,31(8):1744-1749.

[12]AhmedS.Ghiduk. Automatic generation of basis test paths Using variable length genetic algorithm[J]. Information Processing Letters，2014,28(1):304-308.

[13]赵显琼 ， 郑 伟， 唐 涛. 一种基于模型的形式化测试序列自动生成方法及在ETCS一2中的应用[J]. 铁道学报，2012,34(5):70-72.

[14]Ayub Chin Abdullah, Chia Yee Ooi. Study on Test compaction in high-Level automatic test pattern generation (ATPG) platform[J]. Circuits and Systems，2013,31(4):342-349.

[15]Soma Sekhara Babu Lam. Automated generation of independent paths and test suite optimization using artificial bee colony[J]. International Conference on Communication Technology and System Design, 2012,53(1):192-196.

[16]易正俊，韩晓晶.增强寻优能力的改进人工蜂群算法[J].数据采集与处理，2013(6).

A multiple faults test generation algorithm for digital circuits based on artificial bee colony algorithm

ZHAO Ying1, MA Zhan-hui1, LI Yan-juan2

(1. Electrical & information Engineering College, Beihua University，Jilin 132021, China；2. College of Information and Computer Engineering, Northeast Forestry University, Harbin 150040, China)

A multiple stuck-at faults test generation algorithm based on artificial bee colony and neural networks for circuits is proposed in this paper, because the test generation faults coverage is low and the average test generation time is long for multiple stuck-at faults in digital circuits. The algorithm obtains single stuck-at fault model of multiple stuck-at faults by the method of equivalent firstly, and constructs the constraint circuit model of the single stuck-at fault circuit using Hopfield neural networks. The test vectors for multiple stuck-at faults in the original circuit can be obtained by solving the zero value of energy function of the constraint network’s interface circuit with artificial bee colony optimization. The experimental results(ISCAS’85 international standard test circuits) show the faults coverage of the algorithm is above 98.5% and the average test generation time is less than 0.25 μs.

neural networks; artificial bee colony; constraint circuit; energy function

2015-10-15；

2015-12-07

国家自然科学基金(61300098)；吉林市科技局资助项目(201414006)

赵莹(1976-)，女，北华大学电气信息工程学院副教授，主要从事数字集成电路测试及可测性设计研究。

马占辉(1973-)，男，北华大学实验师，主要研究方向为智能仪器仪表开发与设计。

TN407

A

1001-196X(2016)03-0006-07