邊界掃描測試算法的分析與優化

楊迪珂，顏學龍

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

邊界掃描測試算法的分析與優化

楊迪珂，顏學龍

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

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

邊界掃描；測試算法；測試矢量；優化

0 引言

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

目前相關的算法很多，各有其優缺點[2]。本文在分析了多個常用測試算法的基礎上，提出了等權值算法和二進制計數算法的優化，優化后的算法權衡了緊湊型指標和完備性指標，并降低了故障可能出現的概率，具有一定的實際意義。

1 故障模型介紹

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

1.1 固定邏輯故障

也稱呆滯故障，表現為電路或系統中某一個或多個網絡的不可控制性，即網絡的邏輯狀態不受輸出節點的控制，系統在運行過程中始終固定在“1”或“0”電平上。

1.2 短路故障

也稱橋接故障，即兩個或多個網絡之間的連接造成短路故障。短路故障的原理很簡單反而情況很復雜，如果一個電路或系統中發生了短路故障，則很有可能改變整體電路的結構，導致電路或系統的基本功能發生根本性質的變化，所以對電路中短路故障的檢測與診斷也變得十分困難和關鍵。

1.3 時滯故障

電路或系統中信號的動態故障變化，也就是電路中各元件的延時變化，脈沖信號的邊沿參數的變化等等。

1.4 暫態故障

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

由于種類和數目的不同，各種故障模型在實物電路中都是千變萬化的。根據有關資料統計，在可能產生的故障中，固定邏輯故障產生的概率占故障總數的90%以上，因此研究針對這兩者的測試算法變得非常有必要[4]。

2 一些基本概念

邊界掃描測試技術：測試實質上是在芯片管腳和內部邏輯電路之間增加由移位寄存器構成的邊界掃描單元，實現對芯片管腳狀態的設定和讀取，使管腳具有可控性和可觀測性[5]。

(1)

(2)

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

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

3 測試算法

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

當故障征兆存在時，影響測試向量集對所有故障進行準確定位的原因主要是由于存在兩類問題:征兆誤判問題和征兆混淆問題，所以征兆誤判率γa和征兆混淆率γc是測試故障診斷能力的重要指標。

3.1 測試向量生成算法

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

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

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

3.2 自適應測試算法

自適應測試算法的思想是：首先用快速算法較快發現電路中可能存在的故障；然后追加少量的測試向量集準確判斷故障的類型和位置。

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

W自適應算法同樣是由P.Goel和M.T.McMahon提出，第一步與One-Step算法相同，第二步則改為用走步算法在可能出現故障的網絡上進行測試。W算法能夠檢測所以故障誤判和混淆，但是算法需要的PTV較大，緊湊型指標不理想。

NajmiJarwala和C.W.Yau等人后來提出C自適應算法。算法對所有可能發生混淆的網絡采用走步算法進行測試，而對所有可能發生誤判的網絡采用One-Step算法進行測試，C算法是對W算法的改進。

4 算法優化

影響算法精度最主要的原因是征兆誤判和混淆。根據相關資料的統計，在實際的應用中，誤判出現的幾率明顯大于混淆出現的概率，而且單一故障出現的概率明顯大于多故障出現的概率，因此我們的思想是希望能夠構造一個緊湊型指標最優并且能夠明顯減少誤判出現的一組測試向量集。

4.1 等權值算法的優化

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

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

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

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

表2 MCSA和等權值算法的誤判率和混淆率

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

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

表3 等權值優化算法的測試向量集

4.2 二進制計數算法的優化

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

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

測試向量集的對角獨立性原則：矩陣本身經過多次行/列變換后可以得到對角獨立矩陣的測試向量集能夠檢測所有故障。

相異性指標的計算根據上述公式，相異性的概念是指相異性指標越大的測試向量集出現征兆誤判和征兆混淆的概率越低。因此所構造的同一組向量之間的向量需盡可能具備對角獨立性而且相異性指標盡量夠大。

表4 二進制計數算法和權值遞加算法的測試向量集

5 算法分析

5.1 等權值優化算法

等權值優化算法的測試向量集如上表3所示，新的算法的緊湊型指標為p+p/2，與等權值算法相比，緊湊型指標雖然提高了，但是也明顯低于走步算法。表格5是比較在不同網絡數下走步算法、等權值優化算法和等權值算法的緊湊性指標。

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

表6 等權值優化算法的征兆誤判率和征兆混淆率

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

5.2 權值遞加算法

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

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

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

表8 權值遞加算法的征兆誤判率和征兆率

6 結語

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

工藝的提升使得集成電路與芯片朝著超微型化、超復雜化的方向發展[11]。隨著邊界掃描硬件與系統的升級，新的標準和新的算法也在層出不窮的出現，更加優質的的算法將是下一步的研究方向。

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

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

[3] 徐 丹，楊新環，晏新晃. 邊界掃描測試優化算法[J]. 計算機工程, 2009,35(20):255-257.

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

[5] 徐建潔，李 岳，胡 政.邊界掃描測試系統軟件設計與實現[J].計算機測量與控制,2006(7):975-977.

[6] 譚劍波, 尤 路, 黃 新,等. 邊界掃描測試技術[M].北京：國防工業出版社, 2013.

[7] 劉 靜.邊界掃描測試算法和BIST技術的研究與實現[D]. 南京: 南京航空航天大學, 2010.

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

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

[10] 段軍棋. 基于邊界掃描的測試算法和BIST設計技術研究[D].成都: 電子科技大學, 2004.

[11] 潘金海,顏學龍.基于1149.7標準的測試生成方法研究[J].計算機測量與控制,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-)，男，碩士研究生，主要從事可測型設計與測試應用方向的研究。

顏學龍(1964-)，男，碩士研究生導師，教授，主要從事可測性設計與故障診斷、測試信號處理等方向的研究。

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

TP

A