申延強(qiáng)，韓華亭

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

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

申延強(qiáng)，韓華亭

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

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

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

0　引言

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

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

1.1粒子群（PSO）算法

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

1.2免疫（IA）算法

免疫算法基于生物免疫系統(tǒng)機(jī)理。仿照人工免疫系統(tǒng)的高頻變異、免疫記憶、克隆復(fù)制等優(yōu)勢(shì)，使系統(tǒng)能逃逸出局部最優(yōu)解，獲得全局最優(yōu)解。克隆免疫算法主要有克隆擴(kuò)增選擇、交叉、變異、進(jìn)化替代以及局部滅絕5部分。

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

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

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

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

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

圖1　粒子群免疫算法過程

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

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

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

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

圖2　文化算法的基本模型

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

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

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

2　基于CA-IA-PSO的測(cè)試生成

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

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

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

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

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

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

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

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

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

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

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

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

（1）通過輸入輔路電路拓?fù)浣Y(jié)構(gòu)模擬仿真其正確的輸出信號(hào)，以此確保主路在進(jìn)行測(cè)試與故障診斷時(shí)不受其他干擾。

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

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

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

（5）通過計(jì)算機(jī)仿真將生成的測(cè)試矢量集加入無(wú)故障的主路部分仿真電路并采集相應(yīng)的輸出響應(yīng)，生成標(biāo)準(zhǔn)故障字典。

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

3　實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

4　結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

［10］趙瑩，吳麗華，馬懷儉.基于三值神經(jīng)網(wǎng)絡(luò)的組合電路測(cè)試生成算法［J］.哈爾濱理工大學(xué)學(xué)報(bào)，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

申延強(qiáng)（1991-），男，河北邯鄲人，碩士研究生。研究方向：地空導(dǎo)彈發(fā)射系統(tǒng)故障診斷。