吳 瓊，周嘯宇

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

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

1 編碼方案

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

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

表1 最優(yōu)值表

2 編碼表

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

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

編碼表的第1列為組號，第2列表示預(yù)處理后的各段游程長度和其游程長度中位數(shù)差的絕對值，即相對位數(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]。下面以一個實例來檢驗該編碼方案的壓縮效果：

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

3 數(shù)值實驗

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

表3 本方案壓縮率

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

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

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

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

4 總結(jié)

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