尤志強(qiáng)，胡 娜

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

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

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

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

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

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

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

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

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

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

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

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

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

測(cè)試向量和響應(yīng)測(cè)試向量和響應(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)位的測(cè)試集中1的個(gè)數(shù)必然會(huì)增加，直接FDR編碼后的測(cè)試壓縮率也必然會(huì)降低.為了提高測(cè)試壓縮率，我們將對(duì)前一個(gè)的測(cè)試響應(yīng)和根據(jù)它填充無關(guān)位的下一個(gè)測(cè)試向量做差分，形成差分向量.最后，再對(duì)差分向量集使用FDR編碼.

例2 圖1(b)給出了用提出方案填充的測(cè)試向量及對(duì)應(yīng)的測(cè)試響應(yīng).假定觸發(fā)器中的初始狀態(tài)為全0，第一個(gè)差分向量c1為第一個(gè)測(cè)試向量和全0的差分，結(jié)果與第一個(gè)測(cè)試向量相同.我們分別對(duì)r1′和t2′及r2′和t3′做差分得到差分向量c2和c3，差分向量集如圖1(c)所示.可以看出，該差分向量集中確定位1的位數(shù)由原始測(cè)試向量集中的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編碼后得到較短的編碼，提高了測(cè)試壓縮率.

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

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

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

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

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

表1 權(quán)值表

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

(1)

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

例3 假設(shè)測(cè)試向量ti的響應(yīng)ri=110XX，測(cè)試向量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)是一個(gè)有向完全圖， 其中V是一個(gè)節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)測(cè)試向量，A是一個(gè)有向邊集，每條邊的權(quán)是始點(diǎn)和終點(diǎn)對(duì)應(yīng)測(cè)試向量的距離.

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

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

圖3 差分距離圖

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

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

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

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

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

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

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

圖4 測(cè)試向量重排序示例

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

測(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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

表3 測(cè)試壓縮率比較

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

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

(2)

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

4 結(jié) 論

本文提出了一種利用前一個(gè)測(cè)試向量的響應(yīng)填充當(dāng)前測(cè)試向量無關(guān)位的方法，增加了填充的隨機(jī)性，提高了測(cè)試質(zhì)量.為了進(jìn)一步提高測(cè)試壓縮率，利用最近鄰居算法對(duì)測(cè)試集進(jìn)行排序.研究結(jié)果表明，本文方法簡單可行，提高了測(cè)試質(zhì)量和測(cè)試壓縮率，而增加的硬件開銷可以忽略不計(jì).許多用來提高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)秀人才支持計(jì)劃資助項(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