基于免疫粒子群文化算法的數字電路故障診斷

申延強，韓華亭

（空軍工程大學防空反導學院，西安　710051）

基于免疫粒子群文化算法的數字電路故障診斷

申延強，韓華亭

（空軍工程大學防空反導學院，西安710051）

為改善粒子群算法擺脫局部極值點的能力，提升種群進化的多樣性，將免疫算法中免疫機制引入到粒子群算法中形成免疫粒子群算法；為有效提高故障覆蓋率和縮短測試生成時間，將免疫粒子群算法引入文化算法框架中形成免疫粒子群的文化算法。將其應用于數字電路故障模型仿真實驗并與其他測試生成算法進行對比，結果表明該算法能夠有效提高故障覆蓋率，縮短測試生成時間，在大規模電路測試生成與故障診斷中更具優勢。

數字電路，測試生成，測試矢量，免疫粒子群算法，文化算法

0　引言

隨著電子技術的發展，數字電路的規模越來越大，結構越來越復雜，這使得數字電路的測試生成與故障診斷變得越發困難。數字電路的測試生成，就是尋找能激活電路中的故障并將其傳播到原始輸出端的故障測試輸入矢量。而最關鍵的部分是找到故障覆蓋率高、測試時間短的測試生成算法。傳統的測試生成算法需要回退、傳播和確認，過程復雜，測試時間長，已無法滿足現代高集成度數字電路的測試要求。近幾年，仿生學算法發展迅速，可以有效地解決組合優化問題，而測試生成問題本質就是組合優化問題，因此，很多仿生優化算法被用到數字電路的測試中，例如，粒子群算法、免疫算法等。將仿生優化算法應用于測試生成，可以使測試生成問題得到簡化。本文將免疫粒子群算法引入到文化算法的框架中，很好地解決了免疫粒子群算法和文化算法中存在的不足，結合它們各自的優點，更加有效地進行數字電路的測試生成。

1　免疫粒子群的文化（CA-IA-PSO）算法

1.1粒子群（PSO）算法

其中，i=1，2，…，n；d=1，2，…，D；t表示第t代；w為慣性權重；r1，r2是［0，1］上的隨機數。

1.2免疫（IA）算法

免疫算法基于生物免疫系統機理。仿照人工免疫系統的高頻變異、免疫記憶、克隆復制等優勢，使系統能逃逸出局部最優解，獲得全局最優解?？寺∶庖咚惴ㄖ饕锌寺U增選擇、交叉、變異、進化替代以及局部滅絕5部分。

克隆復制是克隆適應度高的粒子，粒子克隆的概率與適應度成正比。粒子適應度函數為：

對于克隆擴增后的子群體，進行高概率的超變異。變異概率P（Xi）=kfi，其中k為歸一化系數。

為利于群體間信息交互，提高群體協作能力，引用免疫系統中的交叉極值對微粒群個體進行交叉。隨機兩兩粒子進行雜交，產生同樣數目的子粒子。子粒子的位置由父粒子的位置的算數加權來計算。交叉算子如下：

其中，X為d維的位置向量；X1（t）和X2（t）為選擇進行雜交操作的粒子；r為d維均勻分布且每個分量都在［0，1］取值的隨機向量。速度用同樣的公式計算，只是將r取不同的隨機向量。

抗體種群在克隆算子的作用下的演化過程如圖1所示。

圖1　粒子群免疫算法過程

1.3免疫粒子群的文化（CA-IA-PSO）算法

文化算法（CA）是模擬人類社會進化過程的計算方法。文化被社會成員全面地接受，指導社會成員的行為，吸納成員個體的先進經驗而不斷地更新自己，且為個體行為在社會中的表現提供說明。CA由群體空間（Population Space，PS）和信仰空間（Belief Space，BS）兩部分組成，二者相互獨立。PS在微觀層面模擬個體按照一定規則進化的過程，通過進化規則和性能評價進行迭代求解問題。BS在宏觀層面通過自身的演化，模擬文化形成、傳遞的進化過程。文化算法的基本模型如圖2所示。

文化算法框架提供了一種多進化過程的計算模型，傳統的CA中，PS由EP（有限狀態機模型）來優化，BS由GA（遺傳算法）來優化。CA算法全局搜索能力強，算法復雜，但其弱點是收斂速度慢，求解時間過長。

粒子群算法全局搜索能力弱，易于“早熟”，但是其算法簡單，收斂速度快。為改善粒子群算法擺脫局部極值點的能力，提升種群進化的多樣性，將免疫算法中免疫機制引入粒子群算法中形成免疫粒子群算法。

圖2　文化算法的基本模型

在此基礎上，本文將免疫粒子群（IA-PSO）算法引入文化算法的框架中，以解決免疫粒子群中存在的問題以及數字電路測試生成問題?；贗A-PSO的文化算法程序結構流程如圖3所示。

圖3　基于IA-PSO的文化算法程序結構流程

在進化過程中，粒子跟蹤個體最優與全局最優兩個極值來更新自己。將PS中利用適應度函數計算求得的全局最優傳遞到BS，替代BS中適應度差的粒子，再利用IA-PSO更新BS，當滿足影響條件時，利用得到的新的BS群體繼續指導PS中的粒子演化。不斷循環直到滿足算法結束條件為止。

2　基于CA-IA-PSO的測試生成

2.1典型數字電路模塊功能和工作原理

碼形成器是某機電設備上角速度編碼器的重要部件，碼形成器電路分為主路和輔路兩部分。輔路電路完成主路電路所需非控制信號的輸入和時鐘的控制；主路電路將8組7位并行二進制代碼轉化為串行二進制代碼并分別輸出到延遲器和設備上的控制單元。本文以主路部分作為研究對象。主路部分電路利用7個54LS151芯片和2個54295芯片把8組7位并行二進制代碼轉換為串行二進制代碼。54LS151芯片是LSTTL型8選1數據選擇器，包含全芯片的二進制譯碼，完成8選1數據輸出。它含一個選通輸入G，低電平有效；輸出W是根據輸入管腳ABC的輸入數字信號選擇D0-D7輸入中的一位數據輸出。54295芯片的功能優點類似移位寄存器，是將54LS151芯片選通輸入的8組7位并行二進制代碼分別轉化為串行二進制代碼輸出。

對主路電路進行深入分析，分析結果如表1所示。該電路輸入激勵較多，輸出響應少；門的個數較少，但不都是基本門，功能較復雜；故障總數較多，但由于門的類別不是單純的與門之類的基本門，電路中每根設定的故障線都有其實際的作用，沒法進行等效壓縮?？偟膩碚f，該電路較典型，能較好完成整個測試生成過程。

表1　主路部分電路分析結果

2.2數字電路模塊測試方案

數字電路測試生成與故障診斷方案的設計框圖，如圖4所示。

圖4　測試生成與故障診斷方案設計框圖

數字電路的故障診斷，采用基于故障字典的診斷方法。故障字典的主要思想包括。①測試矢量集的生成。預先根據實際需要，基于測試生成算法確定測試矢量集。②編制故障字典。設定電路存在某一故障，將激勵的響應特征作為故障特征，將所有可能的故障響應編制成故障與特征對應的故障字典。③故障定位與故障字典完善。對電路施加與測前模擬時同樣的激勵，取得故障響應的特征，最后在故障字典中查找對應的故障，若無，則故障字典未收錄此故障，將其收錄完備。

角速度編碼器數字電路測試與故障診斷以主控計算機為測試系統主機，通過編制各電路或芯片的測試程序、診斷控制程序，建立故障字典實現對板級數字電路的故障診斷。主控機通過接口適配器連接測試診斷平臺完成待測電路的預處理、故障建模、故障表的生成、基于測試生成算法的測試矢量集的生成、對相應的故障仿真、故障表與測試矢量集中測試矢量對應關系表的生成。同時對被測電路施加測試數據（測試矢量），并把響應數據采集到計算機上進行綜合分析、處理；最后完成故障字典的生成，以便定位故障。對有相同故障測試矢量集的故障，能進一步壓縮則壓縮，否則一般通過測取測點信號，采用倒序方式確定。

故障診斷的核心在于診斷定位，就是根據電路響應，利用故障仿真結果進行比較、檢索、測試。

2.3數字電路模塊測試生成與故障診斷過程

主路電路測試生成與故障診斷步驟如下：

（1）通過輸入輔路電路拓撲結構模擬仿真其正確的輸出信號，以此確保主路在進行測試與故障診斷時不受其他干擾。

（2）對主路電路輸入引腳、輸出引腳、門和芯片、故障端進行節點編號。將求元件的故障轉化為求元件輸入輸出端線的故障，即把定位故障元件轉化為確定有故障的端線，以避免出現漏測等錯誤，同時將該電路進行分塊并略去無用引腳。

（3）利用組合測試系統搭建測試診斷平臺，將算法集成到組合測試系統軟件模塊中，在主控計算機的控制下運用本文所述數字電路測試生成方法進行該板級電路模塊的測試生成。

（4）整理故障測試集。通過測試集的壓縮、故障仿真等對測試集進行整理，盡量使單個故障只與測試向量對應且每個故障對應的測試向量不同。對于一個測試生成對應幾個故障可以使用探針確定具體故障節點。對測試集進行處理后，生成故障與測試矢量集相對應的測試表。

（5）通過計算機仿真將生成的測試矢量集加入無故障的主路部分仿真電路并采集相應的輸出響應，生成標準故障字典。

在檢測電路板實物某個節點是否有故障時，查詢故障字典，將該故障對應的測試矢量加入故障電路板，所得輸出結果與故障字典中正確值相同，則是該節點故障否則是該節點無故障，從而定位故障元件。

3　實驗結果及分析

分別將PSO算法、IA-PSO算法和CA-IA-PSO算法用于主路電路的測試生成，結果如表2所示。

表2　主路部分電路測試生成結果

電路雖然故障數較多，但運用仿生測試生成算法同樣能達到100%的故障覆蓋率，表明該電路的故障都能被激活，且能傳播到輸出端被測試出來。電路中有芯片54LS151、54295，比門電路復雜，測試生成時間比基本門電路長?；诿庖吡Ｗ尤何幕惴ㄔ谙嗤姆抡姝h境下，得到的測試生成時間比粒子群算法所耗時間更短，證明了算法有效。

主路部分電路是在時鐘控制下輸出的，不同的時鐘控制，測試生成時間會略有不同，本文中時鐘控制設置為20 ns。

由于時鐘控制和電路結構的特殊性，將電路分塊，在測試生成過程，控制時鐘，每次只用一個芯片的4個輸入和后面門電路的3個輸入即可完成后半部分門電路節點的測試生成，后面門電路的節點測試生成完后再分別進行剩余芯片上節點的測試生成，能節省測試生成時間。表3為電路分塊后的測試生成結果。

表3　電路分塊后的測試生成結果

分析電路的結構對電路進行合理的分塊對縮短測試時間具有一定作用。

4　結論

將免疫粒子群文化算法用于編碼器電路主路部分的測試生成，得到以下結論：

（1）根據不同仿生算法的優缺點，可以將其結合使用。本文利用粒子群算法與免疫算法的優勢互補性，同時利用免疫算法的特點，提出免疫粒子群算法文化算法，克服單一算法的缺陷。

（2）基于免疫粒子群文化算法在相同初始條件、仿真環境和適應度函數下能提高故障覆蓋率，縮短測試生成時間，在用于大規模電路時，優勢更明顯，因而具有實用價值和應用前景。

（3）分析電路的結構并將電路進行合理分塊對縮短測試時間具有一定作用。

［1］劉小東，孫圣和.基于遺傳算法的自適應測試生成［J］.微電子學與計算機，2002，31（3）：14-16.

［2］王宇，付立平，周廣田，等.面向數字電路測試生成的智能方法研究［J］.黑龍江大學自然科學學報，2010，27（6）：827-831.

［3］楊士元.數字系統的故障診斷與可測性設計［M］.2版.北京：清華大學出版社，2000：39-49.

［4］徐建斌，李智.神經網絡在組合電路故障模擬測試生成算法中的應用［J］.電路與系統學報，2001，6（4）：109-110.

［5］高鷹，謝勝利.免疫粒子群優化算法［J］.計算機工程與應用，2004，6（3）：5-7.

［6］潘中良，張光昭.數字電路多故障測試生成的神經網絡方法研究［J］.儀器儀表學報，1999，20（3）：232-234.

［7］趙瑩，吳麗華.基于三值神經網絡的多故障測試生成算法［J］.哈爾濱理工大學學報，2004，9（8）：20-23.

［8］黃鑫，常天慶，邢士勇.數字電路板自動測試與故障診斷系統的設計［J］.計算機測量與控制，2010，18（7）：1512-1514.

［9］王靈，俞金壽.基于離散粒子群和支持向量機的故障診斷方法［J］.華東理工大學學報：自然科學版，2005，31（5）：697-700.

［10］趙瑩，吳麗華，馬懷儉.基于三值神經網絡的組合電路測試生成算法［J］.哈爾濱理工大學學報，2004，9（4）：20-23.

Test Pattern Generation for Digital Integrated Circuits Based on CA-IA-PSO Algorithm

SHEN Yan-qiang，HANHua-ting
（Air Defense and Antimissile Institute，Air Force Engineering University，Xi’an 710051，China）

In order to improve the ability to get rid of partial extreme spot and the diversity in evolution，IA algorithm is imported into PSO algorithm to form IA-PSO algorithm.For the purpose of raising fault rate and shortening test pattern generation time，CA algorithm into is imported IA-PSO algorithm to form CA-IA-PSO algorithm.Finally，single stuck-at fault is adopted and different algorithms is used to the simulation experiment of test pattern generation，the result is that CA-IAPSO algorithm can solve the problem of test pattern generation more practically and efficiently，especially in large digital circuits.

digital integrated circuits，test pattern generation，test vector，IA-PSO algorithm，CA algorithm

TN407

A

1002-0640（2016）08-0192-04

2015-05-04

2015-07-09

申延強（1991-），男，河北邯鄲人，碩士研究生。研究方向：地空導彈發射系統故障診斷。