结合TRC和Golomb编码的二维测试数据压缩

高紫俊， 许 晶

( 1. 哈尔滨理工大学 荣成学院，山东 荣成 264300； 2. 大庆电力集团 油田热电厂，黑龙江 大庆 163314 )

0 引言

随着深亚微米技术的发展，集成电路进入片上系统(SoC)时代.复杂的SoC设计导致测试变得越来越复杂.传统的基于ATE的测试方法很难满足测试成本方面的需求.内建自测试(Built-in Self-Test，BIST)是一种极具吸引力的解决SoC测试问题的测试方法[1-5].BIST通过将测试向量生成器(Test Pattern Generator，TPG)、测试响应分析器(Output Response Analyzer，ORA)和测试控制逻辑(Test Control Logic，TCL)设计在被测电路(Circuit Under Test，CUT)上，从而摆脱对ATE的依赖[1-2].依据测试向量生成方法的不同，BIST被分为伪随机BIST和确定性BIST.伪随机BIST通常采用伪随机测试向量电路，如线性反馈移位寄存器(Linear-Feedback Shift-Register，LFSR)和细胞自动机(Cellular Automaton，CA)等，生成测试向量.采用伪随机测试向量方案具有电路结构简单、硬件开销小等优点，但也存在测试序列长、某些故障难以测试等不足.在确定性BIST方案中，一般将由ATPG生成的测试集存储在被测电路(Circuit under Test，CUT)的ROM中，测试时通过控制逻辑再加载到被测电路上.确定性BIST方案具有测试时间短、故障覆盖率高等优点，也具有测试数据大、测试控制逻辑复杂等缺点[3-6].

周彬等[6]采用“压缩-存储-生成”方案降低测试数据，测试数据的压缩方式可分为水平压缩和垂直压缩.水平压缩是减少测试集中每个测试向量的位数的方法，主要包括输入精简压缩技术和编码压缩技术.输入精简压缩技术通过分析被测电路的各个输入端的相容性，并将相容的输入端合并，从而达到压缩测试数据的目的[7-8]，该方法的优点是压缩效率高；缺点是必须重新设计扫描链结构，进而干扰传统的设计流程.编码压缩技术包括统计码[9]、FDR码[10]、Golomb码[11]、VIHC码[12]、LFSR编码[13]等.垂直压缩是减少测试集中测试向量个数的方法，主要包括相容测试向量的合并技术和测试集嵌入技术.相容测试向量的合并技术通过分析测试集中测试向量的相容性，并将相容进行合并，从而达到减少测试向量个数的目的.测试集嵌入技术通常是利用重播种技术改变测试向量产生器的状态，进而将确定性的测试向量嵌入在定制计数器或LFSR生成的一个长序列中，如基于折叠计数器的确定性测试集的嵌入技术[3-5]和基于扭环计数器(Twisting Ring Counter，TRC)的测试集嵌入技术[14-18].

笔者给出一种基于扭环计数器(TRC)和Golomb编码相结合的二维测试数据压缩方案.首先，采用基于TRC的测试集嵌入技术对由ATPG工具生成的测试集进行垂直压缩；其次，利用TRC种子可以任意移位的特性对所得到种子集进行有效的Golomb编码压缩；最后，使用很少的种子位将这个确定测试集嵌入到扭环计数器所有生成的向量中，并获得100%的故障覆盖率.由于无需调整任何扫描链,该方案完全与标准设计流相容.另外，对于不同的被测试电路，提出方案的测试控制逻辑都是相同的，不需要进行专门的硬件设计.

1 垂直压缩

采用与文献[6]相似的种子选择算法对测试集进行垂直压缩.在算法中，除定义相容百分数(Percentage of Compatibility，PC)外，还定义一个最大确定位个数Max_SB控制种子中确定位的个数，使后续的基于Golomb编码的水平压缩获得更大的压缩效率.

种子选择算法步骤：

(1)计算测试集中每个测试向量中含有无关项X的数量，并且根据无关项的数量，对测试集中的测试向量由小到大进行排序.

(2)在经排序后的测试集中，第1个测试向量集将被选作为算法的候选种子(初始种子)，并且根据TRC的特性，利用该候选种子生成2n2+n个TRC状态，该候选种子中包含有无关项X.

(3)在经排序后的测试集中，取出一个测试向量Tj(除种子向量之外)，如果在长为2n2+n的TRC状态中，找到某一个状态TRCi，使得在XORNEW(TRCi，Tj)的结果中，不存在 ‘1’，并且‘0’的个数大于等于相容数(NCSB(Tj))时，根据Tj指定候选种子中相应的无关项，如果指定之后的候选种子所含确定位的个数小于Max—SB，将Tj从原确定性测试集中删除，否则恢复候选种子到未指定之前的状态；然后再在经排序后的测试集中选取下一个测试向量Tj+1，直至所有测试向量都被遍历为止.XORNEW函数是原始异或函数的扩展，功能与原始异或函数类似，唯一的区别在于XORNEW函数可以对包含无关项X的操作数进行处理，如XORNEW(10x，001)等于10x.

(4)当测试集中仍包含有测试向量时，算法就再次跳转到第2步；当测试集中不包含有测试向量时，算法结束.

由种子选择算法的步骤可知，通过引入最大确定位个数Max—SB，算法所得到种子中包含有大量的无关项，为实现高效的基于Golomb编码的水平压缩提供便利条件.

2 水平压缩

表1 Golomb编码实例(m=4)

选用Golomb码对种子集进行编码，其原因为Golomb码属于无失真编码,不仅具有较高的编码效率,而且易于用硬件解码.m=4时所对应的Golomb编码见表1.其中：m为分组的大小，第1列表示编码的分组信息，第2列为0游程的长度，第3列为编码前缀，第4列为编码尾缀，最后一列为对应的编码码字.如待压缩序列Sd为001001001000000001时，编码后的序列Se为01001001011000.当待压缩序列Sd给定时，随着Golomb编码参数m值的不同，所得的压缩增益是不同的，因此参数m的选取非常关键.采用实验方法确定最佳的m值.

3 测试结构

基于Golomb编码和扭环计数器的重播种结构见图1.其中，在被测电路的原始输入端上增加一个扫描触发器，并与被测电路内部的扫描链构成一个长的扫描链，称之为输入寄存器.测试时，通过该输入寄存器对被测电路进行激励的加载.ROM中存储的是重播种所需要的种子差分向量序列经过Golomb编码之后的测试数据.整个电路的工作过程：首先，被测电路的输入寄存器形成一个移位寄存器，在n个时钟周期内，通过种子差分向量与移位寄存器中上一个种子向量的结束向量相异或，产生一个TRC种子向量；利用该TRC种子向量，在2n2+n时钟周期内产生2n2+nTRC状态，并加载至被测电路的输入端，同时在被测电路的输出端得到相应的响应；接着，ROM计数器加1，下一个TRC种子被装载到输入寄存器中，并产生测试向量序列，重复进行上述过程，直到测试完成.

图1 基于Golomb编码和扭环计数器的播种结构

BIST控制逻辑结构见图1被虚线包围的区域.提出方案的BIST控制逻辑主要包含具有3个状态的有限状态机、2个计数器和组合控制逻辑电路.其中，移位计数器是用来计数每个TRC种子所需要的n次移位操作，在测试生成的过程中，每当2n+1个时钟周期之后，内容自动加1，同时输入寄存器的内容执行一次循环移位操作；扭环计数器被用来对TRC种子的加载操作和TRC种子生成测试向量进行计数.

4 实验结果与分析

基于提出的二维测试数据压缩方案，针对ISCAS’89实验电路进行研究.在实验中，ISCAS’89实验电路的所有输入和其内部的触发器构成被测电路的输入扫描寄存器，采用ATALANTA ATPG工具为被测电路生成测试集.为了提高所生成的确定性测试集中无关项X的含量，在实验中关闭了ATALANTA ATPG工具压缩机制.

提出基于扭环计数器(TRC)和Golomb编码相结合的二维测试数据压缩方案，与其他先进的BIST方案[16,18]在测试数据方面的比较结果见表2.其中：第2、3栏分别描述提出BIST方案所需要的种子个数以及最终的测试数据位数ROM1；第4、5栏分别列出基于TRC的确定性BIST方案[16]所需要测试数据位数ROM2，以及基于LFSR的确定性BIST方案[18]所需要测试数据位数ROM3；最后2栏是文中提出二维测试数据压缩BIST方案与文献[16，18]的比较结果.与文献[16]比较，提出的二维测试数据压缩BIST方案具有更高的压缩倍数，在存储位数方面减少近30%.

表2 二维测试数据压缩方案与其他方案存储位数(ROM)的比较

5 结束语

提出一种结合扭环计数器(TRC)和Golomb编码的二维测试数据压缩的内建自测试方案.首先，利用扭环计数器实现对测试集进行垂直压缩；然后，对经过垂直压缩之后的扭换计数器种子再进行基于Golomb编码的水平压缩.根据实验结果显示，所提出二维测试数据压缩BIST方案在测试数据方面有一定的提高，而且在减少测试数据的同时，不会显著增加测试时间，存储位数减少30%，是一种具有潜力的确定性BIST方案.