基于划分组参考数的差值编码压缩方法

程一飞，吴心竹，吴海峰，邓博文

（安庆师范大学 计算机与信息学院，安徽 安庆 246133）

关键字：测试数据压缩；差值编码；外建自测试；解码

目前，集成电路产业仍在持续发展且势头不减，估计在未来五年仍将保持热度。预计2025年我国芯片规模将达到1.2万亿元[1]。移动智能终端及芯片的爆发式增长导致了诸多难题，尤其是芯片测试方面。本文主要针对呈指数增加的测试数据量与有限的ATE（Automatic Test Equipment，自动测试设备）传输带宽之间的矛盾这一问题，提出一种解决方案。为了解决测试数据量剧增的问题，现在普遍使用测试数据压缩技术。外建自测试技术是测试数据压缩的一种方法，其特点是无损压缩，把测试集压缩成更短的数据集并存储到ATE 上，再通过芯片上的额外解码电路解压，使之还原成与原始数据集确定位一致的数据。传统的游程编码[2]是直接针对每段0、1游程长度进行编码。国外学者提出了一些基于游程编码的测试数据压缩的经典方法，如Golomb码[3]和FDR码[4]。近二十年来，人们陆续提出了许多新的游程编码方案，例如，国外学者提出的混合编码[5]、AFDR码[6]、MFDR码[7]、EFDR码[8]、交替的等游程长度编码[9]等。近几年，国内学者也提出过许多有效的方案，例如，基于三态信号的改进游程编码压缩方法[10]、基于连续和交替序列的编码[11]、混合前缀编码[12]、最大近似相容的分组测试向量相容压缩方法[13]、基于一位标识的混合编码压缩方法[14]、最小游程切换点标记编码压缩方法[15]、应用二分算法压缩测试数据[16]、快速查找最佳有理渐近分数的测试数据压缩方法[17]等。但是这些方案仅仅是针对游程长度进行的无损编码，忽略了每段游程长度之间可能存在的关联性。

本文使用了统计学中较为经典的集中趋势分析方法[18]，合理考虑了游程长度之间的相关性。将电路的测试数据按游程划分，并平均分成若干组，且对每一组进行集中趋势分析，选出该组游程长度中有代表性的值作为参考数，通常为该组的游程长度平均值、众数、中位数等。将组内每段游程的长度与该组参考数作差，再针对差值进行编码，可在不增加游程数量的情况下，有效增加待编码数据中短游程的个数，减少待编码的测试数据长度，因此编码后可以得到比使用原始数据编码时更短的代码字，且可取得很好的压缩效果。

1 编码方案

在编码前，首先将测试数据按照双游程的划分方法划分成若干个0游程和1游程。一些经典的游程编码都是采用双游程划分，如EFDR编码[8]、混合前缀编码[14]、基于一位标识的测试数据压缩[14]等，对测试数据双游程划分能很好地减少用于编码的游程个数。采用的编码方式如表1所示。

表1 差值长度编码方案

由于差值有正负，因此将编码的第一位设定为一个正负标识位，用于记录当前游程与参考数差值的正负类型，如果差值为0或者为正值，则将正负标识位设置为0，以表示当前游程的长度大于或等于参考数的值；同样地，如果差值为负值，则将正负标识位设置为1，以表示当前游程的长度小于参考数的值。第二位设定一个游程类型标识位，用于记录当前游程类型，若当前游程类型为0游程，则游程类型标识位记为0；若当前游程类型为1游程，则游程类型标识位记为1。

每段游程的正负标识位、游程类型标识位和差值长度的编码共同组成其游程编码。而每一组编码不仅包括当前组的参考数编码，还包括游程个数编码和每段游程编码。为了达到无损解压以及进一步精简解压电路，将每组参考数的编码设置为一个固定位长度p的二进制编码（通常将p值设为5），同样的，每组游程个数设置为一个固定长度为q位的二进制编码（通常将q的值设为8）。

假设给出一组测试数据TD=000000000000111111110000000011111111100000000001（48 bit），如果采用经典的FDR编码，经过游程划分后

TD=0000000000001 1 1 1 1 1 1 1 000000001 1 1 1 1 1 1 1 1 00000000001（18个游程序列），编码后的数据

TE=110110 00 00 00 00 00 00 00 110010 00 00 00 00 00 00 00 00 110100（45 bit），如果采用本文方案，采用双游程划分后

TD=0000000000001 11111110 00000001 111111110 0000000001（5个游程序列）。

可以得出，划分后的每段游程长度分别为12、7、7、8、9。若选择游程长度的众数7作为参考数，可得出每段游程与参考数的差值分别为5、0、0、1、2。此时可以将参考数的二进制编码位数p值设为3，即得出当前组的参考数——7的二进制编码为111；同理，将游程个数的二进制编码位数q值设为3，即得出当前组内的游程个数——5的二进制编码为101。将编码后的参考数二进制、游程个数二进制以及各段游程的差值编码相连接，即得出编码后的数据TE=111 101 001011 0100 0000 0101 001000（30 bit）。

若选择游程长度的中位数8作为参考数，即可得出每段游程与参考数的差值分别为4、-1、-1、0、1。此时可以将参考数的二进制编码位数p值设为4，即得出当前组的参考数——8的二进制编码为1000；同理，将游程个数的二进制编码位数q值设为3，即得出当前组内的游程个数——5 的二进制编码为101。将编码后的参考数二进制、游程个数二进制以及各段游程的差值编码相连接，即得出编码后的数据TE=1000 101 001010 1101 1001 0100 0001（29 bit）。

可以看出，选择不同的参考数，将对测试数据产生不同的压缩效率。当选择众数7为参考数时，较原始数据减少了18位，比FDR编码减少了15位；当选择中位数8为参考数时，较原始数据减少了19位，比FDR编码减少了16位。

2 解压设计

由压缩编码方案可知，差值编码的第一位为正负标识位，表示当前游程长度比参考数大或小；编码的第二位为游程类型，即当前游程类型为0游程或1游程，余下部分为差值长度的编码。假设一组游程序列以5作为参考数，差值编码为1101，根据编码规则可以得出，压缩前的游程是一个长度短于参考数的游程序列，且游程类型为1，与原始游程长度差值为1，即原游程是一个长度为4的1游程，因此可还原出原测试数据为11110。

解码可以通过电路实现，在设计电路时，要记录每组的参考数和游程个数，以及差值编码部分。本文在EFDR的解压电路[8]基础上，增加两个m位寄存器，用于存储参考数的编码以及每组的游程个数，并对存储的数据在处理后完成解压。因此最终设计的解压电路是由两个k位计数器、一个log2k位计数器、一个FSM（Finite State Machine，有限状态机）、一个异或门，以及两个m位寄存器构成的解码器。该解码器独立于被测电路且大小可变，由于该电路规模较小，在减少硬件成本上有一定优势，图1为解码框。

图1 解码框

解码器信号及其对应功能如表2所示。根据前述方法和编码表可知，压缩后数据包实际包含若干个组。在每个组的代码字中，前p位为该组的参考数二进制编码，余下编码的前q位为当前组的游程个数二进制编码，以上为本组公共部分；余下为若干小组的差值长度编码数据，所述小组内编码依次包括：当前游程长度与参考数的差值正负标识位、游程类型、差值长度编码。接下来对图1解码框的主要工作原理做出说明。

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

首先通过b_in1接收p位数据，并向m位寄存器一存入一个游程长度为lp的0游程，该寄存器一用于解压缩中间值；其次再连续接收b_in1的q位数据，得到二进制形式的当前组游程个数，并存入m位寄存器二作为循环标志；然后按顺序继续接收2位数据，将第一位赋值给ope以作为正负标记、第二位赋值给flag 以作为游程类型；接着通过log2k计数器依次读取前缀和后缀，在后缀最高位添一位1，将新获得的二进制转换为十进制后减2，即为原游程长度与参考游程长度的差值绝对值。根据ope 的正负类型对m位寄存器一中的游程向高位或低位移动，将游程与flag进行异或操作，可获得解压后游程；重复以上所有流程，直至传入的数据全部解压，解码流程如图2所示。

图2 解码流程图

3 实验结果及分析

为了验证方法有效性，将本文方法应用到ISCAS 89 六个标准电路上，并采用MinTest ATPG 预先计算的测试集进行实验。表3 列出了本文方法的测试集缩短效果。第一列为各测试电路名称，第二列为原测试集长度，第三列为与参考数作差后实际用于编码的测试集长度，最后一列为测试集长度的减少率。以传统游程编码方法为例，编码长度不包括每段游程的终止符，实际用于编码的测试数据占比[19]92%～95%。本文采用了相对游程[20]的方法，对每段游程都进行了差值编码，更大程度的减少了数据长度，每个电路长度的减少率都在20%～45%。

表3 数据集减少效果

表4列出了本文方法的压缩效果，第一列为测试电路名称，第二列为各电路选择的参考数类型，第三列为每个电路的平均划分组数，第四列为各电路的压缩率。本文的编码具有灵活性，在编码时使用了统计分析[18]的方法，并针对每个电路不同的游程分布情况，规划了最优选择的参考数类型。实验结果显示，对测试数据差值编码后，电路压缩率高达63.48%。

表4 本文方法的压缩效果

以测试电路s15850f为例，对实验压缩效果作出分析。该电路平均划分为20个组，第一组参考数为26。根据游程编码规则可知，该组游程长度在13及以上的，与参考数作差后编码长度较原始数据直接编码短，因此差值越大压缩效果越好。据统计，在该组182个游程中，有132个游程的序列长度超过13，占比为该组的73%。由此延伸到整个s15850f电路，该电路中测试数据长游程较多，作差后的编码长度能有效减少，测试数据的压缩率与FDR编码、EFDR编码相比有了很好地提升，约14.7%。同样地，实验电路s5378f中存在较多的短游程，且具分布相对集中，在每段游程长度与参考数作差后，差值编码代码字并不会有较大减少，因此压缩效果不明显。

表5 列出了一些经典编码方案与本文方法的压缩效果，第一列为测试电路名称，第二至第五列分别为Golomb 编码[3]、FDR 编码[4]、EFDR编码[8]，以及本文编码方法的压缩效果，可以看出，本文方案可使得用于编码的数据集长度有效减少，且在编码时合理考虑了游程的相关性。将本文方案应用到几个标准测试电路时，发现本文方法的压缩率再优于其他方法，且平均压缩效果有明显提高。

表5 本文编码方法与其它方法的压缩效果比较

4 结论

本文提出了一种基于相对游程的分组参考数差值编码压缩与解压缩方案，考虑了游程之间的相关性，将游程与参考数作差后用于编码的游程长度变短，有效减少了测试数据量。实验结果发现，利用差值编码对测试数据量处理，压缩率高达44.18%，且6个电路的平均压缩率要优于一些基于游程的经典编码方案。本方法适用于长游程分布较多且游程分布较平均的电路，具体方法是将划分后的游程序列平均分成若干组，在每组中选择合适的游程长度作为参考数，将划分后的游程长度与参考数作差并进行编码。