最小游程切换点标记编码压缩方法
詹文法1,2, 陶鹏程1,2    
1. 安庆师范大学 计算机与信息学院, 安庆 246003;
2. 安徽省高校智能感知与计算重点实验室, 安庆 246003
摘要:针对集成电路所需测试数据量庞大、测试成本过高的问题,该文提出了最小游程切换点标记编码压缩方法,将原始测试数据压缩,达到减少测试成本的目的。该方法将测试集按若干向量分组编码,利用组内向量游程切换范围的重叠关系合并游程切换点,可以将组内所有测试向量的游程位置用一个向量表示出来,突破了传统编码压缩要用编码字后缀表示游程长度的限制,相较于传统编码压缩,极大地缩短了编码字。该方法解压规则简单,硬件开销小,ISCAS 89标准电路实验结果表明:该方案压缩效果优于其他几类编码压缩方案,可为测试数据量过大提供有效解决方法。
关键词测试数据压缩    无损压缩    编码    游程    
Minimum run-changing point mark coding compression method
ZHAN Wenfa1,2, TAO Pengcheng1,2    
1. School of Computer and Information, Anqing Normal University, Anqing 246003, China;
2. Key Laboratory of Intelligent Sensing and Computing in Anhui Province, Anqing 246003, China
Abstract: Integrated circuit testing produces huge quantities of test data in expensive tests. This paper describes use of the minimum run-changing point mark coding compression method to compress the original test data to reduce the test costs. The method encodes the test set into several vectors and uses the overlapping relationships between the vector run range in each group to merge the run-length switching points. The run position in all the test vectors in the group can be represented by a vector which simplifies traditional coding compression. The method breaks through the limitation of using the suffix of the code word to express the length of the run, and greatly shortens the code word compared to conventional code compression. The method has simple decompression rules and low hardware overhead. Tests with the ISCAS 89 standard circuit experiment show that this compression scheme is more effective than other types of coding compression schemes.
Key words: test data compression    lossless compression    coding    run    

随着信息时代的高速发展,作为信息载体的集成电路也被大量运用在各行各业。集成电路测试技术可以有效地保障芯片的良品率,因此是工业生产中一项必不可少的步骤。如今芯片的工业制作水平越来越成熟,促使芯片的集成度越来越高,截至2012年,商业处理器晶体管水平已经达到数十亿级别。针对于集成度越高的芯片,所需要的测试数据数量也越多,大量的测试数据是对基于测试设备测试方法的巨大挑战,主要原因有:自动测试设备内存有限,测试数据超过其内存,若裁剪测试数据则会影响压缩率;自动测试设备带宽有限,限制了数据传输速度;自动测试设备管脚有限,管脚少测试效率低,更新自动测试设备成本过高。因此如何解决上述问题成为集成电路的研究热点[1-5]

测试数据压缩(test data compression,TDC)[6-7]可以在不改变芯片内部IP核的前提下有效缓解上述问题,采用无损压缩技术压缩测试数据,再通过片上解压结构还原数据。编码压缩方法[8-9]是TDC常用方法之一,基本思想是将测试数据分为不同模块,再用较短的代码字代替模块,从而达到压缩效果。根据模块的长度和代码字的长度是否可变,通常将编码压缩分为固定到固定、固定到可变、可变到固定、可变到可变4类。可变到可变可以根据模块长度调整代码字长度,适应性更强,压缩效果更好。经典的编码方法有Golomb码[10]、FDR码[11]、EFDR码[12]、交替连续码[13]、VIHC码[14]、9值码[15]、Variable-Tail码[16]、VRL码[17]、PRL码[18]等。

这些编码方法模块和代码字一一对应,所以模块数量和代码字数量相同,没有考虑相邻测试向量模块之间存在的联系。本文提出了一种最小游程切换点标记编码压缩方法,利用不同模块变换点在相邻测试向量相同位置的重叠关系,用一位数据标记该重叠位,达到压缩效果。通过对测试数据实验,表明该方案压缩效果较好。

1 最小游程切换点标记编码压缩方案 1.1 设计思想

游程切换点是指测试数据从0转换为1或者从1转换0的逻辑位。测试数据由确定位0、1和无关位X组成。由于X可以被填充为0或1而不影响测试数据的故障覆盖率,因此游程切换点可能不是一个确定的逻辑位,而是存在一个范围值。例如图 1中的一条测试数据流。

图 1 (网络版彩图)游程切换点范围

如果2个相邻确定位的值不相同,则这2个确定位之间存在一个游程切换点,并且由于这2个确定位相邻,故该切换点位置确定,如图 1中红色粗箭头标记的位置。如果2个确定位值不同,并且中间存在无关位,那么这2个确定位之间的任何位置都可以插入切换点,故该切换点的位置不确定,如图 1中蓝色细箭头标记的位置。由于游程切换点需要对应测试数据的逻辑位,换言之,游程切换点本身需要确定逻辑值,以确定解压缩时下一段游程类型,本文取值规则为取切换点右侧测试数据逻辑位,图 1测试数据流的游程切换点范围为:(0,1],(2,3],(3,4],(4,9]。

最小游程切换点标记编码压缩方法的基本思想是:将测试集按照每k个测试向量划分成若干个组,最后一组不足k个测试向量的用无关位X补充。从第1组测试数据开始编码:首先,找出该组k个测试向量所有的游程切换范围,并用最小游程切换点提取算法提取最小游程切换点,要求每个游程切换范围都至少被1个游程切换点覆盖;其次,为该组测试数据设置1个与测试向量等长的向量标记游程切换点在测试向量中的位置,称其为“位置参考向量”,在首位和最小游程切换点的位置都置为1,其他位置都置为0;最后,分别对该组k个测试向量编码,在第一位和最小游程切换点的位置用0或1表示当前位置的游程种类,用相同的编码方式编码下一组测试数据,直到所有组编码完成。

编码结束后的每组数据由位置参考向量和游程标记位2部分组成。利用游程范围的重叠关系合并切换点,在游程分布状况最优的情况下,每段游程只要“0”或“1”一位进行编码,码字较短,有利于获得较高的压缩率,理论上有更好的压缩效果。在解压方面,FDR码等游程编码需要借助k位计数器先解压编码字的前缀,再解压后缀,解压数据也是分步移入扫描链,这类方法通信协议较复杂,并且解决信号间的同步问题也比较困难。通过本方案压缩后的测试数据,在解压时只需根据读入的位置参考向量是“0”或“1”来区分是否输出当前的游程标记位到扫描链来解压数据,解压规则和通信协议都比较简单。

1.2 最小游程切换点提取算法

最小游程切换点的提取,其实是区间覆盖问题中的区间选点问题的特例,可以将问题简化为:一条数轴上有n个半开半闭区间(aibi],区间内取整数,要求取最少的点,可以使每个区间内都至少有一个点(同一个点可以在不同区间内),区间长度为L(测试集中测试向量的长度)。

对于该问题,可以用贪心算法对其求解。贪心策略为:将所有区间按照区间右边界大小进行递增排序,相同右边界的按区间左边界大小进行递减排序,再逐个将区间满足(每次选择的点为该区间的右边界值)。如果想让选取的点最少,就要让选取的点在后面的区间内发挥作用,如果区间存在点被取到,则称该区间i被满足。证明该策略正确需要考虑2种情况:1)小区间被大区间包含,针对这种情况,如果小区间被满足,大区间必然被满足,用该策略的方法排序,小区间将排在大区间之前,因此优先选择小区间,从而不用考虑大区间。2)区间不存在包含关系,根据贪心策略从左向右排列区间,那么要想前面区间的点满足后面区间,就要从右端开始选点,以求获得更大的覆盖范围。结合以上2点,该贪心策略正确。最小游程切换点提取的具体流程如图 2所示。

图 2 最小游程切换点提取流

步骤1  将所有游程切换范围按右端从小到大排列(b1b2b3,…,bn),如果bi-1=bi,按左端从大到小排列(ai-1>ai),否则左端满足a1a2a3,…,an。将排序好的范围存入集合UU(i)={(a1b1],(a2b2],(a3b3],…,(anbn]}(i∈1,2,…,n),对于集合U任意元素,若zx∈(aibi],则zxN,(x∈1,2,…,bi-ai)。

步骤2  从集合第一个元素U(1)开始,U(1)=(a1b1],选取右端点b1存入集合P(m),P(1)=b1

步骤3  遍历集合U,判断b1是否属于U(i)(i∈1,2,…,n),如果属于,则将U(i)从集合U中移除,遍历结束后,释放移除元素U(i)的地址i(即U(i+1)=U(1),U(i+2)=U(2),…,U(i+n)=U(n)),得到新集合U(此时n表示更新后的集合U的元素个数)。

步骤4  重复步骤2和3,直到集合U为空,集合P(m)则是所提取的最小游程切换点。

为不失一般性,下面用一个具体实例来说明该算法。假设存在4个测试向量的游程切换范围t1:(4,15],(20,23],(23,27];t2:(0,2],(2,8],(15,18],(18,20],(20,21],(23,27],(27,28];t3:(8,10],(11,12],(27,28];t4:(5,8],(9,18],(20,21],(21,22],(27,30]。现在对其提取最小游程切换点,1)按照范围右端递增对范围进行排序,其中(2,8]和(5,8]、(15,18]和(9,18]右端相同,按左端递减排序,因此(5,8]在(2,8]之前,(15,18]在(9,18]之前。排序之后,U(i)={(0,2],(5,8],(2,8],(8,10],(11,12],(4,15],(15,18],(9,18],(18,20],(20,21],(20,21],(21,22],(20,23],(23,27],(23,27],(27,28],(27,28],(27,30]};2)选取U(1)=(0,2]的右端点“2”存入集合P(m);3)遍历集合U,2∈U(1),移除U(1),更新U(i)={(5,8],(2,8],(8,10],(11,12],(4,15],(15,18],(9,18],(18,20],(20,21],(20,21],(21,22],(20,23],(23,27],(23,27],(27,28],(27,28],(27,30]}。重复第2步和第3步,直到集合U为空,最终得到P(m)={2,8,10,12,18,20,21,22,27,28}。

1.3 编码压缩实例

假设按4个测试向量分组,t1t2t3t4为其中一组测试数据的4个测试向量,每个向量长31 bit,用0~30表示测试数据在测试向量中的位置。现在对该组测试数据用本方案压缩,编码压缩过程如图 3所示。

图 3 编码实例

首先提取4个测试向量的游程切换范围:

t1:(4,15],(20,23],(23,27];

t1:(0,2],(2,8],(15,18],(18,20],(20,21],(23,27],(27,28];

t1:(8,10],(11,12],(27,28];

t1:(5,8],(9,18],(20,21],(21,22],(27,30].

根据最小游程算法提取最小游程切换点:2、8、10、12、18、20、21、22、27、28。为该组测试数据设置位置参考向量RR首位和最小游程切换点的位置设置为1,其他位置设置为0,R与测试向量等长。对4个测试向量编码,在首位和最小游程切换点用0和1表示所在游程的种类。压缩后的测试数据由R和游程标记码组成(如图 3虚线框内所示),原先124 bit的TD(原始测试数据大小)被压缩成75 bit的TE(压缩后测试数据大小)。TE=101000001010 1000001011100001100 11110000100 01000101101 00010000001 11000110110。

1.4 压缩效果分析

对于编码压缩算法通常用压缩率或压缩倍数对压缩效果进行评估,压缩率和压缩倍数呈正相关性,其值越高压缩效果越好。

$ \gamma = \frac{{{\rm{原测试数据大小}}}}{{{\rm{压缩后测试数据大小}}}} = \frac{{{T_{\rm{D}}}}}{{{T_{\rm{E}}}}}, $ (1)
$ {\rm{CR}} = 1 - \frac{{{\rm{压缩后测试数据大小}}}}{{{\rm{原测试数据大小}}}} = 1 - \frac{{{T_{\rm{E}}}}}{{{T_{\rm{D}}}}}. $ (2)

其中:CR表示压缩率,γ表示压缩倍数。由上述表达式可得CR=1-1γγ增大,CR也会增大。压缩倍数表达压缩效果更直观,本文选取压缩倍数为分析标准。因为本方案对测试集分组编码,每组的编码方式相同,所以只对一组测试向量分析。假设该组共有n个游程切换范围,将游程切换范围按右端从小到大排列,如果右端相同,按左端从大到小排列。从第一个范围开始,与第一个范围有交集的范围个数为w(1),从下一个未满足的范围开始,与该范围有交集的范围个数为w(2),直到所有范围被满足最后有交集范围个数为w(p)。测试向量长度为L,一组向量个数为k。得到压缩倍数为

$ \begin{array}{*{20}{l}} {{\gamma _{g{\rm{ - MRCP }}}}(k) = \frac{{kL}}{{(1 + n - \sum\limits_1^p w (i))k + L}},}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} (k \in {{\rm{N}}^ + },n,w(i) \in {\rm{N}}).{\rm{ }}} \end{array} $ (3)

其中:g表示当前组号,γg表示第g组的压缩倍数。又有

$ n \ge \sum\limits_1^p w (i),n - \sum\limits_1^p w (i) \in [0,n]. $

$n - \sum\limits_1^p w (i) = n$时,$\sum\limits_1^p w (i) = 0$,故$n - \sum\limits_1^p w (i) \in [0, L - 1]$,所以有

$ {\gamma _{g{\rm{ - MRCP }}}}(k) \in \left[ {\frac{{kL}}{{kL + L}},\frac{{kL}}{{k + L}}} \right]. $

由于测试向量长度L是常数,因此影响压缩倍数极限值的因素是k,而影响压缩倍数的因素是交集个数w(i),γg的上下限都是在$\sum\limits_1^p {w(i)} $最大和最小的情况下得出的,因为$\sum\limits_1^p {w(i)} $的值存在极大随机性,所以只能取$\sum\limits_1^p {w(i)} $的极限值分析γg的上下限。{γg(k)}和{γg(k)}+分别表示γg的下限和上限。

$ {\{ {\gamma _{g{\rm{ - MRCP }}}}(k)\} ^ - } = \frac{{kL}}{{kL + L}} = \frac{1}{{1 + \frac{1}{k}}}, $ (4)
$ \frac{{\partial {{\{ {\gamma _{g{\rm{ - MRCP }}}}\} }^ - }}}{{\partial k}} = \frac{{ - {{\left( {1 + \frac{1}{k}} \right)}^\prime }}}{{{{\left( {1 + \frac{1}{k}} \right)}^2}}} = \frac{1}{{{k^2}{{\left( {1 + \frac{1}{k}} \right)}^2}}} > 0. $ (5)

{γg-MRCP(k)}在区间内单调递增,k取最小值1时,{γg-MRCP(k)}也取得最小值$\frac{1}{2}$,也就是说在最差情况下,压缩后的测试数据大小比压缩前还要多1倍,但此种情况极少出现,并且随着k的增大,{γg-MRCP(k)}也会逐渐增大,表明压缩效果逐渐提升。

$ {\{ {\gamma _{g{\rm{ - MRCP}}}}(k)\} ^ + } = \frac{{kL}}{{k + L}} = \frac{L}{{1 + \frac{L}{k}}}, $ (6)
$ \begin{array}{*{20}{c}} {\frac{{\partial {{\{ {\gamma _{g{\rm{ - MRCP }}}}\} }^ + }}}{{\partial k}} = }\\ {\frac{{{{(k \cdot L)}^\prime } \cdot (k + L) - (k \cdot L) \cdot {{(k + L)}^\prime }}}{{{{(k + L)}^2}}} = }\\ {\frac{{{L^2}}}{{{{(k + L)}^2}}} > 0.} \end{array} $ (7)

{γg-MRCP(k)}+在区间内单调递增,k最大值为原测试向量个数,若要方案有压缩效果,则需要{γg-MRCP(k)}+>1,得到$k > \frac{L}{{L - 1}} \approx 1$。由此可见,在最好情况下,只要k>1便可达到压缩效果,并且随着k增大,{γg-MRCP(k)}+也会逐渐增大,表明压缩效果逐渐提升。

下面对FDR码用同样的分析方法,有

$ {\{ {\gamma _{g{\rm{ - FDR }}}}(k)\} ^ - } = \frac{{kL}}{{2kL}} = \frac{1}{2}. $ (8)

FDR码是基于0游程的编码方法,最差情况是测试向量为连续的1,因此一位数据需要2位编码字,{γg-FDR(k)}的结果与本方案在最差情况下k=1的情况相同,但是{γg-FDR(k)}结果为一个常数,不会随k的增大而增大,令Y(k)={γg-MRCP(k)}-{γg-FDR(k)}图 4Y(k)的函数图像,可以看出, 在k≥1时, 函数值始终大于0,因此在最差情况下本方案的压缩倍数高于FDR码。

图 4 Y-(k)函数图像

然后对最优情况分析,有

$ \begin{array}{*{20}{l}} {{{\{ {\gamma _{g{\rm{ - FDR }}}}(k)\} }^ + } = \frac{{kL}}{{2(\left\lceil {{\rm{lo}}{{\rm{g}}_2}(kL - 1 + 3)} \right\rceil - 1)}} = }\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \frac{{kL}}{{2\left\lceil {{\rm{lo}}{{\rm{g}}_2}(kL + 2)} \right\rceil - 2}}.} \end{array} $ (9)

{γg-FDR(k)}+在区间范围内同样为单调增函数,令Y+(k)={γg-MRCP(k)}+-{γg-FDR(k)}+L=100。图 5Y+(k)的函数图像,可以看出, 在k>0时, 函数值始终小于0,FDR码的压缩倍数在最优情况下高于本方案,但是该结论基于将k个测试向量看做一条数据流并假设只有一段游程的条件下的结果,如果满足该前提条件,那么必然满足本方案的最优情况条件,而满足本方案的最优情况条件却未必满足FDR码最优结果前提条件,所以其最优极限值很难达到。相对来说本方案的最优情况条件较容易满足,对测试集的压缩效果稳定性更高。综上所述,本方案的综合压缩效果要优于FDR码,通过后文的实验结果也验证了该结论。

图 5 Y+(k)函数图像

1.5 编码过程

在一些经典的游程编码过程(如FDR码)中,往往要先对测试集中的测试向量重新排序,并进行差分运算,以达到使游程分布更加均匀的目的,从而达到更好的压缩效果。本方案的编码方法在编码前不需要对测试集进行差分运算,可以保留原测试集中的无关位,使游程切换范围更广泛,游程切换范围存在重叠的可能性更大,使最小游程切换点的选取更加灵活,编码效果更好。本方案具体编码过程如图 6所示。

图 6 编码过程

步骤1  将测试集按每k个测试向量划分成若干个组,如果最后一组不足k个测试向量,用全是无关位的向量补充。

步骤2   提取k个测试向量的游程切换点范围,调用最小游程切换点提取算法提取最小游程切换点位置。

步骤3  添加位置参考向量RR长度为L,第一位和最小游程切换点位置编码1,其余位置编码0。

步骤4  编码k个测试向量,判断k个测试向量在第一位和游程标记位置的游程种类,属于1游程,编码为1,属于0游程,编码为0。

步骤5  读取下一组测试数据,转到步骤2。

步骤6  若步骤5读取数据为空,编码结束。

2 解码器设计

本文方案的解码器设计主要包括输入控制和解码2个部分,图 7为该方案的解压结构框图。输出控制部分主要工作是将R和游程标记位分开,并且实现向量R的循环复用。该结构包括2个数据存储器RAM1和RAM2、一个L计数器、一个k计数器。RAM1用于存储位置参考向量R,其容量大小为LL为位置参考向量R的长度,同时也是原测试集测试向量的长度,L计数器用来记录向量R的长度。RAM2用于存储游程标记码,其容量大小为mmaxmmax为压缩后测试向量中游程标记位最多一组的游程标记位个数。“testdata”是数据输入,“en0”是使能信号,当“en0”为高电平时,TE中的数据从“testdata”输入。L计数器控制读取向量R,信号“dec0”控制L计数器减1。向量R通过“din”存入RAM1中,从“rout”读出,“addr0”作为地址信号自动加1,当达到RAM1的最大容量时自动复位到初始位置,从而达到向量R的循环复用。k为测试集分组时每组向量的个数,k计数器用来控制向量R的循环输入次数,dec1控制计数器减1,当计数器为空时,停止循环,复位信号“rs”为高电平。

图 7 解压结构图

解码部分包括一个有限状态机FSM和一个M位计数器。“en1”是使能信号,高电平时向量R从“bit_in”读入FSM,低电平是暂停读入。M位计数器用来记录需要从RAM2中输出数据的位置,M的大小是由mmax决定的,$M\left\lceil {{\rm{lb}}\;{m_{\max }}} \right\rceil $,“inc”控制计数器加1,在通过地址信号addr1从RAM2中选定数据输出到被测电路CUT中。该解码器的具体工作步骤如下。

步骤1   Inputctl将“en0”置为1,开始从“testdata”读入一条数据,“en1”为1,L计数器控制数据前L位通过“din”存入RAM1并通过“bit_in”传入FSM,此时RAM2中暂无数据,将其余数据通过“runvin”存入RAM2。

步骤2   “en1”为高电平,FSM从“bit_in”接收数据并读取,当读到数据为“1”时,“inc”为高电平,M位计数器加1,通过“addr1”从RAM2中选择一位数据输出到CUT,当读到数据为“0”时,“inc”为低电平,M位计数器值保持不变,通过“addr1”从RAM2中选择一位数据输出到CUT。

步骤3  每当一个测试向量解码完成后,“dec1”为高电平,k计数器减1。如果该计数器不等于0,则“circle”为高电平,在此从RAM1中读入数据到FSM,转到步骤2进行解码;如果该计数器为空,则“rs”变为高电平,“en0”为高电平,转到步骤1读取下一条待解码数据。

3 实验结果与分析

为了证明本方案有效,用ISCAS 89标准电路作为测试集进行实验,并将实验结果与Golomb码、FDR码和EFDR码3种游程编码方法比较。

本方案在编码之前需要对测试集分组处理,在压缩效果分析中表明,游程切换范围重叠数量和分组向量个数k共同决定,并且k=1时没有压缩效果,所以选取k>1,用不同的k对测试向量进行实验,取最优的测试结果。该过程属于预处理,独立于ATE之外,因而不会影响测试时间。图 8为不同k值对应的不同电路的压缩结果。

图 8 (网络版彩图)k值对压缩率的影响

图 8可以看出,当压缩率达到最大时,k值都集中在4~20之间;当k>20时,压缩率随着k值增加,有明显的下降趋势。表 1给出了不同电路在最优k值下的压缩率。

表 1 电路在最优k值下的压缩率
电路名称 TD k TE 压缩率/%
s5378f 23 754 8 10 484 55.86
s9234f 39 273 8 17 108 56.44
s13207f 165 200 17 27 616 83.28
s15850f 76 986 14 23 279 69.76
s35932f 28 208 16 6 323 77.58
s38417f 164 736 11 59 900 63.64
s38584f 199 104 12 70 332 64.67

表 2中,将本方案与Golomb码、FDR码和EFDR码3种游程编码方法的压缩率比较。由表 2可以看出,除在s35932f电路中,EFDR码压缩率要高于本方案,在其他电路中,本方案的压缩率均高于其他3类方案,并且平均压缩率也高于其他3类方案,由此对比可以看出,本方案有效,并且具有良好的压缩效果。

表 2 本方案与其他编码压缩方案压缩率比较 
%
电路
名称
Golomb码
压缩率
FDR码
压缩率
EFDR码
压缩率
本方案
压缩率
s5378f 37.11 47.98 53.67 55.86
s9234f 45.25 43.61 48.66 56.44
s13207f 79.74 81.3 82.49 83.28
s15850f 62.82 66.21 68.66 69.76
s35932f 80.80 77.58
s38417f 28.37 43.37 62.02 63.64
s38584f 57.17 60.93 64.28 64.67
平均
压缩率
51.74 57.23 65.80 67.32

为了进一步说明本方案的压缩效果,将实验结果与国内其他几种编码压缩方法比较,其他方案均采用自己最优的无关位填充策略填充,并且对混合游程码作差分处理使测试集拥有更长的游程保证其拥有最优的压缩效果,因为本方案的编码方式不同,故不需要作适应性填充,并且未对测试集作差分处理。详细比较结果见表 3

表 3 本方案与国内其他编码压缩方案压缩率比较 
%
电路
名称
混合游
程码[19]
压缩率
对称游
程码[20]
压缩率
双游程
交替码[21]
压缩率
本方案
压缩率
s5378f 56.44 51.80 49.74 55.86
s9234f 60.85 50.94 47.69 56.44
s13207f 84.81 83.77 82.95 83.28
s15850f 70.94 69.98 68.04 69.76
s35932f 82.05 77.58
s38417f 63.47 63.30 62.48 63.64
s38584f 61.73 66.26 63.94 64.67
平均
压缩率
66.37 64.34 65.27 67.32

表 3中数据可以看出,在大部分电路中,本方案的压缩效率较其他3类方案均有提升,并且汇总各方案的平均压缩率可以看出,本方案的压缩率均高于其他3类方案,比对称游程码高了2.98%,比混合游程码高了0.95%。这些数据再次充分说明了本方案压缩效果的有效性。

4 结论

针对于测试数据过多带来的测试成本过高的问题,本文提出了一种最小游程切换点标记编码方法压缩数据。通过相邻向量游程范围的重叠关系来缩减需要标记的游程,使得组内所有游程的位置可以用一个向量表示,用1位数据标识游程种类,极大地缩短了编码字。解压规则极为简单,不像传统游程编码一样先解压前缀再解压后缀,只需循环输出标记位,解压电路大小合理,需要额外引入的硬件开销较小。实验结果表明:本方案有良好的压缩效果,并且压缩效果稳定。

参考文献
[1]
陈田, 易鑫, 王伟, 等. 一种低功耗双重测试数据压缩方案[J]. 电子学报, 2017, 45(6): 1382-1388.
CHEN T, YI X, WANG W, et al. Low power multistage test data compression scheme[J]. Acta Electronica Sinica, 2017, 45(6): 1382-1388. DOI:10.3969/j.issn.0372-2112.2017.06.015 (in Chinese)
[2]
XIANG D, CHAKRABARTY K, FUJIWARA H. Multicast-based testing and thermal-aware test scheduling for 3D ICs with a stacked network-on-chip[J]. IEEE Transactions on Computers, 2016, 65(9): 2767-2779. DOI:10.1109/TC.2015.2493548
[3]
LIANG H G, FANG X S, YI M X, et al. A novel BIST scheme for circuit aging measurement of aerospace chips[J]. Chinese Journal of Aeronautics, 2018, 31(7): 1594-1601. DOI:10.1016/j.cja.2018.04.013
[4]
YU T T, CUI A J, LI M Y, et al. A new decompressor with ordered parallel scan design for reduction of test data and test time[C]//2015 IEEE International Symposium on Circuits and Systems. Lisbon, Portugal: IEEE, 2015.
[5]
袁海英, 陈光, 谢永乐. 故障诊断中基于神经网络的特征提取方法研究[J]. 仪器仪表学报, 2007, 28(1): 90-94.
YUAN H Y, CHEN G J, XIE Y L. Feature extraction method in fault diagnosis based on neural network[J]. Chinese Journal of Scientific Instrument, 2007, 28(1): 90-94. DOI:10.3321/j.issn:0254-3087.2007.01.018 (in Chinese)
[6]
詹文法, 吴琼, 程一飞, 等. 嵌入广义折叠技术的集成电路测试数据压缩方案[J]. 计算机辅助设计与图形学学报, 2017, 29(8): 1542-1548.
ZHAN W F, WU Q, CHENG Y F, et al. Integrated circuit test data compression scheme built-in generalized folding technology[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(8): 1542-1548. DOI:10.3969/j.issn.1003-9775.2017.08.017 (in Chinese)
[7]
李光宇, 梁华国, 李扬, 等. 基于向量优化重组的LFSR重新播种方法[J]. 清华大学学报(自然科学版), 2011, 51(S1): 1455-1459.
LI G Y, LIANG H G, LI Y, et al. LFSR reseeding based on dividing and recombining of test cubes[J]. Journal of Tsinghua University (Science and Technology), 2011, 51(S1): 1455-1459. (in Chinese)
[8]
VOHRA H, SINGH A. Test data compression using hierarchical block merging technique[J]. Iet Computers & Digital Techniques, 2018, 12(4): 176-185.
[9]
RADHIKA K, GEETHA D M. Augmented recurrence hopping based run-length coding for test data compression applications[J]. Wireless Personal Communications, 2018, 102(4): 3361-3374. DOI:10.1007/s11277-018-5372-7
[10]
CHANDRA A, CHAKRABARTY K. System-on-a-chip test-data compression and decompression architectures based on Golomb codes[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 20(3): 355-368.
[11]
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 on Computers, 2003, 52(8): 1076-1088. DOI:10.1109/TC.2003.1223641
[12]
邝继顺, 周颖波, 蔡烁. 一种用于测试数据压缩的自适应EFDR编码方法[J]. 电子与信息学报, 2015, 37(10): 2529-2535.
KUANG J S, ZHOU Y B, CAI S. Adaptive EFDR coding method for test data compression[J]. Journal of Electronics & Information Technology, 2015, 37(10): 2529-2535. (in Chinese)
[13]
梁华国, 蒋翠云. 基于交替与连续长度码的有效测试数据压缩和解压[J]. 计算机学报, 2004, 27(4): 548-554.
LIANG H G, JIANG C Y. Efficient test data compression and decompression based on alternation and run length codes[J]. Chinese Journal of Computers, 2004, 27(4): 548-554. DOI:10.3321/j.issn:0254-4164.2004.04.015 (in Chinese)
[14]
GONCIARI P T, AL-HASHIMI B M, NICOLICI N. Variable-length input Huffman coding for system-on-a-chip test[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 22(6): 783-796. DOI:10.1109/TCAD.2003.811451
[15]
TEHRANIPOOR M, NOURANI M, CHAKRABARTY K. Nine-coded compression technique for testing embedded cores in SoCs[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2005, 13(6): 719-731. DOI:10.1109/TVLSI.2005.844311
[16]
韩银和, 李晓维, 徐勇军, 等. 应用Variable-Tail编码压缩的测试资源划分方法[J]. 电子学报, 2004, 32(8): 1346-1350.
HAN Y H, LI X W, XU Y J, et al. Test resource partitioning using variable-tail code[J]. Acta Electronica Sinica, 2004, 32(8): 1346-1350. DOI:10.3321/j.issn:0372-2112.2004.08.028 (in Chinese)
[17]
彭喜元, 俞洋. 基于变游程编码的测试数据压缩算法[J]. 电子学报, 2007, 35(2): 197-201.
PENG X Y, YU Y. A test set compression algorithm based on variable-run-length code[J]. Acta Electronica Sinica, 2007, 35(2): 197-201. DOI:10.3321/j.issn:0372-2112.2007.02.002 (in Chinese)
[18]
RUAN X Y, KATTI R. An efficient data-independent technique for compressing test vectors in systems-on-a-chip[C]//IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures. Karlsruhe, Germany: IEEE, 2006.
[19]
方建平, 郝跃, 刘红侠, 等. 应用混合游程编码的SOC测试数据压缩方法[J]. 电子学报, 2005, 33(11): 1973-1977.
FANG J P, HAO Y, LIU H X, et al. A hybrid run-length coding for SOC test data compression[J]. Acta Electronica Sinica, 2005, 33(11): 1973-1977. DOI:10.3321/j.issn:0372-2112.2005.11.013 (in Chinese)
[20]
梁华国, 蒋翠云, 罗强. 应用对称编码的测试数据压缩解压方法[J]. 计算机研究与发展, 2011, 48(12): 2391-2399.
LIANG H G, JIANG C Y, LUO Q. Test data compression and decompression using symmetry-variable codes[J]. Journal of Computer Research and Development, 2011, 48(12): 2391-2399. (in Chinese)
[21]
程一飞, 詹文法. 一种双游程交替编码的测试数据压缩方法[J]. 计算机科学, 2014, 41(11): 22-24, 55.
CHENG Y F, ZHAN W F. Test data compression method of dual run length alternating coding[J]. Computer Science, 2014, 41(11): 22-24, 55. DOI:10.11896/j.issn.1002-137X.2014.11.005 (in Chinese)