一种基于测试向量相容的测试向量编码压缩方法

摘要

本发明公开了一种基于向量相容的测试向量编码压缩方法。它包括测试向量的压缩和编码后的解压缩两部分，首先确定测试向量的编码，从测试向量集中取出向量t

说明书

技术领域

本发明涉及集成电路测试技术，尤其涉及一种基于测试向量相容的测试向量编码压缩方法。

背景技术

随着芯片制造技术的进步以及新的设计方法的产生，特别是向SOC设计方法的转变，大量的IP(Intellectual Property)核组合在一起形成片上系统(SOC，System-On-Chip)。导致芯片的复杂度直线上升，每个IP核的测试数据一般都十分庞大(为了达到很高的错误覆盖率)，测试时间变得冗长、测试数据量变得异常庞大，这就使得测试单个SOC所用的测试向量超出了测试设备性能允许的范围，测试成本急剧上升。测试成本已经成为芯片成本的主要组成部分，如何减少测试成本进而减少芯片成本成为研究人员日益关注的问题。BIST(Built-In-Self-Test)测试方法是能解决上述问题的方法之一，但具有芯片面积开销较大和难测故障等一些缺点，并且现有大量IP核并不具有BIST结构。通过测试数据的压缩/解压缩的方法可以解决测试设备性能不足的问题以及缩短测试时间。数据压缩主要包含两类：基于线性反馈移位寄存器LFSR(LinearFeedback Shift Register)的重播种技术和基于编码的技术。LFSR在压缩存在大量无关位的测试集时有很大的优势，不适合确定位个数过多的情况。基于编码的技术通过对测试集定长或者变长的序列进行编码，可以有效减少测试数据量。在测试集中有大量的无关位“x”存在，可以将“x”设为“0”或“1”；测试集中相邻的向量具有很好的相关性，它们之间只有很少的位数值是不同的。利用这个结果可以得到新的差分测试集，该集合具有更好的“0”的游程，编码效率更高；也可以合并相邻的向量，减少向量个数，对合并后的向量压缩，也能很大的提高压缩率。把压缩后的数据放入ATE(Automatic Test Equipment)内存中，由芯片的解码模块进行解码，还原测试向量，减少了测试机与被测芯片的带宽和测试时间。

发明内容

本发明的目的是针对当前只对单个向量进行编码而没有结合向量相容性的不足，提出一种基于向量相容的测试向量编码压缩方法。

基于向量相容的测试向量编码压缩方法包括测试向量的压缩和编码后的解压缩两部分，

测试向量的压缩包括如下步骤：

1)确定测试向量的编码；

2)由被测电路得到第一测试向量集R，选取第一测试向量集R中任一个第一向量t₁，将第一向量t₁从第一测试向量集R中移出，放入测试向量组S中，测试向量组S内的向量个数m为1，设第二测试向量集H，第二测试向量集H与第一测试向量集R相同；

3)从第二测试集H中找出与第一向量t₁相容性最大的第二向量t₂，并将第二向量t₂从第二测试集H中移出；

4)若n₂大于n_max，并且第二测试集H不是空集，则返回步骤3)，若第二测试集H为空集，则到步骤7)完成分组，若n₂小于n_max，则到步骤5)，其中，n_max为测试向量之间不相容位的最大个数，n_max的值可自定义，n₂为第一向量t₁与第二向量t₂不相容位的个数；

5)将第二向量t₂移入测试向量组S中，向量个数m的值增加1，求出第一向量t₁与第二向量t₂相容后的第四向量t₄；

6)对测试向量组S编码，计算第一测试向量组S的压缩率λ和第二向量t₂的压缩率λ_comp，判断第二向量t₂是否要从测试向量组S移出，若第二测试向量集H为空集，则到步骤7)，若第二测试向量集H不为空集，则到步骤3)；

7)完成对测试向量组S的分组，对测试向量组S编码，得到表示测试相量组S内向量个数m的编码M、表示不相容位个数n的编码N以及表示不相容位上值信息的编码Q，由第一向量t₁得到第六向量t₆，第六向量t₆的编码为T6_code，从第一测试向量集R中移出测试向量组S内的向量；

8)若第一测试向量集R为空集，则分组结束，若第一测试向量集R不为空集，则回到步骤2)开始下一测试向量组；

编码后的解压缩包括如下步骤：

9)将表示测试向量组S内向量个数m的编码M、不相容位个数n的编码N和不相容位上值的信息的Q输入到被测电路保存，然后输入第六向量t₆的编码T6_code到被测电路；

10)对第六向量t₆的编码T6_code进行解码，当遇到码字“00”时，将“00”之前的码字解码后的最后一位用步骤9)保存过的不相容位上的值替换，还原一个被压缩的向量，编码M的值减1；

11)若编码M的值不为0，则回到步骤10)继续对第一向量t₁解码，若编码M的值为0，则对测试向量组S解码完成。

所述步骤1)包括：

a)码字由前缀和后缀组成，将码字分组，设编码组为A_k，其中k为组号，码字的前缀和后缀的位数均为k；

b)码字前缀最后一位为“0”，其余位为“1”。码字后缀是由2^k个01组合组成，顺序按大小排列；

c)第一编码组A₁只有只有一个码字“01”用于游程“0”的编码，码字“00”用于标记不相容位的位置；

d)对于长度为l的“0”的游程，落在哪一个编码组是有如下公式决定的：

e)测试集中“0”的游程最长的值加1的编码的前缀作为测试向量组与测试向量组的分割码Sep_code。

所述步骤3)包括：

f)选取第二测试向量集H中任一个第二向量t₂，设定t₁(i)和t₂(i)有四种可能的取值：“0”、“1”、“x”、“c”，其中i为第一向量t₁和第二向量t₂内第i个元素的位置，值“c”所在的位为不相容位，函数Tor(t₁(i)，t₂(i))为t₁(i)和t₂(i)的相容结果，当函数Tor(t₁(i)，t₂(i))值为“1”时，t₁(i)和t₂(i)不相容，当函数Tor(t₁(i)，t₂(i))值为“0”时，t₁(i)和t₂(i)相容，

g)选取第二测试向量集H中任一个第三向量t₃，设定t₃(j)有四种可能的取值：“0”、“1”、“x”、“c”，其中j为第三向量t₃内第j个元素的位置，函数Tor(t₁(j)，t₃(j))为t₁(j)和t₃(j)的相容结果，当函数Tor(t₁(j)，t₃(j))值为“1”时，t₁(j)和t₃(j)不相容，当函数Tor(t₁(j)，t₃(j))值为“0”时，t₁(j)和t₃(j)相容，

h)比较n₂与n₃，若n₂大于n₃，则n₂取n₃的值，第二向量t₂取第三向量t₃的值，其中n₂为第一向量t₁与第二向量t₂不相容位的个数，n₃为第一向量与第三向量不相容位的个数，L为第一向量t₁的长度，若未遍历第二测试向量集H，则到步骤g)，若遍历第二测试集H，将第二向量从第二测试向量集H中移出，然后到步骤4)，

$n_2=\underset{i=1}{\overset{L}{\Sigma }}\mathrm{Tor}(t_1\left(i\right),t_2\left(i\right))$

$n_3=\underset{j=1}{\overset{L}{\Sigma }}\mathrm{Tor}(t_1\left(j\right),t_3\left(j\right))$

$n_2=\left(\begin{array}{cc}{n}_3& n_2>n_3\\ n_2& n_2<=n_3\end{array}\right).$

所述步骤5)包括：

i)将第二向量t₂移入测试向量组S中，m增加1，t₁(k)、t₂(k)和t₄(k)分别为第一向量t₁、第二向量t₂和第四向量t₄第k个位置的元素，t₄(k)的值由以下公式计算，

所述步骤6)包括：

j)由第四向量t₄得到第五向量t₅，t₄(h)和t₅(h)分别为第四向量t₄和第五向量t₅第h个位置的元素；

k)对第五向量t₅进行编码，在编码解码后包含第四向量t₄中“c”的位置的码字之前插入标记码“00”，得到t₅的编码T5_code，编码长度为l_code；

1)测试向量组S中向量个数m和不相容位个数n₁由M和N位二进制信息表示，测试向量组S中不相容位上的值由Q位二进制表示，其中n₁的值为第四向量t₄内值“c”出现的次数，也即第一向量t₁与第二向量t₂不相容位的个数；

Q＝m×n₁

m)计算测试向量组S的压缩率λ和第二向量t₂的压缩率λ_comp，将第二向量t₂中的值“x”变为“0”后进行编码，编码后的长度为l₂，

$\lambda =\frac{L*m-M-N-m*n_1-l_{\mathrm{code}}}{L*m}$

${\lambda }_{\mathrm{comp}}=\frac{L-l_2}{L};$

n)若测试向量组S的压缩率λ小于第二向量t₂的压缩率λ_comp，则将第二向量t₂从测试向量组S中移出，m减1，若λ大于λ_comp，则第二向量t₂留在测试向量组S中，第一向量t₁取第四向量t₄的值；

o)若第二测试向量集H为空集，则到步骤7)，若第二测试向量集H不为空集，则到步骤3)；

所述步骤7)包括：

p)由第一向量t₁得到第六向量t₆，t₁(d)和t₆(d)分别为第一向量t₁和第六向量t₆第d个位置的元素；

q)对第六向量t₆进行编码，在编码解码后包含第一向量t1中“c”的位置的码字之前插入标记码“00”，得到t₆的编码T6_code；

r)测试向量组S中向量个数m和不相容个数n由M和N位二进制信息表示，测试向量组S中不相容位上的值由Q位二进制表示，其中n的值为第一向量t₁内值“c”出现的次数即不相容位的个数；

Q＝m×n

s)在T6_code之前插入(M+N+Q)位的组头信息，并在T6_code的末尾插入组分割码Sep_code，完成对测试向量组S的编码。

本发明根据相容性最大的关系把测试向量集分组，并将测试向量组内的向量合并为一个第一向量t₁，对第一向量t₁进行编码，不相容的位置用标记码标出，极大的减少了用地址信息标记所需的位数，在编码前插入组头信息，形成对测试向量组的编码。解码时，将测试向量组的编码移入被测电路保存，保存在被测电路中的编码可以重复利用，极大地降低了测试机与被测电路的带宽。

附图说明

图1本发明的测试向量压缩流程图；

图2本发明的寻找与第一向量t₁相容性最大的第二向量t₂流程图；

图3本发明的计算测试向量组S和第二向量t₂的压缩率流程图；

图4本发明的对完成分组的测试向量组S编码流程图；

图5本发明的编码结构图；

图6本发明的解压缩测试向量组流程图。

具体实施方式

基于向量相容的测试向量编码压缩方法包括测试向量的压缩和编码后的解压缩两部分，

如图1所示，测试向量的压缩包括如下步骤：

1)确定测试向量的编码；

2)由被测电路得到第一测试向量集R，选取第一测试向量集R中任一个第一向量t₁，将第一向量t₁从第一测试向量集R中移出，放入测试向量组S中，测试向量组S内的向量个数m为1，设第二测试向量集H，第二测试向量集H与第一测试向量集R相同；

3)从第二测试集H中找出与第一向量t₁相容性最大的第二向量t₂，并将第二向量t₂从第二测试集H中移出；

4)若n₂大于n_max，并且第二测试集H不是空集，则返回步骤3)，若第二测试集H为空集，则到步骤7)完成分组，若n₂小于n_max，则到步骤5)，其中，n_max为测试向量之间不相容位的最大个数，n_max的值可自定义，n₂为第一向量t₁与第二向量t₂不相容位的个数；

5)将第二向量t₂移入测试向量组S中，向量个数m的值增加1，求出第一向量t₁与第二向量t₂相容后的第四向量t₄；

6)对测试向量组S编码，计算第一测试向量组S的压缩率λ和第二向量t₂的压缩率λ_comp，判断第二向量t₂是否要从测试向量组S移出，若第二测试向量集H为空集，则到步骤7)，若第二测试向量集H不为空集，则到步骤3)；

7)完成对测试向量组S的分组，对测试向量组S编码，得到表示测试相量组S内向量个数m的编码M、表示不相容位个数n的编码N以及表示不相容位上值信息的编码Q，由第一向量t₁得到第六向量t₆，第六向量t₆的编码为T6_code，从第一测试向量集R中移出测试向量组S内的向量；

8)若第一测试向量集R为空集，则分组结束，若第一测试向量集R不为空集，则回到步骤2)开始下一测试向量组；

如图6所示，编码后的解压缩包括如下步骤：

9)将表示测试向量组S内向量个数m的编码M、不相容位个数n的编码N和不相容位上值的信息的Q输入到被测电路保存，然后输入第六向量t₆的编码T6_code到被测电路；

10)对第六向量t₆的编码T6_code进行解码，当遇到码字“00”时，将“00”之前的码字解码后的最后一位用步骤9)保存过的不相容位上的值替换，还原一个被压缩的向量，编码M的值减1；

11)若编码M的值不为0，则回到步骤10)继续对第一向量t₁解码，若编码M的值为0，则对测试向量组S解码完成。

所述步骤1)包括：

a)码字由前缀和后缀组成，将码字分组，设编码组为A_k，其中k为组号，码字的前缀和后缀的位数均为k；

b)码字前缀最后一位为“0”，其余位为“1”。码字后缀是由2^k个01组合组成，顺序按大小排列；

c)第一编码组A₁只有只有一个码字“01”用于游程“0”的编码，码字“00”用于标记不相容位的位置；

d)对于长度为l的“0”的游程，落在哪一个编码组是有如下公式决定的，如表1所示；

e)测试集中“0”的游程最长的值加1的编码的前缀作为测试向量组与测试向量组的分割码Sep_code。

表1本发明提出的编码表

如图2所示，所述步骤3)包括：

f)选取第二测试向量集H中任一个第二向量t₂，设定t₁(i)和t₂(i)有四种可能的取值：“0”、“1”、“x”、“c”，其中i为第一向量t₁和第二向量t₂内第i个元素的位置，值“c”所在的位为不相容位，函数Tor(t₁(i)，t₂(i))为t₁(i)和t₂(i)的相容结果，当函数Tor(t₁(i)，t₂(i))值为“1”时，t₁(i)和t₂(i)不相容，当函数Tor(t₁(i)，t₂(i))值为“0”时，t₁(i)和t₂(i)相容，

g)选取第二测试向量集H中任一个第三向量t₃，设定t₃(j)有四种可能的取值：“0”、“1”、“x”、“c”，其中j为第三向量t₃内第j个元素的位置，函数Tor(t₁(j)，t₃(j))为t₁(j)和t₃(j)的相容结果，当函数Tor(t₁(j)，t₃(j))值为“1”时，t₁(j)和t₃(j)不相容，当函数Tor(t₁(j)，t₃(j))值为“0”时，t₁(j)和t₃(j)相容，

h)比较n₂与n₃，若n₂大于n₃，则n₂取n₃的值，第二向量t₂取第三向量t₃的值，其中n₂为第一向量t₁与第二向量t₂不相容位的个数，n₃为第一向量与第三向量不相容位的个数，L为第一向量t₁的长度，若未遍历第二测试向量集H，则到步骤g)，若遍历第二测试集H，将第二向量从第二测试向量集H中移出，然后到步骤4)，

$n_2=\underset{i=1}{\overset{L}{\Sigma }}\mathrm{Tor}(t_1\left(i\right),t_2\left(i\right))$

$n_3=\underset{j=1}{\overset{L}{\Sigma }}\mathrm{Tor}(t_1\left(j\right),t_3\left(j\right))$

$n_2=\left(\begin{array}{cc}{n}_3& n_2>n_3\\ n_2& n_2<=n_3\end{array}\right).$

所述步骤5)包括：

i)将第二向量t₂移入测试向量组S中，m增加1，t₁(k)、t₂(k)和t₄(k)分别为第一向量t₁、第二向量t₂和第四向量t₄第k个位置的元素，t₄(k)的值由以下公式计算，如表2所示的相容关系表，

表2相容关系表

  0  1  X  C  0  0  C  0  C  1  C  1  1  C  X  0  1  X  C  C  C  C  C  C

如图3所示，所述步骤6)包括：

j)由第四向量t₄得到第五向量t₅，t₄(h)和t₅(h)分别为第四向量t₄和第五向量t₅第h个位置的元素；

k)对第五向量t₅进行编码，在编码解码后包含第四向量t₄中“c”的位置的码字之前插入标记码“00”，得到t₅的编码T5_code，编码长度为l_code；

1)测试向量组S中向量个数m和不相容个数n₁由M和N位二进制信息表示，测试向量组S中不相容位上的值由Q位二进制表示，其中n₁的值为第四向量t₄内值“c”出现的次数，也即第一向量t₁与第二向量t₂不相容位的个数；

Q＝m×n₁

m)计算测试向量组S的压缩率λ和第二向量t₂的压缩率λ_comp，将第二向量t₂中的值“x”变为“0”后进行编码，编码后的长度为l₂；

$\lambda =\frac{L*m-M-N-m*n_1-l_{\mathrm{code}}}{L*m}$

${\lambda }_{\mathrm{comp}}=\frac{L-l_2}{L};$

n)若测试向量组S的压缩率λ小于第二向量t₂的压缩率λ_comp，则将第二向量t₂从测试向量组S中移出，m减1，若λ大于λ_comp，则第二向量t₂留在测试向量组S中，第一向量t₁取第四向量t₄的值；

o)若第二测试向量集H为空集，则到步骤7)，若第二测试向量集H不为空集，则到步骤3)；

所述步骤7)包括：

p)由第一向量t₁得到第六向量t₆，t₁(d)和t₆(d)分别为第一向量t₁和第六向量t₆第d个位置的元素；

q)对第六向量t₆进行编码，在编码解码后包含第一向量t1中“c”的位置的码字之前插入标记码“00”，得到t₆的编码T6_code；

r)测试向量组S中向量个数m和不相容个数n由M和N位二进制信息表示，测试向量组S中不相容位上的值由Q位二进制表示，其中n的值为第一向量t₁内值“c”出现的次数即不相容位的个数；

Q＝m×n

s)在T6_code之前插入(M+N+Q)位的组头信息，并在T6_code的末尾插入组分割码Sep_code，完成对测试向量组S的编码，如图5所示。

实施例

设测试集R中有四个向量：T1、T2、T3、T4。向量长度L均为24位。选取T1作为分组S的第一个向量，从R中移出，并使t₁＝T1。R中向量为T2、T3、T4。集合H＝R。n_max＝3。组分割码Sep_code取11110

T1：1xxx1xxxx0xx1xxxxx1xxxxx

T2：xxxx0xx0x0xxx0xxxx1xxxxx

T3：0xxx1xxxx1xxxxxxxx1xxx1x

T4：1xxx01xxx1xxxxxxxxx0xx0x

从H中找与t₁相容性最大的向量，得到向量t₂＝T2，n₂＝1。从H中移出t₂。n₂小于n_max并且测试集H不是空集。m＝2，合并t₁与t₂得到向量t₄。t₂移入测试向量组S。t₄中值“c”个数为n₁＝1，M＝N＝2，Q＝m*n₁＝2。

t₄：1xxxcxx0x0xx10xxxx1xxxxx

把“c”设为“1”，把“x”设为“0”，得到向量t₅

t₅：100010000000100000100000

编码：011010110010110000110000                  24bits

插入标记码“00”：01101000110010110000110000    26bits

组头信息编码：M：10N：01Q：10                   6bits

总的编码：10011001101000110010110000110000      32bits

压缩率$\lambda =\frac{48-32}{48}=\frac{1}{3}$

对t₂单独编码

编码：11100101110000                14bits

压缩率${\lambda }_{\mathrm{comp}}=\frac{24-14}{24}=\frac{5}{12}$

由于λ＜λ_comp，则t₂从S中移出，m的值减1。

继续从H中寻找与t₁相容最大的向量，此时H中的向量为T3和T4。

从H中找到与T相容性最大的向量t₂＝T3，n₂＝2，从H中移出t₂。n₂小于n_max并且测试集H不是空集，t₂移入测试向量组S中，合并t₁与t₂得到向量t₄。t₄中值“c”个数为n₁＝2，M＝N＝2，Q＝m*n₁＝4。

t₄：cxxx1xxxxcxx1xxxxx1xxx1x

把“c”设为“1”，把“x”设为“0”，得到向量t₅。

t₅：100010000100100000100010

编码：0110101011100111000010101000                    28bits

插入标记码“00”：01001010101100100111000010101000    32bits

组头信息编码：M：10N：10Q：1001                       8bits

总的编码：1010100101001010101100100111000010101000    38bits

压缩率$\lambda =\frac{48-38}{48}=\frac{5}{24}$

对t₂单独编码

编码：1011101111001110101000                          22bits

压缩率${\lambda }_{\mathrm{comp}}=\frac{24-22}{24}=\frac{1}{12}$

由于λ＞λ_comp，则t₂保留在测试向量组S中。

t₁＝t₄

从H中找到与t₁相容性最大的向量t₂＝T4，从H中移出t₂。n₂＝4，由于n₂＞n_max，所以t₂不能移入组S。H为空集。完成测试向量组S的分组，组内向量为T1，T3，并从R中移出T3。编码组S内向量个数和不相容位个数，不相容位个数Q

对测试向量组S编码，统计t₁内值“c”的个数n＝2，M＝N＝2，不相容位上值信息Q＝m*n

M：10N：10Q：1001

将t₁内的值“c”和值“x”分别变为“1”和“0”得到向量t₆，对t₆编码

得到T6_code。

t₆：100010000100100000100010

编码：0110101011100111000010101000

插入标记码T6_code：01001010101100100111000010101000

在T6_code之前插入组头信息并在末尾插入组分割码。

S：10101001011010101110011100001010100011110

与完成组S相同，T2与T4组成另一个分组Q。

Q：100101011011101011001111000011110

测试集R完成分组。