基于线性生成图编码SoC测试向量方法

黄贵林，张正金，江家宝，吴其林，王洪海

(巢湖学院 信息工程学院，安徽 巢湖 238024)

0 引言

“芯片内集成的晶体管数目每18个月将增加一倍”，同时，系统级芯片和系统级封装的产品，也称片上系统(system-on-chip，缩写为SoC)，已成为半导体产业的主要驱动力。单个芯片上集成的晶体管越来越多，给芯片测试带来了一系列新的挑战。其中，不断增长的数据量测试是芯片测试必须面临的挑战[1]，在有限的ATE存储空间和I/O带宽方面，存储和传输大量的测试数据，测试成本会升高，测试时间变长。测试数据压缩技术一直致力于解决这个难题。

目前，测试数据压缩技术分为三类[2]：基于LFSR结构的压缩方法[3]、基于广播扫描的压缩方法[4]、编码压缩方法[5]。其中，编码压缩是一种十分受欢迎的测试数据压缩方法，根据码字的对应关系对数据块进行编码压缩，如： GOLOMB、FDR、ALT-FDR、EFDR、9C、BM、RL-HC、SHC、VIHC，它们都是一些非常经典优秀的方案[6]。目前其能达到的压缩效果还是非常理想的，但在测试应用时间上很难被接受，它以数据块为单位产生测试数据，不能快速产生整条测试向量。为此，有通过加法器生成后续测试向量进行编码压缩的[7]。为考虑测试应用时间及压缩率等问题，在测试向量层面，本文提出一种利用循环扫描链的测试向量编码方法。该方法对所有测试向量进行顺时针循环移位遍历，找到所有间接相容的测试向量，并将其构造成线性生成图。根据循环移动位置对测试向量进行编码，编码替换测试向量进行存储，实现无损压缩，达到测试数据压缩的目的。本文贡献：⑴解压电路结构简单。除了需要常规的FSM和计数器之外，只需要一个通道MUX即可。⑵测试数据压缩率显著提高。⑶测试应用时间大幅度降低。⑷算法简单。

1 设计方案

1.1 循环扫描链

定义1：对于单扫描链而言，芯片测试外壳当中的所有扫描链是单方向的，是以串的形式连接在一起的。Input为时序电路的功能输入(外部输入)端，即测试向量的部分测试数据的输入端，Output为时序电路的功能输出(外部输出)端，即测试响应的部分数据输出端。每个触发器的Q连接到时序电路当中组合电路的输入端，也连接到下一级触发器单元的Q′。

扫描链当中的第一个触发器和最后一个触发器连接起来，即最后一个触发器的Q也作为第一个触发器的输入TD，如图1所示，图中虚线电路为本文添加的电路结构，与原有的触发器连线，将所有触发器连接形成一个环形的扫描链。测试向量可以在扫描链当中顺时针循环移动，因此称为循环扫描链。

图1 循环扫描链

定义2：物理上形成的循环扫描链，测试向量可在循环扫描链当中顺时针循环移动。逻辑上，就形成了环形的循环测试向量。测试向量1：A0、A1、A2、…、An，测试向量2：B0、B1、B2、…、Bn，测试向量1和2的对应位A0和B0、A1和B1、A2和B2、…、An和Bn等对应位全部相容，则称测试向量1和测试向量2直接相容。

图2 测试向量1在扫描链中循环右移1位

如图2所示，测试向量x0011在循环扫描链当中顺时针循环移动1位，得到测试向量1x001。测试向量1x001与图3当中的测试向量2(1xx01)相容，则称测试向量1与测试向量2间接相容。下划线所示的两个测试位1和1，是新形成的对应位。

图3 测试向量2

1.2 线性生成图

在逻辑上，每个测试向量都是循环测试向量。先探索构造环形生成图，节点是测试向量，所有节点的出度和入度都为1，N个节点共有N条边。再继续构造线性生成图，首节点的出度为1，尾节点的入度为1，其余每个节点的出度和入度都为1，N个节点共有N-1条边。节点之间间接相容，循环右移的位数为权值。测试向量长度为L。

⑴列表List1的初始状态是空集，列表List2的初始状态包含整个测试集，即被测电路的所有测试向量。

⑵第0个测试向量T(0)从List2进入List1，List2中没有T(0)。在(3)到(7)中，List1和List2的并集是被测电路的整个测试集，即被测电路的所有测试向量。

⑶测试向量的长度为L，测试向量T(1)顺时针循环移动n位，然后第n位，第(n+1)位，…，第(L-1)位、第0位、第1位、…以及循环测试向量T(1)的第(n-1)位，分别与循环测试向量T(0)的第0位、第1位、第2位、…、第(L-2)位、第(L-1)位形成新的对应位关系，对T(0)和T(1)之间不相容的位数进行计数。n的范围在0和L-1之间。根据不同的n，统计L次T(0)和T(1)之间不相容的位数。在这个统计过程中，如果不相容位的最小个数为0，说明T(0)和T(1)之间间接相容，那么T(1)从List2进入List1。

⑷重复这个过程，即List1中的任意一个测试向量T(i)和List2中的某个测试向量T(j)之间相容性分析的过程。如果T(i)与T(j)间接相容，那么T(j)从List2进入List1。

⑸如果List1中的任何测试向量与List2中的任何测试向量不间接相容，则选择List1中的任何测试向量T(k)以循环向右移位。当T(k)每次向右移位一位时，判断是否间接相容其他测试向量。如果首先发现T(m)与T(k)间接相容，那么将T(m)设为T(k)的邻节点。T(m)将从List1中删除。

图4 环形生成图

图5 线性生成图

⑹重复(5)直到List1是一个空集。最后一个测试向量T(n)成为T(k)的相邻节点，形成与表1对应的环形生成图，如图4所示。

⑺删除权重最大的边，构造有向线性生成图，如图5所示。在测试过程中，会按照有向线性生成图的顺序生成测试向量，种子测试向量T7会生成测试向量T1，T1会生成T3，以此类推，直到生成T5，所有的测试向量都会生成。

1.3 编码实例

现有9个测试向量，每个测试向量为40位，9个测试向量之间全部间接相容。第一个测试向量T1每次循环右移1位，查找是否存在测试向量与其间接相容，如图4所示。

表1 测试向量相容性分析

在T1循环右移2位时发现，新形成的测试向量与T3最先相容，T1与T3间接相容。因此，T3编码为10010。

T3继续循环右移，当循环右移3位时发现，新形成的测试向量与T8最先相容，T3与T8间接相容。因此，T8编码为10011。

以此类推，T6、T9、T2、T4、T5、T1分别编码为10001、10100、10110、11000、10101 和 10010，如表1所示。删除权值最大的边，得到图5，将测试向量T7作为种子测试向量。在测试过程中，将按照图5所示顺序生成后续测试向量。

按照图5所示线性生成图的顺序，T7循环右移产生T1，T1产生T3，直至产生T5，循环右移位数之和为31，即如图5所示权值之和为31，小于测试向量长度。总的来说，生成图所有测试向量的测试应用时间长度与单个测试向量长度值相当，单个测试向量的测试应用时间长度远小于测试向量长度值。

2 解码体系结构

本方案的解压体系结构主要是由FSM、计数器1、计数器2、计数器3和MUX构成。如图6所示，‘en’和‘bit_in’分别是输入使能和位输入信号。‘flag’为MUX通道选择信号，‘data_in1’和‘data_in2’连接MUX两个输入端，MUX输入端‘data_in2’连接扫描链的末端，MUX输出端‘out’连接扫描链的头部。MUX控制扫描链触发器当中的测试数据在扫描链内部顺时针循环移动，得到新的测试数据，即产生下一个测试向量。

图6 解压结构

计数器1用于测试向量移入扫描链计数。‘dec1’用于计数器1减1，‘rs1’用于指示计数器1的复位0状态，计数器1的长度为┌log2(L)┐。计数器2用于编码code移入暂存器计数。‘dec2’用于计数器2减1，‘rs2’用于指示计数器2的复位0状态，计数器2的长度为┌log2(code_L)┐，code_L为编码长度。

计数器3用于顺时针循环移位时钟周期数计数，即为循环移位位数计数。‘dec3’用于计数器3减1，‘Dec3’用于指示将暂存器中的编码重置至计数器3，‘rs3’用于指示计数器3的复位0状态，┌log2(code_L)┐为计数器3的长度。暂存器里存放的是编码，‘dec’用于使能暂存器，‘data_in’用于将编码code移入暂存器。

3 编码分析

N个测试向量构造线性生成图，构造环形生成图的时间复杂度T(L)=O(N×L)，构造线性生成图的时间复杂度T(L)=O(L)，则整个算法时间复杂度为O(L)，算法简单。压缩率为：

很显然，对于环形生成图，权值之和为L，对于线性生成图，权值之和小于L。除种子测试向量，线性生成图上的测试向量测试应用时间时钟周期数为t。

4 实验结果

为证明本方案在压缩率上的有效性，给出了基于国际公认的ISCAS89标准电路的实验结果。在实验过程中，测试向量被连续注入编码算法。图7至图12是不同情况下的压缩率变化曲线，横坐标表示注入算法的测试向量X的数量，纵坐标表示压缩比Y。由测试图可知，在测试向量注入过程中，压缩率波动，但是总体压缩率保持上升趋势。因此，本文提出的测试数据压缩方案具有鲁棒性，符合公式⑵的预期。

为进一步证明本方案的有效性和科学性，计算标准电路测试向量的总体压缩率，如表2所示。最后一列为本文所提方案的压缩率，压缩率优于其他的大部分方案，平均压缩率都优于其他方案，说明本文所提方案适应性较好。

表2 实验结果

图7 S5378压缩率变化曲线

图8 S9234压缩率变化曲线

图9 S13207压缩率变化曲线

图10 S15850压缩率变化曲线

图11 S38417压缩率变化曲线

图12 S38584压缩率变化曲线

5 结论

本文主要是探索测试向量之间的相容性，通过顺时针循环右移扫描链当中的测试向量错开对应位，原对应位之间的位置关系已经不再对应了。测试向量当中存在大量无关位，新形成的所有对应位存在全部相容的可能性，使得不同的测试向量之间存在间接相容的关系，消除了这种原对应位不相容的问题，为测试数据压缩提供了依据，有效降低测试应用时间。