基于多個連續數據復制的冪次劃分數據壓縮方法

何姍姍，詹文法,程玉勝

(安慶師范學院 統計學研究所, 安徽 安慶 246133)

?

基于多個連續數據復制的冪次劃分數據壓縮方法

何姍姍，詹文法,程玉勝

(安慶師范學院 統計學研究所, 安徽 安慶 246133)

摘要：基于多個連續數據復制壓縮方法是將整個測試數據集根據2的冪次方長度劃分成多個連續的若干不定長塊，不定長塊有幾種可能：全1序列，全0序列，01序列，10序列或者不定序列。對于全0序列、全1序列或者01、10序列，在標志位用1的個數來表示連續塊的長度，標志位和編碼字之間用0來分隔,后綴用兩位連續位編碼。對于不連續也不交替的前綴用0標志，代碼字就是原代碼復制。這種根據數據連續性劃分利用數據的重復性降低編碼中出現的冗余，減少了還原時間，能夠很好的對連續或者連續的交替塊壓縮。

關鍵詞：測試數據集；標志位；代碼字；編碼；壓縮塊

集成電路產業的迅速發展使數據復雜化，芯片越來越趨向微小化、多樣化，這就要求增強芯片本身的功能。同時對數據的測試要求也相應變復雜化。解決方法有兩種：一種是增強外部自動測試設備ATE(Automatic Test Equipment)的存儲空間方法[1],這勢必會大大提高成本；另一種就是對測試的數據進行有效的壓縮，減少對硬件的要求。有效的數據壓縮方法大體分為兩種：(1)基于數據塊編碼壓縮[2]，主要有統計編碼、相容壓縮；(2)基于重播種的壓縮，主要有LFSR重播種[3]和折疊計數器重播種壓縮[4]。本文提出了一種壓縮方法，先對整個數據流進行無關位的填充，使得整個數據流是2的倍數的長度。再對數據流進行冪次劃分，劃分出最大長度的連續重復的數據塊，就可以用較小的數據代碼字代替原數據塊，這樣起到了很好的壓縮作用。

1連續數據復制的冪次劃分思想

首先，根據數據長度來適時添加無關位：如果整個數據流長度不是2的倍數，則增添無關位使得數據流長度是2的倍數[5]。其次，劃分數據流，劃分原則是盡可能最大程度的包含連續塊，如若是連續塊則用標記位標記,若不是則復制原來數據塊。連續數據復制的冪次劃分編碼規則如表1所示。

表1　連續數據復制的冪次劃分編碼規則

從表1中可以看出，測試集中連續塊的長度是2i,對于非連續的編碼塊編碼字直接是0加上原代碼字。對于連續塊前綴中1的個數來表示連續塊的長度，連續序列的編碼字是連續塊的前兩位。且由表1看出標記位中1的個數和整個數據塊的數據個數有關系，即2(標記位個數+1)=數據塊數據個數。例如：

a:10010000111111→10010000111111XX

(a)M=22的數據集(b)填充無關位

→10 010000111111XX→10 01 0000111111XX

(c)第一次劃分(d)第二次劃分

→10 01 0000 111111XX

(e)第三次劃分

劃分過程如上例所示，首先檢查測試數據長度是否是2的倍數，如果不是，則對數據集進行無關位的填充，如上例(b)所示，再進行連續塊的劃分如上例(c)，(d)，(e)所示。上例(e)給出了劃分最終結果。根據以上劃分思想，對M=22測試集劃分過程如下所示：

a(原測試集):000000000000000011111111111110101010100000

b(補充無關位結果)：000000000000000011111111111110101010100000XX

c(劃分結果)：0000000000000000 11111111 1111 10101010 1000 01XX

d(編碼結果):11000 11011 1011 11010 01000 1001

具體編碼過程：取44位數據如(a)所示，先對數據集進行無關位填充，如(b)所示。然后對填充后的數據集進行劃分，按照2的冪次方方法進行劃分，盡可能找出最大可能的連續數據塊,如(c)所示。最后根據編碼規則對數據集壓縮編碼得到(d)結果。從編碼最終結果可以看出，原來44位經編碼之后是33位，這樣大大減少了測試向量。

2實驗結果

解碼電路如圖1所示，首先在初始時，觸發器默認設定為0，最低位觸發器設定為1。當FSM接收到“0”時就表示原來數據塊沒有經過復制操作，直接復制后面的數據塊。但當FSM接收到“1”時就表示有復制操作，此時“shift”操作就將觸發器中“1”左移一位，直到接收到“0”為止。經過幾個移位操作，寄存器會有記錄，根據對應關系可以還原原來數據塊。結束時，“Rst”端輸出“1”表示電路中輸入的數據結束。再在下一個脈沖控制下，由“dec”計數器進入初始狀態[6]。這樣一個解碼電路測試完整結束，實驗結果如表2所示。

圖1　解碼電路

由表2可以看出，多連續復制壓縮不僅相對于Golomb碼或者折半劃分，壓縮率都有提高。平均壓縮率多連續復制壓縮達到62.23%，比折半劃分高出5.01%，比Golomb碼高出18.28%，對于各個壓縮電路多連續復制壓縮都比折半或者Golomb碼有提高，這樣比較起來對于七個Mintest集的壓縮效果更好。

3結論分析

本算法首先根據數據長度添加無關位，如果整體數據集長度是2的倍數就不需要添加無關位，反之則添加最短長度的無關位，使得整體數據集長度為2的倍數。添加無關位之后，要對數據集進行劃分，劃分基本單位也是2的倍數，可以是2也可以是4等。劃分原則是盡可能最大程度的包含連續塊或交替塊，這樣就可以將連續塊、交替塊和非連續塊劃分開來，減少了連續相同的數據重復編碼的冗余。劃分結束后，根據編碼規則對每一塊的數據長度進行編碼，對于既非連續又非非連續的數據塊，其前綴加上0來標志，編碼字就是其本身構成。對于連續塊或者交替塊，前綴1的個數來表示連續塊的長度，編碼字表示連續或交替的代碼字。多段復制算法的壓縮效率取決于加載到緩沖區的速度[7]。低層復制操作可以應用，可以獲得較大的效果。但是增加每一段的大小不一定能獲得高效率的壓縮。對每段之間的數據大小關系應該分析。L是總的測試數據的位數，N是總的段數，每段的長度為si(i=1,2,3,4…n),ni是每段能應用復制操作的數據個數，p是用來標識是否應用了復制操作。對于第一段來說，它有L/s1位來檢測是否能夠應用復制操作。給定一個n1位，如果不能應用復制操作，那么增加數據長度為n1×(s1)/(s2)來檢測數據。最終L結果如下，

(1)

公式中，只有ni是不確定的。為了確定ni，我們分析每個可能匹配的段。給定一個指定概率p，前兩位有可能是1或者0，出現的概率是(p/2)×(p/2)+(p/2)×(p/2)=(p2/2)。所以兩位相容的概率是(1-(p2)/(2))。每段有si位能夠應用復制操作的概率是(1-(p2)/(2))gsi。這樣ni就確定了。

(2)

(3)

由上述看來，ni由si決定，但是它們之間的關系很復雜，壓縮率就定義為

壓縮率相比Golomb碼大大提高，連續復制劃分方法對連續的數據流有很大的壓縮效果。通過對編碼表的分析知道，每塊原數據塊長度可以通過編碼字得知，所以能很好的還原原測試集。

參考文獻:

[1] 李雷定,馬鐵華,尤文斌. 常用數據無損壓縮算法分析[J].電子設計工程,2009,17(1):49-53.

[2] 歐陽一鳴，肖祝紅，梁華國.數據塊前向相容標記碼的測試數據壓縮方法[J].計算機輔助設計與圖形學學報，2007,19(8)：986-990.

[3] 吳孝銀,梁華國,詹凱華,等. 基于部分相容的動態LFSR重新播種方法[J]. 計算機工程與應用, 2008,44(18):70-72.

[4]吳義成，梁華國，李松坤，等.一種基于自選擇狀態的折疊計數器BIST方案[J]. 計算機研究與發展,2010,47(S1):195-199.

[5]徐三子,梁華國,顧婉玉,等. 基于無關位動態賦值的冪次劃分測試壓縮方案[C].合肥：第六屆中國測試學術會議論文集, 2011：325-328.

[6] A. Chandra, K. Chakrabarty. A unified approach to reduce SOC test data volume, scan power and testing time[J]. IEEE Council on Electronic Design Automation,2003,22(3):352-363.

[7] Shih-Ping Lin, Nat. Chiao Tung Univ, Chung-Len Lee, et al. A multilayer data copy test data compression scheme for reducing shifting-in power for multiple scan design[J]. IEEE Circuits and Systems Society, 2007,15(7):767-776.

Compression Method of Multiple Continuous Data Replication Based on the Data of Power Division

HE Shan-shan, ZHAN Wen-fa, CHENG Yu-sheng

(Statistical Institute of Anqing Teachers College, Anqing 246133, China )

Abstract:The replication compression method based on a number of consecutive data is the entire test data set according to the division of powers of 2 times length into a continuous number of indefinite length block. The block has four possibilities: 1 sequence, all zero sequence, sequence 01 and 10 sequences or indefinite sequence. For all zero sequence, full sequence or 01, 10 sequence in our flag with the number 1 said continuous block length, sign and code word between 0 to separate, suffix with two consecutive bits of code. For non-continuous and non-alternating prefix with 0 signs, code word is the original code copy. This is based on the data continuity partition of the use of data redundancy to reduce the redundancy in the code, reduce the reduction time, can be very good for continuous or continuous alternating block compression.

Key words:number of consecutive data,sign,code word,code,block compression

文章編號：1007-4260(2015)03-0042-03

中圖分類號：TP391

文獻標識碼：A

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

作者簡介：何姍姍，女，安徽安慶人，安慶師范學院統計學研究所碩士研究生，研究方向為應用統計學。

基金項目：國家自然科學基金(61306046)。

收稿日期：2014-12-17

網絡出版時間：2015-8-25 15:40網絡出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20150825.1540.012.html