基于人工蜂群算法的數(shù)字電路多故障測(cè)試生成算法

趙 瑩，馬占輝，李艷娟

(1.北華大學(xué) 電氣信息工程學(xué)院，吉林 吉林 132021； 2．東北林業(yè)大學(xué) 信息與計(jì)算機(jī)學(xué)院， 黑龍江 哈爾濱 150040)

·新技術(shù)新設(shè)備·

基于人工蜂群算法的數(shù)字電路多故障測(cè)試生成算法

趙 瑩1，馬占輝1，李艷娟2

(1.北華大學(xué) 電氣信息工程學(xué)院，吉林 吉林 132021； 2．東北林業(yè)大學(xué) 信息與計(jì)算機(jī)學(xué)院， 黑龍江 哈爾濱 150040)

針對(duì)數(shù)字電路多固定故障測(cè)試生成故障覆蓋率低和平均測(cè)試生成時(shí)間長(zhǎng)的問(wèn)題，提出了人工蜂群和神經(jīng)網(wǎng)絡(luò)優(yōu)化的數(shù)字電路多固定故障測(cè)試生成算法。該算法首先通過(guò)等效的方法得到多固定故障的單固定故障模型，再使用Hopfield二值神經(jīng)網(wǎng)絡(luò)的方法得到單固定故障的約束電路模型，最后使用人工蜂群優(yōu)化方法求解故障約束電路接口電路的能量函數(shù)的零值點(diǎn)獲得原電路的多固定故障的測(cè)試生成矢量。實(shí)驗(yàn)結(jié)果(在ISCAS’85國(guó)際標(biāo)準(zhǔn)測(cè)試電路上)表明該算法的故障覆蓋率可達(dá)98.5%以上，平均測(cè)試生成時(shí)間小于0.25μs。

神經(jīng)網(wǎng)絡(luò)；人工蜂群算法；約束電路；能量函數(shù)

0 前言

飛速發(fā)展的微電子技術(shù)使數(shù)字集成電路的集成度和復(fù)雜性越來(lái)越高，這就使數(shù)字電路故障診斷的一個(gè)重要環(huán)節(jié) 數(shù)字電路故障的測(cè)試生成愈發(fā)困難。近些年，國(guó)內(nèi)外眾多學(xué)者對(duì)此進(jìn)行了大量的研究，取得了很多成果，但這些研究成果仍然存在著測(cè)試時(shí)間長(zhǎng)，故障覆蓋率低等問(wèn)題，而且多數(shù)的研究模型為單固定故障模型，對(duì)多固定故障模型的研究非常少。Javier Ferrer等人提出了功能測(cè)試中測(cè)試序列生成的多故障搜索算法[1]，該算法平均故障覆蓋率能夠到達(dá)97%，但平均測(cè)試生成時(shí)間為0.5μs；Stelios Neophytou等人提出了多元化故障分解的多故障測(cè)試生成算法[2]，平均測(cè)試生成時(shí)間較短，但故障覆蓋率只能達(dá)到95%，而且隨著電路復(fù)雜度的提高，存在迭代次數(shù)大的問(wèn)題。由于多固定故障廣泛存在于數(shù)字電路中，因此對(duì)多固定故障測(cè)試生成進(jìn)行研究具有重要的意義。本文使用等效的方法得到多固定故障的單固定故障模型，通過(guò)對(duì)單固定故障模型應(yīng)用Hopfield二值神經(jīng)網(wǎng)絡(luò)和人工蜂群算法的方法獲得原電路的多固定故障測(cè)試生成矢量。實(shí)驗(yàn)結(jié)果表明該算法能夠快速地得到多固定故障的測(cè)試生成矢量，與其它文獻(xiàn)相比，測(cè)試生成效率得到明顯提高。

1 多固定故障與單固定故障的等效轉(zhuǎn)換

在把多固定故障轉(zhuǎn)換成為等效的單固定故障過(guò)程中，需要插入兩種門電路，一種稱為線上門，另一種稱為多輸入故障門。在圖1a所示電路中，V1,V2,V3,V4為輸入，V5,V6,V7,V8為輸出。該電路存在一組多固定故障，V1,V3線路上存在固定0(s-a-0)故障，V2,V4線路上存在固定1(s-a-1)故障。外加兩種門電路分別為：

線上門。線上門是一個(gè)二輸入的門電路，插入在每一條故障線路上，固定1故障插入或門，固定0故障插入與門，插入的線上門的一個(gè)輸入端是故障線路的輸入端，原電路故障線路的輸出就是線上門的輸出。

多輸入故障門。插入的多輸入故障門是與門，其輸入端個(gè)數(shù)是多故障的個(gè)數(shù)。多輸入故障門輸入端的連接方式與故障類型有關(guān)，如果故障線上存在s-a-1故障，故障線直接連接到多輸入故障門的輸入端，如果故障線上存在的是s-a-0故障，則故障線通過(guò)一個(gè)非門連接到多輸入故障門的輸入端。多輸入故障門輸出端的連接方式與線上門類型有關(guān)，如果線上門是或門，故障門的輸出直接與線上門相連，如果線上門是與門，那么故障門通過(guò)一個(gè)非門與線上門相連。轉(zhuǎn)換后的多輸入故障門的輸出端的單固定故障與原電路的多固定故障等價(jià)[2]。例如，圖1b中f處的s-a-1故障與圖1a中的多固定故障等價(jià)。

圖1 多固定故障與單固定故障等效轉(zhuǎn)換Fig.1 The equivalent transformation of multiple and single stuck-at fault

下面證明該方法的正確性。

兩個(gè)電路功能的等價(jià)

對(duì)圖1b,根據(jù)電路可得：

上面的表達(dá)式與圖1a的功能完全相同。

兩個(gè)電路故障的等價(jià)

對(duì)圖1a存在的多固定故障，可以得出：

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

對(duì)圖1b等價(jià)的單固定故障，可以得出：

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

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

由此可見(jiàn)，轉(zhuǎn)換后的單固定故障與原電路的多固定故障等價(jià)。

2 單固定故障測(cè)試生成的神經(jīng)網(wǎng)絡(luò)模型

本文使用Hopfield二值神經(jīng)網(wǎng)絡(luò)建立等效電路單固定故障的模型[3-4]，Hopfield二值神經(jīng)網(wǎng)絡(luò)模型的能量函數(shù)表示為如下：

(1)

其中Vi和Vj是神經(jīng)元i和j的狀態(tài)值(0或1)，神經(jīng)元的數(shù)目是N，神經(jīng)元i的內(nèi)部參數(shù)是Ii,即閾值，神經(jīng)元i和j之間的權(quán)值是Tij，K是常數(shù)，保證能量函數(shù)為非負(fù)值。表1為常用的基本門電路的Hopfield神經(jīng)網(wǎng)絡(luò)能量函數(shù)。

表1 常用基本門電路的Hopfield神經(jīng)網(wǎng)絡(luò)能量函數(shù)

數(shù)字電路由基本門電路組成，因此可以通過(guò)合并神經(jīng)元，并把神經(jīng)元的狀態(tài)值和連接權(quán)值相加的方法得到數(shù)字電路的神經(jīng)網(wǎng)絡(luò)模型，并得到其對(duì)應(yīng)的能量函數(shù)?？梢宰C明，各基本門電路能量函數(shù)之和即為數(shù)字電路對(duì)應(yīng)神經(jīng)網(wǎng)絡(luò)模型的能量函數(shù)[5-6]。例如，圖2是一個(gè)簡(jiǎn)單的數(shù)字電路，可以分別得到或門和與門的神經(jīng)網(wǎng)絡(luò)模型，見(jiàn)圖3a、b、c，按上述方法可以得到圖2數(shù)字電路的神經(jīng)網(wǎng)絡(luò)模型如圖2d所示，最終得到該數(shù)字電路神經(jīng)網(wǎng)絡(luò)模型的能量函數(shù)為

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

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

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

(2)

圖2 一個(gè)簡(jiǎn)單數(shù)字電路Fig.2 A simple digital circuit

圖3 圖2電路的Hopfield神經(jīng)網(wǎng)絡(luò)模型Fig.3 Hopfield neural network model of Fig.2

對(duì)數(shù)字電路相容狀態(tài)(符合數(shù)字電路邏輯功能)，神經(jīng)網(wǎng)絡(luò)能量函數(shù)的值為0，否則大于0[7-8]。為了得到符合相容狀態(tài)的電路，需要構(gòu)建待測(cè)電路的約束電路，單輸出和多輸出電路的約束電路如圖4和圖5所示[9-10]。當(dāng)輸入某個(gè)測(cè)試矢量時(shí)，無(wú)故障電路和有故障電路的輸出肯定相異，所以約束電路處于相容狀態(tài)。

圖4 單輸出電路的約束電路Fig.4 Constraint circuit of single-output circuit

圖5 多輸出電路的約束電路Fig.5 Constraint circuit of multiple-output circuit

這樣通過(guò)計(jì)算約束電路對(duì)應(yīng)能量函數(shù)的零點(diǎn)就可得到單固定故障的測(cè)試矢量。

3 算法的實(shí)現(xiàn)

3.1 簡(jiǎn)化約束電路能量函數(shù)

從前面分析可知，求解單固定故障的測(cè)試矢量可以通過(guò)計(jì)算約束電路的能量函數(shù)的最小值點(diǎn)(也是零點(diǎn))得到，但是約束電路的能量函數(shù)通常比較復(fù)雜，尤其是復(fù)雜的數(shù)字電路。所以簡(jiǎn)化約束電路能量函數(shù)非常有必要[11-14]。對(duì)圖4所示的單輸出電路的約束電路，無(wú)故障電路與故障電路輸出肯定相異，因此接口電路(即非門)肯定處于相容狀態(tài)，所以可以通過(guò)求解接口電路能量函數(shù)的最小值點(diǎn)的方法得到單固定故障的測(cè)試矢量。

按照表1非門的能量函數(shù)，可以得到單輸出電路約束電路的能量函數(shù)為:

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

(3)

其中V(i) 和V(j)分別為無(wú)故障電路和故障電路的輸出。

例如如果圖2所示電路在V5處存在s-a-1故障，則該電路的約束電路如圖6所示。

圖6 圖2電路的約束電路Fig.6 Constraint circuit of fig.2

圖6電路的接口電路是一個(gè)非門，則該接口電路的能量函數(shù)為

(4)

多輸出電路約束電路的簡(jiǎn)化能量函數(shù)也是只寫(xiě)出接口電路的能量函數(shù)即可。

3.2 人工蜂群算法求解能量函數(shù)的零點(diǎn)

人工蜂群算法[15]由土耳其學(xué)者karaboga在2005年提出，是一種模擬蜜蜂找尋最優(yōu)食物源的優(yōu)化仿生算法，這個(gè)算法在每次迭代過(guò)程中都進(jìn)行全局和局部搜索，因此能夠減小進(jìn)入局部最優(yōu)解的概率。在應(yīng)用人工蜂群算法求解優(yōu)化問(wèn)題時(shí)，食物源的位置被抽象為最優(yōu)解，待優(yōu)化問(wèn)題的適應(yīng)度函數(shù)值決定了食物源的優(yōu)劣程度。人工蜂群主要包括引領(lǐng)蜂、跟隨蜂和偵查蜂。本文適應(yīng)度函數(shù)取待測(cè)電路約束電路接口電路的能量函數(shù)E(x)。假設(shè)該算法有N個(gè)初始種群[xi](i=1,2,….,N), [xi]含有m個(gè)量(m為電路輸入端的個(gè)數(shù))，每個(gè)量的取值為0或1。引領(lǐng)蜂首先隨機(jī)對(duì)某個(gè)食物源進(jìn)行鄰域搜索，并按式(5)對(duì)食物源位置進(jìn)行更新[15]：

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

(5)

其中δ為[-1,0,1]中的一個(gè)隨機(jī)數(shù)，[Ii]為修正矩陣，其內(nèi)部數(shù)字也為[-1,0,1]中的一個(gè)隨機(jī)數(shù)。

首先隨機(jī)取一個(gè)食物源，再根據(jù)式(5)得到新的食物源，代入能量函數(shù)E(x)，使E(x)為0時(shí)的[xi]即為給定單固定故障的一個(gè)測(cè)試矢量，否則繼續(xù)搜索。當(dāng)所有的引領(lǐng)蜂搜索完畢后，會(huì)通過(guò)跳搖擺舞的方式把信息傳遞給跟隨蜂，跟隨蜂采用輪盤賭規(guī)則選擇食物源，保留能量函數(shù)值小的食物源。

在該算法中，設(shè)置搜尋控制參數(shù)為L(zhǎng)，它表示食物源未被更新的上限值。如果某個(gè)食物源經(jīng)過(guò)L次搜索后仍未得到改善，說(shuō)明該食物源進(jìn)入了局部最優(yōu)解，那么這個(gè)食物源應(yīng)該被放棄，相應(yīng)的引領(lǐng)蜂變?yōu)閭刹榉?，這時(shí)要按公式(6)隨機(jī)產(chǎn)生一個(gè)新的食物源位置替代原有的食物源[16]。

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

(6)

具體算法的流程圖如圖7所示。

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

下面舉例說(shuō)明。如果某一電路的多固定故障與圖2中V5處的s-a-1故障等價(jià)，下面就用本文算法求解V5處的s-a-1故障的測(cè)試矢量。

則根據(jù)式(5)

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

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

4 實(shí)驗(yàn)結(jié)果

ISCAS’85電路集是為電路測(cè)試生成算法提供的國(guó)際標(biāo)準(zhǔn)電路集合，算法的優(yōu)劣通常要在這些電路上測(cè)試，ISCAS’85電路集中的C17電路如圖8所示，該電路有5個(gè)輸入端，2個(gè)輸出端，由6個(gè)與非門構(gòu)成。根據(jù)本文算法，用C++語(yǔ)言編程，在C17電路上的實(shí)驗(yàn)結(jié)果如圖9所示。本文算法在C432和C499上的部分實(shí)驗(yàn)結(jié)果如表2和表3所示。本文算法與其它文獻(xiàn)算法比較的實(shí)驗(yàn)結(jié)果如表4所示，由結(jié)果可知，本文算法在故障覆蓋率明顯提高的情況下，故障平均測(cè)試時(shí)間明顯縮短，說(shuō)明本文算法較其它文獻(xiàn)算法優(yōu)越。

圖8 ISCAS’85中的C17電路Fig.8 Circuit C17 of ISCAS’85

圖9 C17電路實(shí)驗(yàn)結(jié)果

多故障(故障點(diǎn)/故障類型)測(cè)試生成時(shí)間/μs測(cè)試矢量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實(shí)驗(yàn)結(jié)果

表4 不同算法測(cè)試實(shí)驗(yàn)結(jié)果

5 結(jié)論

本文在數(shù)字電路多故障測(cè)試生成中采用了神經(jīng)網(wǎng)絡(luò)和人工蜂群優(yōu)化的方法，充分利用了神經(jīng)網(wǎng)絡(luò)和人工蜂群算法解決優(yōu)化問(wèn)題的優(yōu)越性，避免進(jìn)入局部最優(yōu)解。實(shí)驗(yàn)結(jié)果表明本文提出的算法的故障覆蓋率可達(dá)98.5%以上，平均測(cè)試生成時(shí)間可低于0.25 μs，與其它文獻(xiàn)算法相比具有明顯的優(yōu)越性。但本文算法應(yīng)用于大規(guī)模時(shí)序邏輯電路時(shí)，會(huì)出現(xiàn)迭代次數(shù)大，故障覆蓋率低和測(cè)試生成時(shí)間長(zhǎng)等缺點(diǎn)，因此該算法不適用于大規(guī)模時(shí)序邏輯電路。

[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] 韋翠榮，顏學(xué)龍，尚玉玲.邊界掃描測(cè)試生成與故障診斷的研究與實(shí)現(xiàn)[J]. 計(jì)算機(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] 李鵬，顏學(xué)龍，孫元.基于多配置的LFSR的測(cè)試生成結(jié)構(gòu)設(shè)計(jì)[J].計(jì)算機(jī)工程與科學(xué)，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ī)測(cè)試生成技術(shù)探討[J].電子測(cè)試，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]吳麗華，王旭東.遺傳優(yōu)化三值神經(jīng)網(wǎng)絡(luò)多故障測(cè)試生成算法[J].儀器儀表學(xué)報(bào)，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]趙顯瓊 ， 鄭 偉， 唐 濤. 一種基于模型的形式化測(cè)試序列自動(dòng)生成方法及在ETCS一2中的應(yīng)用[J]. 鐵道學(xué)報(bào)，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]易正俊，韓曉晶.增強(qiáng)尋優(yōu)能力的改進(jìn)人工蜂群算法[J].數(shù)據(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

國(guó)家自然科學(xué)基金(61300098)；吉林市科技局資助項(xiàng)目(201414006)

趙瑩(1976-)，女，北華大學(xué)電氣信息工程學(xué)院副教授，主要從事數(shù)字集成電路測(cè)試及可測(cè)性設(shè)計(jì)研究。

馬占輝(1973-)，男，北華大學(xué)實(shí)驗(yàn)師，主要研究方向?yàn)橹悄軆x器儀表開(kāi)發(fā)與設(shè)計(jì)。

TN407

A

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