黃 麗，吳 瓊

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

一種基于異或運算折半劃分的測試數(shù)據(jù)壓縮方案

黃 麗，吳 瓊

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

將測試集按單位長度M分成若干塊，通過異或邏輯運算將塊內(nèi)數(shù)據(jù)為“01”和“10”的交替序列變換成全“0”和“1”序列，對于不能轉(zhuǎn)換的序列，不斷進(jìn)行折半劃分。這種基于異或邏輯運算折半劃分的壓縮方法，代碼字的長度可以直接用折半的次數(shù)來表示，一方面減少了代碼字的長度，另一方面解壓時可以直接將計數(shù)器移位，降低了解壓成本，仿真實驗結(jié)果證實壓縮效果良好。

數(shù)據(jù)壓縮；折半劃分；異或邏輯運算；交替序列；Golomb

為了滿足集成電路工藝不斷發(fā)展的要求，IP核復(fù)用思想的提出導(dǎo)致系統(tǒng)芯片（SOC）的集成度越來越高，單個芯片上的數(shù)據(jù)量的增加對電路測試增加了難度。系統(tǒng)自動測試設(shè)備（ATE）已經(jīng)滿足不了測試數(shù)據(jù)量增加的需求，大大增加了測試成本。為了降低測試成本，解決現(xiàn)有的問題，我們發(fā)現(xiàn)壓縮測試數(shù)據(jù)能夠有效減少ATE到SOC的傳輸時間，緩解ATE存儲空間有限的問題。壓縮測試數(shù)據(jù)，即用測試數(shù)據(jù)壓縮技術(shù)，將原測試集TD壓縮為TE存儲在ATE上，傳輸時再通過解碼器還原為TD?，F(xiàn)有壓縮方法也能很好地壓縮數(shù)據(jù)，如FDR碼、Golomb碼、統(tǒng)計碼、交替-連續(xù)長度碼等。

本文所提出基于異或邏輯運算折半劃分的壓縮方法，在折半劃分的基礎(chǔ)上，對非全0/1的序列進(jìn)行優(yōu)化，加入異或邏輯運算化為全1序列，不能進(jìn)行優(yōu)化的再采用折半劃分方法。只要記錄折半的次數(shù)，就可以換算出原始數(shù)據(jù)塊的長度，從而提高壓縮率，減少減壓的硬件開銷，減少成本。

1 折半劃分的基本思想

連續(xù)序列，包括全0序列，如0000……；全1序列，如1111…；交替序列，該數(shù)據(jù)塊中全是0和1交叉的序列，01塊，即010101……；10塊，即101010……

本方法首先將整個測試集看成一個數(shù)據(jù)流，設(shè)定單位長度M（M＜L，L為原測試集的長度），其中M=2n，（n為整數(shù)且n＞0）。按單位長度M的值將整個測試集進(jìn)行劃分。跟折半劃分一樣，取2的冪的長度為單位長度劃分測試集，主要是為了使數(shù)據(jù)塊折半后的長度仍是整數(shù)，以便對測試數(shù)據(jù)長度進(jìn)行統(tǒng)計。然后對每個M長度的數(shù)據(jù)塊進(jìn)行分析，如果全0/1，就用標(biāo)記位來標(biāo)記；如果數(shù)據(jù)塊是01或10序列，就在序列前添加1或0，將每個數(shù)分別與前一個數(shù)異或，化成全1序列，然后用標(biāo)記位表示；如果都不是，對M長度的數(shù)據(jù)塊進(jìn)行折半，再對折半后的數(shù)據(jù)塊進(jìn)行分析，若折半后的長度達(dá)到最小臨界值，則停止折半。假設(shè)最小臨界值為Min，此長度表示折半劃分后的最小塊，也是2的冪。

表1給出了基于邏輯運算的折半劃分的編碼規(guī)則。從表1中可以看出，全0/1塊的長度是2i× Min，其中Min是最小塊長，在編碼字中不做任何編碼，A取值可為0，1，X，表示此塊全0，全1或無關(guān)位，B取值可能為0或1，表示序列前面加0或1異或得到的全1序列。全0/1塊的個數(shù)越多時，它的標(biāo)記位也就越長。全0/1長度為M時的標(biāo)記位最長，可以根據(jù)編碼規(guī)則算出它的標(biāo)記位。如果數(shù)據(jù)塊是01或10序列，就在序列前添加1或0，將每個數(shù)分別與前一個數(shù)異或，化成全1序列，然后用標(biāo)記位表示之后在編碼字后面加上0或1標(biāo)記是前面添加0或1異或而來。

表1 基于異或邏輯運算的折半劃分方法的編碼規(guī)則

由表1可以看出，全0/1的長度每增加2倍，標(biāo)記位就增加一個標(biāo)記位1，這有助于解壓時對全0或全1塊的長度進(jìn)行換算。

2 編碼實例

編碼實例如圖1所示。

圖1 編碼實例

圖1（1）中給定測試集可以看成原始數(shù)據(jù)流。圖1（2）中，（a）表示測試集，（b）表示按單位長度16對測試集進(jìn)行分塊，對于最后不足16的數(shù)據(jù)塊，用無關(guān)位X進(jìn)行填充，（c）表示最終編碼結(jié)果，最小臨界值Min取4。從最終結(jié)果可以看出，此方法將原有的61位測試向量減少到31位，有效地減少了測試向量。

具體編碼過程：取長度為16的單位塊a，如圖2（a）所示，可以看出它不是全0/1數(shù)據(jù)塊，也不能填充無關(guān)位得到01或10交替序列，所以要對它進(jìn)行第一次折半劃分，如圖2（b）所示，得到測試向量b1和b2，b1是連續(xù)的無關(guān)位，則不再劃分，按編碼規(guī)則編碼。b2不全是0/1或也不可通過填充得到01或10交替序列，因此需要繼續(xù)折半劃分。b2折半劃分得到c1和c2，如圖2（c），c1可以通過填充得到10序列（圖2（d）），c2既不是全0/1序列，也不可通過填充為01或10交替序列，但它的長度已經(jīng)達(dá)到最小臨界值，不再進(jìn)行劃分，直接根據(jù)表1的規(guī)則得到最終編碼結(jié)果。

圖2 基于邏輯運算的折半劃分的過程舉例（Min=4）

3 算法理論分析及最小臨界值的選擇

最小臨界值的選取會影響壓縮率，因此有必要對Min進(jìn)行分析，選取最優(yōu)值。對于不足2的冪次方的數(shù)據(jù)用無關(guān)位補(bǔ)齊，另添加后的測試向量總數(shù)為A，最小臨界值為x，壓縮后的向量大小為B，長度大于等于x的全01向量共R個，每個向量的長度分別為L1，L2，…，LR（Lr＞x），（p=1，2，…，P）；交替向量M個，因為異或后成全1向量，因此每個向量的長度可以標(biāo)記成LR+1，LR+2，…，LR+M，壓縮后的長度與同樣長度的全1序列相比多一位標(biāo)記位；最后長度等于x的既非全0/1，也非交替序列的測試向量個數(shù)為N，那么

壓縮后的測試向量大?。?/p>

可以看出，當(dāng)S值比較小的時候，d2y/d x2＞0，則當(dāng)Min=x時，y取最小值，此時壓縮率最高。從實驗中也可得到，所取的Min與x的值很接近。

4 解壓電路的設(shè)計

這里的解壓電路，主要由有限狀態(tài)機(jī)（FSM）、一個k+1移位計數(shù)器、一個異或門、一個或門、兩個觸發(fā)器、一個控制二選一電路f和一個二選一電路MUX等主要電路組成，結(jié)構(gòu)如圖3所示。計數(shù)器內(nèi)的初始值是Min，由于要根據(jù)標(biāo)記位來確定數(shù)據(jù)塊的長度，當(dāng)輸入的標(biāo)記位為1時，計數(shù)器里的數(shù)據(jù)向左移一位，就是在Min的基礎(chǔ)上乘以2，數(shù)據(jù)塊的長度等于Min乘以2n-1，n為標(biāo)記位里1的個數(shù)?！癰it in”是輸入待解壓數(shù)據(jù)，“en”是使能信號，當(dāng)FSM準(zhǔn)備就緒時，“en”輸出1。“rs”信號指示計數(shù)器復(fù)位0狀態(tài)。shift和dec一起控制k+1位計數(shù)器的控制信號。v為低電平，表示輸出無效。“data”表示FSM的位輸出信號，ms是MUX的選擇信號，即ms=1時直接從FSM中選擇數(shù)據(jù)，ms=0時，數(shù)據(jù)從觸發(fā)器D1中選擇。f是每個代碼字解壓時后綴代碼字的默認(rèn)值。解壓時根據(jù)后綴的長度選擇與觸發(fā)器D2的值作邏輯運算，就可以得到原始測試數(shù)據(jù)。

圖3 解壓電路結(jié)構(gòu)

本方案的解壓過程如下：

（1）當(dāng)en為1時，表示FSM準(zhǔn)備完畢，接收bit in的第一位數(shù)據(jù)。如果bite in的第一位數(shù)據(jù)為0，這個時候k+1位移位計數(shù)器處于計數(shù)狀態(tài)，它的控制信號（s1，s2）=（0，1）。此時再令MUX的信號ms為1，直接從FSM中輸出數(shù)據(jù)Min。知道控制信號（s1，s2）=（1，1），移位計數(shù)器處于置數(shù)的狀態(tài)。

（2）如果待解壓數(shù)據(jù)的第一位為1，這時移位計數(shù)器處于左移狀態(tài)，控制信號（s1，s2）=（1，0）。直到輸入的數(shù)據(jù)為0，停止移位，控制信號變?yōu)椋╯1，s2）=（1，0），計數(shù)器處于計數(shù)狀態(tài)。

（3）f為控制二選一電路，如果后綴有一位，將0后面的一位數(shù)據(jù)放到觸發(fā)器D1中，讓MUX的選擇信號變?yōu)?，將觸發(fā)器D1中的數(shù)據(jù)計數(shù)輸出，直到rs1為高電平。如果后綴有兩位，則將后綴最后一位寄存在D2中，將觸發(fā)器D1中輸出的數(shù)據(jù)與D2中的數(shù)異或后輸出，直到ms為高電平。

5 實驗結(jié)果及分析

這一部分將通過實驗數(shù)據(jù)來說明M值的選擇及壓縮率。因為不同的M值會有不同的壓縮率，因此對ISCAS-89的幾個電路選不同的M值做實驗，選出最優(yōu)值，如表2所示。由表2可以看出，M在27到211之間有較高的壓縮率。

表2 不同的指數(shù)n所對應(yīng)的壓縮率

表3列出這個實驗的結(jié)果，并與其他方法的結(jié)果做了對比。實驗電路ISCAS-89，采用Mintest產(chǎn)生的測試集為測試向量，將它的結(jié)果與Golomb碼、折半劃分碼的結(jié)果進(jìn)行比較，壓縮結(jié)果比較如表3所示。表中第一欄是電路名稱，第二欄是原測試集的長度，第三、四欄是golomb碼、折半劃分的壓縮長度和壓縮率，第五欄是本次實驗的壓縮長度和壓縮率。

表3 壓縮效果比較

由表3可以看出，本方法的壓縮效果明顯要比其他兩種好，每一個電路的壓縮率均比Golomb碼要高，僅s38417比折半劃分略低。它的平均壓縮率達(dá)到62.16%，比Golomb碼高18.21%，比折半劃分高4.94%。因為它不僅對全0和全1同時編碼，還對非全0/1序列進(jìn)行優(yōu)化，從而提高了壓縮率。

［1］Hazaoglu I，Patel JH.Reducing Test Application Time for Builtin-self-test Pattem Generators［C］//Proceedings of 18th IEEE VLSI Test Symposium.Washington IEEE Computer Society，2000：369-375.

［2］梁華國，蔣翠云.基于交替與連續(xù)長度碼的有效測試數(shù)據(jù)壓縮和解壓［J］.計算機(jī)學(xué)報，2004，27（4）：545-554.

［3］L.Li，K.Chakrabart.Test data compression using dictionaries with fixed-length indices［C］//Proceeding of 21th IEEE VLSI Test Symposium Washington IEEE Computer Society，2003，219.

［4］Chandra A，Chakrabarty K.System-on-a-chip test data compression and decompression architecture based on Golomb codes［J］.IEEE Trans On CAD of Integrated Circuits and Systems，2001，20（3）：355-368.

［5］梁華國，聚貝勒，海倫布昂特，等.一種折疊計數(shù)器重新播種的確定自測試方案［J］.計算機(jī)研究與發(fā)展，2001，38（8）：931 -938.

［6］張念，梁華國，易茂祥.基于折半劃分的測試數(shù)據(jù)壓縮方法［J］.計算機(jī)應(yīng)用，2007，27（12）：3129-3131，3135.

［7］W F Zhan，H G Liang，F(xiàn) Shi，et al.Test Data Compression Scheme Based on Variable-To-Fixed-Plus-Variable-Length Coding［J］.Journal of Systems Architecture，2007，53（11）：877-887.

［8］A Chandra，K Chakrabarty.Test Data Compression and Decompression Based on Internal Scan Chains and Golomb Coding［J］. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems，2002，21（6）：715-722.

［9］A H E1-Maleh.Test Data Compression for System-on-achip Using Extended Frequency-directed Run-length code［J］.IET Computers&Digital Techniques，2008，2（3）：155-163.

Test Data Compression Based on Exclusive or LogicalOperation and Dimidiate Partition

HUANG Li，WU Qiong
（Insititute of Mathematics and Computer science，Anqing Teachers College，Anqing 246133，China）

A test data compression based on exclusive or logical operation and dimidiate partition is studied.Thewhole test is partitioned to several length-fixed blocks.Firstwe apply exclusive or logical operation into alternating bitsand turn to runsof1sor 0s.；Then，for the none0/1 and none alternating blocks，we use dimidiate partition technique.The length of codewords can be expressed by the times of dimidiate.On the one hand，it reduced the length of codeword.On the other hand it can directly shift the counter when decompress the code test data，reduced the costs of decompression.The simulation results show that thismethod has a good compression effect.

test data compression，dimidiate partition，exclusive or logical operation，golomb codes

TP391.9

A

1007-4260（2014）03-0045-04

時間：2014-9-15 16：07 網(wǎng)絡(luò)出版地址：http：//www.cnki.net/kcms/doi/10.13757/j.cnki.cn34-1150/n.2014.03.012.html

2014-04-28

國家自然基金（61306046）資助。

黃麗，女，安徽桐城人，安慶師范學(xué)院數(shù)學(xué)與計算科學(xué)學(xué)院碩士研究生，專業(yè)方向為應(yīng)用數(shù)學(xué)。