尤志強(qiáng)，胡 娜

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

一種基于FDR的高測試質(zhì)量測試壓縮方法

尤志強(qiáng)?，胡 娜

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

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

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

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

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

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

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

1 測試壓縮方案和解壓縮結(jié)構(gòu)

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

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

測試向量和響應(yīng)測試向量和響應(yīng)差分向量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 無關(guān)位填充舉例

Fig.1 Example for X-filling

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

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

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

圖2 解壓縮電路結(jié)構(gòu)

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

2 測試向量/響應(yīng)重排序方法

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

表1 權(quán)值表

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

(1)

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

例3 假設(shè)測試向量ti的響應(yīng)ri=110XX，測試向量tj=10XX0，由式(1)，假設(shè)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é)點(diǎn)集，每個節(jié)點(diǎn)對應(yīng)于一個測試向量，A是一個有向邊集，每條邊的權(quán)是始點(diǎn)和終點(diǎn)對應(yīng)測試向量的距離.

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

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

圖3 差分距離圖

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

選中第一個測試向量，作為當(dāng)前測試向量tcurrent，標(biāo)識這個向量為已選；

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

重復(fù)上述步驟直到測試集中沒有未標(biāo)識的向量；

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

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

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

圖4 測試向量重排序示例

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

測試集TD響應(yīng)集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 實(shí)驗(yàn)結(jié)果

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

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

表2 測試集測試質(zhì)量比較

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

表3 測試壓縮率比較

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

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

(2)

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

4 結(jié) 論

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

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

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

TP302

A