基于多个连续数据复制的幂次划分数据压缩方法

何姗姗，詹文法,程玉胜

(安庆师范学院 统计学研究所, 安徽 安庆 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