連續(xù)交替共前綴長度碼測試數(shù)據(jù)壓縮和解壓方案

暴　陽，吳　瓊

(安慶師范學(xué)院 數(shù)學(xué)與計算科學(xué)學(xué)院, 安徽 安慶 246133)

?

連續(xù)交替共前綴長度碼測試數(shù)據(jù)壓縮和解壓方案

暴陽，吳瓊

(安慶師范學(xué)院 數(shù)學(xué)與計算科學(xué)學(xué)院, 安徽 安慶 246133)

摘要：本文提出了一種新的編碼方法，對連續(xù)序列進(jìn)行編碼，如果前后兩個編碼組有相同的前綴，那么用一個標(biāo)記位1，就可以代替后一個游程很長的前綴。如果兩個游程不在同一組，就用一個標(biāo)記位0隔開，后面按源代碼編碼。

關(guān)鍵詞：編碼；前綴；游程

隨著科學(xué)技術(shù)的發(fā)展，芯片越來越復(fù)雜，集成度也越來越高，這樣就給測試帶來了很大的困難，因為測試所需要的測試數(shù)據(jù)多了，而現(xiàn)在已有的自動測試芯片的設(shè)備工作頻率、存儲量以及帶寬都非常有限，這就使得 SoC的測試存在著測試時間長、測試成本增加等問題[1]。怎么解決呢？有兩種辦法，第一，更換更加高端的設(shè)備，但這樣會使測試成本增加；第二，找一種好辦法，把測試數(shù)據(jù)壓縮后傳輸?shù)綔y試芯片的設(shè)備中去[2-5]，這樣就能快速有效的測試已有數(shù)據(jù)了，如文獻(xiàn)[6-14]。而這些文獻(xiàn)中的壓縮方案是用較短的代碼字來代替長的游程，沒有想過把碼表中的數(shù)據(jù)變得簡單，并且探討它們之間的關(guān)系。因此，本文提出一種新的編碼方法，該方法在對連續(xù)序列編碼的基礎(chǔ)上，進(jìn)一步探討相鄰游程之間的相關(guān)性。

1連續(xù)交替共前綴長度碼算法思想

連續(xù)交替共前綴長度碼算法是對交替連續(xù)的 “0”或“1”進(jìn)行編碼。如編碼表1中，把所有可能出現(xiàn)的連續(xù)長度分成若干個A1，A2，A3，…，Ak組。在表1的A1組中直接從長度為1的編碼開始，因為不存在0位連續(xù)的數(shù)。表1中最大組Ak的下標(biāo)k由測試集的最長連續(xù)序列的長度Lmax來確定，其中Lmax滿足不等式2k-3

表1　編碼表

編碼思路。首先對被測數(shù)據(jù)的無關(guān)位進(jìn)行賦值，當(dāng)碰到無關(guān)位x，x前要是1就賦值x為1，是0就賦值x為0 (如果是以無關(guān)位開始的，那么x就賦值無關(guān)位后緊接著的數(shù)字，這樣增加了數(shù)據(jù)塊的長度，提高了壓縮率)，這樣編碼字就變成連續(xù)的0和連續(xù)的1交替出現(xiàn)。這樣只要知道第一個數(shù)據(jù)塊是連續(xù)的1還是連續(xù)的0，后面的每個數(shù)據(jù)塊也就可以知道了 ，之后還用短的代碼字代替長的游程。因此本方案更進(jìn)一步探討了相鄰游程之間的關(guān)系，如果前后兩個游程在同一組，那么，根據(jù)表1可以看到，它們就有相同的前綴，這樣就可以省略后面的前綴，只在它們之間加一個標(biāo)記位1就可以了，即將緊跟其后的游程編碼字的前綴部分用一個標(biāo)記位加尾部來表示，這樣就省了一個前綴，多了一位標(biāo)記位。前綴的位數(shù)肯定大于標(biāo)記位，這樣就減少了很多位數(shù)。如果它們不在同一組，那么就用一個標(biāo)記位0隔開，表示它們沒有相同的前綴，后面按源代碼編碼。

2編碼實例

例如1111110000001xx0xxx10x,就賦值為1111110000001110000100。 當(dāng)把測試數(shù)據(jù)的無關(guān)位x賦值了以后，那么被測數(shù)據(jù)就變成連續(xù)的1和連續(xù)的0交替的了，只需知道開頭是連續(xù)的0還是連續(xù)的1，就知道后面分別是連續(xù)的什么了，因為每個數(shù)據(jù)塊都是交替出現(xiàn)的。比如連續(xù)的1之后就是連續(xù)的0，連續(xù)的0之后就又是連續(xù)的1。例如，111111000000011100000000111111111，首先是6個連續(xù)的1，對照表1的編碼字就是110000，然后是7個連續(xù)的0對照表1就是110001，但是6和7都在同一組A3組中，它們的前綴都是110，這樣就可以省了前綴只寫后綴001，但是需要加一個標(biāo)記位1，表示后面7個0和前面6個1在同一組，省了前綴，編碼后就是1100001001。再看7個連續(xù)的0之后是3個連續(xù)的1，它和7個連續(xù)的0不在同一組，就不能共前綴了，只能寫成1001，不共前綴中間也加一個標(biāo)記位0，編碼之后就是110000100101001，后面是8個0和前面的3個1他們不共前綴，所以加一個標(biāo)記位0，就是1100001001010010110010，后面是9個連續(xù)的1，和前面的8個連續(xù)的0在同一組，也可以共前綴，加一個標(biāo)記位1，只寫后綴011就可以了，編碼之后就是11000010010100101100101011，結(jié)果如下：

原始測試向量：1111110000000

11100000000111111111

編碼后測試向量：110000 1001

0 10010 1100101 011

原始測試向量共33位，TE共26 位，節(jié)省7 位。

3編碼算法的理論分析

對于表1，每組中最大的數(shù)Lmax和它的組Am滿足關(guān)系式:

2L-3

如果知道一個長度L，那么它所在的組m滿足關(guān)系式：

m=「log2(L+3)-1?。

Am組就有2m個元素(除第一組外)。Am組前綴的長度為m，它們的長度相同，因此Am的編碼字的長度為2m，則前綴所代表的原始數(shù)據(jù)的長度為2m-2，尾部所能代表的原始數(shù)據(jù)長度為2m+1-3。因此Am這一組所能編碼的原始數(shù)據(jù)長度范圍為[2m-2,3×2m-5]。在測試數(shù)據(jù)中假設(shè)1出現(xiàn)的概率為p，那么0出現(xiàn)的概率就是1-p，則對于編碼數(shù)據(jù)中的任意長度為L的任意1或0游程出現(xiàn)的概率分別為pL或(1-p)L，它們屬于Am組的概率為

相連的兩個游程屬于同一組的概率為

壓縮后的平均編碼字長度是

任意游程編碼字的平均長度為

壓縮率：

4解壓器的設(shè)計

這個解壓器的設(shè)計需要一個有限狀態(tài)機(jī)，1個T觸發(fā)器，2個計數(shù)器，2個寄存器，因此解壓結(jié)構(gòu)比較簡單，電器原件都是常用的，所以不用引進(jìn)新的設(shè)備，從而比較節(jié)約成本。其中bit-in是位輸入，en是使能信號，有限狀態(tài)機(jī)是通過counter-in控制k位計數(shù)器的。Shift把編碼傳送給k位計數(shù)器，有限狀態(tài)機(jī)通過dec1控制計數(shù)器進(jìn)行減一操作。Load再把存在寄存器里的東西傳給計數(shù)器中。Log2k位計數(shù)器用在識別編碼字在表1中的哪一組，inc控制該計數(shù)器進(jìn)行加一計數(shù)，dec2控制計數(shù)器進(jìn)行減一計數(shù)。T觸發(fā)器用來控制是否翻轉(zhuǎn)和輸入的解壓信號是否有效。解壓器的工作原理如圖1所示。

圖1 解碼器

(1) 開始有限狀態(tài)機(jī)發(fā)出“en”,緊接著“shift”還有“inc”都變成高電平，這樣“bit-in”把編碼字的前綴輸給k位計數(shù)器和Log2k位計數(shù)器，操作他們加一。直到“bit-in”遇到0時，操作結(jié)束。

(2) reg-cnt1和reg-cnt2變成高電平，這就使得k-b dcnt復(fù)制剛才的前綴給k位寄存器中，同時dcnt2把存在Log2k位計數(shù)器中的長度復(fù)制到Log2k位寄存器中。

(3) Dec1置于高電平，使k位計數(shù)器進(jìn)行減一操作，out1開始連續(xù)輸出編碼字，當(dāng)rs1為高電平時，k位計數(shù)器減為0，前綴解碼停止。

(4) Log2k位計數(shù)器控制“bit-in”把編碼字的前綴準(zhǔn)確的輸入到k位計數(shù)器中。Out繼續(xù)輸出編碼字，直到k位計數(shù)器減到0為止，第一組連續(xù)序列解碼結(jié)束。

(5) 對bit-in中的數(shù)據(jù)進(jìn)行判斷。如果為0，重復(fù)上述過程(1)，(2)，而(3)，(4)中的Out改為連續(xù)輸出0，即 “Out”變?yōu)楦唠娖?，使T觸發(fā)器翻轉(zhuǎn)一次，使解碼的連續(xù)序列是上一個的反值；如果為1，k-b counter把k位寄存器中的值傳給k位計數(shù)器中，load3把Log2k位寄存器中的值傳給Log2k位計數(shù)器中，之后開始(3)的工作，而(3)，(4)中的Out改為連續(xù)輸出0，即 “Out”變?yōu)楦唠娖?，使T觸發(fā)器翻轉(zhuǎn)一次，使解碼的連續(xù)序列是上一個的反值。

5實驗結(jié)果與討論

用該方法與其他方法對數(shù)據(jù)的壓縮效果如表2所示。從表2可以看出，本文提出的壓縮方法能更好地壓縮測試數(shù)據(jù)，從而有效地證明了該方法的優(yōu)越性。

表2　3種方案的壓縮比較

這種方法把測試數(shù)分成一個個數(shù)據(jù)塊，每一個數(shù)據(jù)塊要么是連續(xù)的1，要么是連續(xù)的0，并且把每組連續(xù)的“0”或連續(xù)的“1” 的長度，用表1進(jìn)行編碼，不用區(qū)分是連續(xù)的1還是連續(xù)的0。另外，本方案還更進(jìn)一步明確了相鄰游程之間的關(guān)系，即后一游程如果與前一游程在同一組，那么它們就有相同的前綴，則將后面游程的前綴部分省去，整個游程只用一個標(biāo)記位1加尾部來表示，這樣就用一個1就可以代替好幾位的前綴。因此該編碼方案能夠有效地壓縮測試數(shù)據(jù)，從而更優(yōu)于其他編碼方法，是一種比較高效的壓縮方法。

參考文獻(xiàn):

[1] 許川佩，胡紅波 . 基于量子粒子群算法的 SoC 測試調(diào)度優(yōu)化研究[J] . 儀器儀表學(xué)報, 2011，32(1)：113-119 .

[2] 俞洋，陳葉富，彭宇. 基于平均值余量的 Wrapper 掃描鏈接平衡算法[J]. 儀器儀表學(xué)報， 2011，32(10)：2290-2296.

[3] A. Chandra，K. Chakrabarty．System-on-a-chip test datacompression and decompression architectures based on golomb codes[J]．IEEE Trans．on CAD of Integrated Circuits and Systems，2001，20(3)：355·368.

[4] A. Chandra，K. Chakrabarty．Test data compression and test resource partitioning for system-on-a-chip using frequency-directed run-iength(FDR) codes[J]．IEEE Trans．on Computers,2003,52(8):1076-1088．

[5] A.Wtrtenberger，C. S. Tautermann，S. HeIIebrand. A hybrid coding strategy for optimized test data compression[C].Proceedings of IEEE InternationaI Test Conference，CharIotte，NC，2003：451-459.

[6] 肖祝紅，歐陽一鳴，梁華國．基于狀態(tài)翻轉(zhuǎn)連續(xù)長度碼的測試數(shù)據(jù)壓縮和解壓[J]．計算機(jī)工程，2007，33(16)：214-216．

[7] 詹文法，粱華國，時峰，等．一種混合定變長虛擬塊游程編碼的測試數(shù)據(jù)壓縮方案[J]．電子學(xué)報，2009，37(8)：1837-1841．

[8] 詹文法,梁華國,時峰,等. 混合定變長碼的測試數(shù)據(jù)壓縮方案[J].計算機(jī)學(xué)報，2008，20(21): 5979-5983.

[9] K. J. Balakrishnan. Emerging techniques for test data compression [C].Proceedings of 14th Asian Test Symposium (ATS 2005). USA:IEEE Computer Society Test Technology Technical Council, 2005:462-462.

[10] N.A.Touba.Survey of test vector compression techniques. [J].Design & Test of Computers (S0740-7475), 2006, 23(4): 294-303.

[11] 歐陽一鳴，黃喜娥，梁國華，等.基于部分?jǐn)?shù)據(jù)塊復(fù)用的 SoC 測試數(shù)據(jù)壓縮方法[J] . 電子測量與儀器學(xué)報，2010，24(5)：487-493.

[12] 歐陽一鳴，鄒寶升，梁華國，等. 基于部分游程翻轉(zhuǎn)的 SoC 測試數(shù)據(jù)壓縮[J] . 電子測量與儀器學(xué)報 ，2010，24(1)：23-28.

[13] Paul T. Gonciari, Bashir M.Al-Hashimi, N. Nicolici. Variable-length input huffman coding for system-on-a-chip test [J].IEEE Transactions on CAD of Integrated Circuits and Systems IEEE Transitions on CAD of Integrated Circuits and System (S0278-0070) , 2003 , 22(6): 783-796.

[14] M. Tehranipoor , M. Nourani, K. Chakrabarty. Nine-coded compression technique for testing embedded cores in SoCs[J]. IEEE Transactions on VLSI Systems (S1063-8210), 2005, 13(6): 719-731.

Scheme of Test Data Compression and Decompression Based on Continuous Alternation Sharing-Prefix Length Code

BAO Yang，WU Qiong

(School of Mathematics and Computation Science，Anqing Teachers College，Anqing,Anhui 246133，China)

Abstract:This paper proposes a new coding method. The method further explores the correlation between the adjacent run on the basis of continuous sequence coding meanwhile if the two have the same prefix. This scheme uses 1 bit to represent the whole prefix.

Key words:coding, sharing-prefixed, run

文章編號：1007-4260(2016)01-0043-04

中圖分類號：TP273

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

DOI：10.13757/j.cnki.cn34-1150/n.2016.01.013

作者簡介：暴陽，男，河北邯鄲人，安慶師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院碩士研究生，研究方向為數(shù)據(jù)壓縮技術(shù)。E-mail: 371877612@qq.com通訊作者：吳瓊，女，安徽黃山人，安慶師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院教授，碩士生導(dǎo)師，主要研究方向為內(nèi)建自測試、電子設(shè)計自動化。E-mail: 1979382944@qq.com

基金項目：國家自然科學(xué)基金(61306046)和國家自然科學(xué)基金(61540011)。

*收稿日期：2014-08-05

網(wǎng)絡(luò)出版時間：2016-03-15 17:05網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160315.1705.013.html