随着信息时代的高速发展，作为信息载体的集成电路也被大量运用在各行各业。集成电路测试技术可以有效地保障芯片的良品率，因此是工业生产中一项必不可少的步骤。如今芯片的工业制作水平越来越成熟，促使芯片的集成度越来越高，截至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中的一条测试数据流。

如果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个半开半闭区间(a_i，b_i]，区间内取整数，要求取最少的点，可以使每个区间内都至少有一个点(同一个点可以在不同区间内)，区间长度为L(测试集中测试向量的长度)。

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

步骤1  将所有游程切换范围按右端从小到大排列(b₁≤b₂≤b₃，…，b_n)，如果b_i-1=b_i，按左端从大到小排列(a_i-1>a_i)，否则左端满足a₁≤a₂≤a₃，…，a_n。将排序好的范围存入集合U，U(i)={(a₁，b₁]，(a₂，b₂]，(a₃，b₃]，…，(a_n，b_n]}(i∈1，2，…，n)，对于集合U任意元素，若z_x∈(a_i，b_i]，则z_x∈N，(x∈1，2，…，b_i-a_i)。

步骤2  从集合第一个元素U(1)开始，U(1)=(a₁，b₁]，选取右端点b₁存入集合P(m)，P(1)=b₁。

步骤3  遍历集合U，判断b₁是否属于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个测试向量的游程切换范围t₁：(4，15]，(20，23]，(23，27]；t₂：(0，2]，(2，8]，(15，18]，(18，20]，(20，21]，(23，27]，(27，28]；t₃：(8，10]，(11，12]，(27，28]；t₄：(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个测试向量分组，t₁、t₂、t₃、t₄为其中一组测试数据的4个测试向量，每个向量长31 bit，用0~30表示测试数据在测试向量中的位置。现在对该组测试数据用本方案压缩，编码压缩过程如图 3所示。

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

t₁：(4，15]，(20，23]，(23，27];

t₁：(0，2]，(2，8]，(15，18]，(18，20]，(20，21]，(23，27]，(27，28];

t₁：(8，10]，(11，12]，(27，28];

t₁：(5，8]，(9，18]，(20，21]，(21，22]，(27，30].

根据最小游程算法提取最小游程切换点：2、8、10、12、18、20、21、22、27、28。为该组测试数据设置位置参考向量R，R首位和最小游程切换点的位置设置为1，其他位置设置为0，R与测试向量等长。对4个测试向量编码，在首位和最小游程切换点用0和1表示所在游程的种类。压缩后的测试数据由R和游程标记码组成(如图 3虚线框内所示)，原先124 bit的T_D(原始测试数据大小)被压缩成75 bit的T_E(压缩后测试数据大小)。T_E=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)}^－。图 4为Y^－(k)的函数图像，可以看出, 在k≥1时, 函数值始终大于0，因此在最差情况下本方案的压缩倍数高于FDR码。

然后对最优情况分析，有

$ \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。图 5为Y⁺(k)的函数图像，可以看出, 在k>0时, 函数值始终小于0，FDR码的压缩倍数在最优情况下高于本方案，但是该结论基于将k个测试向量看做一条数据流并假设只有一段游程的条件下的结果，如果满足该前提条件，那么必然满足本方案的最优情况条件，而满足本方案的最优情况条件却未必满足FDR码最优结果前提条件，所以其最优极限值很难达到。相对来说本方案的最优情况条件较容易满足，对测试集的压缩效果稳定性更高。综上所述，本方案的综合压缩效果要优于FDR码，通过后文的实验结果也验证了该结论。

1.5 编码过程

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

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

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

步骤3  添加位置参考向量R，R长度为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，其容量大小为L，L为位置参考向量R的长度，同时也是原测试集测试向量的长度，L计数器用来记录向量R的长度。RAM2用于存储游程标记码，其容量大小为m_max，m_max为压缩后测试向量中游程标记位最多一组的游程标记位个数。“testdata”是数据输入，“en0”是使能信号，当“en0”为高电平时，TE中的数据从“testdata”输入。L计数器控制读取向量R，信号“dec0”控制L计数器减1。向量R通过“din”存入RAM1中，从“rout”读出，“addr0”作为地址信号自动加1，当达到RAM1的最大容量时自动复位到初始位置，从而达到向量R的循环复用。k为测试集分组时每组向量的个数，k计数器用来控制向量R的循环输入次数，dec1控制计数器减1，当计数器为空时，停止循环，复位信号“rs”为高电平。

解码部分包括一个有限状态机FSM和一个M位计数器。“en1”是使能信号，高电平时向量R从“bit_in”读入FSM，低电平是暂停读入。M位计数器用来记录需要从RAM2中输出数据的位置，M的大小是由m_max决定的，$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值都集中在4~20之间；当k>20时，压缩率随着k值增加，有明显的下降趋势。表 1给出了不同电路在最优k值下的压缩率。

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

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

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

4 结论

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