改進型相對游程長度編碼方法

吳 瓊，周嘯宇

（安慶師范大學(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ù)壓縮，處理部分交替游程時壓縮效果欠佳。相對游程長度編碼方案僅需編碼相對游程長度，即編碼當前游程與所選參考值的差值，縮短待編碼游程長度，減少對應(yīng)代碼字長度，提高壓縮率。但一般方案只是簡單通過編碼當前游程與前一游程長度的差值縮短待編碼游程長度[4]。由于相鄰位游程長度的差值有些很小，有些可能非常大，所縮短的游程長度之和不一定最優(yōu)，因此會影響到壓縮效果。本文對此方案進行改進，將實驗與編程相結(jié)合，編碼之前先尋求最優(yōu)參考值，使得所縮短待編碼游程長度之和最小，達到最優(yōu)的壓縮效果。

1 編碼方案

長度越短的游程，編碼時所需的代碼字越短。相對游程長度編碼方法，先將預(yù)處理后的測試數(shù)據(jù)進行多段劃分[5]，再將各劃分段長度取值與所取參考值“Y”進行比對以進行相對游程編碼處理，從而減少編碼時所需的代碼字，達到最終數(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，也默認記為Q0，表示游程長度值等于Y。稱Q0和Q1中的0和1為正負位[7]。

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

表1 最優(yōu)值表

2 編碼表

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

表2 改進型相對游程長度編碼表

編碼表的第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}進行填充并劃分后得到測試集ZD=010101010100 000000001 10101010100 11111111111110 0000000001，依照編碼表對其進行編碼后得：ZE=110101 001010 000100 111011 001001。原始測試集長度為56位，編碼后長度為30位，壓縮效果顯著。

3 數(shù)值實驗

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

表3 本方案壓縮率

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

將本方案與國內(nèi)2種壓縮方案的壓縮效率進行對比，具體結(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é)

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