一種變異真值表故障模型的神經(jīng)網(wǎng)絡(luò)測試生成算法

戴金玲，許愛強(qiáng)

（1.海軍航空工程學(xué)院 研究生二隊，山東 煙臺 264001；2.海軍航空工程學(xué)院 科研部，山東 煙臺 264001）

一種變異真值表故障模型的神經(jīng)網(wǎng)絡(luò)測試生成算法

戴金玲1，許愛強(qiáng)2

（1.海軍航空工程學(xué)院 研究生二隊，山東 煙臺 264001；2.海軍航空工程學(xué)院 科研部，山東 煙臺 264001）

針對傳統(tǒng)測試生成算法計算復(fù)雜度高的問題，提出一種針對邏輯門功能異常的故障模型，并給出了基于遺傳優(yōu)化的神經(jīng)網(wǎng)絡(luò)測試生成算法。首先，與傳統(tǒng)算法以固定值故障為目標(biāo)不同，構(gòu)建更全面的變異真值表故障模型，在考慮各輸入條件下故障的不同權(quán)重的同時，按故障模型自動生成故障字典；然后，測試生成算法利用邏輯門的二值神經(jīng)網(wǎng)絡(luò)能量函數(shù)，構(gòu)成數(shù)字電路的約束網(wǎng)絡(luò)；最終，調(diào)用故障字典向約束網(wǎng)絡(luò)注入故障，通過遺傳算法求解出被測電路的測試集。仿真實驗結(jié)果顯示，所提的故障模型更加全面，且測試生成算法具有正確性和有效性。

變異真值表故障模型；神經(jīng)網(wǎng)絡(luò)；遺傳算法；測試生成

Abstract:In order to solve the problem of the high complexity of the conditional test generation methods，a new fault model based on functional fails and neural network test generation algorithmare proposed.At first，different from conditional methods based on stuck-at fault model， a mutated truth table fault model is built considering the weights of faults under different inputs.The fault dictionary is automatically formed by fault model.Secondly，the constraint network is constructed with energy function of two-valued neural network.Lastly，faults are injected into the constraint network referring to the fault model，and the testing sets are get by genetic Algorithm.The experimental results show that the fault model and the test generation method are effective.

Key words:mutated truth table fault model； neural networks； genetic algorithm； test generation

傳統(tǒng)的組合電路測試生成算法是一種確定性的生成方法，即分析被測電路（Circuit under test，CUT）的門級描述，以推導(dǎo)出目標(biāo)故障的測試向量，或證明其是不可測的，主要有D算法，PODEM（Path-orientated decision making，PODEM）算法[1]，F(xiàn)AN（Fujiwara and Shimono）算法[2]等。隨著數(shù)字集成電路越來越復(fù)雜，傳統(tǒng)的測試生成方法因其高計算復(fù)雜度已經(jīng)不再適用，建立真實的故障模型、研究新型有效的測試生成算法具有十分重要的理論價值和實際意義。近年來，神經(jīng)網(wǎng)絡(luò)在許多領(lǐng)域的應(yīng)用[3-7]都取得了成功，許多學(xué)者提出利用神經(jīng)網(wǎng)絡(luò)模型和遺傳算法來解決測試生成問題。文獻(xiàn)[8]將組合電路的多故障測試生成問題轉(zhuǎn)化為單故障測試生成問題，通過建立被測電路的二值神經(jīng)網(wǎng)絡(luò)約束網(wǎng)絡(luò)和遺傳算法，求解能量函數(shù)的最小值點(diǎn)，有效地得到多故障電路的測試矢量；文獻(xiàn)[9]成功將三值神經(jīng)網(wǎng)絡(luò)和遺傳算法結(jié)合起來應(yīng)用到數(shù)字電路的多故障測試生成中，與二值神經(jīng)網(wǎng)絡(luò)算法相比，明顯減少了測試時間；文獻(xiàn)[10]針對遺傳算法存在的搜索空間大、時間長的不足，提出一種電路分塊方法，優(yōu)化了遺傳算法在測試生成中的應(yīng)用。已有神經(jīng)網(wǎng)絡(luò)的應(yīng)用，都是建立在固定值故障模型（Stuck-At Fault model， SAF）基礎(chǔ)之上的。然而，有文獻(xiàn)[11]指出，僅用固定值故障模型代表數(shù)字電路中的所有故障是不充分的。因此有必要建立更真實有效的故障模型，并通過神經(jīng)網(wǎng)絡(luò)和遺傳算法進(jìn)行測試生成。

文中提出的組合電路測試生成系統(tǒng)首先基于CUT所有基本邏輯門類型的真值表，針對各輸入構(gòu)建故障字典；然后，通過邏輯門的二值神經(jīng)網(wǎng)絡(luò)能量函數(shù)表示被測電路，并自動調(diào)用故障字典存儲的故障信息向被測電路中注入故障，通過遺傳算法，求得最終的測試集。

1 變異真值表故障模型

故障模型主要研究邏輯門功能異常對其真值表的影響，因此需要對邏輯門功能失效時真值表的變化進(jìn)行分析。對于任意的邏輯門類型G，正常狀態(tài)時的真值表為TG，保持真值表中輸入列部分不變，當(dāng)G的內(nèi)部電路中有故障時，若其對應(yīng)的真值表T*G≠TG，則稱T*G為邏輯門類型G的一個變異真值表（Mutated Truth Table，MTT）。MTT與真值表的區(qū)別僅在于輸出列中的常見邏輯值不同。

顯然，G中包含不止一種內(nèi)部故障，考慮能使電路發(fā)生功能異常的硬故障：開路與短路，通過仿真或?qū)嶒炇侄慰傻枚鄠€與這些故障相對應(yīng)的MTT，最終這些MTT的集合即為邏輯門類型G的故障字典。顯然，G中包含不止一種的內(nèi)部故障，因此通常存在多個與這些內(nèi)部故障相對應(yīng)的MTT，它們即構(gòu)成了該邏輯門類型 G 的故障字典， 記為 DG={＜T*G，k，λG，k＞|k=1，2，…，NG}，其中 NG表示 MTT 的數(shù)量；λG，k表示對應(yīng)的MTT等于T*G，k的累計故障計數(shù)。顯然，一個MTT對應(yīng)的內(nèi)部故障數(shù)量越多，它在邏輯門的故障行為空間中出現(xiàn)的概率就越大?？紤]到在實際數(shù)字電路中，不定態(tài)‘X’是不存在的，既可能為‘1’也可能為‘0’，或者在這兩個邏輯值之間隨機(jī)跳變，因此需要對故障字典進(jìn)行整理，將‘X’狀態(tài)按某種概率分配到‘0’和‘1’上，最終建立可被測試生成算法調(diào)用的故障字典。

測試覆蓋率定義為測試集檢測出的故障之和比上所有邏輯門上注入的故障之和，其計算公式為

其中NTS為CUT生成的測試集向量數(shù)，M為CUT的邏輯門數(shù)，F(xiàn)cj為第j個測試向量所檢測到的故障數(shù)量，F(xiàn)ci為第i個邏輯門中注入的故障數(shù)量。

2 測試生成算法

2.1 組合電路的神經(jīng)網(wǎng)絡(luò)模型

二值神經(jīng)網(wǎng)絡(luò)的能量函數(shù)[12]為：

式中:N是神經(jīng)網(wǎng)絡(luò)中神經(jīng)元的數(shù)目；Ii是神經(jīng)元i的閾值；Tij是神經(jīng)元i和j之間的權(quán)值；Vi是神經(jīng)元i的狀態(tài)值；K是常量。

用Hopfield模型中的能量函數(shù)來表示基本門電路的傳輸特性：對符合一種基本門電路功能函數(shù)的取值稱為這種門電路的一個相容狀態(tài)，其他不符合功能函數(shù)的取值稱為門的非相容狀態(tài)。當(dāng)基本邏輯門的輸入輸出值符正確的邏輯關(guān)系時，對一種門電路的一個相容狀態(tài)，能量函數(shù)E=0，否則不為零?；诖四芰亢瘮?shù)，則將測試生成問題轉(zhuǎn)化為數(shù)學(xué)問題，通過式（1）得出基本門電路的而二值神經(jīng)網(wǎng)絡(luò)能量函數(shù)如表4所示，其中第一列為邏輯門的類型，第二列為輸入，第三列為輸出，第四列為邏輯門的神經(jīng)網(wǎng)絡(luò)能量函數(shù)。

表1 基本邏輯門的能量函數(shù)

圖1 單輸出電路的約束網(wǎng)絡(luò)

數(shù)字電路中一個邏輯單元有故障，如果存在電路的一組輸入使電路的輸出在無故障與有故障時相異，則這組輸入就為該故障的一個測試向量。實現(xiàn)神經(jīng)網(wǎng)絡(luò)故障測試，需要構(gòu)建CUT的約束神經(jīng)網(wǎng)絡(luò)能量函數(shù)。約束網(wǎng)絡(luò)由故障電路（已注入故障）、無故障電路和一個接口電路組成。圖1所示為單輸出電路，接口由一個非門組成；圖2所示為多輸出電路，接口由數(shù)量為輸出端口數(shù)的二輸入異或門和一個或門構(gòu)成，并且或門的輸出為‘1’，這樣的限制是為了使約束網(wǎng)絡(luò)的輸入矢量為故障的測試矢量時，CUT的故障輸出與無故障輸出不同。約束網(wǎng)絡(luò)的能量函數(shù)與邏輯門構(gòu)造方法相同。

對于任何一個組合邏輯電路，利用推導(dǎo)出的基本邏輯門電路的二值神經(jīng)網(wǎng)絡(luò)能量函數(shù)，就能獲得相對應(yīng)的組合邏輯電路的二值神經(jīng)網(wǎng)絡(luò)能量函數(shù)。將每一種基本門電路定義為結(jié)構(gòu)類型，根據(jù)基準(zhǔn)電路給出的各基本門電路的輸入輸出關(guān)系，把它們組合起來就構(gòu)成了被測電路的神經(jīng)網(wǎng)絡(luò)模型。

圖2 多輸出電路的約束網(wǎng)絡(luò)

2.2 遺傳算法

根據(jù)電路的約束電路可得，電路中一個故障存在測試矢量的充要條件是：在故障點(diǎn)處取與正常電路相反的值時，約束網(wǎng)絡(luò)處于相容狀態(tài)，即對應(yīng)神經(jīng)網(wǎng)絡(luò)的能量函數(shù)值為0。因此，通過對故障字典中的故障計數(shù)來決定故障注入的排序，對其測試生成，而數(shù)字電路故障的測試生成問題就可以表示為求能量函數(shù)的最小值點(diǎn)問題，實質(zhì)上是將測試生成問題數(shù)學(xué)化。

遺傳算法模仿了生物進(jìn)化論，利用了選擇、復(fù)制、交叉和變異等策略，能夠提供全局并行搜索和魯棒性搜索，并且對連接權(quán)值不敏感[13]，因此本文通過遺傳優(yōu)化算法求能量函數(shù)的最小值以得到故障的測試矢量。設(shè)置種群的規(guī)模為N，當(dāng)前種群中的個體為xi（i=1，2，…，N），個體的編碼和適值函數(shù)的定義為：

其中 E（x）為約束網(wǎng)絡(luò)能量函數(shù)，f（x）的取值在0到1之間，個體 xi的適值 f（x）越大，說明 xi的性能越好，使f（x）的值為1的個體xi就是使能量函數(shù)等于零的個體，即為給定故障的一個測試矢量。

二值神經(jīng)網(wǎng)絡(luò)遺傳算法流程圖如圖3所示：1）設(shè)置初始種群規(guī)模，并隨機(jī)產(chǎn)生初始種群；2）適應(yīng)度值計算：計算適應(yīng)度值最大和最小的值；3）選擇策略：根據(jù)賭盤選擇選出兩個個體；4）交叉、變異：設(shè)置交叉概率和變異概率，對選出的兩個個體進(jìn)行交叉和變異。

圖3 二值神經(jīng)網(wǎng)絡(luò)遺傳算法流程圖

3 仿真實驗與結(jié)果分析

以CMOS （complimentary metal-oxide-semiconductor）工藝的兩輸入與非門為例[14]（見圖 4），假設(shè)其輸入依次為“00”、“01”、“10”、“11”，真值表輸出相應(yīng)為[1，1，1，0]T，則對其進(jìn)行故障注入和分析可得如表 2 所示的故障字典。 其中，TN1、TN2、TP1、TP2分別為邏輯門中的MOS管 （N型或P型），d、g、s分別表示MOS管的漏極、柵極和源極，符號O（open）、S（short）分別表示元器件上的局部開路和短路，全局的節(jié)點(diǎn)橋接則表示為（n1，n2）_S（其中n1和n2表示不屬于同一元器件的兩個節(jié)點(diǎn)）。合計行中給出了注入故障的總數(shù)（此處為27）和不同輸入組合分別覆蓋的故障數(shù)量（此處為[9，18，18，12]T）。

圖4 兩輸入與非門電路圖

表3所示為將不定態(tài)‘X’按等概率進(jìn)行分配得到的結(jié)果，其中第2、3列分別為MTT列表和整理后其對應(yīng)的故障計數(shù)，以表 2中[1，X，1，0]T為例，引起該MTT的故障數(shù)為4，將‘X’等概率分配后，各以2的權(quán)重加到[1，1，1，0]T和[1，0，1，0]T上，而[1，1，1，0]T為該邏輯門的正常輸出，因此不計入MTT中，而將[1，0，1，0]T的故障計數(shù)加 2，以此類推，得到改進(jìn)的兩輸入與非門故障字典，如表3所示。

表2 兩輸入與非門故障字典

表3 改進(jìn)的兩輸入與非門故障字典

表4 改進(jìn)的邏輯門故障字典

由表3可見：1）向邏輯門電路中注入硬故障均會引起功能異常，而功能異常的具體形式與故障發(fā)生的位置有關(guān)；2）固定1故障出現(xiàn)的次數(shù)最多，高于其他任何一種故障類型，可見，固定值故障的確是一種重要的故障模式；另一方面，非固定值故障的比重之和高達(dá)70.4%，由此可見，經(jīng)典的固定值故障模型并不能代表數(shù)字電路中的真實故障情況。

根據(jù)改進(jìn)的故障字典的內(nèi)容，最終可建立如表4所示的用于測試生成過程調(diào)用的故障字典，內(nèi)容為邏輯門的所有輸入組合下的故障計數(shù)，其中單輸入邏輯門（如 Inv）依次有‘0’、‘1’兩種輸入，兩輸入邏輯門依次考慮“00”、“01”、“10”和“11”4 種輸入組合。測試生成調(diào)用字典的過程是將故障數(shù)權(quán)重較大的輸入作為優(yōu)先注入的對象，并盡可能覆蓋邏輯門的所有輸入組合。按照本文測試生成算法的描述，對國際基準(zhǔn)電路進(jìn)行了測試生成 （仿真實驗在3 GHz CPU、4 GB RAM的計算機(jī)上執(zhí)行），并驗證了測試覆蓋率，設(shè)置種群大小為25，迭代次數(shù)為50，變異概率0.01，交叉概率為0.25。實驗結(jié)果如表5所示，其中第1列為被測電路名稱，第2、4列分別為本文與參考文獻(xiàn)[7]中的測試生成時間，第3、5列分別為本文與參考文獻(xiàn)[7]中生成測試集的故障覆蓋率。

由表5可見：1）文中提出的算法有較高的效率與故障覆蓋率；2）傳統(tǒng)的固定值故障模型下，文獻(xiàn)[7]得到的故障覆蓋率均為100%，其結(jié)果過于樂觀；而變異真值表故障模型更能體現(xiàn)真實的故障覆蓋情況。

4 結(jié) 論

本文首先從電路的內(nèi)部故障出發(fā)，根據(jù)邏輯門不同的外部功能異常表現(xiàn)，構(gòu)建了更全面的變異真值表故障模型，并考慮了各輸入條件下故障的不同權(quán)重，按故障模型自動生成故障字典?；谶壿嬮T的二值神經(jīng)網(wǎng)絡(luò)能量函數(shù)所構(gòu)成的約束網(wǎng)絡(luò)，調(diào)用故障字典向約束網(wǎng)絡(luò)注入故障，通過遺傳算法求解出被測電路的測試集。仿真實驗結(jié)果顯示，本文建立的故障模型更加全面和真實，測試生成算法具有較高的故障覆蓋率和較短的測試時間。

[1]KAI Y,KWANG T C,LI C W.TranGen:A SAT_Based ATPG for Path-Oriented Transition Faults[C]//Proceedings of Asia and south pacific design automation conference，2004:92-97.

[2]楊士元.數(shù)字系統(tǒng)的故障診斷與可靠性 [M].北京：清華大學(xué)出版社，2000.

[3]潘中良，陳翎.基于神經(jīng)網(wǎng)絡(luò)的電路多故障測試及并行實現(xiàn) [J].儀器儀表學(xué)報，2002，23 （6）:680-681.

[4]韓之剛，高蘭芝，宮海燕，等.基于三值神經(jīng)網(wǎng)絡(luò)數(shù)字電路多故障測試生成算法 [J].煤礦機(jī)械，2008，29（1）:205-208.

[5]徐紅兵，李焱駿，王厚軍.一種基于混沌神經(jīng)網(wǎng)絡(luò)的自動測試生成算法[J].儀器儀表學(xué)報，2002，23（5）:77-79.

[6]薛維琴，李莉華，戴明.基于FPGA的人工神經(jīng)網(wǎng)絡(luò)系統(tǒng)的實現(xiàn)方法[J].電子設(shè)計工程，2010，18（9）:151-154.

[7]張宇翔，黃力宇.Hopfield網(wǎng)絡(luò)求解TSP兩種改進(jìn)算法的仿真研究[J].電子設(shè)計工程，2009，17（10）:119-121.

[8]楊興，謝志遠(yuǎn)，馮力娜.神經(jīng)網(wǎng)絡(luò)在組合電路多故障測試生成算法中的應(yīng)用 [J].電力科學(xué)與工程，2009，25（3）:37-41.

[9]吳麗華，王旭東，史芳芳，等.遺傳優(yōu)化三值神經(jīng)網(wǎng)絡(luò)多故障測試生成算法 [J].儀器儀表學(xué)報，2010，31（8）:1744-1749.

[10]許杰，涂小輝.基于改進(jìn)遺傳算法的組合電路測試生成[J].實驗室研究與探索， 2012，31（7）:76-78.

[11]TANG X F， XU A Q， LI W H， et al.Fault Models of CMOS Gates:An empirical study based on mutation analysis[C]//Proceedings of IEEE International Conference on Software Engineering and Service Sciences.Beijing:IEEE，2014:916-920.

[12]趙瑩，吳麗華，王軫.基于神經(jīng)網(wǎng)絡(luò)的數(shù)字電路多故障測試生成算法 [J].電機(jī)控制與學(xué)報，2006，10（5）:478-481.

[13]李鳴，彭大海，高娜，等.基于混沌和遺傳算法的優(yōu)化測試生成算法 [J].微計算機(jī)信息，2005，21（8）:125-127.

[14]康華光，皺壽彬，秦臻，等.電子技術(shù)基礎(chǔ)[M].北京:高等教育出版社，2006.

Testing generation algorithm based on neural networks for mutated truth table fault model

DAI Jin-ling1，XU Ai-qiang2
（1.Graduate Student Team Two， Naval Aeronautical and Astronautical University，Yantai264001，China； 2.Department of Scientific Research，Naval Aeronautical and Astronautical University，Yantai264001，China）

TP407；TP301.6

A

1674－6236（2017）19-0174-05

2016-08-24稿件編號201608175

戴金玲（1991—），女，江蘇溧陽人，碩士研究生。研究方向：電子信息系統(tǒng)測試與診斷技術(shù)。