尤志强，胡 娜

(湖南大学 信息科学与工程学院，湖南 长沙 410082)

一种基于FDR的高测试质量测试压缩方法

尤志强†，胡 娜

(湖南大学 信息科学与工程学院，湖南 长沙 410082)

FDR编码方法有效地降低了测试数据量，但其测试集中的无关位全部填充为0，平均每个测试向量检测的故障数目较少，测试质量较低.为了提高测试质量，并进一步提高测试数据压缩率，本文基于FDR方法提出了一种利用上一个测试向量的响应填充该测试向量中无关位的测试压缩方法.该填充方法提高了测试向量中无关位填充的随机性，从而提高了测试集的测试质量.提出方法的压缩效率与测试向量的顺序有关，基于最近邻居算法对测试集进行排序，降低了测试响应与下一个测试向量之间不相同的位数，对测试响应和测试向量差分处理后再进行FDR编码，从而降低了测试数据量.ISCAS’89电路中几个大电路的实验结果表明，与FDR相比该方法的测试质量平均提高了5.9%，测试数据压缩率平均提高了2.5%，而只需要增加一个异或门的硬件开销.

测试质量；测试数据压缩；无关位；FDR编码

随着超大规模集成(VLSI)电路制造工艺的不断进步，越来越多的知识产权(IP)核被集成到一个芯片上，测试数据量急剧增长.庞大的测试数据对昂贵自动测试设备(ATE)的存储性能、I/O通道数和频率提出更高的要求，同时增加了测试应用时间，提高了测试成本.因此，如何降低测试成本成为集成电路(IC)测试的一个重要研究课题.

测试数据压缩方法能够有效地减少测试数据量，降低存储和测试设备数据传输通道数量的需求.同时，经过适当设计，还可以降低测试应用时间和测试功耗.目前，测试数据压缩技术主要有3大类：1)线性解压方案[1-2]；2)基于广播式扫描的方案[3]；3)基于编码的压缩方案[4-7].

许多编码压缩方法利用测试集中的无关位X.FDR[4]是一种0游程编码，X都被填充为0以增加0游程的长度.文献[5]提出了一种EFDR编码，通过添加一个区分位，同时对0游程和1游程编码.文献[6]提出了交替游程编码，不需要添加区分位，对0游程和1游程交替编码，不仅能降低测试数据量还能减少测试功耗.在文献[7]中，测试集被分成等长的数据块，使用动态参考向量机制，利用前一块的信息对后一块数据进行编码.

在FDR编码中，无关位X都被填充为0，虽然提高了测试数据压缩率，但这种填充方式，使得测试向量中0的比率很高，平均每个测试向量检测的故障数目较少，降低了测试集的测试质量[8].

1 测试压缩方案和解压缩结构

通常测试集中无关位X的比率较高，而测试质量与测试向量无关位填充方式有关.通常来说，测试向量中无关位的填充值随机性越好，测试质量越高.为了提高测试质量，我们考虑到测试向量和测试响应的相关性较弱，在新的测试压缩方案中，测试向量的无关位不再全部填充为0，而是根据前一个测试向量的响应值来填充下一个测试向量的无关位.

例1 在图1(a)中有3个测试向量和对应的测试响应，首先倘若把第一个测试向量无关位填充为0，故障模拟后得到测试响应r1′，然后根据r1′填充测试向量t2中的X，故障模拟后得到测试响应r2′，再根据r2′填充测试向量t3中的X，故障模拟后得到测试响应r3′.填充无关位后的测试向量和测试响应如图1(b)所示.与图1(a)中测试向量的无关位全部填充为0相比，图1(b)中测试向量每位的取值随机性较好，通常可以获得更高的测试质量.

测试向量和响应测试向量和响应差分向量t1 1xx1xxxx0t′1 100100000c1 100100000r1 1xx10xxxxr′1 100100001t2 1xxx1xxxxt′2 100110001c2 000010000r2 xxxx110x0r′2 010011010t3 1x0xx1xx1t′3 110001011c3 100010001r3 x11xx1xxxr′3 011001000(a)(b)(c)

图1 无关位填充举例

Fig.1 Example for X-filling

使用这种方法填充无关位的测试集中1的个数必然会增加，直接FDR编码后的测试压缩率也必然会降低.为了提高测试压缩率，我们将对前一个的测试响应和根据它填充无关位的下一个测试向量做差分，形成差分向量.最后，再对差分向量集使用FDR编码.

例2 图1(b)给出了用提出方案填充的测试向量及对应的测试响应.假定触发器中的初始状态为全0，第一个差分向量c1为第一个测试向量和全0的差分，结果与第一个测试向量相同.我们分别对r1′和t2′及r2′和t3′做差分得到差分向量c2和c3，差分向量集如图1(c)所示.可以看出，该差分向量集中确定位1的位数由原始测试向量集中的7位降为6位.0填充FDR编码后为00 1000 1011 1001 1010 1010 1000，共26位；而差分向量集进行FDR编码后为00 1000 110011 1010 1001 1001，共24位，差分向量集进行FDR编码后得到较短的编码，提高了测试压缩率.

解压缩过程与前述压缩过程相反.解压缩结构如图2所示，由一个FDR解码器和一个二输入异或门组成.TE代表FDR编码后的测试数据，经FDR解码器解压还原成差分向量集Tdiff，Tdiff中的差分向量经过异或门与扫描链中保存的上一个测试向量的响应异或，恢复用提出方法填充无关位的测试集TD.由此可见，与FDR编码方法的解压缩结构相比，提出方法只多了一个二输入异或门，其额外的硬件开销可以忽略不计.

图2 解压缩电路结构

差分向量中1的个数与做差分的测试响应和测试向量不相容的位数相关.对应位中有一位为X或者两位相同时，我们称这两位是相容的，否则是不相容的.不同的测试向量顺序，差分向量中1的总个数有所不同.因此，测试向量重排序可以进一步提高测试压缩效率.

2 测试向量/响应重排序方法

本节针对带无关位的测试集进行排序.对于相邻的测试向量和每个触发器，我们将测试响应和测试向量对RTP用(rik,tjk)表示，其中k为触发器编号.差分向量中对应的位为RTP中rik与tjk的差分.如果RTP为(0,0), (1,1) ，则差分向量中对应的位为0；而如果为(1,0), (0,1)，对应的位为1.对于 (0,X) ，(1,X)通过填充X为其对应的响应值，其差分向量对应的位为0；而对于 (X,0), (X,1)，如果同时将多个响应中的X填为其测试向量值，有可能产生矛盾.因此，我们不能简单地用它们之间不相容的位数来计算差分向量中1的个数.如果RTP为(X,X)，可以先确定测试响应中的X，再用该值将测试向量中的X填充，其差分向量对应的位为0.注意到，虽然RTP为(0,0), (1,1)和 (0,X), (1,X), (X,X)时其差分向量对应的位为0，在排序中若优先考虑(0,0), (1,1)的情况，可以获得较好的压缩效果，应该为其分配更佳的权值.表1为权值表，R代表响应值，T代表测试向量值，表中为具体RTP的权值.如，w0,1是为(0,1)分配的权值.

表1 权值表

定义1 两个向量的距离d(ti,tj)或dij为每个触发器的测试响应和测试向量对RTP权值的总和.

(1)

其中Nff是触发器的个数.由于权值表不对称，d(ti,tj)与d(ti,tj)不一定相同.

例3 假设测试向量ti的响应ri=110XX，测试向量tj=10XX0，由式(1)，假设w1,1=w0,0=-20，w1,0=w0,1=20，w1,X=w0,X=wX,X=-0.5，wX,1=wx,0=0.5，它们之间的距离d(ti,tj)=-20+20+(-0.5)+(-0.5) +0.5=-0.5.

定义2 差分距离图G=(V,A)是一个有向完全图， 其中V是一个节点集，每个节点对应于一个测试向量，A是一个有向边集，每条边的权是始点和终点对应测试向量的距离.

例4 如图1(a)所示的3个测试向量t1，t2，t3，和它们的测试响应r1，r2，r3.可以建立如图3所示的差分距离图，该图包括3个节点t1，t2，t3和6条有向边，每条有向边上的数字为该边的权.每种RTP的权与例3中的相同.由图3可以看出，不同的测试向量顺序有不同的距离值，最优的测试向量顺序即总距离最短的节点路线.

综上所述，测试集的排序问题等价于TSP问题，为NP-完全问题.我们采用解决TSP问题的近似算法——最近邻居算法(Nearest neighbor algorithm)求解，其排序过程概括如下：

图3 差分距离图

根据测试向量集及对应的响应，建立差分距离图；

选中第一个测试向量，作为当前测试向量tcurrent，标识这个向量为已选；

从未标识的测试向量中选择跟tcurrent距离最小的测试向量，作为新的tcurrent，并标识该向量为已选；

重复上述步骤直到测试集中没有未标识的向量；

计算最后选择的测试向量与第一个测试向量的距离，构成汉密尔顿回路；

在汉密尔顿回路中剔除最大距离的边，得到总距离较短的测试向量序列.

例5 对图1(a)中的测试向量进行排序.首先建立差分距离图，如图3所示.假设取t1作为第一个向量，在t2和t3选取与之距离较小的向量， 即t3，距离d13=-21.此时只剩下t2未被选择，选择t2，t3和t2的距离d32=-2.5.添加t2和t1之间的边，权值d21=-22，形成汉密尔顿回路.最后，去掉回路中最大的距离值，这里为d32.重新排序后的测试集顺序如图4所示，为t2,t1,t3.

图4 测试向量重排序示例

重排序之后通过无关位填充和故障模拟可以得到如图5(a)和图5(b)所示的测试集和响应集，通过差分处理可以得到如图5(c)所示的差分集.

测试集TD响应集RD差分集Tdifft″1=100010000r″1=100111010c″1=100010000t″2=100111010r″1=100101011c″2=000000000t″3=110101011r″3=011101000c″3=010000000(a)(b)(c)

图5 差分示例

Fig.5 Example for difference vector

不排序测试向量得到的差分向量用FDR编码压缩后为00 1000 110011 1010 1001 1010，共计24位；而对测试向量排序后得到的差分向量用FDR编码压缩后为00 1001 11100000 110001，总计20位.从本例中可以看出，使用距离排序可获得更高的压缩率.

3 实验结果

我们对提出的测试压缩方法进行了实验，用Synopsys公司的TetraMAX生成测试向量，实验电路为ISCAS’89电路中最大的几个电路.在实验过程中分别取几组不同的权值，取结果最优的一组权值.最优的权值与例3中的相同.

表2为不同测试集中无关位填充方式测试质量的实验结果.第1列为电路名称，第2列为随机填充每个测试向量平均能检测的故障数，第3，4列分别为用0填充和提出填充方案平均每个测试向量检测的故障数与随机填充方法的比值.由实验结果可以看出，用提出填充方案填充的测试集可以获得与随机填充相当的测试质量，与0填充方式相比，提出方案平均每个测试向量多测5.9%的故障.

表2 测试集测试质量比较

表3为测试数据压缩率的实验结果.第一列为电路名称，第2列(#vec)为测试向量数，第3列(#ff)为扫描单元数，第4列为测试集大小，第5列为

表3 测试压缩率比较

FDR编码的压缩率，第6列为本文方法的压缩率.实验结果表明与FDR编码方法相比，本文方法平均压缩率要高2.5%.其中计算压缩率如式(2)所示.

压缩率=(TD-TE)×100%/TD

(2)

其中TD为原测试集的大小，TE为压缩后的测试集大小.

4 结 论

本文提出了一种利用前一个测试向量的响应填充当前测试向量无关位的方法，增加了填充的随机性，提高了测试质量.为了进一步提高测试压缩率，利用最近邻居算法对测试集进行排序.研究结果表明，本文方法简单可行，提高了测试质量和测试压缩率，而增加的硬件开销可以忽略不计.许多用来提高FDR方法压缩率的技术同样适用于本方法，这些改进将在下一步工作中体现.

[1] XIANG D, LI K, SUN J,etal. Reconfigured scan forest for test application cost, test data volume and test power reduction[J]. IEEE Transactions on Computers, 2007, 56(4): 557-562.

[2] XIANG D, CHEN Z, WANG L T. Scan flip-flop grouping to compress test data and compact test responses for Lauc-on-Capture delay testing[J]. IEEE Transactions on Design Automation of Electronic Systems, 2012, 17(2): 18.

[3] YOU Z Q, WANG W Z, LIU P,etal. A scan disabling-based BAST scheme for test cost and test power reduction[J]. IEICE Electronics Express, 2012, 9(2): 111-116.

[4] CHANDRA A, CHAKRABARTY K. Test data compression and test resource partitioning for system-on- a-chip using frequency-directed run-length(FDR) codes[J]. IEEE Transactions Computers, 2003, 52(8):1076-1088.

[5] EI-MALCH A H. Test data compression for system-on-a-chip using extended frequency-directed run-length code[J]. IET Computers & Digital Techniques, 2008, 2(3): 155-163.

[6] YE B, LUO M. A new test data compression method for system-on-a-chip[C]//Proc IEEE International Conference on Computer Science and Information Technology (ICCSIT). Chengdu, 2010:129-133.

[7] YI M X, LIANG H G, ZHANG L,etal. A novel X-ploiting strategy for improving performance of test data compression[J]. IEEE Transactions on Very Large Scale Integration(VLSI) System, 2010, 18(2): 324-329．

[8] CHO K Y, MITRA S, MCCLUSSKEY E J. California scan architecture for high quality and low power testing[C]//Proc IEEE International Test Conference. Santa Clara, 2007:1-10.

A High Test Quality Test Compression Method Based on FDR Codes

YOU Zhi-qiang†, HU Na

(College of Computer Science and Electronic Engineering, Hunan Univ, Changsha, Hunan 410082, China)

FDR codes can compress test stimuli data effectively. However, the number of faults detected by a test pattern is small in average, since don't care bits in the test set are filled by all 0s. The test quality is low. In order to improve the test quality and further increase the test compression ratio, this paper, based on FDR codes, proposed a scheme in which the test response of the previous test pattern is utilized to fill the don't care bits in the current test pattern. This scheme increases the randomness of the X-filling. Therefore, the test quality is improved. In this scheme, the test compression ratio is also related to the order of test patterns. This paper also proposed a test pattern reordering approach based on the nearest neighbor algorithm to decrease the number of conflict bits between the test response of the previous test pattern and the current test pattern. Difference vectors can be obtained by the difference between test patterns and the test responses of their previous test patterns. The test data volume can be reduced by using FDR codes for the difference vectors. Experiment results show that, for larger ISCAS'89 circuits, the proposed approach increases the test quality by 5.9% and test compression ratio by 2.5% in average, compared with those of FDR codes. The hardware overhead, which is only an XOR gate, can be omitted.

test quality; test compression; don’t care bits; FDR codes

1674-2974(2015)02-0109-05

2014-05-18

新世纪优秀人才支持计划资助项目(NCET-12-0165)；国家自然科学基金资助项目(61472123),National Natural Science Foundation of China(61472123)

尤志强(1972-)，男，河北阜城人，湖南大学副教授，博士†通讯联系人，E-mail:zq_you@163.com

TP302

A