混合分数与FDR码的测试数据压缩方法

李 瑞，吴 琼

（安庆师范大学 数理学院，安徽 安庆 246133）

随着超大规模集成电路集成度的日益提高、芯片尺寸的逐步缩小，电路的复杂性急剧增加。复杂的电路给系统芯片的测试工作带来了极大挑战。测试过程中快速增加的数据量对自动测试设备的存储空间、运行频率等方面提出了更高要求，在不显著增加测试时间和测试成本的情况下，系统芯片的测试工作变得越来越困难。为缓解上述问题，国内外学者提出了许多有效减少测试数据量的方法，一般分为三类：测试集紧缩[1]、内建自测试[2]和测试数据压缩[3-10]。（1）测试集紧缩：该技术使用软件调整并紧缩测试数据中的无关位，以此来减少测试向量的个数，节省了硬件开销和测试时间，其缺点是会降低非模型故障的覆盖率。（2）内建自测试：该方法的思想是预先在芯片上设计测试向量生成器，使得测试向量能直接在芯片上生成，并在电路内部独立完成测试工作，脱离了对昂贵的自动测试设备的依赖。但是由于很多IP核没有预先设计测试向量生成器，若考虑内建自测试，则需插入电路重新设计，代价昂贵。（3）测试数据压缩：主要采用无损压缩的方法对测试数据进行压缩，得到较小体量的数据后再传输到自动测试设备中，同时设计解压电路，还原出与原始测试向量一一对应的数据。该技术降低了对测试设备的要求，也能很好地保护知识产权。无损的编码压缩方案是测试数据压缩领域的研究热点，经典的编码压缩方法有Golomb码[3]、FDR码[4]、交替连续长度码[5]、Variable-Tail码[6]、混合定变长码[7]等，这些方案的优点是压缩效率较高且解压结构简单。根据游程出现的规律，本文提出一种混合分数与FDR码的测试数据压缩方法，使编码更加灵活，减少了需要编码的数据量，同时也节省了测试时间。

1 混合分数与FDR码的压缩方法

1.1 分数存储游程规律的方法

（1）数据预处理。待测电路生成的测试数据由0，1和无关位X组成，其中X可以被任意填充为0或1，不影响测试数据的故障覆盖率，因此，在测试之前首先选择适应性填充的方法来填充无关位X，使得到的游程序列能更符合分数存储规律。

（2）统计游程并转化为浮点数。将预处理后的测试数据按照0类型游程划分，当游程长度超过了十进制能表达的最大值9时，即将长游程切分为多个短游程。依此可将测试数据表示为一段整数序列，默认在第一个整数后添加小数点，其余整数依次连接作为小数部分，则游程长度序列转化为浮点数。

（3）转化为分数。利用Stern-Brocot Tree生成所有分母小于100的真分数，建立分数字典。在字典中输入浮点数，查找与浮点数相等的分数并输出分子和分母，最后将测试数据存储为分子、分母和原始测试数据的长度。下面以36 位测试数据100010 0X0000 XXX010 0011XX 001000 100XX1 为例展示分数存储游程规律的过程。首先，将无关位X全部填充为0，统计游程长度对应的整数序列为0，3，9，1，3，0，4，3，4，在第一位整数后添加小数点，其余整数依次连接作为小数部分，得到浮点数0.391 304 34。接下来，查找分数字典有9/23 ≈0.391304 34，于是将上述测试数据存储为9、23和36三个整数。

1.2 混合分数与FDR编码的原理

FDR编码是一种基于0游程的编码压缩方法，对长游程测试数据的压缩非常有效，然而它对短游程数据的压缩效果较差，有可能出现负压缩的情况。因此，本方法不再直接存储游程长度，而是根据游程出现的规律将其存储方式分为两类：（1）若根据测试数据中0和1出现的规律，可以把游程长度的整数序列转化为浮点数，且能在分数字典中找出与浮点数对应的分数，则只需存储分子、分母和原始测试数据长度，再对其进行FDR编码即可。（2）若字典中不存在与浮点数对应的分数，则游程序列不符合转化为分数的规律，此时直接使用FDR编码。混合分数与FDR码测试数据压缩方法的具体流程如下。

步骤1级联测试集中的全部向量记作TD；

步骤2读取一个测试向量，自适应填充无关位X，使用十进制的游程长度表示法将待测数据转换成若干个整数序列，每段序列的原始数据长度记为l；

步骤3遍历整数序列，在第一位整数后添加小数点，其余整数作为小数部分，则整数序列转换为浮点数f，若字典中存在与浮点数对应的分数，且使得n/m≈f，则存储n，m，l三个整数；若不存在与浮点数对应的分数，则直接存储整数序列；

步骤4使用FDR编码步骤3中的所有整数；

步骤5重复执行步骤2至步骤4，直至测试数据集为空编码时结束并计算压缩率。

为了更好说明本方案的编码过程，列举一个测试集进行分数编码，如图1所示，而图2展示了直接使用FDR编码和本方案编码的结果。从图1可以看出，本文压缩方法将原始测试集存储为7、23和64三位整数，再使用FDR 对三位整数编码，对应的编码结果为110001 11101001 111110000010，将64 位测试集压缩为26位，与原始测试集相比减少了38位，压缩率为59.37%。由图2可知，本文方法只需编码7、23和64三位整数，编码数据量远小于直接使用FDR编码的数据量，并产生了更高的压缩率。

图1 编码实例

图2 编码压缩结果比较

2 解压电路

解压结构由一个有限状态机FSM、两个M位寄存器、一个k位计数器、一个log2k位计数器和一个快速浮点除法器实现，如图3所示。

图3 解压结构

图中，bit_in是FSM的输入，信号（en）用于输入编码数据。counter_in作为FSM的输出，用于将代码字的前缀或后缀移位到k位计数器中，shift信号用于将数据移位。log2k位计数器用来计算前缀和后缀的长度，从而识别代码字组别。dec1信号用于控制计数器递减，rs1和rs2是计数器的复位信号，用来表示计数器完成计数。M位寄存器分别存储n，m和l的值，快速浮点除法器用于将分数转化为对应浮点数的整数序列。解压过程如下：

（1）FSM 控制bit_in 向k位计数器提供前缀，当bit_in 输入0 时前缀输入结束，将计数器的值存入M位寄存器1；计数器重置为0后向k位计数器提供后缀，再将计数器的值加在M位寄存器1中，记寄存器1的数值为n；

（2）再次执行步骤（1），将计数器的值分别存入M位寄存器1（记为m）和M位寄存器2（记为l）中；

（3）将n和m移入快速浮点除法器中，计算对应的浮点数并输出整数序列；

（4）根据整数序列以及原始数据长度l输出0 s，解码结束时在0 s后跟1；

（5）重复以上步骤直至解压完毕。

3 实验结果

为验证本文压缩方法的有效性，选取MintestATPG生成的测试向量集，分别对ISCAS89标准电路中的7个时序电路进行实验，压缩效果如表1所示。为了进一步验证可行性，表2给出了本方案与国内外其他编码方案压缩结果的对比情况。

由表1可以看出，本文压缩方法对ISCAS89标准电路中大多数电路的压缩效果较好，压缩率相对稳定，变化范围为45.9%～75.3%，平均压缩率为61.0%。其中对s5378和s9234两个电路的压缩率较低，原因是该电路中的短游程数据较多，数据规律性较差，不易使用分数存储。由表2看出，对于同样的测试数据，本文方法的平均压缩率为61.0%，相较于FDR码提高了11.9%，相较于Golomb码提高了17.6%，与二分算法压缩方案相比提高了16.9%。实验表明本文压缩方法能提高测试数据压缩率、减少测试时间和硬件开销。

表1 本方案的压缩效果

表2 本方案与其他编码方案压缩率的比较

4 总结

集成电路测试是工业生产中必不可少的一步，为降低测试成本，本文提出了一种混合分数与FDR码的测试数据压缩方法。首先，将游程出现的规律存储为分数，分别编码分子、分母和原始测试数据的长度，突破了短游程测试数据对编码压缩效果的限制，同时减少了需要编码的数据量；再对不能转换为分数的游程直接进行FDR编码，该方法使编码更加灵活且能进一步减少编码数据量。实验结果表明，该方法对ISCAS89 标准电路的平均压缩率为61.0%，能有效压缩测试数据量，降低芯片的测试成本，并且解压电路简单，无需引入额外的硬件开销。因此，本文提出的混合分数与FDR码测试数据压缩方法在系统芯片测试领域中具有一定的应用前景。