人工蜂群優化非魯棒路徑時滯故障測試生成算法

趙 瑩，孟 祥，李艷娟，王一帆，趙彥超

(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.