一種變異真值表故障模型的神經網絡測試生成算法

戴金玲，許愛強

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

一種變異真值表故障模型的神經網絡測試生成算法

戴金玲1，許愛強2

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

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

變異真值表故障模型；神經網絡；遺傳算法；測試生成

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

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

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

1 變異真值表故障模型

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

顯然，G中包含不止一種內部故障，考慮能使電路發生功能異常的硬故障：開路與短路，通過仿真或實驗手段可得多個與這些故障相對應的MTT，最終這些MTT的集合即為邏輯門類型G的故障字典。顯然，G中包含不止一種的內部故障，因此通常存在多個與這些內部故障相對應的MTT，它們即構成了該邏輯門類型 G 的故障字典， 記為 DG={＜T*G，k，λG，k＞|k=1，2，…，NG}，其中 NG表示 MTT 的數量；λG，k表示對應的MTT等于T*G，k的累計故障計數。顯然，一個MTT對應的內部故障數量越多，它在邏輯門的故障行為空間中出現的概率就越大。考慮到在實際數字電路中，不定態‘X’是不存在的，既可能為‘1’也可能為‘0’，或者在這兩個邏輯值之間隨機跳變，因此需要對故障字典進行整理，將‘X’狀態按某種概率分配到‘0’和‘1’上，最終建立可被測試生成算法調用的故障字典。

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

其中NTS為CUT生成的測試集向量數，M為CUT的邏輯門數，Fcj為第j個測試向量所檢測到的故障數量，Fci為第i個邏輯門中注入的故障數量。

2 測試生成算法

2.1 組合電路的神經網絡模型

二值神經網絡的能量函數[12]為：

式中:N是神經網絡中神經元的數目；Ii是神經元i的閾值；Tij是神經元i和j之間的權值；Vi是神經元i的狀態值；K是常量。

用Hopfield模型中的能量函數來表示基本門電路的傳輸特性：對符合一種基本門電路功能函數的取值稱為這種門電路的一個相容狀態，其他不符合功能函數的取值稱為門的非相容狀態。當基本邏輯門的輸入輸出值符正確的邏輯關系時，對一種門電路的一個相容狀態，能量函數E=0，否則不為零。基于此能量函數，則將測試生成問題轉化為數學問題，通過式（1）得出基本門電路的而二值神經網絡能量函數如表4所示，其中第一列為邏輯門的類型，第二列為輸入，第三列為輸出，第四列為邏輯門的神經網絡能量函數。

表1 基本邏輯門的能量函數

圖1 單輸出電路的約束網絡

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

對于任何一個組合邏輯電路，利用推導出的基本邏輯門電路的二值神經網絡能量函數，就能獲得相對應的組合邏輯電路的二值神經網絡能量函數。將每一種基本門電路定義為結構類型，根據基準電路給出的各基本門電路的輸入輸出關系，把它們組合起來就構成了被測電路的神經網絡模型。

圖2 多輸出電路的約束網絡

2.2 遺傳算法

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

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

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

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

圖3 二值神經網絡遺傳算法流程圖

3 仿真實驗與結果分析

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

圖4 兩輸入與非門電路圖

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

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

表3 改進的兩輸入與非門故障字典

表4 改進的邏輯門故障字典

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

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

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

4 結 論

本文首先從電路的內部故障出發，根據邏輯門不同的外部功能異常表現，構建了更全面的變異真值表故障模型，并考慮了各輸入條件下故障的不同權重，按故障模型自動生成故障字典。基于邏輯門的二值神經網絡能量函數所構成的約束網絡，調用故障字典向約束網絡注入故障，通過遺傳算法求解出被測電路的測試集。仿真實驗結果顯示，本文建立的故障模型更加全面和真實，測試生成算法具有較高的故障覆蓋率和較短的測試時間。

[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]楊士元.數字系統的故障診斷與可靠性 [M].北京：清華大學出版社，2000.

[3]潘中良，陳翎.基于神經網絡的電路多故障測試及并行實現 [J].儀器儀表學報，2002，23 （6）:680-681.

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

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

[6]薛維琴，李莉華，戴明.基于FPGA的人工神經網絡系統的實現方法[J].電子設計工程，2010，18（9）:151-154.

[7]張宇翔，黃力宇.Hopfield網絡求解TSP兩種改進算法的仿真研究[J].電子設計工程，2009，17（10）:119-121.

[8]楊興，謝志遠，馮力娜.神經網絡在組合電路多故障測試生成算法中的應用 [J].電力科學與工程，2009，25（3）:37-41.

[9]吳麗華，王旭東，史芳芳，等.遺傳優化三值神經網絡多故障測試生成算法 [J].儀器儀表學報，2010，31（8）:1744-1749.

[10]許杰，涂小輝.基于改進遺傳算法的組合電路測試生成[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].電機控制與學報，2006，10（5）:478-481.

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

[14]康華光，皺壽彬，秦臻，等.電子技術基礎[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—），女，江蘇溧陽人，碩士研究生。研究方向：電子信息系統測試與診斷技術。