改進的等權(quán)值抗混淆算法

,燕威,

(1.中國民航大學(xué) 職業(yè)技術(shù)學(xué)院，天津 300300；2.中國民航大學(xué) 電子信息與自動化學(xué)院，天津 300300)

0 引言

在20世紀70年代中期，電路板的測試是通過在線測試進行的，表面貼裝技術(shù)對板上互連測試造成了更大的困難。為了找到解決測試問題的方案，一批科學(xué)家在1980年中組建聯(lián)合測試行動小組(JTAG)。1990年，JTAG推出了基于邊界掃描的測試技術(shù)，被稱為IEEE1149.1標準[1]。邊界掃描技術(shù)的發(fā)展帶動了邊界掃描算法的而不斷的發(fā)展。

目前國內(nèi)外相關(guān)的邊界掃描測試算法很多，各有其優(yōu)缺點，通常可分為三類，第一類是采用無限制短路故障模型的常規(guī)測試算法，第二類是采用有限制短路故障模型的結(jié)構(gòu)測試算法，第三類是利用測試過程中所獲取的信息對測試向量集進行優(yōu)化的自適應(yīng)算法[2]。本文在分析了常規(guī)測試算法等權(quán)值互連測試算法的基礎(chǔ)上，將結(jié)構(gòu)測試算法的思想應(yīng)用到等權(quán)值算法上，提出了基于有限制短路故障關(guān)系的改進等權(quán)值互連測試算法。

1 等權(quán)值算法

1.1 等權(quán)值算法概述

1.2 等權(quán)值算法分析

抗誤判定理[4]：權(quán)值為W的一個固定權(quán)值診斷算法的測試集(Matrix of Test Vectors，MTV)是一個獨立的貫序測試向量(Sequential Test Vector,STVs)矩陣。

推論[4]：由獨立STVs組成的測試集MTV對如下故障無征兆誤判現(xiàn)象：

1)S-A-0/1，S-D-k；

2)W-A/O。

由于等權(quán)值算法生成的測試向量具有固定的權(quán)值，通過上述的抗誤判定理和推論可以得出該算法不存在征兆誤判。等權(quán)值算法和改良計數(shù)算法具有相同的緊湊性指標，并且具備較強的故障檢測能力[3]。等權(quán)值算法減少了征兆誤判的出現(xiàn)，但是征兆混淆率還是較高，并且征兆混淆主要發(fā)生在相似的STV之間[5]。以表1中測試矩陣為例說明，假設(shè)n3和n7短路在一起，n4和n6也短路在一起，它們的貫序測試響應(yīng)向量(Sequential Response Vector，SRV)均為11011，無法判斷是哪兩組網(wǎng)絡(luò)之間發(fā)生短路,即發(fā)生混淆。等權(quán)值算法同傳統(tǒng)的改良計數(shù)算法、WOA算法在測試生成的過程中均未能充分利用電路板的結(jié)構(gòu)信息[3]，即該算法的前提仍然是假設(shè)電路板中的所有網(wǎng)絡(luò)均可能發(fā)生短路故障。

表1 等權(quán)值算法測試矩陣

2 算法改進思路及過程

2.1 算法改進思路

產(chǎn)生誤判和混淆需要同時滿足兩個條件:1)算法生成的測試向量本身存在發(fā)生征兆誤判和征兆混淆的可能；2)分配到發(fā)生短路網(wǎng)絡(luò)上的STV能夠滿足征兆誤判和征兆混淆的發(fā)生條件[8]。因此，有兩種避免發(fā)生誤判和混淆的方法:第1種，提高算法生成的測試向量自身抗誤判和抗混淆的能力；第2種，在算法生成測試向量不變的條件下, 為網(wǎng)絡(luò)分配STV，使誤判和混淆發(fā)生條件不滿足，從而降低誤判和混淆的發(fā)生概率。以表1說明，如果把n2和n3的STV互換，則n3和n7短路的SRV為11101，n4和n6短路的SRV為11011，則不發(fā)生混淆。因此，若是能夠?qū)TV進行分組，將不易發(fā)生混淆的STV分在一組。同時利用電路板的結(jié)構(gòu)信息對電路板網(wǎng)絡(luò)進行適當分組，將發(fā)生短路概率大的網(wǎng)絡(luò)分在一組。最后將把不易發(fā)生混淆的STV組分配發(fā)生短路概率大的網(wǎng)絡(luò)組，從概率的角度上則可以降低誤判和混淆發(fā)生的可能性。

目前邊界掃描測試算法優(yōu)化包括兩類典型的問題，第一類是滿足完備性指標尋找緊湊性指標最小的測試向量集，第二類是確定緊湊性指標尋找完備性指標最佳的測試向量集[6]。因此目前的算法優(yōu)化方向主要集中在如何在緊湊性和完備性指標之間折中，尋求征兆誤判和征兆混淆率低的測試向量集，而利用電路板結(jié)構(gòu)信息優(yōu)化測試向量的方法較少。

綜合以上內(nèi)容，陶瓷與酒的結(jié)合在歷史上由來已久，對于現(xiàn)代酒類包裝設(shè)計工作的展開來說，設(shè)計人員必須能在確保陶瓷這一傳統(tǒng)文化元素發(fā)揮出自身作用的同時，保證酒類產(chǎn)品外包裝設(shè)計的創(chuàng)新性。

2.2 算法改進過程

如前面章節(jié)中所述，分組的目標是將不發(fā)生混淆的STV分在一組，同時將易發(fā)生短路故障的網(wǎng)絡(luò)盡可能分在同一組內(nèi)。因此優(yōu)化分組的過程主要分為兩步，即首先是對STV分組，然后對電路板網(wǎng)絡(luò)進行分組。

2.2.1 STV分組

通過對表1的STV進行分析可以發(fā)現(xiàn)，由于分配給各網(wǎng)絡(luò)的STV具有相同的權(quán)值，網(wǎng)絡(luò)N1、N2、N3和N4的第1位相同，第2至5位是移位“1”序列。同樣N5、N6和N7的前兩位相同，第3至5位是移位“1”序列，因此我們可以定義測試相似組對STV進行分組。

定義1(測試相似組[9])測試相似組是指組內(nèi)的測試向量前i位值相同，i+1位至最后位由移位“1”算法組成。

根據(jù)定義可將表1 的測試矢量集分為三個測試相似組，如表2所示。由于每個測試相似組中，相異部分由移位“1”序列組成，所以相似組內(nèi)不會產(chǎn)生征兆混淆，不同的測試相似組之間才會產(chǎn)生征兆混淆。

表2 測試相似組

2.2.2 電路板網(wǎng)絡(luò)分組

研究表明,電路板的管腳之間距離的長短會對管腳之間發(fā)生短路的概率產(chǎn)生影響。這種影響關(guān)系可以采用衰減函數(shù)來描述,如公式(1)[7]：

(1)

其中：pm和pn代表兩個任意的管腳，L0代表兩個管腳間的最小距離(取決于制造工藝)，Lm代表管腳間發(fā)生短路的最大可能物理距離，L為任意兩管腳間的實際距離，T0為最鄰近的兩個管腳間發(fā)生短路的可能性，A為遠大于1的衰減系數(shù)，代表相對于管腳距離的增大短路的概率衰減大小。通過衰減函數(shù)可以看出來，不同的網(wǎng)絡(luò)之間短路的概率不同，因此電路板網(wǎng)絡(luò)之間的短路故障是有限制。

網(wǎng)絡(luò)由相互連接的多個焊點構(gòu)成，網(wǎng)絡(luò)之間發(fā)生短路的可能性為各焊點短路的可能性的概率和，網(wǎng)絡(luò)之間發(fā)生短路故障的可能性為：

(2)

將式子展開，并忽略無窮小項，可得網(wǎng)絡(luò)之間的短路概率eij：

(3)

網(wǎng)絡(luò)之間發(fā)生短路的可能性可以通過上式進行計算，給定閾值?T0(不同的電路板閾值?T0的選取不同)。當eij

通過上述計算方法，獲取各網(wǎng)絡(luò)之間的短路概率,在此基礎(chǔ)上，建立網(wǎng)絡(luò)短路關(guān)系圖G=(V,E)，其中V={v1,v2,…,vn}，E=eij。其中vi表示網(wǎng)絡(luò)，E=eij表示vi與vj之間短路概率，圖1是某電路板的網(wǎng)絡(luò)短路關(guān)系圖[7]，下章節(jié)中將用此短路故障圖為研究對象進行網(wǎng)絡(luò)分組。圖中Ni代表網(wǎng)絡(luò)，圖中網(wǎng)絡(luò)間的權(quán)值代表短路概率，β是與電路板制造工藝有關(guān)的常數(shù)，圖中權(quán)值為0的網(wǎng)絡(luò)之間的邊進行了省略。

圖1 某電路板的有限制網(wǎng)絡(luò)短路關(guān)系圖

2)網(wǎng)絡(luò)分組

通過對圖1的電路板的網(wǎng)絡(luò)短路關(guān)系圖的分析，可以將其等價為一個具有n個節(jié)點的無向完全圖G(V,E)，其中V={v1,v2,…vn}代表網(wǎng)絡(luò)，E=eij代表權(quán)值，即網(wǎng)絡(luò)間短路概率。對于該無向完全圖G，邊集E的權(quán)值之和是個常數(shù)，因此將網(wǎng)絡(luò)分組問題轉(zhuǎn)換為無向完全圖G的分割問題。即為求滿足不同子圖間的邊權(quán)值之和最大值的分割，即滿足公式(4)：

(4)

該問題是帶權(quán)無向圖的k-最大割問題，是NP-hard問題，目前沒有多項式時間內(nèi)的精確求解算法[11]。對于具有大規(guī)模網(wǎng)絡(luò)的電路板來說，需要采用一種能夠在較短的時間內(nèi)獲得較好的網(wǎng)絡(luò)分組策略的方法。因此本文采用啟發(fā)式分組算法。

算法的思想是，首先計算各網(wǎng)絡(luò)之間的權(quán)值矩陣D，然后計算單個網(wǎng)絡(luò)與其他所有網(wǎng)絡(luò)的權(quán)值之和，根據(jù)權(quán)值之和對網(wǎng)絡(luò)進行降序排序，選擇權(quán)值之和最少的分組構(gòu)造初始分組，最后再對分組結(jié)果進行優(yōu)化。

對于給定的分組數(shù)k，啟發(fā)式算法的主要步驟如下：

a)計算網(wǎng)絡(luò)之間的權(quán)值矩陣D。

b)對于每一個網(wǎng)絡(luò)vi，計算其與其它所有網(wǎng)絡(luò)的權(quán)值之和ei=∑eij，并根據(jù)ei對網(wǎng)絡(luò)進行降序排序。依據(jù)排序結(jié)果順次對網(wǎng)絡(luò)進行分組。

d)對分組進行優(yōu)化。檢查是否存在網(wǎng)絡(luò)vi，將其從當前分組移動到另一分組時，總的權(quán)值會下降。如果存在則對vi行移動，直到找不到在這樣的網(wǎng)絡(luò)。

通過章節(jié)2.2中的電路板網(wǎng)絡(luò)分組算法對圖1所示的電路板網(wǎng)絡(luò)短路關(guān)系圖進行分組，最終分組結(jié)果為G1={n4,n1,n8,n6}，G2={n5,n7,n9}，G3={n2,n3}。

2.2.3 STV補償

網(wǎng)絡(luò)分組結(jié)果與章節(jié)2.2.1的STV分組結(jié)果結(jié)合，得到優(yōu)化后的測試矩陣如表3所示。

表3 優(yōu)化后的測試矩陣

考慮到網(wǎng)絡(luò)分組只是將短路概率大的網(wǎng)絡(luò)分在同一組，而不同的網(wǎng)絡(luò)組之間仍存在短路的可能，為了減少組間可能出現(xiàn)混淆，可以通過增大測試向量集的緊湊指標，從而達到完備性指標提高。由于走步“1”算法是完備性算法，可以選擇走步“1”序列作為補充向量，為了滿足向量的緊湊性指標要求，補充向量的個數(shù)應(yīng)盡可能少，因此可以選擇組間走步“1”序列，補充向量的個數(shù)與測試相似組的個數(shù)相同。表4為最終改進后的等權(quán)值測試向量集。

3 改進的算法分析

改進的等權(quán)值算法的測試向量集如上表所示，改進的算法的緊湊性指標為(P+N)，其中N為測試相似組的數(shù)目。與等權(quán)值算法相比，緊湊性指標提高了，表5給出了不同網(wǎng)絡(luò)下數(shù)目下，兩種算法的緊湊性指標。

表4 最終改進后的測試矩陣

表5 兩種算法的緊湊性指標比較

表6給出了不同網(wǎng)絡(luò)下不考慮網(wǎng)絡(luò)分組情況下的兩種算法的征兆誤判率和征兆混淆率。但是由于網(wǎng)絡(luò)的合理分組，給測試相似組分配了短路概率大的網(wǎng)絡(luò)組，因此征兆混淆發(fā)生的概率降低，改進的等權(quán)值算法的實際征兆混淆率應(yīng)比表6中的數(shù)據(jù)遠低。

表6 兩種算法的征兆誤判率和征兆混淆率

4 結(jié)論

針對等權(quán)值算法在利用電路板結(jié)構(gòu)信息方面的不足,提出了一種基于網(wǎng)絡(luò)有限制短路故障關(guān)系的改進等權(quán)值算法。與等權(quán)值算法相比,本文提出的算法充分利用了電路板結(jié)構(gòu)信息，通過對測試矢量和電路板網(wǎng)絡(luò)進行分組，給短路故障發(fā)生概率高的網(wǎng)絡(luò)組分配不發(fā)生混淆的測試向量組，雖然不能完全避免混淆的發(fā)生，但是可以從概率的角度降低征兆混淆發(fā)生幾率，從而提高等權(quán)值算法的測試能力。