组合电路的测试生成

1、第二章 组合电路的测试生成2.1 组合电路的测试生成组合电路的测试生成（Test Generation）就是对给定电路的给定故障来确定测试的过程。测试生成要解决的两个主要问题是：一是保证故障在其源处的可观性，二是能把故障效应传播到电路某一原始输出端。另外故障覆盖率与测试成本也是测试生成要考虑的重要因素。测试生成的方法比较多，但是应用时都有局限性，因此测试生成过程是测试环节的一个瓶颈。测试生成按测试矢量的确定方法可分为确定性测试生成和非确定性测试生成。确定性测试生成就是采用算法自动生成测试矢量的方法，用此种方法进行测试生成时，测试生成器一般需要测试情形（test view）描述。测试情形是门级的

2、电路描述，它是实际的电路结构（晶体管级描述）的一种近似表达。采用测试情形可以简化测试生成过程，大量实验表明，在门级生成的测试矢量，可以检测出大多数晶体管级的缺陷。非确定性测试生成是一种由人工进行的测试生成，也就是测试人员根据被测对象的功能、测试经验，用人工产生测试矢量；另一种是用软件或电路产生随机测试矢量，对电路进行穷举或伪穷举测试。测试生成方法按其生成的手段可归为两大类：代数法及算法。代数法是根据描述电路功能的布尔等式求解出测试矢量，其主要缺点是占用存储空间大，当电路复杂时，不存在或很难求得布尔等式。算法则是使用各种电路机理跟踪、敏化路径，使得故障效应传播到电路的原始输出，然后给原始输入分配

3、满足故障传播和生成条件的值。代数方法的测试生成典型的例子就是采用布尔差分法，本章我们把它用到组合电路种，但是也可以用到时序电路中，不过对于大规模集成电路，则该方法难以有效。但是该方法使得路径敏化的理论得到系统化，因此布尔差分法和布尔微分法在测试理论中占有重要地位，是进行理论研究的必要工具和基础。Goel提出算法的执行时间与电路中门的个数的平方成正比。由于测试生成的如此复杂，就有一些迭代方法的提出，最著名的是方法是D算法，PODEM算法，Fan算法和SOCRATES算法。所有的算法都基于四个最主要的操作过程：激活（excitation）、敏化（sensitization）、确认（justific

4、ation）和蕴涵（implication）。2.2 异或法2.2.1 异或法（Exclusive-OR method）异或法是测试生成最简单的方法，它是根据描述电路的功能函数求解出测试矢量的代数方法。无故障时电路开关函数为f，有故障p/d时电路的开关函数记为fp/d，应用代数运算就可得到故障p/d的所有测试集，我们用Fp/d表示：Fp/d就是满足上式条件的最小项的集合。 异或法直观，但是计算过程冗长、繁琐，对于重聚的扇出电路有可能找不到测试生成，在实际中他只是作为验证的方法。图2.1对于图2.1中的故障1/0，其最小项，也就是说1/0故障的测试矢量式110。对于故障3/0，有其最小项有，因此

5、故障3/0的测试向量应为001，010，011。图2.1中的电路比较简单，因此用异或法确定其测试向量较为简单，对于图2.2中的电路，如果用异或法则计算过程就比较冗长繁琐。图2.2图2.2中的电路故障6/0，其测试矢量可见故障6/0的测试矢量是比较多的，对于实际中的电路还要比图2.2中的电路复杂，异或法可能就不具实用性。对于有重聚的扇出电路可能找不到测试生成，实际中只是作为验证方法。2.2.2 不可测故障一故障p/d如果存在至少一个测试矢量的话，则说此故障是可测的。但是对于重聚的扇出的电路，并非所有的故障都是可测试的，这样的故障叫做不可测故障。对于图2.3(a)中的故障13/0，就是属于不可测故

6、障。图2.3 不可测故障因此故障13/0不存在测试矢量，这就提出了一个问题：如何确认不可测故障。这需要研究逻辑电路中的冗余问题，一电路具有冗余是指，该电路存在且只存在一条线，该线被去掉或由适当的逻辑常数（0或1）代替后，实现的功能不变。如图2.3（a）中，线13用0代替后所得的电路2.3（b）实现的功能与2.3（a）相同，因此线13是冗余的。不可测故障只存在于具有冗余的电路中，其判断方法如下：i代表电路中的冗余线，如果i可以去掉或由一逻辑常数a（a为0或1，但不能既为0又为1）代替的话，那么故障i/a是不可测的，但故障是可测的；如果i可由a和代替的话，那么故障i/a和均不可测。冗余也是在电路设

7、计中所需要注意的一个问题，因为冗余不但增加了电路的复杂程度，还有可能给电路的测试带来困难。2.2.3 多输出电路实际中大多数电路输出端不止一个，也就是说电路实现不止一个功能。图2.4描述了一个二输出端子的电路，当对这样的电路生成测试矢量时，两个输出函数都应该考虑。假定Fp/d表示故障p/d所有可能的测试矢量的布尔函数表达，就有：F1p/d和F2p/d分别表示对故障p/d在f1,f2输出端所有的测试矢量。对于图2.4中电路的故障1/0：0图2.4 多输出电路F21/00，因此故障1/0在f2不可观。一般来说，如果一电路具有m个输出的端子，对于故障p/d测试矢量就为：2.3 布尔差分法2.3.1布

8、尔一阶差分布尔差分法是组合逻辑电路测试矢量生成的一种代数方法，其描述严格而简洁，物理意义清晰，因而在研究组合逻辑电路测试的理论和方法时具有重要的意义。为了叙述方便，本节中采用下述符号：对于开关函数（布尔函数），定义：布尔函数对变量xi的偏差分定义为上式的意义是：当xi变化时，其对应的的异或结果为1时，相应的电路输出反映了xi的变化，即xi是可测的，反之xi是不可测的。对此函数可推导出以下性质：(i)这里的表示的反，xi是自变量(ii) (iii) (iv) (v) (vi)如果与xi无关，那么：2.3.2布尔一阶差分法检测电路的故障图2.5对于如图2.5所示的组合电路中的故障f2/1，用布尔差

9、分法来检测时，先将其实现的功能f对变量f2求差分。求解其测试矢量时，应该根据下面两式来确定：上面两式合并起来可得：即：1上式的解为：x1x2x3x4=0000,0001,0010,0100,0101,0110,1000,1001,1010，其中任意一个都是故障f2/1的测试矢量。布尔差分的结果如果为1，则表明fi的变化将导致函数的值的变化；否则fi的变化对的值无影响。因此我们可以建立检测s-a-0故障的逻辑等式：；即：对于fk的s-a-1故障，其检测时的逻辑等式为：；即：利用上面的等式可以求解出其测试矢量。2.3.3 高阶布尔差分一阶布尔差分主要用来求单故障测试矢量集。如果要求多故障的测试矢量

10、集，就必须引入高阶布尔差分的概念。这里主要叙述二阶布尔差分及其双故障测试矢量集的求法。更高阶的布尔差分和多故障测试矢量集产生的方法可依此类推。函数其对变量xi的一阶偏差分和一阶微差分相同，即：而对于二阶布尔偏差分的定义为：二阶布尔微差分定义为：二阶布尔偏差分与二阶布尔微分的关系为：检测双故障的测试集为：其中，为0或1，。 2.4 路径敏化法一维路径敏化法是测试生成的第一个方法，其原理是从故障点到输出之间敏化一条路径，将故障效应传播到输出端，其步骤如下：1）推导测试矢量，使得故障在其源点可观。例如，对于s-a-1故障，在其源处出现的条件是逻辑“0”；2）选择一条路径，沿此路径，故障效应可传播到电

11、路输出；3）对于选定的路径上的元件，给定输入变量，使得该元件的输出值仅由路径上连接到该元件的输入线确定；4）确定故障及故障传播到输出端的输入变量的条件。这四个步骤实际上是确定性测试生成的主要过程，分别是故障激活、敏化或传播、确认和蕴涵。2.4.1 确定性算法的基本过程为了对一条线上的SA故障进行测试生成，首先要对故障进行激活（excite or provoke），然后敏化（sensitize）此结果到输出端，接着对电路中其它线的值确认（justify），再就是对其它门的值蕴涵（implication）。图2.6 路径敏化法示例激活 激活某一条线上的故障就是控制该线，使得其值为故障的补码，这等效

12、于把故障信号置于该线上。例如要激活图2.6中的故障，应该控制门4的输入使得。敏化（传播） 敏化或传播就是选择一条路径，沿此路径可把故障信息从其源处传播到原始输出。此条路径叫敏化路径或者是传播路径。例如图2.6中，故障的传播路径只能是。有些故障可能具有不止一条敏化路径。确认 通过对电路中其它线的赋值，确定电路中这些线的逻辑值。例如图2.6中，要把敏化到f5，须对f1赋值，要把故障效应传播到原始输出Z，则必须要对f3赋值。蕴涵 通过确认电路中线的值，寻找电路中非敏化路径上门的输入或输出值的过程。如果先确定的是该门的输入值，那么确定其输出值的过程就叫向前蕴涵，如果先确定的是该门的输出值，则寻找其输入

13、端的过程叫向后蕴涵。一致性（consistency）检查 在敏化与确认的过程中，必须检查某些线要赋的值与先前已赋的值是否有矛盾，这个过程叫做一致性经常。如果有矛盾，则需要重新处理。2.4.2 路径敏化法应用的实例例2.1 对于图2.6中的故障12/1，我们来研究路径敏化法对其的测试生成。12/1故障激活的条件是，f4是门4的输出，要使就必须使门4的输入满足下面的条件：选择敏化路径：。故障要从f4传播到f5，必须确认门5的另一个输入（或门），故障要从f5传播到f6，得确认门6得另一个输入（与门），总结得： 上式的求解实际上是向后跟踪路径敏化要完成的任务。再考虑到电路元件要实现的功能，系统输入就采

14、取以下形式：，上式是多解的，每一个解都是特定故障的测试矢量。例如输入1110111就是一解，当对电路无故障施加此输入时，输出Z也为0，而因为有故障12/1的存在，实际电路的输出为1，因此故障在其输出端是可观的。例2.1中的电路是无扇出的电路，采用的是单路径的敏化方法。但是对于有扇出的电路，采用单路径敏化可能行不通。例如图2.7所示的电路，对于故障a/1，可以有两条单敏化路径或。故障激活时，x1和x2应使得a为0，；对G2的输入确认应该使得，对G4的输入确认使得，对G3的输入蕴涵得，这显然与激活条件矛盾。同样对这条路径敏化时也会出现不一致。因此单路径敏化不能进行测试生成。图2.7 单路径敏化的反

15、例（a）单路径敏化 （b）双路径敏化但是这个电路还有第三条敏化路径，如图2.7(b)所示为双路径敏化。显然当激活故障时，故障效应沿双路径可传播到Z。无故障时Z=0，有故障时Z=1。总之，扇出对路径敏化的影响可归纳为三种情况：1 单一路径或多路径均可产生测试；2 只有单一路径产生测试；3 只有多路径产生测试；对于扇出电路，为了避免路径敏化法推导测试矢量所遇到的问题，给出下列提示：1 先试用单一路径法推导测试矢量，如果无测试矢量，则再用步骤2：2 试用多路径推导测试矢量。检验每一个可能测试矢量的有效性，如果确实找到并检验了此测试矢量，则停止测试生成；3 在没有找到测试矢量前，所有组合的多路径都应该

16、进行检查。2.5 D算法D算法基于集合理论，1966念由Roth正式提出，它是关于非冗余组合电路测试生成的第一个算法，属于多路径算法。除了用到多路径扫描法的几个主要操作过程中之外，还发展了一系列术语。2.5.1 D算法的关键术语1.d立方（d-cube）D算法的基础是布尔函数的d立方，d立方是通过奇异立方来求的，因此我们先介绍一下奇异立方的概念。逻辑函数除最小项以外的其它表示项，叫奇异立方。任一逻辑函数都可用若干奇异立方来表示。例如函数可以用奇异立方（x11）和（1x0）描述。事实上函数的奇异立方就是函数的真值表压缩表示法。为了表示奇异立方，要用到符号0，1和x，这里的变量x可代表0或1。图2

17、.8(a)是一与非门的奇异立方表示，图2.8(b)是对一两输入与门、两输入或非门、两输入或门组成的电路的奇异立方表示。图2.8 电路的奇异立方表示讨论奇异立方的目的是为了引入d立方。d立方由符号O、l、x和d表示，d可为O或l，的表示值则相反。d立方表示了数字电路的特征，由两个具有不同输出的奇异立方相交运算得到，其运算符合以下规律 因此，对一个两输入与非门，其奇异立方为 与 我们通过运算得到其d立方 2.故障的原始d立方(Primitive d cube) 故障的原始d立方用于确定一给定故障的存在，包含两方面内容: 1）使得故障效应传播到输出的输入方式。输入信号方式应使得故障在其源处激活，还应

18、使得该故障信号传播到输出。 2）输出应有符号d和。d表示电路无故障时输出为1，有故障时输出为0; 反之。故障的原始d立方可由上述的d立方运算规律求得。假定表示电路无故障时的d立方，表示电路有故障时的奇异d立方，则有其中、的下标l、0分别表示电路的输出为1或0。 例2.2 求图2.8(b)中故障30的原始d立方。解：电路正常时的奇异立方1和0，电路有故障30时的奇异立方，分别表示如下再对1与0一一求交得d：或 再将输出信号补上，得故障d立方为(0xD)和(x0D)。可以看出故障的原始d立方就是故障激活的条件。 3.故障的传播d立方(Propagate d-cube) 把电路输入端的故障效应传播到

19、电路输出端的最小输入条件叫做传播d立方，它表明了敏化路径的敏化条件，也是对被测电路的结构描述。简单门的传播d立方，可以直接观察写出。图2.9表示了几种基本门电路的传播d立方。图2.9 基本门电路的传播d立方一般地，对于线上的传播d立方，可以用以下两种方法求解： (1)把=O时，电路的奇异立方0和=l时电路的奇异立方l相交运算； (2)把=l时，电路的奇异立方0和=O时电路的奇异立方1相交运算： 其结果就是传播d立方，它是成对出现的，且d互补。物理意义是，能够作为dd传播条件的必可作传播，能够做d传播的必可作一d传播。4.d驱赶(d drive) 逐级将故障信号d()从故障点敏化至原始输出端的过

20、程叫d驱赶(d drive)。d驱赶的具体做法是将输入端有d()信号而输出值尚未值确定的元件的传播d立方同测试立方作求交运算，使该元件输出d或信号。如果该交存在，说明本次驱赶成功，否则不成功。驱赶过程中的求交运算按表2.1进行。d交运算是建立敏化通路数学工具，Roth对d交的定义示于表2.1，并用算符表示。在表2.1中，表示d交为空，y表示d交无意义，其准确含义将在具体进行d交运算时解释。表2.1 Roth d交定义01xDD00f0yy1f11yyx01xDDDyyDDyDyyDyD2.5.2 d算法的基本步骤1)建立失效的原始d立方PDCF(Primitive d-cube for fai

21、lure),激活故障； 2)选择敏化路径； 3)沿敏化路径传播PDCF，一次一个门按表2.1进行相交运算，直到原始输出，也就是d驱赶，驱赶过程中对电路中节点赋值，对原始输入确认； 4)如果d或出现在原始输入，驱赶成功，否则返回至步骤2： 5)一致性检查，若成功则确定测试矢量，否则,则无测试生成。D算法流程图如图2.10所示。图2.10 d算法流程图2.5.3 d算法举例例2.3 对图2.11所示电路中的故障，求其测试生成。解：首先，对电路中所有节点赋值x以初始化； 其次，对门2建立原始d立方，过程见例2.2。推导门1和门3的奇异立方，对门4推导传播d立方。敏化路径为，原始d立方我们选择。图2.

22、11 d算法故障f2=0的测试生成然后开始d驱赶，先是对故障d立方C0与定义门4的d立方C1作求交运算，结果为C2再计算门5的d立方c3与c2的交分析立方c4，表明被测电路的节点9有d出现，d驱赶完成。进行向后操作，立方c4能够与门l和门3的奇异立方相交，结果为结果立方C8说明：输入模式为x1x2x3x4=1010时，故障f2=0的效应可传播到电路输出端，也就是说输入1010是故障f2=0的测试矢量。2.6 PODEM算法 经典的D算法能够对非冗余的组合逻辑电路的故障找到测试矢量，但对于重聚的扇出电路。如奇偶检测电路、表决电路、误码校正及检测电路等，由于工作量大，以致很难付诸实施。其主要问题是

23、返回的操作次数太多，原因是d驱赶及向后的线确认涉及到选择过程，这可能导致对门赋值时的赋值相互矛盾，一旦矛盾出现，就得返回原先的判断点重新进行敏化路径和赋值。如图2.12(a)所示电路中的DO故障，由D算法的线确认和相容性检查我们得到测试矢量为：ABC=001，但此测试矢量并不能检测DO故障，因为不管D0是否存在，原始输出Y保持为0。因此必须寻找另外一个测试矢量来检测该故障，这就是我们所说的向后操作。 图2.12 (a)测试矢量与测试故障效应相矛盾 (b)返回操作找到了一新的测试矢量新的测试矢量ABC=101，故障在其源处效应为10，即d(无故障时为1，有故障时为O)，在原始输出端可观察到d，也

24、就是说，新的测试矢量既可以使得故障在其源处再现，又可以在原始输出Y测试到故障DO的效应。但对于大规模集成电路而言，返回操作使得这种试探矛盾的过程太多，而真正的有效操作较少为了解决这个问题，就产生了各种改进的算法，PODEM算法就是其中之一。PODEM(path oriented decision making)算法首先由Goel提出，实际上是一个程序，它使用了D算法的一些术语，吸收了穷举法的优点，对D算法作了有益的改进。2.6.1 PODEM算法PODEM算法的思路对激活的故障向后追踪到原始输入，搜索所有可能的输入变量，只要找到一个符合要求的输人组合即可作为测试矢量，算法即告结束。对于一确定的

25、故障，首先是确定目标，然后对连接到门的输入线选择原始输入向量。如图2.13所示电路AB是原始输入PI,Y是原始输出PO,对图中的s-a-O故障，首先要确定的目标是，确定输入使得无故障时Y为0，有故障时Y为l，为达到这个目的，必须确定AB=11。目标：Y=01 测试：AB=11图2.13 PODEM算法目标设定 对每一个门都重复此过程，一直到原始输入端，然后对此原始输入赋所需要的值(其余的原始输入保持不变)。对于原始输入的每一个新的赋值，如果在原始输出可观察到故障效应，就对有故障及无故障的电路进行模拟，这样就建立了一条从故障源处到原始输出的敏化路径。如果在原始输出没观察到故障效应，就选择一条向前

26、的故障传播路径，此路径的物理长度最短，对每一个门重新确定目标。物理长度最短的意思是指，从故障源处到原始输出的路径上门的个数最少。由于原始输入的选值具有随机型，那么按什么变量次序来穷举输入矢量才能较快地得到所需要的测试矢量呢？PODEM算法中采用分支判决树的方法来解决此问题。图2.14 PODEM算法中的分支判决树 图2.14就是PODEM算法中的分支判决树的流程图。A，B，C，D，E，分别表示原始输入，由于每个原始输人只有两种可能的值，因此可以对每个原始输入进行两种试探。当选择1时，执行右分支，否则执行左分支，对下一个原始输入赋值时，如果第一个分支无测试，则过程返回到先前的节点，最后就形成图中的二分树其中的所谓的无测试可能是两种情形：一是故障没有激活，二是故障的路径没有得到敏化。如果一原始输入的两种值都已试探过，其结果都是无测试，则删掉此节点，同时也删掉前一个原始输入的选值，也不对后一个原始输入选值。每次从一节点选取第二分支时，就作