尤志強(qiáng)，羅奇鈞

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

?

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

尤志強(qiáng)?，羅奇鈞

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

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

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

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

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

1IFDR編碼

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

表1　IFDR編碼表

2ERFDR碼

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

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

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

表2　ERFDR編碼表

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

用FDR編碼：

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

用EFDR編碼：110001101101100101110010共24位；

用IFDR編碼：100100110000110011110011共24位.

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

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

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

1)盡量使用長(zhǎng)游程編碼；

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

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

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

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

目標(biāo)：采用ERFDR方法編碼長(zhǎng)度較短.

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

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

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)中選取的測(cè)試片段可以看出，P0到P3是否可以填充為相等游程取決于對(duì)h和r中X的合理填充能否滿足要求.若P3所在位的值和P6的相等且n滿足關(guān)系式m-h≤n≤m或m

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

若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: 游程長(zhǎng)度不等時(shí)的填充.

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

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

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

4解碼器設(shè)計(jì)

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

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

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

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

圖2　解碼器示意圖

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

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

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

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

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

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

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

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

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

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

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

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

(1)

式中：TD為原測(cè)試集的大?。籘E為壓縮后的測(cè)試集大小.

6結(jié)論

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

參考文獻(xiàn)

[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]歐陽(yáng)一鳴，郭文鵬，梁華國(guó). 改進(jìn)型FDR 碼對(duì)SoC 測(cè)試數(shù)據(jù)的壓縮及解壓[J].計(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

中圖分類(lèi)號(hào)：TP302

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

*收稿日期：2014-12-08

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