专利摘要

专利摘要

本发明提出了一种基于间隔划分的测试数据压缩与解压缩方法，该方法首先对测试数据集同时按0游程和1游程进行划分，然后间隔提取划分中的数位，最后依据间隔序列的长度计算出其对应编码。由于仅对从划分中提取出来的间隔序列进行编码，间隔划分长度比原划分的长度短，所以间隔划分对应的编码比原划分对应编码短；另外原始划分的最短长度为2，新划分最短长度为1，因此不存在长度为0的新划分。编码时依据间隔划分的长计算并构造一种新的编码，能够减少测试数据解压缩电路的硬件开销。本方法能够进一步提高压缩率，不需要对原始测试数据进行差分操作，采用新的编码方式能使解压电路硬件开销更小。

权利要求

1.一种基于间隔划分的测试数据压缩与解压缩方法，包括以下步骤：

压缩步骤：

（1）依次按位读取二进制原始数据，得到一个0游程或1游程；记录该游程类型，同时将该游程记为一个划分；

（2）若步骤（1）所得划分的长度为奇数，则将所得划分的左边第1位去掉，得到间隔划分基础码；若步骤（1）所得划分的长度为偶数，则将该划分记为间隔划分基础码；同时将步骤（1）所得划分长度的奇偶性记为奇偶标志，奇偶标志用1bit表示，该位为1表示划分长度为奇数，该位为0表示划分长度为偶数；

（3）对步骤（2）所得间隔划分基础码，从第1位开始，每隔1位取1位组成间隔划分码，并将该间隔划分码的长度记为十进制数L；

（4）计算最终编码；

（4.1）将步骤（3）所得十进制数L加1；

（4.2）将步骤（4.1）所得结果转换成其对应的二进制形式代码串；

（4.3）去除步骤（4.2）所得二进制形式代码串的最左位；

（4.4）计算步骤（4.3）所得结果之长度为十进制数G；

（4.5）若步骤（1）所得游程类型为0游程，则生成由G个0和1个1组成的分隔符串；若步骤（1）所得游程类型为1游程，则生成由G个1和1个0组成的分隔符串；

（4.6）将步骤（2）所得奇偶标志位作为最终编码的第一位，再将步骤（4.5）所得分隔符串和步骤（4.3）所得代码串逐位交替组建最终编码，所述分隔符串的各位依次放在最终编码的偶数位，所述代码串的各位依次放在最终编码的奇数位；

（5）重复步骤（1）至步骤（4），所得最终编码序列即为压缩后的数据；

（6）读入步骤（5）所得压缩数据后进行解压缩。

2.如权利要求1所述的基于间隔划分的测试数据压缩与解压缩方法，其特征在于：所述步骤（6）包括：

a)初始化: 置en=1；置V为1;置rs为1；置shift为0;置data为1表示解码准备好;

b)接收b_in的一位数据（奇偶标志），若数据为1，则data输出一位0，若数据为0，则不做处理；

c)继续接收b_in的一位数据，并在FSM内部保存该数据，记为s，同时通过F输出该值;继续接收b_in的一位数据并从c_in 移入(k+1)位计数器，shift置1；

d)若data为0，则data与F异或得到out输出，否则不处理；

e) 继续接收b_in的一位数据，若其值与s相同，转f)，若其值与s不相同，转g)；

f)继续接收b_in的一位数据并从c_in 移入(k+1)位计数器，shift保持不变；转e);

g)(k+1)位计数器进行减法操作，(k+1)位计数器每减一，data 输出00，直到(k+1)位计数器值为2，最后data 输出01；

h)data与F异或得到out；

i)重复a)到h)直到所有数据解码结束。

说明书

技术领域

本发明涉及计算机信息领域，具体涉及一种测试数据压缩与解压缩方法。

背景技术

与同软件产品，硬件产品投入市场之前必须经过严格测试，集成电路芯片产品也不例外。测试在整个产品的生产制造过程中的地位起来越高，测试时间的长短影响产品投入市场的时间，同时也影响产品成本。产品测试时间过长，产品测试成本逐渐上升。因此如何缩短产品测试时间，降低测试成本成为工业界和科研工作者都广泛关注的问题。

集成电路功能越来越丰富、规模越来越大，内部电路结构相应地也越来越复杂，测试芯片需要的测试数据量同样逐渐增加。日益增加的庞大的测试数据量是造成测试成本上升的重要因素之一。在不降低测试效果的前提下减少测试数据的方法主要有测试紧缩、内建自测试以及外建自测试。测试紧缩虽然能够减少测试向量数目，但紧缩后的数据量仍然很庞大，需要进一步压缩。无论是内建自测试还是外建自测试都期望需要存储的测试数据量小，因此测试数据压缩技术成为芯片测试中普遍采用并且非常关键的技术之一。测试数据压缩技术在压缩效果、硬件开销、测试应用时间等方面都具有比较显著的优势，是近年来研究者充分研究的热点。而基于编码的测试数据压缩方法又是测试数据压缩中最主要的方法之一。近年来国内外研究都对其进行了广泛深入地研究。近年来关于测试数据压缩技术的代表性的工作有：Golomb码、FDR码和交替码以及国内学者提出的Variable-Tail编码、交替与连续长度码、SVIC码、变游程码、和PTIDR编码等。这些方法都能够在较小的硬件开销下取得较好的压缩率，尤其是国内学者提出的很多方法都能在对原始的测试集未进行差分处理的情况下，取得较好的压缩率。虽然国内外学者研究都取得了一定的进展，但提高压缩率、减小解压缩的硬件开销仍值得进一步研究。

将待测试的原始二进制数据划分为游程是一种基本方法，游程包括0游程和1游程两种类型，其中0游程是指一个由至少1位的连续的0及结尾的1个1组成的字符段，1游程是指一个由至少1位的连续的1及结尾的1个0组成的字符段。在所述0游程中，连续0的位数称为游程长度；在所述1游程中，连续1的位数称为游程长度。

发明内容

本发明所要解决的技术问题在于提供一种基于间隔划分的测试数据压缩与解压缩方法，其压缩效率高，硬件开销小。

为解决上述技术问题，本发明的基于间隔划分的测试数据压缩与解压缩方法，包括以下步骤：

压缩步骤：

（1）依次按位读取二进制原始数据，得到一个0游程或1游程；记录该游程类型，同时将该游程记为一个划分；

（2）若步骤（1）所得划分的长度为奇数，则将所得划分的左边第1位去掉，得到间隔划分基础码；若步骤（1）所得划分的长度为偶数，则将该划分记为间隔划分基础码；同时将步骤（1）所得划分长度的奇偶性记为奇偶标志，奇偶标志用1bit表示，该位为1表示划分长度为奇数，该位为0表示划分长度为偶数；

（3）对步骤（2）所得间隔划分基础码，从第1位开始，每隔1位取1位组成间隔划分码，并将该间隔划分码的长度记为十进制数L；

（4）计算最终编码；

（4.1）将步骤（3）所得十进制数L加1；

（4.2）将步骤（4.1）所得结果转换成其对应的二进制形式代码串；

（4.3）去除步骤（4.2）所得二进制形式代码串的最左位；

（4.4）计算步骤（4.3）所得结果之长度为十进制数G；

（4.5）若步骤（1）所得游程类型为0游程，则生成由G个0和1个1组成的分隔符串；若步骤（1）所得游程类型为1游程，则生成由G个1和1个0组成的分隔符串；

（4.6）将步骤（2）所得奇偶标志位作为最终编码的第一位，再将步骤（4.5）所得分隔符串和步骤（4.3）所得代码串逐位交替组建最终编码，所述分隔符串的各位依次放在最终编码的偶数位，所述代码串的各位依次放在最终编码的奇数位；

（5）重复步骤（1）至步骤（4），所得最终编码序列即为压缩后的数据。

（6）读入步骤（5）所得压缩数据后进行解压缩。

所述步骤（6）包括以下步骤：

a)初始化: 置en=1；置V为1;置rs为1；置shift为0;置data为1表示解码准备好;

b)接收b_in的一位数据（奇偶标志），若数据为1，则data输出一位0，若数据为0，则不做处理；

c)继续接收b_in的一位数据，并在FSM内部保存该数据，记为s，同时通过F输出该值;继续接收b_in的一位数据并从c_in 移入(k+1)位计数器，shift置1；

d)若data为0，则data与F异或得到out输出，否则不处理；

e) 继续接收b_in的一位数据，若其值与s相同，转f)，若其值与s不相同，转g)；

f)继续接收b_in的一位数据并从c_in 移入(k+1)位计数器，shift保持不变；转e);

g)(k+1)位计数器进行减法操作。(k+1)位计数器每减一，data 输出00，直到(k+1)位计数器值为2。最后data 输出01；

h)data与F异或得到out；

i)重复a)到h)直到所有数据解码结束。

本发明提出了一种基于划分的测试数据编码方法，该方法首先对测试数据集同时按0游程和1游程进行划分，然后间隔提取划分中的数位，最后依据间隔序列的长度计算出其对应编码。由于仅对从划分中提取出来的间隔序列（简述为间隔划分）进行编码，间隔划分长度比原划分的长度短，所以间隔划分对应的编码比原划分对应编码短；另外原始划分的最短长度为2，间隔划分最短长度为1，因此不存在长度为0的间隔划分。编码时依据间隔划分的长计算并构造一种新的编码，该编码不同于由前缀和后缀两部分构成的传统编码构建规则，能够减少测试数据解压缩电路的硬件开销。综上所述，本方法（1）能够进一步提高压缩率，（2）不需要对原始测试数据进行差分操作，直接压缩原始测试数据，（3）采用新的编码方式能使解压电路硬件开销更小。

附图说明

图1 是本发明中解压缩步骤所涉及的解码电路框图；

图2是本发明中解压缩步骤的流程图。

具体实施方式

以下结合附图对本发明的具体实施方式做进一步说明。

本发明的基于间隔划分的数据压缩与解压缩方法，包括以下步骤：

压缩步骤：

（1）依次按位读取二进制原始数据，得到一个0游程或1游程；记录该游程类型，同时将该游程记为一个划分；

（2）若步骤（1）所得划分的长度为奇数，则将所得划分的左边第1位去掉，得到间隔划分基础码；若步骤（1）所得划分的长度为偶数，则将该划分记为间隔划分基础码；同时将步骤（1）所得划分长度的奇偶性记为奇偶标志，奇偶标志用1bit表示，该位为1表示划分长度为奇数，该位为0表示划分长度为偶数；

（3）对步骤（2）所得间隔划分基础码，从第1位开始，每隔1位取1位组成间隔划分码，并将该间隔划分码的长度记为十进制数L；

（4）计算最终编码；

（4.1）将步骤（3）所得十进制数L加1；

（4.2）将步骤（4.1）所得结果转换成其对应的二进制形式代码串；

（4.3）去除步骤（4.2）所得二进制形式代码串的最左位；

（4.4）计算步骤（4.3）所得结果之长度为十进制数G；

（4.5）若步骤（1）所得游程类型为0游程，则生成由G个0和1个1组成的分隔符串；若步骤（1）所得游程类型为1游程，则生成由G个1和1个0组成的分隔符串；

（4.6）将步骤（2）所得奇偶标志位作为最终编码的第一位，再将步骤（4.5）所得分隔符串和步骤（4.3）所得代码串逐位交替组建最终编码，所述分隔符串的各位依次放在最终编码的偶数位，所述代码串的各位依次放在最终编码的奇数位（第一位除外）；

（5）重复步骤（1）至步骤（4），所得最终编码序列即为压缩后的数据。

下面通过一个实例来说明本编码方法，假设原始测试数据为00000000001111111100000010000010000000000000001101000000001，共59b。若采用FDR编码，其对应划分分别为：00000000001 1 1 1 1 1 1 1 0000001 000001 00000000000000011 01 000000001，编码为110100 00 00 00 00 00 00 00 110000 1011 11100001 00 01，共102b。

以下用本发明方法对原始测试数据进行运算，可依次获得下面结果：

表1 编码过程表

分析最后一行的编码可知，最终经过本方法得到的编码总长度为46b。

需要说明的是，在本方法中，基于某一个游程所产生的划分，该划分的长度始终为该游程的长度加1。即：对于0游程，其末尾存在一个游程结束标志1，对于1游程，其末尾存在一个游程结束标志0；该游程结束标志不计入游程长度，但计入划分长度。

特殊情况的处理：对于原始数据的结尾，可能出现不能构成游程的情形，例如结尾为1个0、1个1、若干个连续的0、若干个连续的1等情形。出现此种情况，则在所获得的编码后面加上游程结束标志，让其结尾构成一个游程。例如最后得到的结果是111111，则在其后添加1位0，变成1111110；例如得到得到的结果是00000，则添加1位1，得到000001。经过处理后，本发明能够连续工作完成压缩编码。在后续的解码步骤，能够解码得到原始的结尾数据以及附加的游程结束标志，而在芯片测试过程中，对测试集数据长度是有要求的，因而在读取测试数据时，最后附加的游程结束标志不被读入，因而不影响测试结果。

解压设计

由编码码字表（表1）可知，划分长度L等于1+所有偶数位部分组成的二进制数换算为十进制再减1，即L=(1t)2-1。如划分长度L=6的0游程编码为01011，提取偶数位部分得到11，则(111)2-1=7-1=6，又如L=8的1游程编码为1010110，提取偶数位部分得到001，则(1001)2-1=9-1=8。因此可以使用一个特殊的K+1位计数器控制输出序列的长度。该计数器的初值置为1，当编码输入时，将1和编码偶数位部分依次向高位移位得到一个k+1位二进制数。通过该计数器减1操作控制输出序列的长度，直到该计数器的值为十进制1（二进制01时）输出结束。

输入编码的第1位决定输出游程的类型，其值为0表示需要输出的是0游程，其值为1表示需要输出的是1游程。

此于上述分析，我们设计一个由一个FSM(有限状态机)、一个K+1位计数器、和一个异或门构成的解码器，该解码器结构简单，独立于被测电路和测试数据集并且大小可变，解码器结构框图见图1，其中的信号名称及其对应功能描述见表2。

下面结合图1、图2及解码器中信号及表2介绍本方法解码基本过程。

a)初始化: 置en=1；置V为1;置rs为1；置shift为0;置data为1表示解码准备好;

b)接收b_in的一位数据（奇偶标志），若数据为1，则data输出一位0，若数据为0，则不做处理；

c)继续接收b_in的一位数据，并在FSM内部保存该数据，记为s，同时通过F输出该值;继续接收b_in的一位数据并从c_in 移入(k+1)位计数器，shift置1；

d)若data为0，则data与F异或得到out输出，否则不处理；

e) 继续接收b_in的一位数据，若其值与s相同，转f)，若其值与s不相同，转g)；

f)继续接收b_in的一位数据并从c_in 移入(k+1)位计数器，shift保持不变；转e);

g)(k+1)位计数器进行减法操作。(k+1)位计数器每减一，data 输出00，直到(k+1)位计数器值为2。最后data 输出01；

h)data与F异或得到out；

i)重复a)到h)直到所有数据解码结束。

步骤a)到h)用流程图表示见图2.

表 2解码器中信号及其对应功能

需要说明的是，本领域技术人员可依据本发明所提供的压缩方法自行设计多种解压缩方法，本发明的具体实施方式包括但不局限于上述实施例，在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员可根据本发明作出各种相应的改变和变形，但仍然落入本发明的保护范围。

基于间隔划分的测试数据压缩与解压缩方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。