改进型相对游程长度编码方法

吴 琼，周啸宇

（安庆师范大学数学与计算科学学院，安徽安庆246133）

集成电路产业发展迅速，电路芯片的复杂度不断提高，测试难度和成本迅速增加，而测试芯片的传输带宽和存储能力的增长却十分有限。二者之间的矛盾导致测试成本提高、测试时间增加。减少测试数据量可以有效地解决此问题。采用编码压缩的方法可以有效降低测试数据量[1-3]。传统编码通过减少代码字的平均长度来实现数据压缩，处理部分交替游程时压缩效果欠佳。相对游程长度编码方案仅需编码相对游程长度，即编码当前游程与所选参考值的差值，缩短待编码游程长度，减少对应代码字长度，提高压缩率。但一般方案只是简单通过编码当前游程与前一游程长度的差值缩短待编码游程长度[4]。由于相邻位游程长度的差值有些很小，有些可能非常大，所缩短的游程长度之和不一定最优，因此会影响到压缩效果。本文对此方案进行改进，将实验与编程相结合，编码之前先寻求最优参考值，使得所缩短待编码游程长度之和最小，达到最优的压缩效果。

1 编码方案

长度越短的游程，编码时所需的代码字越短。相对游程长度编码方法，先将预处理后的测试数据进行多段划分[5]，再将各划分段长度取值与所取参考值“Y”进行比对以进行相对游程编码处理，从而减少编码时所需的代码字，达到最终数据压缩的效果[6]。相对游程编码方法在预处理后根据划分统计每组游程的长度A1、A2、A3、A4、… 、An，从小到大依次排列，设相对游程参考值为“Y”值（若为小数，则四舍五入取整），各组游程长度依次与“Y”做差并取绝对值得a= ||A1-Y。若a＜0，则记为Q0，表示游程长度值小于Y；若a＞0，则记为Q1，表示游程长度值大于Y；若a=0，也默认记为Q0，表示游程长度值等于Y。称Q0和Q1中的0和1为正负位[7]。

参照小规模实验结果，本方案的“Y”取实验结果中较好的中位数、平均数和众数（此处是指各划分段长度取值的中位数、平均数和众数）。按以下流程确定相对游程最优参考值：预处理后对待测集进行分段；对Y进行取值，令Y=n（n=1,2,3,…,100）；将Y的不同取值分别输入所编程序，运用程序统计出Y与所有游程段的相对长度之和的最小值，此时的Y取值即为相对游程最优秀参考值；将最优取值与对应游程段的中位数、平均数和众数等进行比较，确定最优值。通过实验，得到结果如表1所示。从表1可以得出中位数最接近实验最优值，优于平均数和众数，为最优取值。

表1 最优值表

2 编码表

为使得编码后的数据集能够在解码时恢复到原始的测试集，改进型相对游程长度编码如表2所示。

表2 改进型相对游程长度编码表

编码表的第1列为组号，第2列表示预处理后的各段游程长度和其游程长度中位数差的绝对值，即相对位数，第3、4、5列表示连续0游程编码，第3列为连续0游程的附加值，第4列形式如同10、110、1110、…，表示连续0游程的前缀，第5列为其后缀；与之类似，第6列表示连续1游程的附加值，第7、8列表示其前缀及后缀；第9列表示交替01游程的附加值，第10列表示其前缀，形式如同01、001、0001、…，第11列表示其后缀；第12列表示交替10游程的附加值，第13、14列表示其前缀及后缀[8]。下面以一个实例来检验该编码方案的压缩效果：

将原始测试集{0101010101000000X0X01101010101001111111111111000X00X0001}进行填充并划分后得到测试集ZD=010101010100 000000001 10101010100 11111111111110 0000000001，依照编码表对其进行编码后得：ZE=110101 001010 000100 111011 001001。原始测试集长度为56位，编码后长度为30位，压缩效果显著。

3 数值实验

为证明本改进型相对游程长度编码方案的有效性，采用MinTest产生的测试向量集，对ISCАS 89标准电路中的部分规模较大的时序电路分别进行实验，实验结果如表3所示。

表3 本方案压缩率

从压缩效果看，本方案对s5378和s9234两个规模相对较小电路的压缩效率较低，原因是其测试集中大部分游程长度较短，不规律游程段相对较多。本文方案对此类电路压缩效果不是很好，而对电路中含有大量的长游程和规律交替游程的s13207、s15850、s35932、s38417和s38584几个电路的压缩效率则比较高。在实际操作中，集成电路的电路规模一般都比较大，含有较多无关位，处理这些电路，本文的相对游程长度编码方案是有效的[9]。

将本方案与国内2种压缩方案的压缩效率进行对比，具体结果如表4所示。

表4 本方案与国内2种方案压缩效率对比表

相对国内另两种压缩方案，本方案有较高的压缩率、较好的稳定性。同FDR码作对比，本方案的压缩率平均值优于其1.3%；同Golomb码对比，本方案的压缩率平均值优于其7.0%。

4 总结

为进一步提高压缩率，本文提出了一种改进型相对游程长度编码方案，对测试数据进行一系列预处理后，先取得最优值，再将游程长度与最优值作差，取得相对位数进行数据编码，压缩效果良好。本方案提供的编码方法适用于游程长度跨度较小与待测数据中交替游程比较多的电路，具有较高的压缩率和较好的稳定性。