暴　陽(yáng)，吳　瓊

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

?

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

暴陽(yáng)，吳瓊

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

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

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

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

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

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

表1　編碼表

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

2編碼實(shí)例

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

原始測(cè)試向量：1111110000000

11100000000111111111

編碼后測(cè)試向量：110000 1001

0 10010 1100101 011

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

3編碼算法的理論分析

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

2L-3

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

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

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

相連的兩個(gè)游程屬于同一組的概率為

壓縮后的平均編碼字長(zhǎng)度是

任意游程編碼字的平均長(zhǎng)度為

壓縮率：

4解壓器的設(shè)計(jì)

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

圖1 解碼器

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

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

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

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

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

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

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

表2　3種方案的壓縮比較

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

參考文獻(xiàn):

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

[2] 俞洋，陳葉富，彭宇. 基于平均值余量的 Wrapper 掃描鏈接平衡算法[J]. 儀器儀表學(xué)報(bào)， 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] 肖祝紅，歐陽(yáng)一鳴，梁華國(guó)．基于狀態(tài)翻轉(zhuǎn)連續(xù)長(zhǎng)度碼的測(cè)試數(shù)據(jù)壓縮和解壓[J]．計(jì)算機(jī)工程，2007，33(16)：214-216．

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

[8] 詹文法,梁華國(guó),時(shí)峰,等. 混合定變長(zhǎng)碼的測(cè)試數(shù)據(jù)壓縮方案[J].計(jì)算機(jī)學(xué)報(bào)，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] 歐陽(yáng)一鳴，黃喜娥，梁國(guó)華，等.基于部分?jǐn)?shù)據(jù)塊復(fù)用的 SoC 測(cè)試數(shù)據(jù)壓縮方法[J] . 電子測(cè)量與儀器學(xué)報(bào)，2010，24(5)：487-493.

[12] 歐陽(yáng)一鳴，鄒寶升，梁華國(guó)，等. 基于部分游程翻轉(zhuǎn)的 SoC 測(cè)試數(shù)據(jù)壓縮[J] . 電子測(cè)量與儀器學(xué)報(bào) ，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

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

中圖分類號(hào)：TP273

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

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

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61306046)和國(guó)家自然科學(xué)基金(61540011)。

*收稿日期：2014-08-05

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