基于長游程二次編碼的測試數(shù)據(jù)壓縮方法

于海濤,程曉旭,李 梓

(大慶師范學(xué)院 計算機科學(xué)與信息技術(shù)學(xué)院，黑龍江 大慶 163712)

0 引言

隨著超深亞微米技術(shù)的廣泛應(yīng)用，集成電路的尺寸變得越來越小，而芯片內(nèi)部的結(jié)構(gòu)變得更加復(fù)雜，一個芯片上可能集成數(shù)億個晶體管，芯片的復(fù)雜性和測試數(shù)據(jù)量的不斷增加使得芯片的測試費用不斷上升，而測試數(shù)據(jù)量也變得越來越龐大。一方面，需要測試設(shè)備具有較大的存儲容量來存儲測試數(shù)據(jù)，另一方面將測試數(shù)據(jù)從測試設(shè)備傳輸?shù)綔y試芯片需要更多的測試通道[1]。所有這些問題，如果僅通過更大容量、更高頻率的測試設(shè)備來解決，必然會造成測試成本的巨幅增加。因此，單純地提高測試設(shè)備的性能并不是一個好的解決方案，而探索高效的、快速的測試技術(shù)無疑是解決這些問題的重要途徑。提高測試數(shù)據(jù)壓縮技術(shù)是解決這一問題的有效手段，是近年來大量學(xué)者們廣泛關(guān)注的熱點，其中編碼方法是測試數(shù)據(jù)壓縮的主要技術(shù)之一。編碼方法主要有Run-length[2],Golomb編碼[3]，F(xiàn)DR碼[4]和Variable-tail編碼[5]等。

Run-length 編碼方法對于游程長度特別大的串進行編碼時，需要進行分組，例如碼字長度為3的Run-length 編碼，最多有23=8個編碼字。如果測試向量中的游程長度大于8，就需要分組進行編碼。此時的壓縮效果不是很理想；Golomb編碼則是變長-變長的編碼，對于游程長度沒有限制，不需要對長游程的串進行分組。但是這種編碼方法的缺點是每個前綴所對應(yīng)的編碼字的個數(shù)不變。所以前綴不能得到有效的利用；FDR碼是一種變長-變長的編碼，但是該種編碼的尾部是變長的，尾部的長度等于頭部的長度，因此每個前綴對應(yīng)編碼字的個數(shù)隨著前綴長度的增加而增加；Variable-tail編碼也是基于游程的編碼技術(shù)，每組編碼的后綴不相同，并且一次增加一位，所以每組包含的編碼字總是上一組所含編碼字數(shù)的2倍。該種編碼中每組的編碼字都比上組的編碼字多兩位，所以隨著組號的增加，每組所包含的編碼字的數(shù)量增加很快，呈指數(shù)級增加速度。因此前綴得到有效的利用。使用以上這些方法，長游程的壓縮率不是很高，因此本文針對長游程編碼字，進行二次編碼壓縮，從而進一步提高了長游程的編碼壓縮率。

1 長游程二次編碼的壓縮方法

通過研究提出了一種長游程編碼進行二次編碼的方法，通過該方法使得長游程的編碼得到了進一步的壓縮。

1.1 預(yù)處理

在進行壓縮之前，首先應(yīng)對測試集合進行如下過程預(yù)處理：①對測試向量中的無關(guān)位X進行處理和相容的測試向量的合并；②對測試向量進行排序；③對測試向量進行差分變換。

1.1.1 對無關(guān)位進行處理和相容測試向量的合并

大量的實驗表明測試向量中存在大量的無關(guān)位X, 無關(guān)位取0或取1不影響故障的覆蓋率。我們對無關(guān)位進行賦值的原則是盡量增加游程0的長度，從而起到增加壓縮率與減少測試功耗的目的。兩個測試向量相容，是指兩個測試向量對應(yīng)位相同，或者至少其中一位為無關(guān)位。通過相容測試向量合并能夠減少測試向量的數(shù)量。

1.1.2 測試向量進行排序

鑒于測試向量之間不同數(shù)值位較少的事實，為了獲得更高的壓縮率，我們需要把原始的測試向量集進行排序，經(jīng)過排序的測試向量集合中相鄰的測試向量的海明碼距最小。排序的方法利用圖論中的Hammilton圖[5]的方法。實現(xiàn)過程：設(shè)完全有向圖G=(V,E),節(jié)點vi∈V表示S的測試向量，每一條邊(vi,vj)∈E,表示測試向量對。邊上的權(quán)值表示向量之間的海明碼距，然后我們找到一條路徑，使得邊上的權(quán)值和最小，這類似于Hammilton的旅行商問題。求解該問題是一個NP問題，我們利用貪婪算法可以解決這一問題，該方法雖然不能得到最優(yōu)解，但是得到的解接近最優(yōu)解[6]。

1.1.3 向量的差分變換

由于經(jīng)過排序的測試向量之間數(shù)值位的差別較少，所以把經(jīng)過排序的測試向量集合TD轉(zhuǎn)換為差分向量序列Tdiff={t1,t1?t2,t2?t3…..tn-1?tn},經(jīng)過差分變化后Tdiff中的差分向量就含有較多的0位，這樣有利于進行“0”游程長度的編碼，編碼的壓縮效果比較好。

1.2 一次編碼

1.3 進行二次編碼的壓縮方法

設(shè)表1共有2n個游程編碼字，我們對前n個編碼字保持不變，而對后n個(n+1)～2編碼字進行重新編碼，將它們編碼為以0為前綴的編碼字。編碼的方法如下：

第n+1個編碼字為010(01為前綴) 第n+2個編碼字為011(01為前綴)

第n+3個編碼字為00100(001為前綴) 第n+4個編碼字為00101(001為前綴)

……

例如某個測試集合中最大的游程長度為26，如果按照游程壓縮編碼方法進行編碼，那么從第14～26個(即按照游程長度進行升序排序，排在后50%的游程)游程長度的編碼字分別為：111100000，111100001，111100010，111100011，111100100，111100101，111100110，111100111，111101000，111101001，111101010，111101011，111101100,編碼的長度都為9。那么經(jīng)過二次編碼后的編碼為：010，011，00100，00101，00110，00111，0001000，0001001，0001001，0001010，0001011，0001100，0001101，那么經(jīng)過二次編碼后的長度的減少為：9-3=6，9-3=6，9-5=4，9-5=4，9-5=4，9-5=4，9-7=2，9-7=2，9-7=2，9-7=2，9-7=2，9-7=2，9-7=2。減少的總長度為：6*2+4*4+2*7=42。減少的百分比為42/(9*13)=35%。隨著游程的最大長度的增加，壓縮的百分比也會增加。

2 解壓縮算法與解壓縮電路的設(shè)計

2.1長游程二次編碼的解壓縮算法

解壓算法如下：

①輸入壓縮編碼；

②讀取前綴，如果前綴為一連串的1與表示結(jié)束標志的0字組成，那么按照如下方法解壓縮，否則轉(zhuǎn)向③；

i)求出前綴的長度Lpre,確定編碼所在的組，所在的組號=Lfirst-1，該組的第1個編碼字所對應(yīng)的編碼字的游程長度為Lfirst=2Lpre-1-2；

ii)根據(jù)前綴的長度Lpre，讀取相應(yīng)的后綴，后綴的長度=Lpre-1，后綴即為該編碼在該組中的相對位置Lpos,游程長度Llen=Lfirst+Lpos;轉(zhuǎn)向④；

③如果前綴為一連串的0與表示結(jié)束標志的1字組成，那說明該編碼字是經(jīng)過二次壓縮的編碼字，按照如下步驟進行解壓：

i)求出前綴的長度Lpre,確定編碼所在的組，所在的組號=Lpre-1，該組的第1個編碼字所對應(yīng)的編碼字的游程長度為Lfirst=2Lpre-1-2；

ii)根據(jù)前綴的長度Lpre，讀取相應(yīng)的后綴，后綴的長度=Lpre-1，后綴即為該編碼在該組中的相對位置Lpos,游程長度L’len=Lfirst+Lpos, 該長度值不是真正的游程長度值，因為此時的游程長度與實際的游程長度存在一個偏差n(n-L/2,L為最大的游程長度)，所以實際的游程程度為Llen=L’len+n，轉(zhuǎn)向④；

④輸出Llen個0，然后輸出一個1，該編碼字解壓解壓結(jié)束；

⑤如果存在下一個編碼字，讀取下一個編碼字并轉(zhuǎn)向②，否則轉(zhuǎn)向⑥；

⑥該測試向量的壓縮編碼解壓結(jié)束。

2.2解碼器電路

解碼器的設(shè)計類似FDR解碼器，它是基于有限狀態(tài)機(FSM)的設(shè)計。該解碼器的結(jié)構(gòu)簡單，電路規(guī)模小，只是增加了一個S_bit計數(shù)器，其中S=int(log2N)+1(int為取整函數(shù))(N=L/2,L為最大游程長度)。圖1為解碼器框圖。該電路由1個有限狀態(tài)機，一個K_bit計數(shù)器，一個(log2K-1)_bit計數(shù)器，一個S_bit計數(shù)器?！癰it-in”和“en”分別是位輸入和使能信號，當有限狀態(tài)機準備就緒時，輸入編碼數(shù)據(jù)。“counter_in”是到K_bit計數(shù)器的位輸出,dec1控制計數(shù)器減1，rs1表明K_bit計數(shù)器復(fù)0狀態(tài)。(Log2k-1)計數(shù)器用作識別后綴長度，信號”inc”和“dec2”分別控制計數(shù)器加1和減1計數(shù)?！眗s2”指示完成計數(shù)?！癲ec3”和”rs3”分別用于計數(shù)器減1和標明計數(shù)器復(fù)0狀態(tài)。

工作原理如下：

圖1 解碼器框圖

1)首先，有限狀態(tài)機發(fā)出使能信號“en”為1，然后“shift”和“inc”均為高電平，控制“bit_in”和“counter_in”移入前綴進入K_bit計數(shù)器，(log2K-1)_bit計數(shù)器加1(由于后綴比前綴少1位，所以當前綴為0時，就停止加1)。當“bit_in”為0時，前綴輸入結(jié)束。如果輸入前綴以1開始的，則編碼沒有經(jīng)過2次編碼，將0移入S_bit計數(shù)器(此時游程的偏移量為0)，如果輸入前綴以0開始的，則說明編碼經(jīng)過2次編碼，將n移入S-bit計數(shù)器(此時游程的偏移量為n)；

2)“dec1”為高電平控制計數(shù)器減1，out連續(xù)輸出0，直至K_bit計數(shù)器為0。此時前綴解碼結(jié)束；

3)然后S_bit的“dec3”為高電平控制計數(shù)器減1，out連續(xù)輸出0，直至S_bit計數(shù)器為0。此時二次編碼的解碼結(jié)束；

4)接下來，輸入后綴進入K_bit計數(shù)器，(log2K-1)_bit計數(shù)器控制后綴長度，“dec2”為高電平控制計數(shù)器減1，out連續(xù)輸出0，當(log2K-1)_bit計數(shù)器為0，返回“rs2”高電平。后綴輸入結(jié)束；

5)“dec1”為高電平控制計數(shù)器減1，out連續(xù)輸出0，直至K_bit計數(shù)器為0，此時后綴解碼結(jié)束。

3 實驗結(jié)果

實驗的硬件平臺包括Intel P4 3.0G CPU,512M內(nèi)存的PC工作站。編碼算法是在PC工作站上完成的，測試向量數(shù)據(jù)是在SUN工作站上產(chǎn)生的，采用的MINTEST產(chǎn)生測試向量，這些測試向量對固定型故障的覆蓋率均為100%。

我們先對測試向量先進行如下處理：相容合并、向量排序、差分變換。測試數(shù)據(jù)壓縮率實驗結(jié)果如表2所示。由表2可以看出，本文提出的方法使測試數(shù)據(jù)的壓縮率得到了進一步的提高。在表中S13207電路的壓縮率最高，原因是該電路中測試矢量集的長度最大，因此測試矢量之間的相關(guān)性比較高，經(jīng)過排序和差分變換后，測試矢量中0的個數(shù)較多，所以導(dǎo)致長游程的比率較大，因此該電路的編碼壓縮率最高。相反S5378電路測試集合的長度最小，因此該電路的編碼壓縮率最低。

表2 測試編碼壓縮率的比較

4 結(jié)論

本文提出了一種長游程編碼的二次編碼的壓縮方案，該方法是對經(jīng)過一次編碼后的編碼字中編碼字長度較大的編碼進行了二次編碼壓縮，實驗結(jié)果表明該壓縮方法有效地提高了測試數(shù)據(jù)的壓縮率。該方法的壓縮率高，解壓電路簡單，硬件開銷小，該方法對于長游程比率較高的測試數(shù)據(jù)的壓縮效果較好。在今后的工作中，應(yīng)重點進行增加長游程比率的預(yù)處理的研究工作。

[參考文獻]

[1] A.Khoche， J.Rivoir.I/O bandwidth bottleneck for test:Is it real？[C]. USA:Proceeding International Workshop Test Resource Partitioning,2000: 231-236.

[2] A Jas and N.A. Touba. Test vector compression via Cyclical Scan Chain and Its Application to Testing Core-Based Designs[C]. USA:Proceedings of IEEE International Test Conference, 1998:458-464.

[3] Chandra A，Chakrabarty K．System-on-a-chip test data compression and decompression architectures based on Golomb codes[J]. IEEE Transactions on CAD of Integrated Circuits and System,2001,20(3):355-368.

[4] Chandra A，Chakrabarty K．Frequency—directed run length (FDR) codes with application to system—on—a—chip test data compression [C].USA :Proceedings of VLSI Test Symposium．Marina Del Rey,2001:2-47.

[5] 韓銀河,李曉維.測試數(shù)據(jù)壓縮和測試功耗協(xié)同優(yōu)化技術(shù)[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2005, 17(6):1307-1311.

[6] 王健波,曾成碧,苗虹.減小數(shù)字電路測試功耗的方法—測試向量排序方法[J].四川大學(xué)學(xué)報:工程科學(xué)版,2000(6):89-91.