一種基于互連測(cè)試的綜合優(yōu)化算法?

吳 中 邱衛(wèi)東 林 明

（1.江蘇科技大學(xué)電子信息學(xué)院 鎮(zhèn)江 212000）（2.南理工港世順有限公司 南京 210000）

1 引言

邊界掃描技術(shù)是對(duì)以往測(cè)試技術(shù)的一種革新，不需要將器件每個(gè)管腳連接到測(cè)試設(shè)備，只需通過JTAG 端口，發(fā)送內(nèi)部傳輸數(shù)據(jù)經(jīng)過輸入輸出的比較即可實(shí)現(xiàn)對(duì)各引腳的測(cè)試。解決了其他技術(shù)難以解決的問題。而互連測(cè)試作為其重要的一環(huán)，主要對(duì)板級(jí)網(wǎng)絡(luò)互連進(jìn)行分析，測(cè)試覆蓋率，測(cè)試時(shí)間以及故障診斷定位等作為衡量測(cè)試優(yōu)劣指標(biāo)都需要進(jìn)行不斷優(yōu)化，尋求較優(yōu)的測(cè)試算法一直是該技術(shù)的研究重點(diǎn)。以往大多算法在研究過程中均默認(rèn)只存在W-O 短路故障，而并不考慮W-A 短路，這也使得該測(cè)試技術(shù)在這一方面研究較為薄弱，并存在較大的局限性。本文通過邊界掃描技術(shù)的測(cè)試指標(biāo)對(duì)當(dāng)前相關(guān)算法進(jìn)行有效分析，意圖找出能綜合考慮此兩種短路故障，且緊湊性良好的算法。

2 相關(guān)概念和故障模型

2.1 相關(guān)概念

1）網(wǎng)絡(luò)：網(wǎng)絡(luò)是由通過導(dǎo)線連接的一系列輸入、輸出節(jié)點(diǎn)構(gòu)成的，記為ni，i=1，2，…，N。

2）串行測(cè)試向量（STV）：多次測(cè)試循環(huán)加載到同一網(wǎng)絡(luò)的測(cè)試矢量，記作VQi，i=1，2，…，N。

3）并行測(cè)試向量（PTV）：一次測(cè)試循環(huán)加載到不同網(wǎng)絡(luò)的測(cè)試矢量，記作Vpj，j=1，2，…，P。

4）測(cè)試矩陣（T）：由所有PTV 為列向量組成的布爾矩陣。

5）緊湊性指標(biāo)：掃描測(cè)試的時(shí)間決定于測(cè)試循環(huán)的次數(shù)［1］，即PTV 的個(gè)數(shù)或STV 的維數(shù)，用P 表示。

2.2 故障模型

常討論的故障模型包括固定故障與橋接故障［2］。固定故障包括滯0 故障（S-A-0）和滯1 故障（S-A-1），解釋為與地或電源短路。橋接故障包括W-O和W-A短路，如下式：

征兆誤判：當(dāng)測(cè)試向量存在STVi同某類橋接故障征兆相同時(shí)，無法確定該測(cè)試向量所在的網(wǎng)絡(luò)是否也與故障網(wǎng)絡(luò)短路。

征兆混淆：當(dāng)故障征兆S1f與S2f矢量相同時(shí)，無法確認(rèn)S1f與S2f所在網(wǎng)絡(luò)之間是否短路。

3 當(dāng)前較優(yōu)算法的描述分析

算法的優(yōu)劣主要通過兩個(gè)指標(biāo)來進(jìn)行判定，即緊湊性指標(biāo)，誤判征兆與混淆征兆的檢查能力［3］。

從緊湊性方面來看，目前MCSA 算法緊湊性最好，P=log（N+2），但是其對(duì)故障網(wǎng)絡(luò)的檢測(cè)效果比較差［4］。從完備性來看，走步算法是最完備的算法，然而其緊湊性為N，測(cè)試時(shí)間過長(zhǎng)。綜合考慮，當(dāng)前等權(quán)值算法是比較理想的，其生成測(cè)試向量STV 最大數(shù)為C（P，q），其中q=P/2。當(dāng)測(cè)試N 個(gè)網(wǎng)絡(luò)時(shí)，P 需滿足C（P，q）≥N，很明顯，當(dāng)網(wǎng)絡(luò)很多時(shí)，P 遠(yuǎn)小于N。另外等權(quán)值算法是一個(gè)抗誤判的算法，能做到零誤判，且一定程度下降低混淆率。因此在等權(quán)值算法的基礎(chǔ)上進(jìn)行算法優(yōu)化，具有一定實(shí)用意義。

文獻(xiàn)［5］提出了一種緊湊性指標(biāo)最小的抗誤判算法，該算法即是基于等權(quán)值算法，通過遞歸得到的。

該算法能消除W-O 短路故障的誤判，不能消除W-A 故障的誤判［5］。在緊湊性方面，該文提出的最小緊湊性具有一定局限性，設(shè)該算法緊湊性指標(biāo)為P，則P=n，通過數(shù)學(xué)推理證明P 需滿足，這說明只在網(wǎng)絡(luò)數(shù)較小的情況下，緊湊性低于等權(quán)值算法。如當(dāng)網(wǎng)絡(luò)數(shù)為100 時(shí)，等權(quán)值算法緊湊性為9，而緊湊性最小算法指標(biāo)為15，明顯大于等權(quán)值算法。

文獻(xiàn)［6｝中作者介紹了一種較優(yōu)的W-A 短路故障抗誤判算法，與文獻(xiàn)［4］一樣是通過遞歸得到的，是目前較少數(shù)對(duì)線與短路研究分析的算法，能完全消除W-A 短路故障誤判，卻不能消除W-O 短路故障的誤判［6］。

文獻(xiàn)［7］提出了一種等權(quán)值算法的優(yōu)化，在STV 矢量后附加了P/2 個(gè)走步算法［7］，犧牲了部分緊湊性指標(biāo)，但有效地降低了混淆率。如表1，當(dāng)網(wǎng)絡(luò)數(shù)為12 時(shí)，等權(quán)值算法和優(yōu)化的等權(quán)值算法的測(cè)試向量集。和目前大部分算法一樣，該算法只考慮了線或短路，而對(duì)線與短路情況不作判斷。

表1 等權(quán)值算法和優(yōu)化的等權(quán)值算法測(cè)試向量集

4 算法的綜合優(yōu)化

基于以上分析，本文提出了一種綜合考慮線或、線與短路故障的優(yōu)化算法。算法的主要思路是基于等權(quán)值算法的兩重優(yōu)化，由于等權(quán)值算法能檢測(cè)固定故障，且是零誤判的［8］，所以這里只需考慮混淆率和緊湊性。首先針對(duì)等權(quán)值算法，當(dāng)緊湊性相同時(shí)，將權(quán)值適當(dāng)降低，來降低故障率；另外針對(duì)線或短路和線與短路，按照走位1 算法在等權(quán)值算法STV 矢量后先加載P/2 個(gè)矢量，再按走位0 算法施加P/2個(gè)矢量。

4.1 等權(quán)值算法的優(yōu)化

在很多情況下，當(dāng)網(wǎng)絡(luò)數(shù)量一定時(shí)，通過等權(quán)值算法產(chǎn)生測(cè)試矢量，我們發(fā)現(xiàn)，權(quán)值可以適當(dāng)?shù)男∮趞P/2|（這里定義|P/2|≤P/2，且為整數(shù)），這種測(cè)試矢量也能滿足要求。如當(dāng)網(wǎng)絡(luò)為N=12 時(shí)，P=6，此時(shí)權(quán)值一般默認(rèn)為P/2=3，但實(shí)際上權(quán)值為2 也是可行的。

表2 網(wǎng)絡(luò)N=12時(shí)，兩種算法的測(cè)試矢量

采用固定故障模型，對(duì)兩種算法進(jìn)行模擬仿真，得出表3結(jié)果。

表3 等權(quán)值算法和降權(quán)值的等權(quán)值算法權(quán)值與混淆率

由表3 可知，降權(quán)值的等權(quán)值算法在一定程度下降低了故障混淆率，此外從表中也可以看出在某些情況，即當(dāng)時(shí)，權(quán)值是不可降低的，如N=16時(shí)，兩算法權(quán)值均為3。

降權(quán)值等權(quán)值算法實(shí)現(xiàn)流程如下：

圖1 降低權(quán)值的等權(quán)值算法實(shí)現(xiàn)流程（其中q為權(quán)值）

4.2 綜合考慮的優(yōu)化算法

在4.1 節(jié)中降低權(quán)值的優(yōu)化算法，其故障率還是比較高。為了繼續(xù)降低可能出現(xiàn)混淆的概率，按照文獻(xiàn)［4］的思路，考慮到走步1與走步0算法原理相同，且是分別針對(duì)線或和線與故障的完備算法［9］，在降權(quán)值的等權(quán)值算法STV后附加|P/2|個(gè)走步1算法向量，再附加|P/2|個(gè)走步0 算法向量。網(wǎng)絡(luò)數(shù)為12 時(shí)，綜合考慮的優(yōu)化算法產(chǎn)生的測(cè)試向量集如表4所示。

表4 N=12時(shí)，綜合考慮的優(yōu)化算法測(cè)試向量集

4.2.1 故障混淆率分析

綜合考慮的優(yōu)化算法同時(shí)考慮兩種短路混淆故障，依次附加了一定的走步1 和走步0 算法。一方面，附加向量的出現(xiàn)會(huì)大幅度降低整體故障率；而另一方面由于附加走步算法向量長(zhǎng)度明顯小于網(wǎng)絡(luò)數(shù)N，則必然會(huì)循環(huán)性地施加相同向量，這會(huì)降低STV 后面走步算法對(duì)混淆故障的檢測(cè)。表5為等權(quán)值算法，文獻(xiàn)［6］中優(yōu)化的等權(quán)值算法以及綜合優(yōu)化的等權(quán)值算法的混淆率。

表5 三種算法的混淆率比較

由表5 可知，綜合優(yōu)化的等權(quán)值算法雖不能做到完全排除混淆故障，但相比較其他算法，也是大幅度地降低了混淆率，而且當(dāng)網(wǎng)絡(luò)數(shù)越大，抗混淆能力越強(qiáng)。

4.2.2 緊湊性分析

綜合優(yōu)化算法的緊湊性指標(biāo)為P+2|P/2|，當(dāng)P為偶數(shù)時(shí)，指標(biāo)為2P；P 為奇數(shù)時(shí)，指標(biāo)為2P-1。表6為幾種算法緊湊性的比較。

表6 不同算法緊湊性指標(biāo)比較

表6 顯示的緊湊性指標(biāo)，盡管綜合優(yōu)化的等權(quán)值算法相比較等權(quán)值算法較大，大約為其兩倍，為優(yōu)化的等權(quán)值算法的1.5 倍，但是和走步算法相比是非常小的。

5 結(jié)語

本文在等權(quán)值研究的基礎(chǔ)上，相比較傳統(tǒng)算法而言，將W-O 短路和W-A 短路同時(shí)納入進(jìn)去，提出了綜合考慮的優(yōu)化降權(quán)值算法，從緊湊性以及混淆率分別進(jìn)行分析并折衷考慮，得出該算法是一種非常實(shí)用的算法。