吳 瓊，周嘯宇

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

集成電路產(chǎn)業(yè)發(fā)展迅速，電路芯片的復(fù)雜度不斷提高，測(cè)試難度和成本迅速增加，而測(cè)試芯片的傳輸帶寬和存儲(chǔ)能力的增長(zhǎng)卻十分有限。二者之間的矛盾導(dǎo)致測(cè)試成本提高、測(cè)試時(shí)間增加。減少測(cè)試數(shù)據(jù)量可以有效地解決此問(wèn)題。采用編碼壓縮的方法可以有效降低測(cè)試數(shù)據(jù)量[1-3]。傳統(tǒng)編碼通過(guò)減少代碼字的平均長(zhǎng)度來(lái)實(shí)現(xiàn)數(shù)據(jù)壓縮，處理部分交替游程時(shí)壓縮效果欠佳。相對(duì)游程長(zhǎng)度編碼方案僅需編碼相對(duì)游程長(zhǎng)度，即編碼當(dāng)前游程與所選參考值的差值，縮短待編碼游程長(zhǎng)度，減少對(duì)應(yīng)代碼字長(zhǎng)度，提高壓縮率。但一般方案只是簡(jiǎn)單通過(guò)編碼當(dāng)前游程與前一游程長(zhǎng)度的差值縮短待編碼游程長(zhǎng)度[4]。由于相鄰位游程長(zhǎng)度的差值有些很小，有些可能非常大，所縮短的游程長(zhǎng)度之和不一定最優(yōu)，因此會(huì)影響到壓縮效果。本文對(duì)此方案進(jìn)行改進(jìn)，將實(shí)驗(yàn)與編程相結(jié)合，編碼之前先尋求最優(yōu)參考值，使得所縮短待編碼游程長(zhǎng)度之和最小，達(dá)到最優(yōu)的壓縮效果。

1 編碼方案

長(zhǎng)度越短的游程，編碼時(shí)所需的代碼字越短。相對(duì)游程長(zhǎng)度編碼方法，先將預(yù)處理后的測(cè)試數(shù)據(jù)進(jìn)行多段劃分[5]，再將各劃分段長(zhǎng)度取值與所取參考值“Y”進(jìn)行比對(duì)以進(jìn)行相對(duì)游程編碼處理，從而減少編碼時(shí)所需的代碼字，達(dá)到最終數(shù)據(jù)壓縮的效果[6]。相對(duì)游程編碼方法在預(yù)處理后根據(jù)劃分統(tǒng)計(jì)每組游程的長(zhǎng)度A1、A2、A3、A4、… 、An，從小到大依次排列，設(shè)相對(duì)游程參考值為“Y”值（若為小數(shù)，則四舍五入取整），各組游程長(zhǎng)度依次與“Y”做差并取絕對(duì)值得a= ||A1-Y。若a＜0，則記為Q0，表示游程長(zhǎng)度值小于Y；若a＞0，則記為Q1，表示游程長(zhǎng)度值大于Y；若a=0，也默認(rèn)記為Q0，表示游程長(zhǎng)度值等于Y。稱Q0和Q1中的0和1為正負(fù)位[7]。

參照小規(guī)模實(shí)驗(yàn)結(jié)果，本方案的“Y”取實(shí)驗(yàn)結(jié)果中較好的中位數(shù)、平均數(shù)和眾數(shù)（此處是指各劃分段長(zhǎng)度取值的中位數(shù)、平均數(shù)和眾數(shù)）。按以下流程確定相對(duì)游程最優(yōu)參考值：預(yù)處理后對(duì)待測(cè)集進(jìn)行分段；對(duì)Y進(jìn)行取值，令Y=n（n=1,2,3,…,100）；將Y的不同取值分別輸入所編程序，運(yùn)用程序統(tǒng)計(jì)出Y與所有游程段的相對(duì)長(zhǎng)度之和的最小值，此時(shí)的Y取值即為相對(duì)游程最優(yōu)秀參考值；將最優(yōu)取值與對(duì)應(yīng)游程段的中位數(shù)、平均數(shù)和眾數(shù)等進(jìn)行比較，確定最優(yōu)值。通過(guò)實(shí)驗(yàn)，得到結(jié)果如表1所示。從表1可以得出中位數(shù)最接近實(shí)驗(yàn)最優(yōu)值，優(yōu)于平均數(shù)和眾數(shù)，為最優(yōu)取值。

表1 最優(yōu)值表

2 編碼表

為使得編碼后的數(shù)據(jù)集能夠在解碼時(shí)恢復(fù)到原始的測(cè)試集，改進(jìn)型相對(duì)游程長(zhǎng)度編碼如表2所示。

表2 改進(jìn)型相對(duì)游程長(zhǎng)度編碼表

編碼表的第1列為組號(hào)，第2列表示預(yù)處理后的各段游程長(zhǎng)度和其游程長(zhǎng)度中位數(shù)差的絕對(duì)值，即相對(duì)位數(shù)，第3、4、5列表示連續(xù)0游程編碼，第3列為連續(xù)0游程的附加值，第4列形式如同10、110、1110、…，表示連續(xù)0游程的前綴，第5列為其后綴；與之類似，第6列表示連續(xù)1游程的附加值，第7、8列表示其前綴及后綴；第9列表示交替01游程的附加值，第10列表示其前綴，形式如同01、001、0001、…，第11列表示其后綴；第12列表示交替10游程的附加值，第13、14列表示其前綴及后綴[8]。下面以一個(gè)實(shí)例來(lái)檢驗(yàn)該編碼方案的壓縮效果：

將原始測(cè)試集{0101010101000000X0X01101010101001111111111111000X00X0001}進(jìn)行填充并劃分后得到測(cè)試集ZD=010101010100 000000001 10101010100 11111111111110 0000000001，依照編碼表對(duì)其進(jìn)行編碼后得：ZE=110101 001010 000100 111011 001001。原始測(cè)試集長(zhǎng)度為56位，編碼后長(zhǎng)度為30位，壓縮效果顯著。

3 數(shù)值實(shí)驗(yàn)

為證明本改進(jìn)型相對(duì)游程長(zhǎng)度編碼方案的有效性，采用MinTest產(chǎn)生的測(cè)試向量集，對(duì)ISCАS 89標(biāo)準(zhǔn)電路中的部分規(guī)模較大的時(shí)序電路分別進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示。

表3 本方案壓縮率

從壓縮效果看，本方案對(duì)s5378和s9234兩個(gè)規(guī)模相對(duì)較小電路的壓縮效率較低，原因是其測(cè)試集中大部分游程長(zhǎng)度較短，不規(guī)律游程段相對(duì)較多。本文方案對(duì)此類電路壓縮效果不是很好，而對(duì)電路中含有大量的長(zhǎng)游程和規(guī)律交替游程的s13207、s15850、s35932、s38417和s38584幾個(gè)電路的壓縮效率則比較高。在實(shí)際操作中，集成電路的電路規(guī)模一般都比較大，含有較多無(wú)關(guān)位，處理這些電路，本文的相對(duì)游程長(zhǎng)度編碼方案是有效的[9]。

將本方案與國(guó)內(nèi)2種壓縮方案的壓縮效率進(jìn)行對(duì)比，具體結(jié)果如表4所示。

表4 本方案與國(guó)內(nèi)2種方案壓縮效率對(duì)比表

相對(duì)國(guó)內(nèi)另兩種壓縮方案，本方案有較高的壓縮率、較好的穩(wěn)定性。同F(xiàn)DR碼作對(duì)比，本方案的壓縮率平均值優(yōu)于其1.3%；同Golomb碼對(duì)比，本方案的壓縮率平均值優(yōu)于其7.0%。

4 總結(jié)

為進(jìn)一步提高壓縮率，本文提出了一種改進(jìn)型相對(duì)游程長(zhǎng)度編碼方案，對(duì)測(cè)試數(shù)據(jù)進(jìn)行一系列預(yù)處理后，先取得最優(yōu)值，再將游程長(zhǎng)度與最優(yōu)值作差，取得相對(duì)位數(shù)進(jìn)行數(shù)據(jù)編碼，壓縮效果良好。本方案提供的編碼方法適用于游程長(zhǎng)度跨度較小與待測(cè)數(shù)據(jù)中交替游程比較多的電路，具有較高的壓縮率和較好的穩(wěn)定性。