一種用于測試數據壓縮的自適應EFDR編碼方法

鄺繼順 周穎波 蔡 爍

?

一種用于測試數據壓縮的自適應EFDR編碼方法

鄺繼順 周穎波*蔡 爍

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

該文提出一種用于測試數據壓縮的自適應EFDR(Extended Frequency-Directed Run-length)編碼方法。該方法以EFDR編碼為基礎，增加了一個用于表示后綴與前綴編碼長度差值的參數，對測試集中的每個測試向量，根據其游程分布情況，選擇最合適的值進行編碼，提高了編碼效率。在解碼方面，編碼后的碼字經過簡單的數學運算即可恢復得到原測試數據的游程長度，且不同值下的編碼碼字均可使用相同的解碼電路來解碼，因此解碼電路具有較小的硬件開銷。對ISCAS-89部分標準電路的實驗結果表明，該方法的平均壓縮率達到69.87%，較原EFDR編碼方法提高了4.07%。

測試數據壓縮；EFDR(Extended Frequency-Directed Run-length)編碼；自適應EFDR編碼；解碼

1 引言

測試成本的迅速增長是目前集成電路設計制造中的一個主要問題。一方面，隨著特征尺寸的減小，集成電路中所包含的IP核與集成的邏輯門數量增多，使得所需測試數據規模增大；而另一方面，自動測試儀(ATE)的工作頻率、I/O通道數目、傳輸帶寬、存儲能力卻增長有限。兩者之間的矛盾是導致測試時間增加，測試成本上升的主要原因[1]。

對測試數據進行壓縮是一種能有效解決該矛盾的方法。目前測試數據壓縮方法主要分為3類：基于線性解壓結構的壓縮方法、基于廣播掃描的壓縮方法和基于編碼的壓縮方法[2]。其中編碼壓縮方法主要針對給定測試集，將測試集中的測試數據分割成多個符號(字符串)，再將每個符號用一個新碼字替代，形成壓縮后的數據，存儲在ATE中。編碼壓縮方法主要分為兩類，其中一類是基于游程的編碼方法，它的基本原理是對原始測試數據中連續的0或1的長度(稱作游程)進行編碼，包括FDR編碼[3]，EFDR(Extended Frequency-Directed Run-length)編碼[4]，多維游程編碼(MD-PRC)[5]，交替變游程編碼(AVR)[6]，對稱游程編碼(SVC)[7]和一位標識混合編碼[8]等；另一類是基于數據塊的編碼方法，它是將原始數據劃分為定長或變長的數據塊，根據不同數據塊的出現頻率進行編碼，對高頻率的數據塊賦予較短的碼字。這類編碼包括可變長Huffman編碼(VIHC)[9]，塊合并編碼(BM)[10]，四值稀疏存儲編碼[11]等。此外近年來人們也提出了一些適用于多掃描鏈結構[12,13]和用于降低測試功耗[14,15]的編碼壓縮方法。編碼壓縮不需要了解被測電路的內部結構信息，也不需要進行故障模擬或測試產生，非常適用于嵌入有IP核電路的測試數據壓縮[1]。

目前基于游程的編碼壓縮方法大都是根據整個測試集的游程分布情況提出的，沒有考慮到在測試集的不同測試向量之間，游程分布存在著巨大差異。本文以此為切入點，提出一種自適應EFDR編碼方法，以EFDR編碼為基礎，增加了一個用于表示后綴與前綴編碼長度差值的參數，對測試集中的不同測試向量，用不同的值進行編碼，有效提高了測試數據壓縮率。

2 EFDR編碼

EFDR編碼是一種重要的基于游程的編碼壓縮方法。EFDR編碼被稱之為FDR編碼[3]的擴展碼，在FDR編碼的基礎上增加了一位標識位，0表示對0游程編碼，1表示對1游程編碼。由于可同時對兩種游程編碼，因此經過對無關位Ｘ的適當填充，EFDR 編碼的游程總數會遠遠小于僅基于0 游程的FDR編碼，其壓縮率也比FDR編碼有較大提高。EFDR的完整編碼由標識位加前綴加后綴組成，其編碼表在表1中給出。

表1 EFDR編碼表

然而EFDR編碼自身也存在一些缺陷，制約了它編碼壓縮率的提高：

EFDR編碼對測試集中的所有測試向量均使用相同的編碼方法，而沒有考慮到不同測試向量的游程分布存在巨大差異。表2為Mintest測試集中測試向量的無關位X比例表，列出了各電路測試集的測試向量中包含X位比例的最低值、最高值和平均值。由表2中可以看出，最低值與最高值之間差異顯著，這使得各測試向量的游程分布也大為不同[1]。以電路s9234為例，X位比例的最低值僅為4.86%，對應的測試向量中絕大部分位都是確定位，游程分布以短游程為主，若用EFDR進行編碼，則編碼后的數據量反而大于原始數據，起不到壓縮的效果；而X位比例的最高值則為95.14%，此時對應的測試向量中絕大部分位都是無關位，游程分布以長游程為主(X填充后，最短游程長度為14位)，而EFDR編碼中，卻將大量編碼碼字用于對短游程編碼(由表1可知，長度為1~6的游程，占用了前綴為0和10的編碼碼字)，這造成了編碼資源的極大浪費。因此對這些游程分布差異很大的測試向量單一使用EFDR編碼并不合適。

表2 MinTest測試集中X位比例

3 自適應EFDR編碼

針對上一節中EFDR編碼的缺陷，本文提出了一種用于測試數據壓縮的自適應EFDR(Adaptive EFDR, A-EFDR)編碼方法，在原EFDR編碼的基礎上，增加了一個用于表示后綴與前綴編碼長度差值的參數。對測試集中的每個測試向量，根據其游程分布情況，選擇最合適的值進行編碼。表3和表4列出了其中和時A-EFDR編碼的編碼表，其余值下的A-EFDR編碼表可依類似方法得出(其中的編碼表即為表1)。

表3 A-EFDR編碼表(N=-1)

表4 A-EFDR編碼表(N=1)

與EFDR編碼類似，A-EFDR編碼也采用由標識位加前綴再加后綴組成。標識位用于區分是對0游程編碼還是對1游程編碼；前綴與EFDR編碼中前綴相同，對于不同組別A(=1,2,3,)，前綴編碼由個1和一個0構成；后綴長度則不再固定與前綴長度相同，而是相差一個值。因為前綴的起始長度為1位，而后綴起始長度必須大于等于0，所以參數的取值范圍為：。A-EFDR編碼表中，起始的游程長度為1位，對應的起始編碼長度為位，同一組別的游程編碼長度不變，跨組別的相鄰游程編碼長度增量為2；每一個組別A中，包含的游程長度個數為個。

給出一個A-EFDR編碼的實例。

原始測試數據：TD=000000111110 0000000001 (22位)

編碼后數據：

=0時，TE=01011 11001 0110010 (17位)

=1時，TE=010001 1011 010100 (16位)

可以看出，對于相同的測試數據，不同值的A-EFDR編碼對應的編碼長度各不相同，我們選取使編碼長度最短的值進行編碼，這里選取=1。

對比上一節提到的EFDR編碼中的缺陷。EFDR編碼中，前后綴長度相等，值固定為0，對測試集中所有測試向量都使用同一種編碼方法；而在A-EFDR編碼中，值大小可變，可根據測試向量中游程的分布選取最合適的進行編碼。當測試向量中X位比例較低，游程分布以短游程為主時，可選取較小的值，值減小，則編碼表中游程的起始編碼長度減小，有利于對短游程的編碼；而當測試向量中X位比例較高，長游程比例增加時，可選取較大的值，值增大，雖然編碼表中游程的起始編碼長度增加，但每一個組別中包含的不同游程長度個數呈指數增長，仍有利于對長游程的編碼。A-EFDR編碼增加了編碼方法的靈活性，根據游程的分布，優化了編碼字的長度，有效避免了EFDR編碼中的缺陷。

4 壓縮增益分析

我們從概率論的角度來計算壓縮增益。根據A-EFDR編碼規則，設參數大小為，則組別A包含的游程范圍為，對應的碼字長度為2++1。

設測試數據中某一位為0的概率為，則為1的概率為，其中。則長度為的0游程出現概率為，長度為的1游程出現概率為。由此可得，對于某一游程，其屬于組別A的概率為

組別A對應的碼字長度為2++1。因此A-EFDR編碼的平均編碼長度為

而原始數據中的平均游程長度為

因此得到A-EFDR編碼的壓縮增益為

取=0，即可得到EFDR編碼的壓縮增益為

為了更直觀比較不同值下A-EFDR編碼的壓縮增益，我們通過Matlab畫出了其中取值為-1, 0, 1時A-EFDR編碼的壓縮增益曲線，如圖1所示。縱軸表示壓縮增益，橫軸為每一位取0的概率。因增益曲線關于=0.5軸對稱，所以這里只給出了區間中的曲線進行分析。從圖中可以看出，不同值的A-EFDR編碼有各自優勢的值區間，且值越小，優勢的區間越靠近=0.5。在時，壓縮增益最高；時，=0壓縮增益最高；＞0.88時，=1壓縮增益最高。實際上，隨著的增大，值也需要增加才能取得更高的壓縮增益，如＞0.92時，=2比=1的壓縮增益更高。因此我們可以根據測試向量中值的大小，選取對應壓縮增益最高的值進行編碼，提高編碼壓縮率。

圖1 不同N值下A-EFDR編碼壓縮增益圖

5 解碼器設計

一個優秀的編碼壓縮方法，在保持較高數據壓縮率的同時，還應當具有較小的硬件解碼開銷[1]。對經過A-EFDR編碼壓縮的碼字經過簡單的數學運算即可解碼，且不同值的A-EFDR編碼均可使用相同的解碼電路來解碼。

設測試數據游程長度為，編碼參數為，編碼后碼字的前綴大小為1，后綴大小為2，則與,1,2之間的數學關系表達式為

以=1時的A-EFDR編碼為例，設前綴1= (10)2，后綴2=(111)2，則游程長度為：位，表達式前綴1乘以2，對應于解碼器中是將前綴1左移位的操作，不同值的A-EFDR編碼對應移位的長度不同。在電路中實現移位操作較為簡單，所需的硬件代價較小。

圖2為A-EFDR編碼方案解碼電路框圖。其結構由一個有限狀態機(FSM)、一個位計數器、一個log2位計數器、一個位計數器、一個位寄存器和一個異或門組成。其中位計數器用于讀取編碼中的前綴和后綴；log2位計數器記錄前綴和后綴的長度；位寄存器和位計數器分別存儲當前編碼的參數和對應的測試向量數目；標識位flag通過異或門控制當前解碼數據的游程種類。與EFDR解碼電路[4]相比，本解碼電路僅增加了一個位計數器和一個位寄存器，增加的硬件開銷相對較小。

該解碼電路解碼步驟如下：

(1)讀入信息控制位部分：信號en置為高電平,接收bit_in中的數據，將當前編碼參數和對應的向量數目分別存入位寄存器和位計數器中。

(2)讀入標識位部分：接收bit_in的一位數據，賦值給flag信號。

(3)讀入前綴部分：bit_in中的數據讀入位計數器，直到接收到0為止(接收到0表示前綴部分讀入完畢，這里0讀取但不存入計數器中)；log2計數器記錄前綴的位數。之后讀取位寄存器中的參數，將位計數器中數值左移位，log2計數器中數值增加。

(4)前綴部分解壓：FSM輸出0至data,輸出高電平，表示輸出有效。FSM每輸出一個0,位計數器減1，直到位計數器為空，rs1為1，前綴部分解壓結束。

(5)讀入后綴部分：bit_in中的數據接著讀入位計數器，每讀入一位數據log2位計數器減1，直到log2位計數器為空，rs3為1，后綴部分讀入結束。

(6)后綴部分解壓：與前綴解壓部分類似，FSM輸出0至data，輸出0的個數為位計數器的數值，之后再輸出一個1，游程解壓完畢。

(7)若一個測試向量解壓完畢，位計數器減1。當計數器數值為0時，轉入步驟(1)，重新讀入控制信息位；否則轉入步驟(2)，開始新游程的解碼。

圖2 解碼電路框圖

6 實驗結果與分析

為了驗證A-EFDR編碼的壓縮效果，本文以Mintest故障測試集為對象，對ISCAS-89 標準電路中最大的幾個電路進行了實驗。

在A-EFDR編碼中，需要對測試集中不同測試向量選取各自最合適的值進行編碼。本文中對每個測試向量用不同的值進行了嘗試，選取對應最合適的那個，得到的值分布表如表5所示，表中任意值對應的列，表示選取相應值的測試向量個數，最后一列為測試向量數目總和。之后每個測試集中的測試向量按對應值的大小進行了重排序。

從表中可以看出，值的大小分布在-1~7之間，不同測試集的值范圍各不相同。其中電路s5378和s38417的值最高值都比較小，這是因為這兩個電路的高Ｘ位比例的測試向量中，確定位并非均勻分布，而是集中出現的，這使得測試向量中仍存在相當比例的短游程，導致對應的值比較小。

表5 N值分布表

由第5節提到的解碼過程可知，A-EFDR編碼與EFDR編碼相比，需要額外存儲一些控制信息位，包括當前編碼參數，以及值對應的測試向量數目。表6為控制信息位表，列出了各個測試集中原始測試數據的位數，和所需額外存儲的控制信息位數。信息位計算方法以電路s9234為例：由表5可知，s9234的測試集被分為了8個子集，每個子集需要提供一次對應的值和測試向量數目。值最大為6，需要用3位表示；而不同值下，最大測試向量個數為42(時)，需要用6位表示，因此s9234總共所需存儲的控制信息位位數為：位。

從表6中可以看出，各個測試集中所需存儲的控制信息位都很小，最大不超過100位，對比于Mintest測試集中原始測試數據的位數，所占比例極小，因而對測試數據的壓縮不會有太大影響。

表7為本方法與目前國內外主流的編碼壓縮方法在壓縮率[3]方面的比較，其中第2列到第5列為基于游程的編碼壓縮方法，分別為EFDR編碼[4]，多維游程編碼(MD-PRC)[5]，交替變游程編碼(AVR)[6]和對稱游程編碼(SVC)[7]；第6第7列為基于數據塊的編碼壓縮方法，分別為塊合并編碼(BM)[10]和四值稀疏存儲編碼[11]；最后一列為本文提出的A-EFDR編碼。以上編碼壓縮方法都是選用的相同的測試集，且都沒有進行向量差分或掃描鏈重排序等操作。本文A-EFDR編碼方法中，對無關位X的填充，采用文獻[16]中提出的動態最優填充算法。

表6控制信息位表

電路名稱測試數據位數控制信息位數占比(%) s5378 23754320.13 s9234 39273720.18 s13207165200990.06 s15850 76986640.08 s35932 28208240.08 s38417164736360.02 s38584199104720.04

從表７中可以看出，與EFDR編碼相比，本文方法對每個電路測試集的壓縮率都有提高，平均提高了4.07%，這也說明了本方法對EFDR編碼中缺陷的改進是有效果的。7個電路中，電路s35932在壓縮率已經很高(80.80%)的基礎上繼續提高了4.27%，這主要是因為s35932測試集中確定位0和1并非均勻分布，而是“抱團”出現，測試集中含有大量的連續0和連續1，形成了許多長游程，使得每個測試向量對應的值都比較高(參見表5)，因而壓縮率較值固定為0的EFDR編碼有較大提高。

表7本方法壓縮效果與其他壓縮方法的比較(%)

電路名稱EFDR[4]MD-PRC[5]AVR[6]SVC[7]BM[10]稀疏存儲[11]本文方法 s537853.6754.6352.3051.8054.9853.6355.70 s923448.6653.2050.7250.9451.1954.2354.91 s1320782.4986.0183.3883.7784.8985.9185.85 s1585068.6669.9970.0869.9869.4971.4572.32 s3593280.80-81.72-78.3578.0785.07 s3841762.0255.3862.8263.3059.3962.0366.02 s3858464.2867.7365.8966.2666.8668.5069.21 Avg65.8064.4966.7064.3466.4567.6969.87

對比表中的其他國內外參考文獻，除s13207電路外，本文方法的壓縮效果都是最優的，且本文方法還有解碼電路簡單的優勢，這些數據也充分說明了本編碼壓縮方法的有效性。

7 結論

針對測試集中不同測試向量的游程分布存在巨大差異的特點，本文提出了一種自適應EFDR編碼的測試數據壓縮方法。本文方法以EFDR編碼為基礎，增加了一個用于表示后綴與前綴編碼長度差值的參數，對測試集中的不同測試向量，選用不同的值進行編碼，有效提高了測試數據壓縮率。在解碼方面，本方法較EFDR編碼僅需增加少量硬件資源，硬件解碼開銷仍然較低。綜上所述，本文方法具有較好的應用前景。

[1] Mehta U S, Dasgupta K S, and Evashrayee N J. Un-length-based test data compression techniques: how far from entropy and power bounds a survey[J]., 2010(1): 1-9.

[2] 劉鐵橋, 鄺繼順, 蔡爍. 一種將測試集嵌入到Test-per-Clock位流中的方法[J]. 計算機研究與發展, 2014, 51(9): 2022-2029.

Liu Tie-qiao, Kuang Ji-shun, and Cai Shuo. A new method of embedding test patterns into test-per-clock bit stream[J]., 2014, 51(9): 2022-2029.

[3] Anshuman C and Krishnendu C. Frequency-Directed Run- length(FDR) codes with application to system-on-a-chip test data compression[C]. Proceedings of the 19th IEEE VLSI Test Symposium, Atlantic, 2001: 42-47.

[4] EL-Maleh A H. Test data compression for system-on-a-chip using Extended Frequency-Directed Run-Length Code[J].&, 2008(2): 155-163.

[5] Dauh T W and Jen L L. Test data compression using multi-dimensional pattern run-length codes[J]., 2010, 26(3): 393-400.

[6] Ye B, Zhao Q, Zhou D,.. Test data compression using alternating variable run-length code[J].,, 2011(44): 103-110.

[7] 梁華國, 蔣翠云, 羅強. 應用對稱編碼的測試數據壓縮方法[J]. 計算機研究與發展, 2011, 48(12): 2391-2399.

Liang Hua-guo, Jiang Cui-yun, and Luo Qiang. Test data compression and decompression using symmetry-variable codes[J]., 2011, 48(12): 2391-2399.

[8] 馬會, 鄺繼順, 馬偉. 基于一位標識的測試向量混合編碼壓縮方法[J]. 電子測量與儀器學報, 2013, 27(4): 312-318.

Ma Hui, Kuang Ji-shun, and Ma Wei. Hybrid coding compression method of test vector based on an identification [J]., 2013, 27(4): 312-318.

[9] Gonciari P T, AI-Hashimi B M, and Nicolici N. Variable- length input Huffman coding for system-on-a-chip test[J]., 2003, 22(6): 783-789.

[10] EL-Maleh A H. Efficient test compression technique based on block merging[J].&, 2008, 5(2): 327-335.

[11] Zhang L and Kuang J S. Test data compression using selective sparse storage[J]., 2011, 27(4): 565-577.

[12] 劉杰, 易茂祥, 朱勇. 采用字典詞條衍生模式的測試數據壓縮[J]. 電子與信息學報, 2012, 34(1): 231-235.

Liu Jie, Yi Mao-xiang, and Zhu Yong. Test data compression using entry derivative mode of dictionary[J].&, 2012, 34(1): 231-235.

[13] Sismanoglou P and Nikolos D. Test data compression based on reuse and bit-flipping of parts of dictionary entries[C]. Proceedings of 17th International Symposium on Design and Diagnostics of Electronic Circuits & Systems, Warsaw, 2014: 110-115.

[14] Tyszer J, Filipek M, Mrugalski G,.. New test compression scheme based on low power BIST[C]. Processdings of 18th IEEE European Test Symposium, Avignon, 2013: 1-6.

[15] Chloupek M, Jenicek J, Novak O,.. Test pattern decompression in parallel scan chain architecture[C]. Proceedings of 16th International Symposium on Design and Diagnostics of Electronic Circuits & Systems, Karlovy, 2013: 219-223.

[16] 方昊, 姚博, 宋曉笛. 雙游程編碼的無關位填充算法[J]. 電子學報, 2009, 37(1): 1-7.

Fang Hao, Yao Bo, and Song Xiao-di. The algorithm of filling X bits in dual-run-length coding[J]., 2009, 37(1): 1-7.

Adaptive EFDR Coding Method for Test Data Compression

Kuang Ji-shun Zhou Ying-bo Cai Shuo

(&,,410082,)

An adaptive Extended Frequency-Directed Run-length (EFDR) code method for test data compression is presented in this paper. The method is based on EFDR code, and adds an additional parameter, which is used to represent the code length difference between tail and prefix. According to the distribution of the runs in each test vector of the test set, the method selects the most suitablevalues to code, and it can improve the compression ratio. For the decompression, according to the size of the codeword, the run length of the original test data can be obtained with a simple mathematical operation. Meanwhile, those codeword under different parameter values can be decoded by the same decompression circuit. Thus, the decompression circuit can keep in a low hardware cost level. The experimental result shows that the average compression rate of the proposed method can achieve to 69.87%, over 4.07% than original EFDR code method.

Test data compression; Extended Frequency-Directed Run-length (EFDR) code; Adaptive EFDR code; decode

TP302

A

1009-5896(2015)10-2529-07

10.11999/JEIT150177

2015-02-02；改回日期：2015-05-21；

2015-07-06

周穎波 zhoubobo@163.com

國家自然科學基金(61472123, 60673085)

The National Natural Science Foundation of China (61472123, 60673085)

鄺繼順： 男，1959年生，博士，教授，研究方向為集成電路測試與設計，嵌入式系統.

周穎波： 男，1984年生，博士生，研究方向為集成電路測試.

蔡 爍： 男，1982年生，博士生，研究方向為集成電路測試.