一个超大规模集成电路芯片功能测试的系统方案

摘要：在超大规模集成电路芯片中，电路板的详细实现通常是不知道的，只有功能特性对用户是公开的。在这篇论文中，我们呈现了一个系统的方案，仅仅基于被测电路板的功能特性，我们可以检测出并确定出固定故障和桥接故障。被提议的这个方案对于学术和工业超大规模集成电路使用者检测固定故障和桥接故障以及确认芯片的功能都及有帮助。规则和实验结果将会被报告。

关键词：功能特性；固定0-1故障；桥接故障；标准输入矩阵

中图分类号：TP3 文献标识码：A 文章编号：1009-3044（2013）12-2866-05

超大规模集成电路的高速发展导致了单个芯片的组成元素个数的指数增长。然而，由于每个芯片的基本输入输出是有限的，这导致了测试芯片工作更加困难。此外，集成电路制造商们因为知识产权的问题不乐意公开电路板内部实现的详细细节。另外，为了确保一个系统操作的可靠性，用户需要在在芯片提供给系统前对其进行测试。尽管如此，用户通常可以从集成电路制造商的数据书中找到一些该芯片的功能属性和芯片的部分体系结构。因此，两个问题出来了：1）只是基于一个芯片的功能特性而不知道其内部的实现细节，对其进行测试可能吗？2）进一步，用和上一步同样的信息，不仅测试这个芯片的固定故障而且测试其桥接故障可能吗？事实是，对这两个问题的回答都是积极的。

在这篇文章中，我们根据芯片的功能特性提出了一些系统的测试方法。不管怎样，基于对被测电路板的有限信息，我们的测试也会受限。因此，我们在此只考虑电路板的基本输入输出上的故障。换句话说，我们将要测试的故障仅限于下边几种：

1） 基本输入输出上的固定故障；

2） 输入线间的非反馈桥接故障；

3） 输出线间的非反馈桥接故障；

4） 输入和输出间的反馈桥接故障。

尽管我们的测试仅仅是根据电路板的外部特性提供的有限信息，我们得到了很好的效果，可以很方便的检测电路板的功能特性。对于大多数的用户来说，这个方案可以直接实现而不用复杂设备，软件和其他复杂工作。

1 基本定理

下边的定理，已经在前几篇论文中提出并证明，在这里再次列出但不予证明。方便起见，不失一般性，在这片文章中，我们提到桥接故障时就是这与-桥接故障模型。此外，我们把桥接故障划分为反馈型桥接故障和非反馈型桥接故障。

定理1：让我们来考虑一个电路板，其实现的F（n，m）这个功能函数，该功能函数有n个输入x1，...xn和m个输出F1，...Fm，我们在此提出一个输入矩阵T，其格式如下：

我们称T为输入矩阵T。

T可以检测出输入线x1，...，xm中的任何一个固定故障，当且仅当（a）T既不包含全0列也不包含全1列。（b）对每一个i（1≦i≤n），这里总存在一个j（1≤j≤N）和一个k（1≤k≤m）使得Fk（t1j，...ti-1j，0，ti+1j，...，tnj）≠Fk（t1j，...ti-1j，1，ti+1j，...tnj）.

定理2：定理1中提到的输入矩阵T检测所有的输出线上的固定故障当且仅当对应定理1中的输入矩阵，输出矩阵。

既不包含全0列也不包含全1列。

定理3：功能函数F（n，m），有n个输入x1，...xm，m个输出F1，...Fm，在这个电路板中非反馈桥接故障可以被检测当且仅当至少存在一个输入结合（a1，...as，xs+1，...，xn），（a1，...as）不是全0也不是全1，且有一个k（1≦k≦m）满足

Fk（a1，...as，xs+1，...，xn）≠Fk（0，...，0， xs+1，...，xn）

定义1：X=（x1，...，xn），xi={0，1}。对于有n个变量的布尔功能函数F来说，当X中含有的1的个数最少且使F=1时，X成为F的最轻最小项。

定理4：实现布尔功能函数F的输入输出间的任何反馈桥接故障都可被检测出来通过一个一步测试方案0或者一个两步测试（0，LM），这里LM是F的一个最轻最小项。

因为对于所有的反馈桥接故障来说，只有上边所提的一步或两步测试被需要。不管怎样，在两步测试中，LM必须提供给电路板，测试将第二步尾随第一步进行。

2 测试固定故障和桥接故障的案例应遵循的规则

基于上面所描述的理论，我们发现一些测试一个电路板的外部输入输出的固定故障和桥接故障应遵循的规则。

让我们考虑一个实现功能函数F（n，m）的电路板。T和F（T）是我们以上提到的输入输出矩阵。然后，我们可以发现如果T检测错误，那么输入矩阵T和输入矩阵F（T）必须满足如下规则：

规则1：为了检测固定故障，T和F（T）都既不包含全0列也不包含全1列。因为，如果不这样，一个固定型故障不能与非固定性故障但是有全0或全1列的区分开来。

规则2：为了检测输入线上的固定故障，对于每一个输入线Xi，必须存在一个j和一个k，使得Fk（t1j，...ti-1j，0，ti+1j，...，tnj）≠Fk（t1j，...ti-1j，1，ti+1j，...，tnj）。

规则3：为了检测输入和输出线上的非反馈桥接故障，T和F（T）都不能含有两列相同列，这样任意的非反馈桥接故障都可以被检测到。因为这个原因，这里必须

规则4：为了检测一个电路板的输入输出间的反馈桥接故障，输入矩阵中必须包括上边所提到的一步和两步阵列。

基于上述的规则，固定故障和桥接故障的测试矩阵可以很容易的产生且不用去了解被测芯片的内部详细实现。

作为一个例子，我们来考虑一个8-bit RAM，其有8个输入（x1，x2...x8），4个地址线（a1，a2，a3，a4）和一个读写控制线C.当C=0时是写模式，当C=1时是读模式。此RAM的8个输入线可以被描述为：

失一般性，我们假定所有的存储单元在测试前置0，这样下边的输入输出矩阵可以用来检测所有以上提到的故障。我们首先按顺序依次写5个8-bit数据，然后是读操作把数据倒序读出来。

可以看出我们上边提到的固定故障和桥接故障用这对输入输出矩阵都可以被检测出来。为了进一步的阐述输入输出矩阵的用途，我们简单的看几个例子：

1） 检测输入线上的固定故障：一个控制线C上的固定故障，任何一个地址线ai或任何一个数据输入线xj上的固定故障都可以用T和F（T）检测到。例如，在a1上有一个固定0故障，这样第五行的输入变成（0011111110000），使得地址单元（0111）重新写入（11110000），而地址单元（1111）并没有数据写入。因此，在输出矩阵中，输出的第六行变成（00000000）而且输出的第七行变成（11110000）.因此，a1上的固定0故障可以被检测到。

2） 检测输出线上的固定故障：对于人一个输出线zi上的固定故障可以简单的被输出矩阵检测到。任何输出线上的固定故障将会形成输出矩阵上的全0或全1列。

3） 检测输入线上的非反馈桥接故障：地址线间的任何非反馈桥接故障可以检测到通过观察到两行相同的输出。例如，两个地址线a1和a3连接到了一起，那么数据输入矩阵的第三行（01010101）将被重新写到地址单元（0001）。结果是，输出矩阵的第8和第9行有相同的值（01010101）。用类似的方法，一旦地址线和输入线间有连接在一起的，这样在输出矩阵中将有多余一行的数据会被改变，因此这个故障可以轻易的检测到。

4） 检测基本处出现上的非反馈桥接故障：这个故障可以被直接检测到仅仅通过检查在输出矩阵里是否有至少两个形同的列即可。因为任何输出线上的非反馈桥接故障都会导致在输出矩阵中至少有一对相同的列。

3 固定故障和桥接故障的确定

通过上述讨论的规则，我们现在发明一个系统的方法可以确定一个电路板的固定故障和桥接故障的位置，而不用知道电路板的详细实现。

方便起见，我们来考虑一个4位快速全加法器。这个加法器有9个输入线：包括4个数据输入线（A1，A2，A3，A4），（B1，B2，B3，B4）和一个低位向高位的进位C0，五个输出线：4个输出线（∑1，∑2，∑3，∑4）和一个向高位的进位线C5.然后让我们来考虑如下的输入-输出矩阵。用来检测和确定可能的固定故障和桥接故障。

从上面可以看出，4位全加器实现的布尔功能函数F（9，5），它有9个输入5个输出。为了测试和定位故障，矩阵可以称为标准输入矩阵（standard input matrix ， SIM）， 它生成的矩阵称为符合输出矩阵（corresponding output matrix， COM）。在COM中的每一行都是根据运算法则对输入产生的。现在我们考虑为什么这个选择好的SIM和COM可以用来测试和定位所有可能的固定型故障和桥接故障。

1） 如果在输入线上有任何固定型故障，那么至少会有两个相等的形式出现在SIM中。因此，也会有两个相等的形式出现在COM。

2） 如果在输出线上有任何固定型故障，那么在COM中会有全0或全1的列出现。

3） 如果在任何两个输入线之间有NFBF故障，那么至少有两个相等的形式出现在SIM中，因些也会有两个相等的形式出现在COM中。

4） 如果在任何两个输出线上有NFBF故障，那么至少有两个相等的列现在COM中。

5） 如果在任何输入线和输出线之间有FBF故障，然后根据一步或两步测试序列，至少错误列上会有一个0。

从上面的例子，可以和很容易看到，不仅固定型故障和桥故障可以被测试出来，而且它们的位置也可以根据他们在输出矩阵中的错误形式找出来。根据上面的讨论，可以得到下面的结果。在一个电路的合适SIM中，可以找出在主输入和输出上的各种错误，只要它的相应COM符合下面的条件：

1） 在输出矩阵中不多于两个相等且相邻的行。

2） 在输出矩阵中不多于两个相等的列。

3） 在输出矩阵中没有任何的0（1）列。

进一步，如果输入形式SIM也满足在III中的规则4，那么它也可以测试在输入线和输出线上的FBF故障。

为了定位故障，我们重新考虑下面SIM和它COM的通用例子。SIM中根据函数有个n条输入，我们的（n+1 x n）输入矩阵中每行ti有（i-1）0s，第（tn+1）th行是全（1，1，. . . ，1）向量。图1（a）展示了SIM的初始化状态。对于M列的输出矩阵，我们称是SIM按照F函数对应生成的。

根据上面的呈现的三个可测试条件，我们现在可以用下面的几个原则去定位固定型故障和桥故障。

1）如果在输入线xi（1≤i≤n）上有一个故障s-a-0，那么SIM中的输入形式t（n-i+2）将要变成t（n-i+1），这让SIM中的两个相邻行t（n-i+2） 和t（n-i+1）相等。同样，在输出矩阵中，F（n-i+2）也将变成F（n-i+1），标记为：F（n-i+2） F（n-i+1）.

2）如果在两行以上输入线上有NFBF错误，就是xi和xj，（1≤i≤j≤n ）那么，根据上面相同的原因，可以很容易地知道在输出形式COM中将发生F（n-i+2） F（n-i+1）的变化。

3）接下来可能会琐碎些，对于输出线上的固定型故障或NFBF故障，可以直接观察输出矩阵就可以看出来。因此，上面的规则使用（n+1 x n）SIM和（n+1 x m）COM可以应用来去确定固定型故障和桥故障。

对于输入线和输出线间的FBF故障，可以使用测试序列（0，LM）在加在SIM的前面就测试任何在输入线和输出线间的FBF故障。

事实上，在图1上描述的SIM不一定能保证产生一个有效的COM去满足上面的三个测试条件。因此，现在的测试生成算法如果生成一个错误的SIM，就交换SIM中的列再生成合适的COM，可以有效地适应初始SIM。这里讲一种列交换算法，它将修饰输出形式COM以满足合适的测试条件。

列交换算法的任务是进行列交换，描述如下。

列交换规则：

第一步：对于给定的函数F（n ， m），形成初始化的a （n+1） x n SIM，可如图3所示。

第二步：根据给定的函数和SIM，运算生成它相应的COM。

第三步：检查新生成的COM是否符合三个条件。 符合条件就停止运行。不符合条件进行第四步。

第四步：完成当前SIM中所有列的交换以生成一个新SIM，转回第二步。

为了举例说了列交换算法中的列交换，我们考虑了一个熟知的电路上的应用。如图4，它是一个4位的ALU，带着14条输入线和5条输出线，首先从它初始的SIM通过函数得到相应的COM。

然而很明显可以看到，从初始SIM计算出来的COM并不满足上面三个可测试条件。因为一些COM中相邻的行是相等的。如F4 =F5 ，F6 =F7 ，F10 = …=F14。经过重复执行2-4步，我们通过交换SIM中列的位置可以改变的输入形式，因此再次计算所得的COM也会改变它的值，此时再次重新检查新的COM是否满足三个输出条件。经过几次重复列交换算法后，初始的SIM和COM已经改变了他们的形式产生出新的COM，新计算的COM也可满足可以可测试条件，这样我们就可以根据原则进行测试。变成图5所示。

4 加速寻找速度和实验结果

交换算法可以生成有效的SIM和它的COM，事实上，最坏的情况下，交换算法的时间复杂度可以达O（n），n为被测试电话的输入线数。这是因为它需要所有可能的输入排列去找到一个合适的SIM。当N增加时，算法的时间复杂度也就增加。因此，一个随机的交换算法可以很好地提高查找速度以生成符合条件的COM。使用随机交换算法，我们每次交换的SIM的n个输入数列是随机产生的，而不是以前算法中的相邻地一个接一下产生的。理论上，最坏的情况下，随机交接算法和原始算法有相同的时间复杂度，但在实际操作中，前者却是更高效的。下面的表中，列出了以四项基准比较这两种算法的实验运行时间。

参考文献：

[1] S.Xu and S.Y. H. Su， “Detecting I/O and Internal Feedback Bridging Faults”， IEEE Trans. On Computers Vol.34， No.6， pp.553-557， 1985 ；Also re-printed in IEEE Computer Society Press， 1992， pp.9 –13.

[2] S.Xu and S.Y. H. Su， “Testing Feedback Bridging Faults Among internal， Input and Output Lines by two patterns”， Proc. ICCC 82， 1982， pp.214-217

[3] S. M. Thatte and J. A. Abraham， “Test Generation for Microprocessors”， IEEE Trans. on Computers C29， 1980， pp.429-441.

[4] S. Y. H. Su and Y. I. Hsieh， “Testing Functional Faults in Digital Systems Described by Register Transfer Language”， J. Digital Systems. Vol. 6， 1982， pp.161-183.

[5] M. Karpovshy and S. Y. H. Su， “Detecting Bridging and Stuck-at Faults at Input and Output Pins of Standard Digital Components”， IEEE Proc. 17th Design Automation Conf. pp. 494-505

[6] J. P. Shen et al， “Inductive Fault Analysis of MOS Integrated Circuits”， IEEE Design & Test， Dec. 1985， pp. 13-26

[7] H. Fujiwara， “Computational Complexity of Controllability /Observability Problems for Combinational Circuits”， IEEE Trans. on Computers Vol.39， No.6， 1990， pp.762-767.