基于人工蜂群算法的數字電路多故障測試生成算法

趙 瑩，馬占輝，李艷娟

(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神經網絡能量函數

數字電路由基本門電路組成，因此可以通過合并神經元，并把神經元的狀態值和連接權值相加的方法得到數字電路的神經網絡模型，并得到其對應的能量函數?？梢宰C明，各基本門電路能量函數之和即為數字電路對應神經網絡模型的能量函數[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