一種基于FDR的高測試質量測試壓縮方法

尤志強，胡 娜

(湖南大學 信息科學與工程學院，湖南 長沙 410082)

一種基于FDR的高測試質量測試壓縮方法

尤志強?，胡 娜

(湖南大學 信息科學與工程學院，湖南 長沙 410082)

FDR編碼方法有效地降低了測試數(shù)據(jù)量，但其測試集中的無關位全部填充為0，平均每個測試向量檢測的故障數(shù)目較少，測試質量較低.為了提高測試質量，并進一步提高測試數(shù)據(jù)壓縮率，本文基于FDR方法提出了一種利用上一個測試向量的響應填充該測試向量中無關位的測試壓縮方法.該填充方法提高了測試向量中無關位填充的隨機性，從而提高了測試集的測試質量.提出方法的壓縮效率與測試向量的順序有關，基于最近鄰居算法對測試集進行排序，降低了測試響應與下一個測試向量之間不相同的位數(shù)，對測試響應和測試向量差分處理后再進行FDR編碼，從而降低了測試數(shù)據(jù)量.ISCAS’89電路中幾個大電路的實驗結果表明，與FDR相比該方法的測試質量平均提高了5.9%，測試數(shù)據(jù)壓縮率平均提高了2.5%，而只需要增加一個異或門的硬件開銷.

測試質量；測試數(shù)據(jù)壓縮；無關位；FDR編碼

隨著超大規(guī)模集成(VLSI)電路制造工藝的不斷進步，越來越多的知識產權(IP)核被集成到一個芯片上，測試數(shù)據(jù)量急劇增長.龐大的測試數(shù)據(jù)對昂貴自動測試設備(ATE)的存儲性能、I/O通道數(shù)和頻率提出更高的要求，同時增加了測試應用時間，提高了測試成本.因此，如何降低測試成本成為集成電路(IC)測試的一個重要研究課題.

測試數(shù)據(jù)壓縮方法能夠有效地減少測試數(shù)據(jù)量，降低存儲和測試設備數(shù)據(jù)傳輸通道數(shù)量的需求.同時，經過適當設計，還可以降低測試應用時間和測試功耗.目前，測試數(shù)據(jù)壓縮技術主要有3大類：1)線性解壓方案[1-2]；2)基于廣播式掃描的方案[3]；3)基于編碼的壓縮方案[4-7].

許多編碼壓縮方法利用測試集中的無關位X.FDR[4]是一種0游程編碼，X都被填充為0以增加0游程的長度.文獻[5]提出了一種EFDR編碼，通過添加一個區(qū)分位，同時對0游程和1游程編碼.文獻[6]提出了交替游程編碼，不需要添加區(qū)分位，對0游程和1游程交替編碼，不僅能降低測試數(shù)據(jù)量還能減少測試功耗.在文獻[7]中，測試集被分成等長的數(shù)據(jù)塊，使用動態(tài)參考向量機制，利用前一塊的信息對后一塊數(shù)據(jù)進行編碼.

在FDR編碼中，無關位X都被填充為0，雖然提高了測試數(shù)據(jù)壓縮率，但這種填充方式，使得測試向量中0的比率很高，平均每個測試向量檢測的故障數(shù)目較少，降低了測試集的測試質量[8].

1 測試壓縮方案和解壓縮結構

通常測試集中無關位X的比率較高，而測試質量與測試向量無關位填充方式有關.通常來說，測試向量中無關位的填充值隨機性越好，測試質量越高.為了提高測試質量，我們考慮到測試向量和測試響應的相關性較弱，在新的測試壓縮方案中，測試向量的無關位不再全部填充為0，而是根據(jù)前一個測試向量的響應值來填充下一個測試向量的無關位.

例1 在圖1(a)中有3個測試向量和對應的測試響應，首先倘若把第一個測試向量無關位填充為0，故障模擬后得到測試響應r1′，然后根據(jù)r1′填充測試向量t2中的X，故障模擬后得到測試響應r2′，再根據(jù)r2′填充測試向量t3中的X，故障模擬后得到測試響應r3′.填充無關位后的測試向量和測試響應如圖1(b)所示.與圖1(a)中測試向量的無關位全部填充為0相比，圖1(b)中測試向量每位的取值隨機性較好，通常可以獲得更高的測試質量.

測試向量和響應測試向量和響應差分向量t1 1xx1xxxx0t′1 100100000c1 100100000r1 1xx10xxxxr′1 100100001t2 1xxx1xxxxt′2 100110001c2 000010000r2 xxxx110x0r′2 010011010t3 1x0xx1xx1t′3 110001011c3 100010001r3 x11xx1xxxr′3 011001000(a)(b)(c)

圖1 無關位填充舉例

Fig.1 Example for X-filling

使用這種方法填充無關位的測試集中1的個數(shù)必然會增加，直接FDR編碼后的測試壓縮率也必然會降低.為了提高測試壓縮率，我們將對前一個的測試響應和根據(jù)它填充無關位的下一個測試向量做差分，形成差分向量.最后，再對差分向量集使用FDR編碼.

例2 圖1(b)給出了用提出方案填充的測試向量及對應的測試響應.假定觸發(fā)器中的初始狀態(tài)為全0，第一個差分向量c1為第一個測試向量和全0的差分，結果與第一個測試向量相同.我們分別對r1′和t2′及r2′和t3′做差分得到差分向量c2和c3，差分向量集如圖1(c)所示.可以看出，該差分向量集中確定位1的位數(shù)由原始測試向量集中的7位降為6位.0填充FDR編碼后為00 1000 1011 1001 1010 1010 1000，共26位；而差分向量集進行FDR編碼后為00 1000 110011 1010 1001 1001，共24位，差分向量集進行FDR編碼后得到較短的編碼，提高了測試壓縮率.

解壓縮過程與前述壓縮過程相反.解壓縮結構如圖2所示，由一個FDR解碼器和一個二輸入異或門組成.TE代表FDR編碼后的測試數(shù)據(jù)，經FDR解碼器解壓還原成差分向量集Tdiff，Tdiff中的差分向量經過異或門與掃描鏈中保存的上一個測試向量的響應異或，恢復用提出方法填充無關位的測試集TD.由此可見，與FDR編碼方法的解壓縮結構相比，提出方法只多了一個二輸入異或門，其額外的硬件開銷可以忽略不計.

圖2 解壓縮電路結構

差分向量中1的個數(shù)與做差分的測試響應和測試向量不相容的位數(shù)相關.對應位中有一位為X或者兩位相同時，我們稱這兩位是相容的，否則是不相容的.不同的測試向量順序，差分向量中1的總個數(shù)有所不同.因此，測試向量重排序可以進一步提高測試壓縮效率.

2 測試向量/響應重排序方法

本節(jié)針對帶無關位的測試集進行排序.對于相鄰的測試向量和每個觸發(fā)器，我們將測試響應和測試向量對RTP用(rik,tjk)表示，其中k為觸發(fā)器編號.差分向量中對應的位為RTP中rik與tjk的差分.如果RTP為(0,0), (1,1) ，則差分向量中對應的位為0；而如果為(1,0), (0,1)，對應的位為1.對于 (0,X) ，(1,X)通過填充X為其對應的響應值，其差分向量對應的位為0；而對于 (X,0), (X,1)，如果同時將多個響應中的X填為其測試向量值，有可能產生矛盾.因此，我們不能簡單地用它們之間不相容的位數(shù)來計算差分向量中1的個數(shù).如果RTP為(X,X)，可以先確定測試響應中的X，再用該值將測試向量中的X填充，其差分向量對應的位為0.注意到，雖然RTP為(0,0), (1,1)和 (0,X), (1,X), (X,X)時其差分向量對應的位為0，在排序中若優(yōu)先考慮(0,0), (1,1)的情況，可以獲得較好的壓縮效果，應該為其分配更佳的權值.表1為權值表，R代表響應值，T代表測試向量值，表中為具體RTP的權值.如，w0,1是為(0,1)分配的權值.

表1 權值表

定義1 兩個向量的距離d(ti,tj)或dij為每個觸發(fā)器的測試響應和測試向量對RTP權值的總和.

(1)

其中Nff是觸發(fā)器的個數(shù).由于權值表不對稱，d(ti,tj)與d(ti,tj)不一定相同.

例3 假設測試向量ti的響應ri=110XX，測試向量tj=10XX0，由式(1)，假設w1,1=w0,0=-20，w1,0=w0,1=20，w1,X=w0,X=wX,X=-0.5，wX,1=wx,0=0.5，它們之間的距離d(ti,tj)=-20+20+(-0.5)+(-0.5) +0.5=-0.5.

定義2 差分距離圖G=(V,A)是一個有向完全圖， 其中V是一個節(jié)點集，每個節(jié)點對應于一個測試向量，A是一個有向邊集，每條邊的權是始點和終點對應測試向量的距離.

例4 如圖1(a)所示的3個測試向量t1，t2，t3，和它們的測試響應r1，r2，r3.可以建立如圖3所示的差分距離圖，該圖包括3個節(jié)點t1，t2，t3和6條有向邊，每條有向邊上的數(shù)字為該邊的權.每種RTP的權與例3中的相同.由圖3可以看出，不同的測試向量順序有不同的距離值，最優(yōu)的測試向量順序即總距離最短的節(jié)點路線.

綜上所述，測試集的排序問題等價于TSP問題，為NP-完全問題.我們采用解決TSP問題的近似算法——最近鄰居算法(Nearest neighbor algorithm)求解，其排序過程概括如下：

圖3 差分距離圖

根據(jù)測試向量集及對應的響應，建立差分距離圖；

選中第一個測試向量，作為當前測試向量tcurrent，標識這個向量為已選；

從未標識的測試向量中選擇跟tcurrent距離最小的測試向量，作為新的tcurrent，并標識該向量為已選；

重復上述步驟直到測試集中沒有未標識的向量；

計算最后選擇的測試向量與第一個測試向量的距離，構成漢密爾頓回路；

在漢密爾頓回路中剔除最大距離的邊，得到總距離較短的測試向量序列.

例5 對圖1(a)中的測試向量進行排序.首先建立差分距離圖，如圖3所示.假設取t1作為第一個向量，在t2和t3選取與之距離較小的向量， 即t3，距離d13=-21.此時只剩下t2未被選擇，選擇t2，t3和t2的距離d32=-2.5.添加t2和t1之間的邊，權值d21=-22，形成漢密爾頓回路.最后，去掉回路中最大的距離值，這里為d32.重新排序后的測試集順序如圖4所示，為t2,t1,t3.

圖4 測試向量重排序示例

重排序之后通過無關位填充和故障模擬可以得到如圖5(a)和圖5(b)所示的測試集和響應集，通過差分處理可以得到如圖5(c)所示的差分集.

測試集TD響應集RD差分集Tdifft″1=100010000r″1=100111010c″1=100010000t″2=100111010r″1=100101011c″2=000000000t″3=110101011r″3=011101000c″3=010000000(a)(b)(c)

圖5 差分示例

Fig.5 Example for difference vector

不排序測試向量得到的差分向量用FDR編碼壓縮后為00 1000 110011 1010 1001 1010，共計24位；而對測試向量排序后得到的差分向量用FDR編碼壓縮后為00 1001 11100000 110001，總計20位.從本例中可以看出，使用距離排序可獲得更高的壓縮率.

3 實驗結果

我們對提出的測試壓縮方法進行了實驗，用Synopsys公司的TetraMAX生成測試向量，實驗電路為ISCAS’89電路中最大的幾個電路.在實驗過程中分別取幾組不同的權值，取結果最優(yōu)的一組權值.最優(yōu)的權值與例3中的相同.

表2為不同測試集中無關位填充方式測試質量的實驗結果.第1列為電路名稱，第2列為隨機填充每個測試向量平均能檢測的故障數(shù)，第3，4列分別為用0填充和提出填充方案平均每個測試向量檢測的故障數(shù)與隨機填充方法的比值.由實驗結果可以看出，用提出填充方案填充的測試集可以獲得與隨機填充相當?shù)臏y試質量，與0填充方式相比，提出方案平均每個測試向量多測5.9%的故障.

表2 測試集測試質量比較

表3為測試數(shù)據(jù)壓縮率的實驗結果.第一列為電路名稱，第2列(#vec)為測試向量數(shù)，第3列(#ff)為掃描單元數(shù)，第4列為測試集大小，第5列為

表3 測試壓縮率比較

FDR編碼的壓縮率，第6列為本文方法的壓縮率.實驗結果表明與FDR編碼方法相比，本文方法平均壓縮率要高2.5%.其中計算壓縮率如式(2)所示.

壓縮率=(TD-TE)×100%/TD

(2)

其中TD為原測試集的大小，TE為壓縮后的測試集大小.

4 結 論

本文提出了一種利用前一個測試向量的響應填充當前測試向量無關位的方法，增加了填充的隨機性，提高了測試質量.為了進一步提高測試壓縮率，利用最近鄰居算法對測試集進行排序.研究結果表明，本文方法簡單可行，提高了測試質量和測試壓縮率，而增加的硬件開銷可以忽略不計.許多用來提高FDR方法壓縮率的技術同樣適用于本方法，這些改進將在下一步工作中體現(xiàn).

[1] XIANG D, LI K, SUN J,etal. Reconfigured scan forest for test application cost, test data volume and test power reduction[J]. IEEE Transactions on Computers, 2007, 56(4): 557-562.

[2] XIANG D, CHEN Z, WANG L T. Scan flip-flop grouping to compress test data and compact test responses for Lauc-on-Capture delay testing[J]. IEEE Transactions on Design Automation of Electronic Systems, 2012, 17(2): 18.

[3] YOU Z Q, WANG W Z, LIU P,etal. A scan disabling-based BAST scheme for test cost and test power reduction[J]. IEICE Electronics Express, 2012, 9(2): 111-116.

[4] CHANDRA A, CHAKRABARTY K. Test data compression and test resource partitioning for system-on- a-chip using frequency-directed run-length(FDR) codes[J]. IEEE Transactions Computers, 2003, 52(8):1076-1088.

[5] EI-MALCH A H. Test data compression for system-on-a-chip using extended frequency-directed run-length code[J]. IET Computers & Digital Techniques, 2008, 2(3): 155-163.

[6] YE B, LUO M. A new test data compression method for system-on-a-chip[C]//Proc IEEE International Conference on Computer Science and Information Technology (ICCSIT). Chengdu, 2010:129-133.

[7] YI M X, LIANG H G, ZHANG L,etal. A novel X-ploiting strategy for improving performance of test data compression[J]. IEEE Transactions on Very Large Scale Integration(VLSI) System, 2010, 18(2): 324-329．

[8] CHO K Y, MITRA S, MCCLUSSKEY E J. California scan architecture for high quality and low power testing[C]//Proc IEEE International Test Conference. Santa Clara, 2007:1-10.

A High Test Quality Test Compression Method Based on FDR Codes

YOU Zhi-qiang?, HU Na

(College of Computer Science and Electronic Engineering, Hunan Univ, Changsha, Hunan 410082, China)

FDR codes can compress test stimuli data effectively. However, the number of faults detected by a test pattern is small in average, since don't care bits in the test set are filled by all 0s. The test quality is low. In order to improve the test quality and further increase the test compression ratio, this paper, based on FDR codes, proposed a scheme in which the test response of the previous test pattern is utilized to fill the don't care bits in the current test pattern. This scheme increases the randomness of the X-filling. Therefore, the test quality is improved. In this scheme, the test compression ratio is also related to the order of test patterns. This paper also proposed a test pattern reordering approach based on the nearest neighbor algorithm to decrease the number of conflict bits between the test response of the previous test pattern and the current test pattern. Difference vectors can be obtained by the difference between test patterns and the test responses of their previous test patterns. The test data volume can be reduced by using FDR codes for the difference vectors. Experiment results show that, for larger ISCAS'89 circuits, the proposed approach increases the test quality by 5.9% and test compression ratio by 2.5% in average, compared with those of FDR codes. The hardware overhead, which is only an XOR gate, can be omitted.

test quality; test compression; don’t care bits; FDR codes

1674-2974(2015)02-0109-05

2014-05-18

新世紀優(yōu)秀人才支持計劃資助項目(NCET-12-0165)；國家自然科學基金資助項目(61472123),National Natural Science Foundation of China(61472123)

尤志強(1972-)，男，河北阜城人，湖南大學副教授，博士?通訊聯(lián)系人，E-mail:zq_you@163.com

TP302

A