一種基于IFDR改進的測試激勵數(shù)據(jù)壓縮方法*

尤志強，羅奇鈞

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

?

一種基于IFDR改進的測試激勵數(shù)據(jù)壓縮方法*

尤志強?，羅奇鈞

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

摘要：通過改進IFDR碼，提出一種基于游程相等編碼的改進FDR(ERFDR)方法.首先，該方法不僅能同時對原測試集的0游程和1游程進行編碼，而且，當相鄰游程相等時還可以用較短的碼字來代替，從而進一步提高了壓縮率.其次，還提出針對該壓縮方法的測試集無關(guān)位填充算法，增強提出方法的壓縮效果.實驗結(jié)果表明，與FDR，EFDR，IFDR和ERLC相比較，本文提出的方法獲得了更高的壓縮率，降低了測試費用.

關(guān)鍵詞：全掃描測試；測試數(shù)據(jù)壓縮；無關(guān)位；FDR編碼

隨著超大規(guī)模集成(VLSI)電路制造工藝的不斷進步，越來越多的知識產(chǎn)權(quán)(IP)核被集成到一個系統(tǒng)芯片(SoC)上，與SoC相關(guān)的可測試性和測試方法問題被擺到了重要的位置.近十年來，如何降低測試成本，減少測試應(yīng)用時間，降低測試功耗成為了研究的熱點問題.

數(shù)據(jù)壓縮技術(shù)能較好地解決這個問題，而編碼壓縮又是眾多壓縮方法中較好的一種．當前比較成熟的編碼壓縮方法有字典編碼[1]、游程編碼[2]、Huffman碼[3]、Golomb碼[4-5]、FDR碼[6]、EFDR碼[7-8]、IFDR碼[9]等.這些編碼壓縮方法充分利用了測試集中的無關(guān)位(X).FDR是一種變長0游程編碼，測試集中的X都被填充為0以增加0游程的長度，當測試集中1的個數(shù)較少時有較好的壓縮效果.EFDR碼和IFDR碼可以同時對0，1游程進行編碼，當測試集中1的個數(shù)較多時，也能取得較好的壓縮效果.然而以上方法均沒考慮等游程的情況.本文在IFDR上進行改進，提出一種基于游程相等的改進FDR(ERFDR)，一方面能同時對0,1游程編碼，另一方面當相鄰游程相等時用較短的碼字來代替，以進一步提高壓縮率，減少測試應(yīng)用時間.

1IFDR編碼

IFDR編碼是一種改進型FDR編碼(Improved FDR).該方法將原測試集看作連續(xù)的0游程和1游程，0游程和1游程共用同一套碼字，并規(guī)定0游程后接1游程，1游程后接0游程.若不是，即0游程后是0游程或者1游程后是1游程，編碼時在兩個相同游程中間添加一個“00”作為標識符.該方法默認從1游程開始編碼，若測試集第一位為0，則在編碼的過程中先必須加個“00”作為標識.表1給出了IFDR的編碼表，可以看出游程長度l和其所在組k的關(guān)系為:k=「log2(l+3)?-1.前綴中1的個數(shù)和其所在組的關(guān)系為：k組的前綴為1k-10，表示有k-1個1再接一個0.對于任一組，前綴和尾部的長度是相等的，組前綴是用來區(qū)分該碼字所在的組(通過前綴的長度)，尾部用來確定該碼字所在組中的位置.和FDR編碼表不同的是IFDR編碼表的A1組只包含一個游程長度，且沒有長度為0的游程.用IFDR對0游程和1游程編碼時共用同一套編碼.

表1　IFDR編碼表

2ERFDR碼

為了進一步提高測試壓縮率，本文在IFDR基礎(chǔ)上進行改進，提出一種基于游程相等的改進FDR(ERFDR)，編碼表見表2.與IFDR碼類似，ERFDR碼也能同時對0游程和1游程編碼，0游程和1游程共用同一套碼字，且默認從1游程開始編碼.考慮到相鄰游程類型相同的可能性較高，與IFDR碼不同，本文用一位“0”作為標識，則可多壓縮一位.代價是游程長度為2n+1-3的編碼增長2位，其中n為自然數(shù).當這種游程個數(shù)小于相鄰游程類型相同的游程個數(shù)的一半時，該編碼方式有效.可以預(yù)見，當測試集中確定位比例越低，該編碼方式越有效.進一步考慮到，每個游程的編碼都是從1開始，且不會連續(xù)出現(xiàn)兩個“0”標識符.我們可以用“00”標識相鄰兩個游程相等的情況，從而取得進一步的壓縮效果.在不發(fā)生混淆的前提下，本文用“0000” 標識相鄰游程類型相同且相等的情況.

總之，提出的方法有如下5個編碼原則：1)若測試集第一個游程為0游程，須加“0”作為標識；2)當相鄰游程類型相同但游程不相等時，在兩游程的編碼之間加“0”標識；3)當相鄰游程長度相等且類型不同時，后一個游程用“00”編碼；4)當相鄰游程長度相等且類型相同時，后一個游程用“0000”編碼；5)為了避免解碼時發(fā)生歧義，當出現(xiàn)連續(xù)3個游程長度相等時，則對第3個游程直接用編碼表編碼，而不使用原則3)和4)編碼.

如表2所示，全部游程長度分為A1，A2,…,Akmax組，其中kmax由測試集中最大游程長度lmax決定，滿足不等式2kmax+1-4

表2　ERFDR編碼表

例1下面是31位的測試向量，分別用幾種編碼方法求1110111111000000000011111111110的編碼．

用FDR編碼：

0000000110111100110000000000000000000001共40位，比原向量位數(shù)還多；

用EFDR編碼：110001101101100101110010共24位；

用IFDR編碼：100100110000110011110011共24位.

而用本方法編碼：1010 0 110001 110100 00共19位，可見本方法比上面的幾種方法壓縮效果都有改善.

3無關(guān)位的填充方法

大規(guī)模測試數(shù)據(jù)中無關(guān)位占95%以上，測試數(shù)據(jù)壓縮效果的好壞在一定程度上取決于對X的填充.本方法對0,1同時編碼，并充分利用游程長度和類型信息進一步提高測試壓縮率，在對無關(guān)位填充的過程中應(yīng)遵循下列兩個基本原則：

1)盡量使用長游程編碼；

2)盡可能地讓相鄰游程相等.

例如：00XX00X00XXXXXXX11XX11XX10這樣一組測試數(shù)據(jù)，若在填充過程中僅僅遵循原則1)，則填充后為00000000000000001111111110，用 表2編碼，結(jié)果為11100011 110011，共14位.若遵循上述兩原則：0000000000001 1111111111110，用本文的方法編碼為110111 00共8位，減少了6位，壓縮效果明顯改善.本文所用的填充算法(無關(guān)位填充算法)如下.

輸入：帶無關(guān)位X的測試集T0；

輸出：不含無關(guān)位X的測試集T1；

目標：采用ERFDR方法編碼長度較短.

STEP1: 從T0中按先后順序選取測試數(shù)據(jù)片段.

首先，標記開始的位置為P0；從P0開始尋找第一個確定位，標記該位置為P1；接著從P1開始找到第一個與P1所在位不同的確定位，記這個位置為P2；再從P2開始尋找第一個與P1所在位相等的確定位，記該位置為P3；接著按相反的順序從P2向P0方向?qū)ふ业谝粋€確定位，記為P4；從P3向P0的方向?qū)ふ业谝粋€確定位，記為P5.從P0到P3即為一塊數(shù)據(jù)片段.此外，再從P3往正方向?qū)ふ业谝粋€確定位，記該位置為P6，從P3往正方向?qū)ふ业谝粋€與P3不同的確定位，記為P7.圖1(a)為數(shù)據(jù)片段選取實例.

STEP2: 等游程判斷.

我們記P0到P4間的位數(shù)(包括P0和P4)為n，P4到P2間的位數(shù)(不包括P4和P2)為h，P2到P5間的位數(shù)(包括P5但不包括P2)為m，P5到P3間的位數(shù)(不包括P5和P3)為r.從圖1(a)中選取的測試片段可以看出，P0到P3是否可以填充為相等游程取決于對h和r中X的合理填充能否滿足要求.若P3所在位的值和P6的相等且n滿足關(guān)系式m-h≤n≤m或m

圖1　一測試向量數(shù)據(jù)片段填充實例

若P3所在位的值和P6所在位的值不相等或n不滿足上述關(guān)系，轉(zhuǎn)到STEP4.

若P2與P5重合，將P3調(diào)整到P7的位置，并令P8=2×P2+1-P0.若P3

STEP3: 等游程填充.

根據(jù)游程相等情況填充X，轉(zhuǎn)到STEP5.

STEP4: 游程長度不等時的填充.

令從P0到P4中的所有X填充為P1所在位置的值，再令從P2到P3中的所有X填充為P2所在位置的值，這樣從P0到P3即為...aaaXXXbbb...(a可以為0或1，相應(yīng)的b為1或0)的形式.若將X完全填為a(或b)，且不會使原a串(或b串)的碼字增加，則將X填充為a(或b).否則，填充X時盡量讓長串更長：在不增長a串編碼長度的前提下，將部分X填為a，使a串飽和；在不增長b串編碼長度的前提下，將剩余部分X填為b，使b飽和；若還有X未被填充，則填為a,b串中較長的那個.

STEP5：直到T0中沒有X，算法終止，否則轉(zhuǎn)STEP1.

圖1(b)為圖1(a)的填充實例.此時，n=9，h=7，m=8，r=3，P3所在位的值和P6的相等(都是0)，且滿足m

4解碼器設(shè)計

進一步分析ERFDR編碼表可以得知游程長度l與前綴(c)和尾部(d)的關(guān)系:l=(c)2+(d)2-1，例如，游程長度為3時，l=(10)2+(10)2-1.接下來我們分析得到各碼字的前綴都是以111...1110的形式出現(xiàn)，可得：

l=(c)2+(d)2-1=(c+10+d)2-3=

該解碼器的結(jié)構(gòu)是基于一個有限狀態(tài)機(FSM)的設(shè)計，類似于FDR解碼器電路，結(jié)構(gòu)簡單，硬件開銷小.如圖2所示，該結(jié)構(gòu)由一個FSM， k+1位計數(shù)器， k+1位寄存器，log2k位計數(shù)器和一個T觸發(fā)器組成.其中,bit_in：輸入端口，壓縮后的數(shù)據(jù)TE從此端口輸入到有限狀態(tài)機進行解碼；en：使能信號，控制bit_in的輸入；clk：時鐘信號；log2k位計數(shù)器：用來計算前綴的位數(shù)，并以此來控制尾部的輸入；inc/dec分別控制log2k位計數(shù)器的加1和減1操作；dec1控制k+1位計數(shù)器的減1，rs和rs1分別指示k+1位和log2k位計數(shù)器已復位；shift：控制各個數(shù)據(jù)位移入k+1位計數(shù)器；load：裝載信號；reg_ent1：寄存器控制信號；v：指示scaninput何時有效.

該解碼器的工作原理如下：

圖2　解碼器示意圖

1)初始化，讓使能信號en為1，準備接收數(shù)據(jù).T觸發(fā)器初始化為1.若解壓數(shù)據(jù)第一位是0，則FSM令out為1，T觸發(fā)器翻轉(zhuǎn)；若為1，則令out為0.

2)FSM讓使能信號為1，shift和inc為1，F(xiàn)SM控制log2k位計數(shù)器加1，直到bit_in為0為止.

3)FSM輸出端為低電平，控制T觸發(fā)器輸出上一狀態(tài)值，同時v為高電平，表示輸出有效.

4)FSM將k+1位計數(shù)器的初始值設(shè)為1，并通過log2k計數(shù)器控制將初始值1和尾部一起向高位移動.此時，dec為高電平控制log2k計數(shù)器的減1，直到rs1為高電平，log2k計數(shù)器為0時，尾部輸入結(jié)束.

5)reg_ent1為高電平時，通過dcopy復制k+1位計數(shù)器的值到k+1位寄存器中.

6)FSM控制dec1為高電平，控制k+1位計數(shù)器的減1操作，直到k+1位計數(shù)器的值為3(即0…011)時，out輸出為高電平，T觸發(fā)器的輸出翻轉(zhuǎn).

7)當解碼完一個游程后，一直到bit_in為1之前，若bit_in共出現(xiàn)1個“0”，則令out為低電平，且v也為低電平0，表示輸出無效，同時也為下一個游程編碼做準備；出現(xiàn)兩個0時，即“00”，則置load為高電平，通過dload把寄存器的值載入k+1位寄存器中，轉(zhuǎn)到6)；當出現(xiàn)“000”時(共3個時鐘周期)，則在前2個時鐘周期置load為高電平，通過dload把寄存器的值載入k+1位寄存器中，轉(zhuǎn)到6)，第3個時鐘周期令out為低電平，v且也為低電平0，表示輸出無效；出現(xiàn)“0000”時，令out為低電平，然后置load為高電平，通過dload把寄存器的值載入k+1位寄存器中，轉(zhuǎn)到6)；當出現(xiàn)“00000”時，重復上述出現(xiàn)4個0的步驟，之后在最后一個時鐘周期令out為低電平，且v也為低電平.

5實驗結(jié)果

本文針對ISCAS89標準電路中較大的6個電路，采用mintest測試集在Visual C++平臺上實驗，得出的結(jié)果分別與Golomb碼、FDR碼、EFDR碼、IFDR碼以及ERLC[10]碼進行比較，實驗結(jié)果見表3.可以看到平均壓縮率均優(yōu)于其他方法，平均壓縮率比Golomb編碼方法提高了將近14%，比FDR和IFDR分別提高了6%和1.84%，比EFDR和ERLC也提高了0.5%.

表3　本方法與其他幾種測試壓縮方法的比較

其中壓縮率計算公式如式(1)所示.

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

(1)

式中：TD為原測試集的大??；TE為壓縮后的測試集大小.

6結(jié)論

本文在IFDR編碼方法的基礎(chǔ)之上進行改進，不僅能同時對0,1串編碼，而且當出現(xiàn)相鄰游程相等時，后一個游程用較短的碼字來代替，進一步提高壓縮率.實驗結(jié)果充分驗證了本文提出方法的有效性.該法簡單可行，解碼電路簡單，硬件開銷不高.

參考文獻

[1]TOUBA N. Survey of test vector compression technique [J]. IEEE Design &Test of Computer, 2006,23(4)：294-303.

[2]JAS A, TOUBA N. Test vector decompression via cyclical scan chains and its application to testing core-based designs[C]//Proceedings of International Test Conference. New York: IEEE, 1998: 458-464.

[3]JAS A, GOSH-DASTIDAR J, NG M,etal. An efficient test vector compression scheme using selective Huffman coding[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 22(6):797-806.

[4]CHANDRA A, CHAKRABARTY K. Test data compression and decompression based on internal scan chains and Golomb coding[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002,21(6):715-722．

[5]CHANDRA A, CHAKRABARTY K. System-on-a-chip test-data compression and decompression architectures based on Golomb codes[J]. IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 2001, 20 (3):355-368.

[6]CHANDRA A, CHAKRABARTY K. Frequency-directed run-length(FDR) codes with application to system-on-a-chip test data compression[C]//19th IEEE Proceedings on VLSI Test Symposium. New York: IEEE, 2001: 42-47.

[7]EL-MALEH A, AL-ABAJI R. Extended frequency-directed run-length codes with improved application to system-on-a-chip test data compression[C]//Proceedings of 9th International Conference of Electronics, Circuits and Systems. New York: IEEE, 2002: 449-452.

[8]EL-MALEH A. Test data compression for system-on-a-chip using extended frequency directed ran-length code[J]. IET Computers & Digital Techniques, 2008，2(3)：155-163.

[9]歐陽一鳴，郭文鵬，梁華國. 改進型FDR 碼對SoC 測試數(shù)據(jù)的壓縮及解壓[J].計算機應(yīng)用研究, 2008,25(1) :174-177.

OUYANG Yi-ming, GUO Wen-peng, LIANG Hua-guo. Soc test data compression and decompression with improved FDR code[J]. Application Research of Computers, 2008, 25(1):174-177.(In Chinese)

[10]ZHAN W F, EL-MALEH A. A new scheme of test data compression based on equal-run-length coding (ERLC)[J]. Integration the VLSI Journal , 2012, 45(1): 91-98.

A Test Compression Method Based on IFDR Code

YOU Zhi-qiang?, LUO Qi-jun

(College of Information Science and Engineering, Hunan Univ, Changsha, Hunan410082, China)

Abstract:Based on equal runlength code and IFDR, a new coding method (called ERFDR) was proposed. Firstly, the proposed method can not only encode both 0 and 1 runs for a test set simultaneously, but also can use shorter code if the adjacent runlengths are equal. Therefore, the compression ratio can be further improved. This paper also put forward a new filling algorithm for a test set with don't care bits, which can enhance the compression efficiency of the proposed method. Experimental results show that the proposed method can obtain a higher compression rate compared with FDR, EFDR, IFDR and ERLC codes. The test cost can be reduced effectively.

Key words:full scan testing; test compression; don’t care bits; FDR codes

中圖分類號：TP302

文獻標識碼：A

作者簡介：尤志強(1972-)，男，河北阜城人，湖南大學副教授?通訊聯(lián)系人，E-mail:469363963@qq.com

基金項目：新世紀優(yōu)秀人才支持計劃項目(NCET-12-0165)

*收稿日期：2014-12-08

文章編號：1674-2974(2016)02-0130-05