康 鵬，金 婕，嚴(yán) 偉

（1 上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620；2 北京大學(xué) 軟件與微電子學(xué)院，北京 102600）

0 引 言

隨著電路板集成度和元器件復(fù)雜度呈現(xiàn)指數(shù)式增長，對其可控性、可測性和可觀察性的要求越來越高，而對實踐中電路板的測試要求也更加嚴(yán)格。傳統(tǒng)的電路板故障檢測方法都是以功能測試為出發(fā)點，步驟復(fù)雜，測試時間長，很難精確定位到故障點。為針對電子系統(tǒng)故障診斷的難點提供全面可靠的故障診斷方案，聯(lián)合測試行動組（JTAG）提出了一套邊界掃描體系結(jié)構(gòu)標(biāo)準(zhǔn)化可測試性技術(shù)。邊界掃描技術(shù)對待測電路發(fā)送測試向量，獲取測試響應(yīng)，通過測試向量和測試響應(yīng)分析診斷電路故障。因此，在邊界掃描的板級測試中，測試向量集的優(yōu)劣直接影響故障檢測的效果。如何生成高質(zhì)量的測試向量集是當(dāng)今邊界掃描技術(shù)重點關(guān)注的問題。

近些年來，學(xué)者們提出了一系列的測試向量生成算法。如，改良計數(shù)算法MCSA、等權(quán)值抗誤判算法、極小權(quán)值-極大相異性算法等等。這些算法建立在無限制故障模型的基礎(chǔ)上，雖然有不錯的故障誤判率和故障混淆率，但是未能結(jié)合電路板的結(jié)構(gòu)信息，難以實現(xiàn)最佳的測試效果。結(jié)構(gòu)測試算法（Structural Test）通過分析電路板的結(jié)構(gòu)和工藝信息，建立有限制故障模型，使得測試向量在具備完備故障診斷能力的前提下獲得更小的緊湊性指標(biāo)?；诮従W(wǎng)絡(luò)排序集的測試向量優(yōu)化算法，雖然可以極大地優(yōu)化測試向量集的緊湊性和完備性，但是受制于近鄰網(wǎng)絡(luò)排序集難以獲取的特點，無法應(yīng)用于工程實踐。為此，本文提出一種有限制短路故障模型和蟻群算法相結(jié)合的測試向量生成策略。首先，結(jié)合PCB電路板的結(jié)構(gòu)特征、元器件特性和工藝建立有限制短路故障模型，分析各網(wǎng)絡(luò)間發(fā)生短路故障的概率。然后將問題轉(zhuǎn)換成圖論中最小點覆蓋的問題，利用蟻群算法尋找最小覆蓋點，結(jié)合網(wǎng)絡(luò)近鄰關(guān)系矩陣生成優(yōu)化的測試矩陣，最后通過實驗分析了該方法的有效性，最終生成的測試矩陣在保證完備性的情況下，具有較好的緊湊性。

1 有限制短路故障模型

對于包含個網(wǎng)絡(luò)電路板的無限制故障模型，任意2個網(wǎng)絡(luò)之間都會發(fā)生故障，故障類型分為固定邏輯故障和橋接短路故障。假定一個5網(wǎng)絡(luò)的電路，研究時基于無限制故障模型的思想，可得到的拓?fù)浣Y(jié)構(gòu)如圖1（a）所示。然而PCB板上的短路故障大多發(fā)生在元件管腳（焊點）、導(dǎo)線、過孔等之間，并且與其在PCB板的分布情況密切相關(guān)。因此，不同的2個網(wǎng)絡(luò)之間發(fā)生短路的幾率也是不相同的。另有研究表明，元器件管腳的焊點之間發(fā)生短路的幾率和焊點之間的物理位置，可以用指數(shù)衰減函數(shù)來進行描述，對此可表示為：

其中，P、P表示電路板中的2個節(jié)點；表示節(jié)點之間的最短距離；表示兩節(jié)點距離；表示兩節(jié)點出現(xiàn)短路故障時的最大間距；表示距離最小的2個節(jié)點間出現(xiàn)短路故障的機率，1；表示衰減系數(shù)，1。

網(wǎng)絡(luò)是由導(dǎo)線連接元器件管腳（焊點）構(gòu)成的，對于一個有個網(wǎng)絡(luò)的電路板，若n、n是其中的2個子網(wǎng)絡(luò)，則n和n之間發(fā)生短路的可能性關(guān)系的數(shù)學(xué)表達(dá)式可寫為：

將式（2）簡化成式（3）：

由式（3）計算出不同網(wǎng)絡(luò)之間發(fā)生短路的幾率。當(dāng)小于閾值時，這2個網(wǎng)絡(luò)不會發(fā)生故障?；诖死碚?，對于同一個5網(wǎng)絡(luò)的電路板，結(jié)合電路板的結(jié)構(gòu)信息，就可以計算出各網(wǎng)絡(luò)之間發(fā)生短路故障的可能性。通過比較和閾值，可以將無限制的短路故障模型拓?fù)鋱D簡化成如圖1（b）所示的模型圖。

圖1 網(wǎng)絡(luò)短路故障關(guān)系拓?fù)淠Ｐ虵ig.1 Network short-circuit fault relationship topology model

2 蟻群算法

2.1 問題描述

邊界掃描測試給每個網(wǎng)絡(luò)賦予一個測試向量，通過采集并分析測試響應(yīng)，即可推斷出故障位置。在圖1（b）中，如果能找到一個網(wǎng)絡(luò)子集使得圖中所有的邊至少有一個端點在該子集中，那么由該網(wǎng)絡(luò)子集組成的測試向量矩陣就可以診斷所有的短路故障。因此，可以采用求解圖論最小點覆蓋問題生成測試矩陣。

2.2 蟻群算法求解最小點覆蓋

首先通過比較網(wǎng)絡(luò)之間的短路幾率和閾值的大小，確定對應(yīng)邊的權(quán)值，將無限制短路故障模型拓?fù)鋱DG＝（，E）化簡成有限制短路故障模型拓?fù)鋱D（，），求有限制短路故障模型的最小點覆蓋問題。根據(jù)蟻群算法的螞蟻搜索原理，確定連接函數(shù)，函數(shù)定義式見式（4）：

根據(jù)式（4）定義動態(tài)啟發(fā)函數(shù)η，由此推得：

其中，ω表示頂點的權(quán)值。

其中，表示啟發(fā)式因子，該值越大，螞蟻選擇這個頂點的可能性越大，該值過小容易陷入局部最優(yōu)解；表示期望啟發(fā)因子；是標(biāo)準(zhǔn)參數(shù)；是隨機變量，01。

螞蟻在行走時會釋放“信息素”，在最小點覆蓋問題中，螞蟻從一個頂點轉(zhuǎn)移到另一個頂點是沒有關(guān)聯(lián)的，因此在螞蟻選擇新的頂點時需要進行更新局部信息素τ，推得的數(shù)學(xué)定義公式為：

對于子集是否為全局最優(yōu)解可用式（8）來判斷：

當(dāng)全部螞蟻群完成所有路徑后，全局信息素會進行更新，推導(dǎo)得到的數(shù)學(xué)公式可寫為：

算法終止的條件是所有的螞蟻結(jié)束循環(huán)，輸出，選擇不同的初始點，可以得到不同的覆蓋集，比較得出最小點的覆蓋集。

3 測試向量生成

為驗證基于有限制短路故障模型和蟻群算法相結(jié)合的測試向量生成策略的可行性，方案流程如圖2所式，以PCB電路板網(wǎng)絡(luò)數(shù)23為例進行驗證，通過Protel DXP軟件獲取電路板的結(jié)構(gòu)信息網(wǎng)表，由式（3）計算各網(wǎng)絡(luò)之間的短路可能性，通過閾值確定網(wǎng)絡(luò)之間的權(quán)值，建立網(wǎng)絡(luò)近鄰關(guān)系如圖3所示，并將其轉(zhuǎn)變成布爾關(guān)系矩陣式，利用矩陣構(gòu)造初始測試矩陣。與的數(shù)學(xué)定義公式分別如下：

圖2 蟻群算法求解測試矩陣流程圖Fig.2 Flowchart of solving the test matrix by the ant colony algorithm

圖3 網(wǎng)絡(luò)關(guān)系拓?fù)鋱DFig.3 Network relationship topological diagram

在初始測試矩陣中，“”代表了無效測試信息，第個列向量代表圖3中n網(wǎng)絡(luò)的測試向量，其測試向量中的第位用“1”表示。從圖3中可知，網(wǎng)絡(luò)與網(wǎng)絡(luò)存在短路的可能，因此初始測試矩陣第一列中第2位屬于有效的測試位，用“0”表示；然而在初始測試矩陣中第二列的第一位也用于檢測網(wǎng)絡(luò)與網(wǎng)絡(luò)是否短路，造成了測試信息的冗余，需要利用蟻群算法求出最小點覆蓋集，計算結(jié)果見表1。根據(jù)最小點覆蓋集，對初始測試矩陣進行優(yōu)化，選取初始測試矩陣中相關(guān)列向量，組成新的測試向量矩陣，最后還需確定矩陣中“”元素的具體值。為了滿足檢測固定邏輯故障的要求，最終確定“”值時，需要確保測試矩陣中沒有全“0”或全“1”的行向量，一般通過合理的設(shè)定“”的值或增加列向量來滿足測試要求。最終可求得測試矩陣：

表1 蟻群算法求解結(jié)果Tab.1 Ant colony algorithm solution results

4 性能分析

在生成的測試向量中，如果存在n和n短路故障特征向量與n無故障網(wǎng)絡(luò)的測試響應(yīng)相同，那么在對電路板進行測試時，就無法判斷n和n網(wǎng)絡(luò)之間是否存在故障，即故障征兆誤判。此外，在測試向量中同樣會出現(xiàn)n和n短路故障特征向量與n和n短路故障特征向量相同的情況，這樣也會造成故障無法定位，即故障征兆混淆。

本文提出的測試向量生成方法，有效地結(jié)合電路板的結(jié)構(gòu)信息，計算n和n網(wǎng)絡(luò)之間出現(xiàn)短路故障的機率，若n和n網(wǎng)絡(luò)之間不存在短路可能，就可降低故障誤判率和故障混淆率。為分析本文測試向量生成方法的性能，采用等權(quán)值算法、極小權(quán)值極大權(quán)值相異性算法和本文的算法，依據(jù)不同網(wǎng)絡(luò)數(shù)的電路板進行了仿真實驗。傳統(tǒng)測試矩陣生成算法與本文算法結(jié)果對比見表2。

表2 傳統(tǒng)測試矩陣生成算法與本文算法結(jié)果比較Tab.2 Comparison of the traditional test matrix generation algorithms and the results of this algorithm

從表2中可以看出，在不同值條件下，本文提出的測試矩陣生成算法，在保證測試完備性指標(biāo)和緊湊性指標(biāo)的前提下，具有較低的故障征兆誤判率和故障征兆混淆率。

5 結(jié)束語

本文在建立有限制短路故障模型的基礎(chǔ)上，引入蟻群算法，能夠快速、高效地獲取被測電路板的最小網(wǎng)絡(luò)覆蓋集，以此生成測試矩陣。實驗結(jié)果表明，在閾值假定的前提下，該方法生成的測試矩陣能在保證測試完備性指標(biāo)的同時擁有良好的緊湊性指標(biāo)，具有較強的應(yīng)用價值。