组合电路测试方法

上次课主要内容：1.可测试性度量2.SCOAP度量方法

组合SCOAP度量时序SCOAP度量2024/8/15ICTest:Lecture51回顾可控制性:通过电路的原始输入设置电路内部节点到0（或1）的难易程度。可观测性:通过电路的原始输出观察电路内部节点值（0或1）的难易程度。基本数字逻辑门的输出可控制性：2024/8/15ICTest:Lecture42回顾基本数字逻辑门的输出可控制性（续)：2024/8/15ICTest:Lecture43回顾基本数字逻辑门的可观测性：2024/8/15ICTest:Lecture44回顾基本数字逻辑门的可观测性：2024/8/15ICTest:Lecture45回顾对于下图中电路,计算组合SCOAP可测试性度量（可控制性和可观测性）。要求：标出门的级数，列出计算公式。2024/8/15ICTest:Lecture56作业解析——SCOAP度量方法2024/8/15ICTest:Lecture57作业解析——SCOAP度量方法首先设置各个逻辑门的级数；对所有PIs及其扇出节点,置CC0=CC1=1；从PIs到POs,采用SCOAP度量计算CC的方程获得可控制性；从POs至PIs计算各个逻辑门的级数；对于所有POs,置CO=0；从POs到PIs工作,采用SCOAP度量计算CO的方程和可控制性获得可观察性；扇出源CO=min分枝(CO(1),CO(2)，……)。2024/8/15ICTest:Lecture58作业解析——SCOAP度量方法第二章组合电路测试生成1.算法与表示结构测试与功能测试搜索空间的抽象算法完备性

ATPG代数算法类型2.重要的组合ATPG算法

D算法

PODEM算法

FAN算法2024/8/15ICTest:Lecture59自动测试矢量生成（ATPG）

是为测试电路而生成测试矢量的过程，其中电路是用逻辑级网表（电路图）严格描述的。ATPG算法具有多重目的：可以生成电路的测试矢量，可以发现冗余或不必要的电路逻辑，可以证明一个电路实现是否与另一个电路实现匹配。2024/8/15ICTest:Lecture5101

算法与表示Eldred(1959)–

第一次将结构测试应用于HoneywellDatamatic1000计算机Galey,Norby,Roth(1961)–

第一次发表stuck-at-0andstuck-at-1故障Seshu&Freeman(1962)–

用于并行故障模拟的固定故障模型Poage(1963)–

给出固定故障的理论分析2024/8/15ICTest:Lecture5111.1

结构测试与功能测试图164位加法器:功能测试和结构测试(固定故障)2024/8/15ICTest:Lecture5121.1

结构测试与功能测试（a）求和部分（b）进位部分2024/8/15ICTest:Lecture5131.1

结构测试与功能测试功能ATPG–为电路的输入-输出组合生成完备测试集.129输入,65输出（64位加法器）2129=680,564,733,841,876,926,926,749,214,863,536,422,912输入测试矢量

265=36,893,488,147,419,103,232

输出响应采用1GHzATE,需要花费2.15x1022年结构测试:没有多余的加法器硬件,64bitslices（位片）加法器每个位片仅有27

故障(采用故障等价)至多64x27=1728

故障(测试)花费0.000001728s（1GHzATE）设计者给出小的功能测试集–增加结构测试可使覆盖率增大到98+%2024/8/15ICTest:Lecture5141.1

结构测试与功能测试图2电路的不同表示2024/8/15ICTest:Lecture5151.2

搜索空间的抽象所有的ATPG程序均需要一种数据结构来描述测试矢量的搜索空间。BDD–从源到沉节点的路径–沿着各个路径的积给出沉处的布尔值。最右边路径:ABC=1

（检查与功能是否一致）BDD已经应用于ATPG。问题:大小随变量顺序变化。2024/8/15ICTest:Lecture516二元判决图（BDD）图3二元判决图（BDD）定义:如果它最终可搜索整个二元判决图,生成测试矢量的算法是完备的。不可测试的故障–

对于不可测试的故障，整个树搜索完之后,也不会找到它的测试矢量。仅组合电路–

不可检测的故障是冗余的,表明存在不必要的硬件。2024/8/15ICTest:Lecture5171.3

算法的完备性ATPG代数是一个高阶布尔集合符号，其目的是同时表现出“好”或“坏”电路的值。优点是只需要执行1遍ATPG就可确定好、坏电路的信号值。2024/8/15ICTest:Lecture5181.4ATPG代数：五值和九值代数2024/8/15ICTest:Lecture5191.4ATPG代数：五值和九值代数对于n输入组合电路,要产生所有2n

输入矢量，称为穷举测试（exhaustivetesting）。穷举测试的故障覆盖率很高，除了那些能使电路增加状态数（如CMOS电路中的s-op故障产生存储点）的故障外，绝大多数故障都可检测。不切实际的,除非将电路划分为小的逻辑模块,如15个输入或更少:对每个模块进行全部的ATPG。可能无法检测出需要多个逻辑模块同时激活才可以测试的故障。

2024/8/15ICTest:Lecture5201.5

算法类型1穷举测试和伪穷举测试核心部分是选择有效测试矢量的故障模拟器。采用获得的测试矢量可测试60-80%的故障,然后转换到D-算法或其它ATPG生成测试矢量。2024/8/15ICTest:Lecture521图4随机矢量生成方法1.5

算法类型2随机测试矢量生成（RPG）2024/8/15ICTest:Lecture5223符号法-布尔差分法假设是具有n个变量的逻辑功能表达式，如果其中的一个输入，比如说是ni出现了故障，则输出将变成,则F(X)相对于xi变量的布尔差分定义为：

1.5

算法类型——布尔差分法就被称为F(X)相对于xi的布尔差分运算。2024/8/15ICTest:Lecture523当的时候，；当的时候，。基于以上原理，在检测xi处的故障的时候，需要找出合适的输入逻辑组合，保证当xi由于出现故障而变成相反值的时候，。换句话说，对于每一个输入端口xi处需要推导出合适的逻辑组合，从而保证

1.5

算法类型——布尔差分法1.5

算法类型——布尔差分法2024/8/15ICTest:Lecture524异或运算法则：1.5

算法类型——布尔差分法2024/8/15ICTest:Lecture525布尔差分运算的一些有用的关系式是F(X)的反运算1.5

算法类型——布尔差分法2024/8/15ICTest:Lecture526如果F(X)和xi具有无关性，如果F(X)的结果仅与xi有关，如果F(X)和xi具有无关性，如果F(X)和xi具有无关性，1.5

算法类型——布尔差分法2024/8/15ICTest:Lecture527例推导出相对于输入x3的布尔差分结果1.5

算法类型——布尔差分法2024/8/15ICTest:Lecture528以上差分结果说明，当输入端x3处有故障时，只有当的情况下，输出F处才能显示出来这个故障，也就是说，输入向量中，应使x4为1，x1和x2中有一个为零或全为零。优点：纯数学方法，不需要试验，不会出错。缺点：需要首先推导出电路的布尔方程式,再进行布尔差分和异或运算,这对较大的电路来说,所耗费的时间和空间是难以接受的.

故在超大规模集成电路中应用较少。1.5

算法类型——布尔差分法2024/8/15ICTest:Lecture5291).故障敏化：对一个固定故障通过使驱动它的信号成为与故障值相反的逻辑值来激活。也称为故障激活或故障激发。2).故障传递：故障响应通过一条或多条路径传播到电路的PO。对于某些故障，为了测试它必须同时在多条路径上传播故障响应。3).线确认(LineJustification)：前面为敏化故障或传播其故障响应所做的内部信号赋值通过设置电路的原始输入来确认。2024/8/15ICTest:Lecture5304路径敏化法1.5

算法类型——路径敏化法三种情况：1.沿路径f–h–k–L传播；2.沿路径g–i–j–k–L传播；3.沿路径f–h–k–L和g–i–j–k–L同时传播。1.5算法类型——路径敏化法例输入端B存在sa0故障，推导其测试矢量。2024/8/15ICTest:Lecture531为了故障沿f–h–k–L

传播,需要设置AND门输入为1，OR门输入为0。因此,设A=1，j=0，E=1。路径f–h–k–L在

j阻塞,由于不存在判断i为1的路径。2024/8/15ICTest:Lecture5321.5

算法类型——路径敏化法0DD111DDD同时考虑f–h–k–L

和g–i–j–k–L

在

k

阻塞，因为D-边界（frontier

）消失。2024/8/15ICTest:Lecture5331.5

算法类型——路径敏化法1DDDDD111最后试验:路径g–i–j–k–L

测试矢量建立，测试B处sa0故障的测试矢量为0111。2024/8/15ICTest:Lecture5341.5

算法类型——路径敏化法0DDD1DD101DD基本的和第一个算法是Roth提出的D算法，采用D立方建立ATPG的运算和算法。其次的发展是Goel提出的PODEM算法，采用路径传播约束有效地限制了ATPG算法的搜索空间，并且引入了回溯的概念。第三个重要发展是Fujiwara和Shimono提出的FAN算法，有效限制了回溯从而加快了搜索的速度，并且利用信号信息来限制搜索空间。2024/8/15ICTest:Lecture5352.重要的组合ATPG算法2.1D立方2024/8/15ICTest:Lecture536

第一个成功用于非冗余组合电路测试向量生成的算法。

基本概念：

奇异立方故障D立方故障的传播D立方D相交D边界

D驱赶

2.1D立方2024/8/15ICTest:Lecture537（1）奇异立方n维空间中任意一个点、一条线段,……均称为一个立方.其中点是对应逻辑函数的最小项.而除了点以外的各种线段、面积等表示的均不是最小项,称为奇异立方。任何一个逻辑函数都可以用若干奇异立方来描述.

例如,f=x1x3+x2x3

可以用奇异立方（1×1）及（×10）来描述。

×表示变量可以是0或1。

或非门对应的真值表及奇异立方(a)真值表(b)奇异立方2.1D立方2024/8/15ICTest:Lecture538（1）奇异立方实际上,逻辑函数的奇异立方就是函数真值表的压缩表示法。

如或非门NOR的奇异立方,有的也称为初始立方，每一行称为一个立方。2.1D立方2024/8/15ICTest:Lecture539（1）奇异立方复杂电路的奇异立方

复合电路原理图和所对应的奇异立方该电路的奇异立方由三部分组成，每一部分对应每一个门，也就是说，对于复合电路，每一个门的奇异立方的共同集合构成了复合电路的奇异立方。2.1D立方2024/8/15ICTest:Lecture540（1）奇异立方基本电路的奇异立方2.1D立方2024/8/15ICTest:Lecture541（2）故障D立方在元件E的输出可产生故障信号D（D）的最小输入

条件称为故障D立方.其中D表示正常电路输出为1,故障时输出为0,

记为D=1/0;D则反之,记为D=0/1;如果用b表示正常电路的奇异立方,用a表示故障电路的奇异立方,则有D=b1na0

逻辑门的故障D立方是通过正常门和故障门的初始立方进行交（n）运算而得到的。D=b0na12.1D立方2024/8/15ICTest:Lecture542（2）故障D立方的形成规则首先形成逻辑门的正常初始立方和故障初始立方.对正常初始立方和故障初始立方进行交运算.

abf1110x0x00abf1x10x0（1）正常初始立方（2）故障初始立方b0b1b0a1与门，b（s-a-1）故障a0b（s-a-1）2.1D立方2024/8/15ICTest:Lecture543（2）故障D立方的形成规则运算符合如下规则：

2.1D立方2024/8/15ICTest:Lecture544把元件E的输入端的若干故障信号能传播至E的输出端

的最小输入条件称为传播D立方。传播D立方可从门的正常初始立方得到,即把门的正

常初始立方中具有不同输出值的立方进行交运算即

可获得。可以认为，故障是可以按照这种D立方传递的方式进

行的。（3）故障的传播D立方2.1D立方2024/8/15ICTest:Lecture545对应双输入或非门，传播D立方为：如果或非门的一个输入端为0，则输出与另一个输入端成互补关系。（3）故障的传播D立方2.1D立方2024/8/15ICTest:Lecture546基本电路的故障传播D立方（3）故障的传播D立方2.1D立方2024/8/15ICTest:Lecture547（4）D相交D相交又称D立方相交,它是建立敏化通路的工具,又是回推相容运算中是否相容的工具。（5）D边界它是指输入含有D/D~信号而输出还未定值的所有逻辑单元的集合。（6）D驱赶

指D运算中,把D/D~从故障源向原始输出传播的过程。正向蕴涵是指当一个逻辑单元的一个或几个输入的值确定之后,对其输出定值的运算.2024/8/15ICTest:Lecture548正向蕴涵(ForwardImplication)（a）正向蕴涵（b）AND门正向蕴涵表2.1D立方反向蕴涵指当门的输出和某些门的输入的值确定之后,确定其输入值的运算.2024/8/15ICTest:Lecture549反向蕴涵(BackwardImplication)图1反向蕴涵2.1D立方提出基本概念:第一个完备的ATPG算法D-立方D-驱赶蕴涵–

正向和反向线确认相容性检查-50-D-算法--RothIBM(1966)2.2D算法（Roth）2.2D算法（Roth）2024/8/15ICTest:Lecture551D算法针对输入端口2的s-a-0故障建立一个测试向量：针对该故障的初始D立方是：2.2D算法（Roth）2024/8/15ICTest:Lecture552为了将节点4处的传过G2，必须在满足G2的传播D立方关系中找到与相关的，如下：

整个电路的D立方：设置能够将从端口2至节点4至输出5的路径敏感化，从而能够检测该路径上相关的故障。D算法2.2D算法（Roth）2024/8/15ICTest:Lecture553如果在选择满足G2的传播D立方关系中，找到的是的话，它与故障对应的初始D立方进行相交运算将不能产生测试向量。因为节点4对应状态的第一个值是，则第二个值需要置为零，这是与要求相矛盾的。D算法2.2D算法（Roth）2024/8/15ICTest:Lecture554选择待测量故障的初始D立方；将待查故障门一直到输出之间所有可能传播故障的路径进行敏感化；这可以通过将故障的初始D立方与无故障的传输D立方相交生成；D驱动，输出端对应的值将会出现D或。一致化操作，将输入向量一致化，使在D驱动过程中，所有输入端口都设置为0或1。D算法2.2D算法（Roth）2024/8/15ICTest:Lecture555例1：推导出能够检测节点6处s-a-0故障的测试向量。

D算法2.2D算法（Roth）2024/8/15ICTest:Lecture556与节点6相关的门是G2，需要确定它的故障初始D立方，确定敏感路径上的门G4和G5的传播D立方，另外门G1和G3与故障完全无关，需要确定它们的奇异立方。D算法G2的故障初始D立方，G4和G5门的传播D立方分别为：2.2D算法（Roth）2024/8/15ICTest:Lecture557G1和G3的奇异立方为：D算法2.2D算法（Roth）2024/8/15ICTest:Lecture558与节点6处s-a-0故障相关的D立方，选择一个输出为D的，这样与G2门有关的D立方就选择（10D），然后与门G4的传输D立方进行相交运算，所得结果再与G5门的传输D立方进行相交运算。D驱动操作步骤各节点所对应结果

123456789选择D立方

10D与G4的D立方相交010D与G5的D立方相交

010D1DD算法2.2D算法（Roth）2024/8/15ICTest:Lecture559最后再进行端口一致化操作，即根据所得结果，将其它未有赋值的节点全部推导出相应的结果，这里所谓的“一致化”，指的是，在其它节点赋值时，要以不改变目前已经得到的结果为目标，使得结果一致化。

一致化操作步骤各节点所对应结果123456789根据G3的奇异立方检查节点7为1，将节点5设置为0

0100D1D根据G1的奇异立方检查节点5为0时对应的输入端口1的值，将端口1设为1

10100D1DD算法2.2D算法（Roth）2024/8/15ICTest:Lecture560以上在D驱动和一致化过程中，由于故障点处的D立方选择理想，所以在后面推导中未出现矛盾问题，在实际应用中，不可避免要出现由于D立方选择不当造成推导不下去的时候，这时就要重新确定故障处的D立方，重新进行D驱动