连续交替共前缀长度码测试数据压缩和解压方案

暴　阳，吴　琼

(安庆师范学院 数学与计算科学学院, 安徽 安庆 246133)



连续交替共前缀长度码测试数据压缩和解压方案

暴阳，吴琼

(安庆师范学院 数学与计算科学学院, 安徽 安庆 246133)

摘要：本文提出了一种新的编码方法，对连续序列进行编码，如果前后两个编码组有相同的前缀，那么用一个标记位1，就可以代替后一个游程很长的前缀。如果两个游程不在同一组，就用一个标记位0隔开，后面按源代码编码。

关键词：编码；前缀；游程

随着科学技术的发展，芯片越来越复杂，集成度也越来越高，这样就给测试带来了很大的困难，因为测试所需要的测试数据多了，而现在已有的自动测试芯片的设备工作频率、存储量以及带宽都非常有限，这就使得 SoC的测试存在着测试时间长、测试成本增加等问题[1]。怎么解决呢？有两种办法，第一，更换更加高端的设备，但这样会使测试成本增加；第二，找一种好办法，把测试数据压缩后传输到测试芯片的设备中去[2-5]，这样就能快速有效的测试已有数据了，如文献[6-14]。而这些文献中的压缩方案是用较短的代码字来代替长的游程，没有想过把码表中的数据变得简单，并且探讨它们之间的关系。因此，本文提出一种新的编码方法，该方法在对连续序列编码的基础上，进一步探讨相邻游程之间的相关性。

1连续交替共前缀长度码算法思想

连续交替共前缀长度码算法是对交替连续的 “0”或“1”进行编码。如编码表1中，把所有可能出现的连续长度分成若干个A1，A2，A3，…，Ak组。在表1的A1组中直接从长度为1的编码开始，因为不存在0位连续的数。表1中最大组Ak的下标k由测试集的最长连续序列的长度Lmax来确定，其中Lmax满足不等式2k-3

表1　编码表

编码思路。首先对被测数据的无关位进行赋值，当碰到无关位x，x前要是1就赋值x为1，是0就赋值x为0 (如果是以无关位开始的，那么x就赋值无关位后紧接着的数字，这样增加了数据块的长度，提高了压缩率)，这样编码字就变成连续的0和连续的1交替出现。这样只要知道第一个数据块是连续的1还是连续的0，后面的每个数据块也就可以知道了 ，之后还用短的代码字代替长的游程。因此本方案更进一步探讨了相邻游程之间的关系，如果前后两个游程在同一组，那么，根据表1可以看到，它们就有相同的前缀，这样就可以省略后面的前缀，只在它们之间加一个标记位1就可以了，即将紧跟其后的游程编码字的前缀部分用一个标记位加尾部来表示，这样就省了一个前缀，多了一位标记位。前缀的位数肯定大于标记位，这样就减少了很多位数。如果它们不在同一组，那么就用一个标记位0隔开，表示它们没有相同的前缀，后面按源代码编码。

2编码实例

例如1111110000001xx0xxx10x,就赋值为1111110000001110000100。 当把测试数据的无关位x赋值了以后，那么被测数据就变成连续的1和连续的0交替的了，只需知道开头是连续的0还是连续的1，就知道后面分别是连续的什么了，因为每个数据块都是交替出现的。比如连续的1之后就是连续的0，连续的0之后就又是连续的1。例如，111111000000011100000000111111111，首先是6个连续的1，对照表1的编码字就是110000，然后是7个连续的0对照表1就是110001，但是6和7都在同一组A3组中，它们的前缀都是110，这样就可以省了前缀只写后缀001，但是需要加一个标记位1，表示后面7个0和前面6个1在同一组，省了前缀，编码后就是1100001001。再看7个连续的0之后是3个连续的1，它和7个连续的0不在同一组，就不能共前缀了，只能写成1001，不共前缀中间也加一个标记位0，编码之后就是110000100101001，后面是8个0和前面的3个1他们不共前缀，所以加一个标记位0，就是1100001001010010110010，后面是9个连续的1，和前面的8个连续的0在同一组，也可以共前缀，加一个标记位1，只写后缀011就可以了，编码之后就是11000010010100101100101011，结果如下：

原始测试向量：1111110000000

11100000000111111111

编码后测试向量：110000 1001

0 10010 1100101 011

原始测试向量共33位，TE共26 位，节省7 位。

3编码算法的理论分析

对于表1，每组中最大的数Lmax和它的组Am满足关系式:

2L-3

如果知道一个长度L，那么它所在的组m满足关系式：

m=「log2(L+3)-1⎤。

Am组就有2m个元素(除第一组外)。Am组前缀的长度为m，它们的长度相同，因此Am的编码字的长度为2m，则前缀所代表的原始数据的长度为2m-2，尾部所能代表的原始数据长度为2m+1-3。因此Am这一组所能编码的原始数据长度范围为[2m-2,3×2m-5]。在测试数据中假设1出现的概率为p，那么0出现的概率就是1-p，则对于编码数据中的任意长度为L的任意1或0游程出现的概率分别为pL或(1-p)L，它们属于Am组的概率为

相连的两个游程属于同一组的概率为

压缩后的平均编码字长度是

任意游程编码字的平均长度为

压缩率：

4解压器的设计

这个解压器的设计需要一个有限状态机，1个T触发器，2个计数器，2个寄存器，因此解压结构比较简单，电器原件都是常用的，所以不用引进新的设备，从而比较节约成本。其中bit-in是位输入，en是使能信号，有限状态机是通过counter-in控制k位计数器的。Shift把编码传送给k位计数器，有限状态机通过dec1控制计数器进行减一操作。Load再把存在寄存器里的东西传给计数器中。Log2k位计数器用在识别编码字在表1中的哪一组，inc控制该计数器进行加一计数，dec2控制计数器进行减一计数。T触发器用来控制是否翻转和输入的解压信号是否有效。解压器的工作原理如图1所示。

图1 解码器

(1) 开始有限状态机发出“en”,紧接着“shift”还有“inc”都变成高电平，这样“bit-in”把编码字的前缀输给k位计数器和Log2k位计数器，操作他们加一。直到“bit-in”遇到0时，操作结束。

(2) reg-cnt1和reg-cnt2变成高电平，这就使得k-b dcnt复制刚才的前缀给k位寄存器中，同时dcnt2把存在Log2k位计数器中的长度复制到Log2k位寄存器中。

(3) Dec1置于高电平，使k位计数器进行减一操作，out1开始连续输出编码字，当rs1为高电平时，k位计数器减为0，前缀解码停止。

(4) Log2k位计数器控制“bit-in”把编码字的前缀准确的输入到k位计数器中。Out继续输出编码字，直到k位计数器减到0为止，第一组连续序列解码结束。

(5) 对bit-in中的数据进行判断。如果为0，重复上述过程(1)，(2)，而(3)，(4)中的Out改为连续输出0，即 “Out”变为高电平，使T触发器翻转一次，使解码的连续序列是上一个的反值；如果为1，k-b counter把k位寄存器中的值传给k位计数器中，load3把Log2k位寄存器中的值传给Log2k位计数器中，之后开始(3)的工作，而(3)，(4)中的Out改为连续输出0，即 “Out”变为高电平，使T触发器翻转一次，使解码的连续序列是上一个的反值。

5实验结果与讨论

用该方法与其他方法对数据的压缩效果如表2所示。从表2可以看出，本文提出的压缩方法能更好地压缩测试数据，从而有效地证明了该方法的优越性。

表2　3种方案的压缩比较

这种方法把测试数分成一个个数据块，每一个数据块要么是连续的1，要么是连续的0，并且把每组连续的“0”或连续的“1” 的长度，用表1进行编码，不用区分是连续的1还是连续的0。另外，本方案还更进一步明确了相邻游程之间的关系，即后一游程如果与前一游程在同一组，那么它们就有相同的前缀，则将后面游程的前缀部分省去，整个游程只用一个标记位1加尾部来表示，这样就用一个1就可以代替好几位的前缀。因此该编码方案能够有效地压缩测试数据，从而更优于其他编码方法，是一种比较高效的压缩方法。

参考文献:

[1] 许川佩，胡红波 . 基于量子粒子群算法的 SoC 测试调度优化研究[J] . 仪器仪表学报, 2011，32(1)：113-119 .

[2] 俞洋，陈叶富，彭宇. 基于平均值余量的 Wrapper 扫描链接平衡算法[J]. 仪器仪表学报， 2011，32(10)：2290-2296.

[3] A. Chandra，K. Chakrabarty．System-on-a-chip test datacompression and decompression architectures based on golomb codes[J]．IEEE Trans．on CAD of Integrated Circuits and Systems，2001，20(3)：355·368.

[4] A. Chandra，K. Chakrabarty．Test data compression and test resource partitioning for system-on-a-chip using frequency-directed run-iength(FDR) codes[J]．IEEE Trans．on Computers,2003,52(8):1076-1088．

[5] A.Wtrtenberger，C. S. Tautermann，S. HeIIebrand. A hybrid coding strategy for optimized test data compression[C].Proceedings of IEEE InternationaI Test Conference，CharIotte，NC，2003：451-459.

[6] 肖祝红，欧阳一鸣，梁华国．基于状态翻转连续长度码的测试数据压缩和解压[J]．计算机工程，2007，33(16)：214-216．

[7] 詹文法，粱华国，时峰，等．一种混合定变长虚拟块游程编码的测试数据压缩方案[J]．电子学报，2009，37(8)：1837-1841．

[8] 詹文法,梁华国,时峰,等. 混合定变长码的测试数据压缩方案[J].计算机学报，2008，20(21): 5979-5983.

[9] K. J. Balakrishnan. Emerging techniques for test data compression [C].Proceedings of 14th Asian Test Symposium (ATS 2005). USA:IEEE Computer Society Test Technology Technical Council, 2005:462-462.

[10] N.A.Touba.Survey of test vector compression techniques. [J].Design & Test of Computers (S0740-7475), 2006, 23(4): 294-303.

[11] 欧阳一鸣，黄喜娥，梁国华，等.基于部分数据块复用的 SoC 测试数据压缩方法[J] . 电子测量与仪器学报，2010，24(5)：487-493.

[12] 欧阳一鸣，邹宝升，梁华国，等. 基于部分游程翻转的 SoC 测试数据压缩[J] . 电子测量与仪器学报 ，2010，24(1)：23-28.

[13] Paul T. Gonciari, Bashir M.Al-Hashimi, N. Nicolici. Variable-length input huffman coding for system-on-a-chip test [J].IEEE Transactions on CAD of Integrated Circuits and Systems IEEE Transitions on CAD of Integrated Circuits and System (S0278-0070) , 2003 , 22(6): 783-796.

[14] M. Tehranipoor , M. Nourani, K. Chakrabarty. Nine-coded compression technique for testing embedded cores in SoCs[J]. IEEE Transactions on VLSI Systems (S1063-8210), 2005, 13(6): 719-731.

Scheme of Test Data Compression and Decompression Based on Continuous Alternation Sharing-Prefix Length Code

BAO Yang，WU Qiong

(School of Mathematics and Computation Science，Anqing Teachers College，Anqing,Anhui 246133，China)

Abstract:This paper proposes a new coding method. The method further explores the correlation between the adjacent run on the basis of continuous sequence coding meanwhile if the two have the same prefix. This scheme uses 1 bit to represent the whole prefix.

Key words:coding, sharing-prefixed, run

文章编号：1007-4260(2016)01-0043-04

中图分类号：TP273

文献标识码：A

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

作者简介：暴阳，男，河北邯郸人，安庆师范学院数学与计算科学学院硕士研究生，研究方向为数据压缩技术。E-mail: 371877612@qq.com通讯作者：吴琼，女，安徽黄山人，安庆师范学院数学与计算科学学院教授，硕士生导师，主要研究方向为内建自测试、电子设计自动化。E-mail: 1979382944@qq.com

基金项目：国家自然科学基金(61306046)和国家自然科学基金(61540011)。

*收稿日期：2014-08-05

网络出版时间：2016-03-15 17:05网络出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160315.1705.013.html