楊迪珂，顏學(xué)龍

(桂林電子科技大學(xué) 電子工程與自動(dòng)化學(xué)院，廣西 桂林 541004)

邊界掃描測(cè)試算法的分析與優(yōu)化

楊迪珂，顏學(xué)龍

(桂林電子科技大學(xué) 電子工程與自動(dòng)化學(xué)院，廣西 桂林 541004)

伴隨著電子技術(shù)和邊界掃描測(cè)試技術(shù)的飛速發(fā)展，新的邊界掃描測(cè)試算法也在不斷涌現(xiàn)；而邊界掃描測(cè)試的算法，一般都是指在互聯(lián)模型的基礎(chǔ)上，邊界掃描測(cè)試向量的生成算法；生成合理的測(cè)試向量集可以以最短的測(cè)試時(shí)間來覆蓋盡可能多的故障；從對(duì)一些常用的邊界掃描測(cè)試算法進(jìn)行了粗略的分析，到后來對(duì)等權(quán)值算法和二進(jìn)制計(jì)數(shù)算法進(jìn)行了詳細(xì)的分析，通過引入和分析邊界掃描測(cè)試算法的定理、公式以及推論等，分別提出了等權(quán)值優(yōu)化算法和權(quán)值遞加算法；與優(yōu)化前的算法作為比較，等權(quán)值優(yōu)化算法降低了征兆混淆出現(xiàn)的概率，而權(quán)值遞加算法同時(shí)降低了征兆誤判率和征兆混淆率；綜合分析，新的算法更好的權(quán)衡了測(cè)試向量集的完備性指標(biāo)和緊湊型指標(biāo)。

邊界掃描；測(cè)試算法；測(cè)試矢量；優(yōu)化

0 引言

伴隨著高密度、大規(guī)模集成電路的迅速發(fā)展，傳統(tǒng)的測(cè)試手段已經(jīng)很難滿足測(cè)試的要求[1]，邊界掃描技術(shù)的出現(xiàn)很大程度上解決了這一技術(shù)難題。由于測(cè)試時(shí)間、故障覆蓋率以及故障定位精度的要求, 測(cè)試生成算法也存在優(yōu)化的問題[2]。測(cè)試矢量集的大小及其故障覆蓋率直接影響測(cè)試的時(shí)間和效果、故障覆蓋率高、診斷準(zhǔn)確的測(cè)試矢量，一直是算法測(cè)試研究的目標(biāo)和方向[3]。

目前相關(guān)的算法很多，各有其優(yōu)缺點(diǎn)[2]。本文在分析了多個(gè)常用測(cè)試算法的基礎(chǔ)上，提出了等權(quán)值算法和二進(jìn)制計(jì)數(shù)算法的優(yōu)化，優(yōu)化后的算法權(quán)衡了緊湊型指標(biāo)和完備性指標(biāo)，并降低了故障可能出現(xiàn)的概率，具有一定的實(shí)際意義。

1 故障模型介紹

在介紹和分析測(cè)試算法之前需要了解電路和系統(tǒng)中可能存在的故障模型，一般電路中可能存在的典型故障模型包括四種：

1.1 固定邏輯故障

也稱呆滯故障，表現(xiàn)為電路或系統(tǒng)中某一個(gè)或多個(gè)網(wǎng)絡(luò)的不可控制性，即網(wǎng)絡(luò)的邏輯狀態(tài)不受輸出節(jié)點(diǎn)的控制，系統(tǒng)在運(yùn)行過程中始終固定在“1”或“0”電平上。

1.2 短路故障

也稱橋接故障，即兩個(gè)或多個(gè)網(wǎng)絡(luò)之間的連接造成短路故障。短路故障的原理很簡(jiǎn)單反而情況很復(fù)雜，如果一個(gè)電路或系統(tǒng)中發(fā)生了短路故障，則很有可能改變整體電路的結(jié)構(gòu)，導(dǎo)致電路或系統(tǒng)的基本功能發(fā)生根本性質(zhì)的變化，所以對(duì)電路中短路故障的檢測(cè)與診斷也變得十分困難和關(guān)鍵。

1.3 時(shí)滯故障

電路或系統(tǒng)中信號(hào)的動(dòng)態(tài)故障變化，也就是電路中各元件的延時(shí)變化，脈沖信號(hào)的邊沿參數(shù)的變化等等。

1.4 暫態(tài)故障

暫態(tài)故障包括兩種類型：瞬態(tài)故障和間歇性故障。瞬態(tài)故障是由電源干擾和粒子輻射等原因造成的。間歇性故障是由元件參數(shù)的變化、溫度和濕度等其它外部環(huán)境原因等。

由于種類和數(shù)目的不同，各種故障模型在實(shí)物電路中都是千變?nèi)f化的。根據(jù)有關(guān)資料統(tǒng)計(jì)，在可能產(chǎn)生的故障中，固定邏輯故障產(chǎn)生的概率占故障總數(shù)的90%以上，因此研究針對(duì)這兩者的測(cè)試算法變得非常有必要[4]。

2 一些基本概念

邊界掃描測(cè)試技術(shù)：測(cè)試實(shí)質(zhì)上是在芯片管腳和內(nèi)部邏輯電路之間增加由移位寄存器構(gòu)成的邊界掃描單元，實(shí)現(xiàn)對(duì)芯片管腳狀態(tài)的設(shè)定和讀取，使管腳具有可控性和可觀測(cè)性[5]。

(1)

(2)

向量的權(quán)值(H)：對(duì)于向量vi={v1,v2,...}，若向量中第一個(gè)為“1”的位為vl，則定義權(quán)值：HW(vi)=l[10]。

緊湊型問題：測(cè)試向量的個(gè)數(shù)(P)，也就是測(cè)試的時(shí)間。完備性問題：測(cè)試向量集的故障診斷能力，也就是故障定位的精度以及故障覆蓋率等問題。

3 測(cè)試算法

邊界掃描測(cè)試算法也就是測(cè)試向量集的生成算法，測(cè)試向量集的選擇會(huì)直接影響邊界掃描測(cè)試結(jié)果的輸出，我們把測(cè)試向量集檢測(cè)故障的能力稱為故障分辨力[6]。那么怎樣判斷一個(gè)測(cè)試算法的故障分辨力？這就需要引入兩個(gè)概念。

當(dāng)故障征兆存在時(shí)，影響測(cè)試向量集對(duì)所有故障進(jìn)行準(zhǔn)確定位的原因主要是由于存在兩類問題:征兆誤判問題和征兆混淆問題，所以征兆誤判率γa和征兆混淆率γc是測(cè)試故障診斷能力的重要指標(biāo)。

3.1 測(cè)試向量生成算法

最常見的算法是基于STV的測(cè)試向量生成算法，一般情況下這一類的算法能夠快速發(fā)現(xiàn)線路故障，但是出現(xiàn)征兆誤判率和征兆混淆率的概率還是比較高。

二進(jìn)制計(jì)數(shù)算法(CSA算法)于1974年Kautz在IEEE計(jì)算機(jī)學(xué)報(bào)上首次提出，但是存在比較嚴(yán)重的誤判和混淆而且無法覆蓋開路故障。于是后來在1982年Goel和McMahon提出了改良計(jì)數(shù)序列算法(MCSA算法)，算法在單一故障模型下更夠檢測(cè)故障，但是也存在一定的誤判和混淆問題[8]。

在1987年Wagner提出計(jì)數(shù)補(bǔ)償算法，Wagner算法在MCSA算法的基礎(chǔ)上增加了互補(bǔ)向量集，提高了定位故障的能力，但是無法避免故障混淆等問題。包括后來提出的走步算法(Walk算法)，算法能夠檢測(cè)所有短路故障和呆滯故障，但明顯的缺點(diǎn)是需要大量的測(cè)試向量導(dǎo)致測(cè)試時(shí)間過長(zhǎng)，在一些測(cè)試中很難直接應(yīng)用。

3.2 自適應(yīng)測(cè)試算法

自適應(yīng)測(cè)試算法的思想是：首先用快速算法較快發(fā)現(xiàn)電路中可能存在的故障；然后追加少量的測(cè)試向量集準(zhǔn)確判斷故障的類型和位置。

One-Step自適應(yīng)算法由NajmiJarwala和C.W.Yau提出，算法第一步生成一個(gè)測(cè)試向量集(比如MCSA)，快速發(fā)現(xiàn)故障問題，第二步在可能認(rèn)為被誤判的網(wǎng)絡(luò)上加載“1”，其他網(wǎng)絡(luò)加載“0”，不過此算法只能檢測(cè)故障誤判，不能檢測(cè)故障混淆。

W自適應(yīng)算法同樣是由P.Goel和M.T.McMahon提出，第一步與One-Step算法相同，第二步則改為用走步算法在可能出現(xiàn)故障的網(wǎng)絡(luò)上進(jìn)行測(cè)試。W算法能夠檢測(cè)所以故障誤判和混淆，但是算法需要的PTV較大，緊湊型指標(biāo)不理想。

NajmiJarwala和C.W.Yau等人后來提出C自適應(yīng)算法。算法對(duì)所有可能發(fā)生混淆的網(wǎng)絡(luò)采用走步算法進(jìn)行測(cè)試，而對(duì)所有可能發(fā)生誤判的網(wǎng)絡(luò)采用One-Step算法進(jìn)行測(cè)試，C算法是對(duì)W算法的改進(jìn)。

4 算法優(yōu)化

影響算法精度最主要的原因是征兆誤判和混淆。根據(jù)相關(guān)資料的統(tǒng)計(jì)，在實(shí)際的應(yīng)用中，誤判出現(xiàn)的幾率明顯大于混淆出現(xiàn)的概率，而且單一故障出現(xiàn)的概率明顯大于多故障出現(xiàn)的概率，因此我們的思想是希望能夠構(gòu)造一個(gè)緊湊型指標(biāo)最優(yōu)并且能夠明顯減少誤判出現(xiàn)的一組測(cè)試向量集。

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

以MCSA算法為例，征兆誤判率和混淆率的計(jì)算根據(jù)公式(1)和公式(2)，這里可以采用固定的故障模型，利用計(jì)算機(jī)對(duì)所有可能出現(xiàn)的固定邏輯故障進(jìn)行模擬得出結(jié)果。

抗誤判定理：測(cè)試向量集V不出現(xiàn)征兆誤判的充分條件是：存在vi∈V，而且測(cè)試向量集V最多只能包含一個(gè)不同于vi的向量vj[7]。推論：某個(gè)測(cè)試向量集不出現(xiàn)征兆誤判的充分條件是，測(cè)試向量集中的任何一個(gè)向量均不能包含另一個(gè)向量[7]。

根據(jù)抗誤判定理的推論，而對(duì)于任何布爾向量vi和vj，如果vi被vj所包含，則vi的權(quán)值大于vj的權(quán)值。那么如果權(quán)值q相同的兩個(gè)向量，它們一定不存在相互包含的關(guān)系。由此可以構(gòu)造一個(gè)測(cè)試向量集，測(cè)試向量集中的向量具有相同的權(quán)值，而且他們各不相同，可以選定向量的權(quán)值q=p/2。等權(quán)值算法測(cè)試向量集如下表1所示。MCSA算法和等權(quán)值算法的征兆誤判率和征兆混淆率如表2所示[4]。

表1 等權(quán)值算法的測(cè)試向量集(N=10，p=5)

表2 MCSA和等權(quán)值算法的誤判率和混淆率

等權(quán)值算法在一定程度上消除了征兆誤判的出現(xiàn)，但是征兆混淆的概率還是比較高，而征兆混淆主要發(fā)生在相似的STV之間。根據(jù)表1，網(wǎng)絡(luò)N3、網(wǎng)絡(luò)N7短路與網(wǎng)絡(luò)N4、網(wǎng)絡(luò)N6短路的SRV完全相同(都是11011)，因此不能準(zhǔn)確判斷到底是N3和N7發(fā)生故障還是N4和N6發(fā)生故障。為了減少可能出現(xiàn)混淆的概率，可以選擇通過犧牲測(cè)試向量集的緊湊型來提高它的完備性[7]。

因此可以在STV里面增加不同的補(bǔ)充向量來減少混淆出現(xiàn)的情況。為了盡可能的區(qū)分相似的STV和滿足向量的緊湊性指標(biāo)要求，補(bǔ)充向量的個(gè)數(shù)不能太多，在這里可以將補(bǔ)充的向量個(gè)數(shù)選定為p/2。測(cè)試向量集的權(quán)值越小，發(fā)生故障混淆的可能性越低[7]。根據(jù)此推論可以選擇將走步“1”算法作為補(bǔ)充的向量。改進(jìn)后的等權(quán)值算法測(cè)試向量集如表2所示，其中n=10，p=7。

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

4.2 二進(jìn)制計(jì)數(shù)算法的優(yōu)化

二進(jìn)制計(jì)數(shù)算法(CSA算法)的測(cè)試向量集是由從0開始遞加的一系列二進(jìn)制數(shù)字序列組成，CSA算法可以檢測(cè)出線網(wǎng)故障，但是存在過多的相似測(cè)試向量集從而導(dǎo)致誤判率和混淆率都比較高[6]。算法的優(yōu)化可以考慮將遞加加載到權(quán)值上，構(gòu)成新的權(quán)值遞加算法，具體方法如下：

一般情況下，征兆誤判率和征兆混淆率的發(fā)生主要是在相似的測(cè)試向量之間，為了避免相似測(cè)試向量之間的誤判和混淆可以將相似的測(cè)試向量進(jìn)行分組，選擇分組個(gè)數(shù)m=p/2+1(p為二進(jìn)制計(jì)數(shù)算法的緊湊性指標(biāo))，每個(gè)組之間具有相同的權(quán)值，第一個(gè)組中的所有向量權(quán)值都為1，第二個(gè)組中的所有向量權(quán)值都為2，以此類推。而相同組之間的測(cè)試向量集可以根據(jù)如下對(duì)角獨(dú)立性原則和相異性概念來確定。

測(cè)試向量集的對(duì)角獨(dú)立性原則：矩陣本身經(jīng)過多次行/列變換后可以得到對(duì)角獨(dú)立矩陣的測(cè)試向量集能夠檢測(cè)所有故障。

相異性指標(biāo)的計(jì)算根據(jù)上述公式，相異性的概念是指相異性指標(biāo)越大的測(cè)試向量集出現(xiàn)征兆誤判和征兆混淆的概率越低。因此所構(gòu)造的同一組向量之間的向量需盡可能具備對(duì)角獨(dú)立性而且相異性指標(biāo)盡量夠大。

表4 二進(jìn)制計(jì)數(shù)算法和權(quán)值遞加算法的測(cè)試向量集

5 算法分析

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

等權(quán)值優(yōu)化算法的測(cè)試向量集如上表3所示，新的算法的緊湊型指標(biāo)為p+p/2，與等權(quán)值算法相比，緊湊型指標(biāo)雖然提高了，但是也明顯低于走步算法。表格5是比較在不同網(wǎng)絡(luò)數(shù)下走步算法、等權(quán)值優(yōu)化算法和等權(quán)值算法的緊湊性指標(biāo)。

表5 三種算法的緊湊型比較

表6 等權(quán)值優(yōu)化算法的征兆誤判率和征兆混淆率

表格6是采用固定的故障模型，進(jìn)行模擬得出的征兆誤判率和征兆混淆率。與表2相比較，新的算法繼承了等權(quán)值算法的低征兆誤判率，并在一定程度上降低了征兆混淆率。

5.2 權(quán)值遞加算法

權(quán)值遞加算法的測(cè)試向量集如上表4所示，算法的緊湊性為p+1，緊湊性略大于二進(jìn)制計(jì)數(shù)算法，但明顯低于走步“1”算法。算法緊湊性的比較如下表7所示。

表7 三種算法的緊湊型比較

算法征兆誤判率和征兆混淆率同如表8所示。根據(jù)表8可以看出，與二進(jìn)制計(jì)數(shù)算法相比新的算法在一定程度上可避免征兆誤判的出現(xiàn)，而且降低了征兆混淆率。

表8 權(quán)值遞加算法的征兆誤判率和征兆率

6 結(jié)語(yǔ)

本文首先通過對(duì)電路中故障模型和一些基本概念的介紹從而引入邊界掃描測(cè)試算法。對(duì)一些常見的邊界掃描算法進(jìn)行了介紹和分析，并選擇了兩種常用算法對(duì)其進(jìn)行詳細(xì)的分析和優(yōu)化，對(duì)比之前的算法，優(yōu)化后的兩種算法更好的權(quán)衡了測(cè)試向量集的緊湊性指標(biāo)和完備性指標(biāo)。

工藝的提升使得集成電路與芯片朝著超微型化、超復(fù)雜化的方向發(fā)展[11]。隨著邊界掃描硬件與系統(tǒng)的升級(jí)，新的標(biāo)準(zhǔn)和新的算法也在層出不窮的出現(xiàn)，更加優(yōu)質(zhì)的的算法將是下一步的研究方向。

[1]ZhangZhaobo，WangZhanglei，GuXinli，etal.Board-levelfaultdiagnosisusinganerror-flowdictionary[A].ProceedingsInternationalTestConference[C]． 2010: 1-10．

[2] 陳圣儉,等.邊界掃描測(cè)試生成算法優(yōu)化問題[J].電子測(cè)量與儀器學(xué)報(bào),2006,20(4):73-76.

[3] 徐 丹，楊新環(huán)，晏新晃. 邊界掃描測(cè)試優(yōu)化算法[J]. 計(jì)算機(jī)工程, 2009,35(20):255-257.

[4] 孫媛媛.FPGA的邊界掃描測(cè)試方法研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2004.

[5] 徐建潔，李 岳，胡 政.邊界掃描測(cè)試系統(tǒng)軟件設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)測(cè)量與控制,2006(7):975-977.

[6] 譚劍波, 尤 路, 黃 新,等. 邊界掃描測(cè)試技術(shù)[M].北京：國(guó)防工業(yè)出版社, 2013.

[7] 劉 靜.邊界掃描測(cè)試算法和BIST技術(shù)的研究與實(shí)現(xiàn)[D]. 南京: 南京航空航天大學(xué), 2010.

[8]P.Goel,M.T.McMahon.ElectronicChip-in-placeTest[A].ProceedingsInternationalTestConference[C].IEEE.1982:126-137.

[9] 胡 政, 溫熙林. 邊界掃描測(cè)試生成的數(shù)學(xué)基礎(chǔ)[J]. 工程數(shù)學(xué)基礎(chǔ), 2008,25(2):204-210.

[10] 段軍棋. 基于邊界掃描的測(cè)試算法和BIST設(shè)計(jì)技術(shù)研究[D].成都: 電子科技大學(xué), 2004.

[11] 潘金海,顏學(xué)龍.基于1149.7標(biāo)準(zhǔn)的測(cè)試生成方法研究[J].計(jì)算機(jī)測(cè)量與控制,2016,24(8):5-8.

Analysis and Optimization of Boundary Scan Test Algorithm

Yang Dike，Yan Xuelong

(School of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin 541004, China)

Along with the rapid development of electronic technology and boundary scan test technology, some new boundary scan test algorithms have emerged.The boundary scan test algorithm generally refers to the test vector generation algorithm of boundary scan test technology which is on the basis of the interconnection model. Generate reasonable test vector set can cover the failure as much as possible in the shortest time.Some commonly used test algorithms are analyzed,And then analyzed two kinds of commonly used algorithm: Equal Weight Algorithm and CSA.Through the analysis of boundary scan test algorithm, formula and theorem inference, then proposed two kinds of algorithms:Equal Weight Optimization Algorithm and Weight Increment Algorithm.Compared with the pre-algorithm,the Equal Weight Optimization Algorithm reduces the probability of the appearance of the symptom confusion; and The Weight Increment Algorithm reducing confusion rate and error rate of the symptoms and signs.Generally,the new algorithm improves the completeness and compactness of test vectors.

boundary scan; test algorithm;test vector;optimization

2016-10-31；

2016-12-19。

楊迪珂(1990-)，男，碩士研究生，主要從事可測(cè)型設(shè)計(jì)與測(cè)試應(yīng)用方向的研究。

顏學(xué)龍(1964-)，男，碩士研究生導(dǎo)師，教授，主要從事可測(cè)性設(shè)計(jì)與故障診斷、測(cè)試信號(hào)處理等方向的研究。

1671-4598(2017)05-0004-03DOI：10.16526/j.cnki.11-4762/tp

TP

A