应用二分算法压缩测试数据的方案

张振林，詹文法

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

随着集成电路制造工艺水平的提高，集成电路已经进入纳米量级尺寸，根据摩尔定律，未来单个芯片上晶体管的集成数量依然会呈现指数性增长，由此带来测试数据量的急剧增加，使得测试问题将变得更加困难。测试数据压缩技术大多都是通过编码方法[1-2]压缩原始测试向量，减少测试数据量，通过自动测试设备（ATE）的存储，在被测电路以硬件解码的方式还原原始测试向量，加载到待测电路，实现完整的测试流程。该方法能够有效解决测试数据量大的问题，降低测试所需成本。目前，国内外研究测试数据压缩技术主要分为两种：内建自测试（BIST）和外建自测试（BOST）。内建自测试技术主要针传统测试方法的复杂度高、故障覆盖率低、测试时间较长等因素导致测试所需成本较高的缺点，提出在电路内部建立测试生成、加载、分析和测试控制结构的方法，使得电路能够测试自身，以此来降低测试所需成本。外建自测试主要是通过压缩的形式把核的测试向量存储在测试装置中，然后把压缩后的向量输入到芯片中，并通过一个需要很小代价的硬件结构执行数据的转化。由于内建自测试技术需要满足高故障覆盖率的要求，在芯片设计阶段就必须考虑使用BIST，但目前市场上大部分核不具备BIST的特征，因此外建自测试技术应用更为普遍。本文提出的基于二分法的测试数据压缩方法，正是基于外建自测试技术的测试数据压缩方法。

1 二分算法编码压缩的主要思想

游程[3-4]长度，是指在一个由任意个0、1组成的数据流中，连续0或者连续1的个数。传统的双游程[5]测试编码方法是通过对测试向量进行游程处理，通过设计编码表计算对应游程长度的测试向量，并且通过巧妙的标记位，实现游程之间的转换，从而达到压缩原始测试数据的目的。与传统的双游程编码不同，本文在处理游程编码[6]这一环节，采用的是进制处理法。该方法主要是采用一定进制，对超过一定进制长度集中的测试向量0、1 进行切分。 以10 进制为例，假设原始的测试集为00000000000001111110000000111111111111111，传统的游程划分可分为14，5，6和15，这种游程在进行编码表编码时需要增加标记位区分测试向量在具体位置进行游程切换，以进行编码；采用本文的进制编码方法，可将游程划分为9，4，6，7，9和6，只需考虑游程为9时，后续游程是否小于进制大小，若小于进制大小，则与前一游程为同一游程，否则为交替后的游程[7-9]，即前一游程为0游程，则后续游程为1游程。需要注意的特殊情况是，当游程结束刚好为9时，增加一位0以区分此特殊情况。在原始测试集变为单个游程时，将这些游程组合起来，作为一个小数计算。

2 二分压缩方案

本方案主要在于运用二分法查找测试算法，通过将原始测试集的测试数据编码后的游程做小数处理，通过不断的二分查找，存储该二分查找的规律即可存储该若干个测试向量甚至整个测试集。压缩方法流程如图1所示。

图1 压缩方法流程图

测试数据压缩方法流程如下：

（1）根据待测试集成电路的电路结构生成若干故障的故障列表。

（2）选择任一故障，运行自动测试向量生成工具，以此生成该故障的测试向量，同时将该故障点从故障列表中删除，最终形成级联后原始测试数据即测试向量序列S，记长度为T0。

（3）游程长度统计。统计级联后原始测试数据的长度K1，K2，…，Kn，其中，Kn表示为第n个测试向量的游程长度，n为正整数。将该测试向量按0和1类型游程统计长度，采取交替游程[10-11]统计方法，选择合适的进制N，对于游程长度超过N的采用切分统计，对于游程刚好为N的交替情况，在N后面补0来区分交替情况。

（4）转化为整数，根据步骤（3）所统计的游程长度依次组成所需小数，记为m。

（5）初始化区间和原始编码，原始编码为空。

（7）上述步骤（4）中小数m在步骤（5）中初始时，原始编码为空。重复上述步骤（6），可得到最终的m编码情况，记长度为Tm。

不失一般性，记级联后原始测试数据为00000000 1111 000 1111111 00000，对于该测试向量，取10进制为例，运用上述步骤过程，最终m的编码为1101，由此可以看出原始测试数据由37位压缩到4位。

3 解压电路

3.1 硬件解压

硬件解压的关键在于运用有限状态机，将压缩后的编码实现先进先出的状态传输至CPU，同时利用CPU的二分计算将传输的编码状态还原为原始的游程长度，其间K位计数器和时钟控制器起到一定的辅助作用。本文方法的解压电路结构如图2所示，其中包含一个有限状态机（FSM）、两个特殊的K位计数器、一个时钟控制器T，同时利用了SOC中的CPU模块，将解压电路嵌入芯片中，该电路规模小且结构简单，成本较低。

图2 硬件解压图

解压电路的工作过程如下：

步骤1有限状态机发出信号使数据读入，由K位计数器不断累加计数，且时钟控制器T记录下读入“1”的时间节点，每累加一次“1”记录，同时由第一个K位计数器和时钟控制器将传输记录传入FSM和CPU。

步骤2FSM不断读取编码数据直至每组测试向量读写完毕，同时K位计数器和时钟控制器T将读取后的状态传输至CPU。

步骤3由FSM将读取后的每位编码传送至CPU，并进行上下限相加后的模2运算，由K位计数器和时钟控制器同时控制每次查找的状态，并做自减运算。

步骤4由CPU 计算后的结果，依次赋值每位小数的数值到K 位计数器，并输出相应位数的“0”和“1”的个数。

3.2 软件解压

软件解压方法的流程图如图3所示，其主要工作原理是由控制计算机将原始测试数据压缩后的测试规律通过ATE传输至被测芯片，由解压和控制电路将测试规律还原为原始测试数据传送至被测电路，然后将测试结果返回至控制计算机。

图3 软件解压图

不失一般性，以10进制举例，假设原始测试集为00000000 1111 000 1111111 00000，可以通过二分编码压缩为1101，解压步骤如下：

步骤1将控制计算机编码计算出的1101由ATE传输至被测芯片，通过解压和控制电路中CPU模块转换编码规律进行解压。

步骤2当前以0为下限m0，1为上限m1，做模2操作得到的值为t=0.5，当读取第一位编码规律为1时，即向右查找，令t=m0，初始化t，继续读取第二位编码规律为1，继续向右查找；如此循环，直至编码规律读取结束。

步骤3将解压后的小数，进行分位，通过不断赋值给控制电路中的K 位计数器，交替输出K 位的“0”和“1”到被测电路中。

步骤4将测试结果与期望值进行比较，若结果一致，测试通过；否则，测试未通过。

4 实验分析

为了证明本实验的有效性，采用MinTest产生的测试向量集，对ISCAS 89标准电路中部分规模较大的时序电路分别进行了实验，得出实验结果如表1所示。

表1 本方案压缩率

从实验结果来看，本二分编码方案对s5378 和s9234 两个规模较小的电路压缩率较低，原因是其测试数据在游程编码时较短且集中，游程位数较多，本方案对该类电路压缩效果不是很好；针对电路中存在较长游程和比较规律的电路s13207、电路s35932有较好的压缩率。实际上，在测试芯片的大规模集成电路中，无关位较多，本文的方案能够起到很好的压缩效果。

表2给出本方案与国内两种方案压缩率对比情况。由表2可以看出，相对国内另两种压缩方案，本二分编码方案具有一定的压缩率、较好的稳定性，同Golomb 码对比，本方案的压缩率平均值优于其0.7%；同时本方案在s35932电路中的压缩率皆高于另外两种编码方案。

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

5 总 结

传统的编码方法多为基于FDR/EFDR编码表的方法压缩代码字，压缩方式复杂且成本较高。本文提出一种新的基于二分编码压缩的方法，其主要特点：（1）采用一定进制的编码方法，实现双游程无标记位交替编码。（2）通过运用二分编码算法，实现测试向量压缩。（3）硬件解压电路简单，不会给测试增加多余成本。因此，本方案的编码方法，不但节省代码字的长度，而且减少了硬件开销，为缩减原始测试数据、降低测试所需成本提供了一种有效的方法，具有一定的实用价值。