申延強，韓華亭

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安　710051）

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

申延強，韓華亭

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安710051）

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

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

0　引言

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

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

1.1粒子群（PSO）算法

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

1.2免疫（IA）算法

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

克隆復(fù)制是克隆適應(yīng)度高的粒子，粒子克隆的概率與適應(yīng)度成正比。粒子適應(yīng)度函數(shù)為：

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

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

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

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

圖1　粒子群免疫算法過程

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

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

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

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

圖2　文化算法的基本模型

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

圖3　基于IA-PSO的文化算法程序結(jié)構(gòu)流程

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

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

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

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

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

表1　主路部分電路分析結(jié)果

2.2數(shù)字電路模塊測試方案

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

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

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

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

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

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

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

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

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

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

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

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

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

3　實驗結(jié)果及分析

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

表2　主路部分電路測試生成結(jié)果

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

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

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

表3　電路分塊后的測試生成結(jié)果

分析電路的結(jié)構(gòu)對電路進行合理的分塊對縮短測試時間具有一定作用。

4　結(jié)論

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

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

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

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

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

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

［3］楊士元.數(shù)字系統(tǒng)的故障診斷與可測性設(shè)計［M］.2版.北京：清華大學(xué)出版社，2000：39-49.

［4］徐建斌，李智.神經(jīng)網(wǎng)絡(luò)在組合電路故障模擬測試生成算法中的應(yīng)用［J］.電路與系統(tǒng)學(xué)報，2001，6（4）：109-110.

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

［6］潘中良，張光昭.數(shù)字電路多故障測試生成的神經(jīng)網(wǎng)絡(luò)方法研究［J］.儀器儀表學(xué)報，1999，20（3）：232-234.

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

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

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

［10］趙瑩，吳麗華，馬懷儉.基于三值神經(jīng)網(wǎng)絡(luò)的組合電路測試生成算法［J］.哈爾濱理工大學(xué)學(xué)報，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-），男，河北邯鄲人，碩士研究生。研究方向：地空導(dǎo)彈發(fā)射系統(tǒng)故障診斷。