第2章电子电路故障

1、第第2章组合电路测试与故障诊断章组合电路测试与故障诊断什么叫算法？什么叫算法？第第2.1节节 通路敏化通路敏化u基本概念基本概念-什么是敏化通路？什么是敏化通路？u敏化通路法的实施步骤及举例敏化通路法的实施步骤及举例u关于一维敏化与多维敏化的讨论关于一维敏化与多维敏化的讨论第第2.2节节 d 算法算法ud 算法的基本思想算法的基本思想ud算法的数学工具算法的数学工具ud算法的实施步骤及举例算法的实施步骤及举例第第2.3节节 扩展扩展 d 算法算法 u扩展扩展 d 算法的数学工具算法的数学工具u扩展扩展 d 算法的实施步骤及举例算法的实施步骤及举例第第2.4节节 布尔差分法布尔差分法布尔差分的基

2、本概念布尔差分的基本概念布尔差分的特性布尔差分的特性求解布尔差分的方法求解布尔差分的方法故障测试故障测试电子科大电子科大CATCAT室室第第2.1节节 通路敏化通路敏化2.1.1. 通路敏化的基本定义通路敏化的基本定义 1.Eldred在在1959年提出了第一篇关于组合电路的测试报告，开始年提出了第一篇关于组合电路的测试报告，开始 了数字系统故障诊断的研究。了数字系统故障诊断的研究。 2.D.B.Armstrong根据根据Eldred的基本思想，在的基本思想，在1966年提出了一维通年提出了一维通 路敏化的方法，其主要思路是对多级门电路寻找一条从故障点到路敏化的方法，其主要思路是对多级门电路寻

3、找一条从故障点到可及输出端的敏化通路，使在可及端可以观察到故障信号。可及输出端的敏化通路，使在可及端可以观察到故障信号。 3.1967年年Schneidr用例子指出单通路敏化法并不能找出所有的故障。用例子指出单通路敏化法并不能找出所有的故障。 4.同年同年Roth提出了多通路敏化法的提出了多通路敏化法的D算法算法 电子科大电子科大CATCAT室室第第2.1节节 通路敏化通路敏化2.1.1. 通路敏化的基本定义通路敏化的基本定义 算法的定义：算法的定义：一个问题一个问题无二义性无二义性解的解的过程（时间和空间）过程（时间和空间） 是利用计算机解决一切问题的基础！是利用计算机解决一切问题的基础！主

4、输入端：主输入端：一条输入线，若不受电路其它任何一条线馈给信号，这个输入端就称一条输入线，若不受电路其它任何一条线馈给信号，这个输入端就称之为主输入端，也称原始输入端；之为主输入端，也称原始输入端；主输出端：主输出端：一条通到电路外部去的信号线称为主输出端，也称原始输出端；一条通到电路外部去的信号线称为主输出端，也称原始输出端；通路：通路：在组合电路中，从一个主输入端经内部信号线通到主输出端而不含有环路在组合电路中，从一个主输入端经内部信号线通到主输出端而不含有环路（无反馈线）的通路（定向信流图）；（无反馈线）的通路（定向信流图）；敏化通路：敏化通路：对一条通路中所有门电路的一切输入适当赋值（

5、与门赋对一条通路中所有门电路的一切输入适当赋值（与门赋“1”，或门赋，或门赋“0”)，使该通路上的逻辑变化能沿该通路传输到主输出端，这样的通路就称，使该通路上的逻辑变化能沿该通路传输到主输出端，这样的通路就称之为敏化通路；之为敏化通路；电子科大电子科大CATCAT室室第第2.1节节 通路敏化通路敏化2.1.1. 通路敏化的基本定义通路敏化的基本定义例：例：u主输入端主输入端：x1,x2,x3u主输出端主输出端：yu通路通路：a f h , b d f h , b e g h , c g hu敏化通路敏化通路：敏化：敏化 a f h 通路通路赋值：赋值：d = 1 ，g = 0敏化：敏化：a f

6、 h 通路上的逻辑变化都能传输到主输出端通路上的逻辑变化都能传输到主输出端 y（故障传播或前相跟踪故障传播或前相跟踪）u赋值条件检查赋值条件检查：赋值条件能否在主输入端实现（：赋值条件能否在主输入端实现（一致性检查或后相跟踪一致性检查或后相跟踪）由由 g = 0，必须，必须 e = 1 或或 c = 1 或二者均为或二者均为 1由由 d = 1，必须，必须 b = 1 即即 e = 1综上：综上：e = 1 即即 x2 = 1 c = x (随意）随意）利用敏化通路进行利用敏化通路进行测试测试-可测试可测试 a f h 通路上的故障通路上的故障T=（01x) ; 0无故障；无故障；T=(01x

7、) ; 1a,f,h-s-a-1 故障测试故障测试T=（11x) ; 1无故障无故障T=(11x) ; 0a,f,h-s-a-0 故障测试故障测试x1x2x3abcfghde电子科大电子科大CATCAT室室2.1.2 通路敏化法通路敏化法1.基本思想：利用敏化通路原理基本思想：利用敏化通路原理2.数学关系数学关系u故障算子故障算子D-故障表示故障表示D 可为可为 “1”，也可为，也可为 “0”。在同一系统中应统一在同一系统中应统一；若若 ，则，则 ;若若 ，则，则；D 故障赋值故障赋值为了测试，在故障点应将为了测试，在故障点应将 D 赋于故障相反值：赋于故障相反值：在在 D = 0 的系统中的

8、系统中对于故障对于故障 s-a-0 则故障赋值则故障赋值 对于故障对于故障 s-a-1 则故障赋值则故障赋值 u为了故障传播，引入为了故障传播，引入 算子算子或门：或门： 或门赋值条件或门赋值条件与门：与门： 与门赋值条件与门赋值条件 1D0D1D0D1D0DDD或D1110DDDDD0100DDDDD电子科大电子科大CATCAT室室2.1.2 通路敏化法通路敏化法3.3.通路敏化法的实施步骤通路敏化法的实施步骤u故障表现故障表现-故障赋值故障赋值u故障传播（通路敏化，前相跟踪）故障传播（通路敏化，前相跟踪）-敏化条件敏化条件u一致性检查（后相跟踪）一致性检查（后相跟踪）-敏化条件能否在主输入

9、端实现敏化条件能否在主输入端实现u测试确定测试确定-测试函数的寻求测试函数的寻求4.4.举例：举例：用通路敏化法求用通路敏化法求 1_s_a_1 1_s_a_1 的测试的测试（1 1）故障表现）故障表现系统定义：系统定义： D = 0D = 0对于对于 1_s_a_1 1_s_a_1 故障故障， 则则 故障表现为故障表现为 D D ； 1_s_a_0 1_s_a_0 故障，故障， 则则 故障表现为故障表现为 ； x1x2x3x4123456879101112yxDDD110D电子科大电子科大CATCAT室室2.1.2 通路敏化法通路敏化法（2）故障传播）故障传播通路通路 L1-L10-L12

10、敏化（见图）：与门赋敏化（见图）：与门赋“1”，即，即 L5 和和 L8 赋赋 “1”； 或门赋或门赋“0”，即，即 L11 赋赋 “0”；D 传播到主输出端，仍为传播到主输出端，仍为 D；（3）一致性检查）一致性检查由赋值：由赋值：L5=1，则要求，则要求 L2 = x2 = 1； L8=1，则要求，则要求 L7=1，即，即 x2 或或 x3 或或 x4 为为 1； L11=0，则要求，则要求 L9=L7=1，即，即 x2 或或 x3 或或 x4 为为 1；综上：综上：x2 = 1，x3 = x4 = x，在主输入端可实现敏化条件；，在主输入端可实现敏化条件；（4）测试确定）测试确定综上可得

11、综上可得 x1-s-a-1故障的测试如下：故障的测试如下：T=（01xx）；）；0 无故障测试；无故障测试； T=（01xx）；）；1 x1,L10,L12-s-a-1故障测试；故障测试；优点：优点：简单，存储空间小，有拓扑的直观性。简单，存储空间小，有拓扑的直观性。电子科大电子科大CATCAT室室2.1.2 通路敏化法通路敏化法 自从自从1966年年Armstrong提出一维通路敏化提出一维通路敏化法以来，数字电路测试矢量自动生成理法以来，数字电路测试矢量自动生成理论的研究课题经历了一个从雏型到成熟、论的研究课题经历了一个从雏型到成熟、从理论到应用、从实用到完备的发展历从理论到应用、从实用到

12、完备的发展历程。程。 电子科大电子科大CATCAT室室2.1.3 讨论讨论问题：问题：上面分析的是一维敏化，即每次只敏化一条通路。但一维敏化是不是一种算法上面分析的是一维敏化，即每次只敏化一条通路。但一维敏化是不是一种算法呢？先看几个例子：呢？先看几个例子：例例1：无扇出的树形电路无扇出的树形电路故障：故障：a = x3 = D通路：通路：a b c (一维敏化）一维敏化）敏化：敏化：x4 = 1 x1 = 0 或或 x2 = 0 = 0 或或 =0 =0 或或 =0一致性检查通过一致性检查通过测试：测试：T=00D11111；D 无故障测试无故障测试 T=00D11111； a,b,c-s-

13、a-1 故障测试故障测试结论：结论：由于无扇出电路输入端是独立的，赋值自由，不相互约束。因此，每条通路的由于无扇出电路输入端是独立的，赋值自由，不相互约束。因此，每条通路的一维敏化都是成功的，可求出电路的最小完备测试集。一维敏化都是成功的，可求出电路的最小完备测试集。x1x2x3x4abc00 x0005x6x7x8x5x6x7x8xD电子科大电子科大CATCAT室室2.1.3 讨论讨论例例2：有扇出汇聚电路有扇出汇聚电路故障：故障：h-s-a-0 ( =1)敏化通路（一维）：敏化通路（一维）：h j lx1=a=1g=0 x2=b=1c=0h= =1d=0h j l 敏化不成功！敏化不成功！

14、敏化通路（一维）：敏化通路（一维）：h k m 敏化成功！敏化成功！结论：结论：对有扇出汇聚电路，一维敏化可能成功，也可能不成功！对有扇出汇聚电路，一维敏化可能成功，也可能不成功！x1x2x3x4abcdefghjklmy1y2x11000000矛盾矛盾DDDD电子科大电子科大CATCAT室室2.1.3 讨论讨论例例3：Schneider电路电路故障表现：故障表现：6-s-a-0 敏化通路（一维）：敏化通路（一维）：L6-L9-L12敏化条件：敏化条件：由由 6-s-a-0， 有：有：x2=0 ,x3=0 ;由由L10=0 及及 L6=0，必须，必须 x4=1；由由L11=0 及及 x3=0，

15、必须，必须 L7=1，即必须，即必须，x2=0,x4=0 x4矛盾，敏化不成功！矛盾，敏化不成功！敏化通路（一维）：敏化通路（一维）：L6-L10-L12由于电路是完全对称的，由于电路是完全对称的，x3矛盾，敏化也不成功！矛盾，敏化也不成功！x1x2x3x4x61091187000D12D5DDDD电子科大电子科大CATCAT室室2.1.3 讨论讨论多维敏化：同时对多条通路进行敏化。多维敏化：同时对多条通路进行敏化。上例：同时对上例：同时对L6-L9-L12 及及L6-L10-L12 两两条通路进行敏化，条通路进行敏化，故障表现：故障表现：6-s-a-0( )-x2=0，x3=0；敏化条件：敏

16、化条件：L11=0，因，因 x3=0，所以，所以 L7=1-x2=0，x4=0；L8=0， 因因 x2=0，所以，所以 L5=1-x1=0，x3=0；多维敏化成功！多维敏化成功！测试：测试：T=（0000）；）；1 无故障测试；无故障测试；T=（0000）；）；06-s-a-0故障测试；故障测试；x1x2x3x4x61091187000D12D5DDD电子科大电子科大CATCAT室室2.1.3 讨论讨论结论：结论：通路敏化是数字系统测试的基础，但一维敏化不是一种算法，通路敏化是数字系统测试的基础，但一维敏化不是一种算法， 而多维敏化而多维敏化才才是一种算法。是一种算法。多维敏化的实施：多维敏化

17、的实施：多路同时敏化有多种组合，因此，需要多路同时敏化有多种组合，因此，需要遍历遍历，反复搜索反复搜索和计算和计算。用人工的方法是十分困难的，甚至是不可能的，必须借助于计。用人工的方法是十分困难的，甚至是不可能的，必须借助于计算机进行测试，即利用算法进行算机进行测试，即利用算法进行计算机辅助测试（计算机辅助测试（CAT）：组合电路测：组合电路测试算法有：试算法有：*d 算法算法*扩展扩展d 算法算法*布尔差分法布尔差分法*等效笵式法等效笵式法-ENF*SPOOF法法 等等。等等。电子科大电子科大CATCAT室室2.2 d算法算法u1966年提出的算法，可以认为是拓扑结构测试中最经典的方年提出的

18、算法，可以认为是拓扑结构测试中最经典的方法，也是最早实现自动化的测试生成算法之一。它是完备的测试算法，法，也是最早实现自动化的测试生成算法之一。它是完备的测试算法，它可以检测非冗余电路中所有可以检测的故障。虽然它是在世纪它可以检测非冗余电路中所有可以检测的故障。虽然它是在世纪年代提出的，而且被该经过多次，但是，许多新的测试方法都是在它年代提出的，而且被该经过多次，但是，许多新的测试方法都是在它的基础上发展起来的。而且一直沿用至今。的基础上发展起来的。而且一直沿用至今。uD算法在具体应用时，计算工作量很大，尤其是对大型的组合电路算法在具体应用时，计算工作量很大，尤其是对大型的组合电路计算时间很长

19、计算时间很长,原因是在作敏化通路的选择时其随意性太大，特别是在考原因是在作敏化通路的选择时其随意性太大，特别是在考虑多通路敏化时各种组合的情况太多，然而真正虑多通路敏化时各种组合的情况太多，然而真正“有效有效”的选择往往较的选择往往较少，做了大量的返回操作。少，做了大量的返回操作。u改进的算法，如改进的算法，如PODEM和和FAN算法，有效地减小了返回次数，提算法，有效地减小了返回次数，提高了效率。高了效率。 电子科大电子科大CATCAT室室2.2 d算法算法d 算法又称为多维敏化，其基本思想：算法又称为多维敏化，其基本思想：从故障位置到电路的一切输出端的全部从故障位置到电路的一切输出端的全部

20、通路进行多维敏化！通路进行多维敏化！电子科大电子科大CATCAT室室2.2.1 基本数学关系基本数学关系 1.简化表简化表-d 算法的基础算法的基础(电路描述）电路描述）简化表是由真值表求简化表是由真值表求质蕴涵项质蕴涵项的方法整理出来的一种形式比真值表的方法整理出来的一种形式比真值表更紧奏更紧奏的一个的一个表，但不能丢失任何信息。表，但不能丢失任何信息。例：一或门例：一或门质蕴涵项质蕴涵项真值表真值表简化表简化表x1 x2 y1 2 3_0 0 01 x 10 1 1x 1 11 0 10 0 01 1 1x1x2123y12121122112112120()() 2yx xx xx xx

21、xxxx xx XXxyx x电子科大电子科大CATCAT室室2.2.1 基本数学关系基本数学关系可见：可见：u简化表比真值表简单，且电路愈复杂，简化愈多；简化表比真值表简单，且电路愈复杂，简化愈多；u简化表中每一行称为一个矢量，表示电路的输入简化表中每一行称为一个矢量，表示电路的输入/输出的因果关系；输出的因果关系；用同样方法可以求出其它基本电路的简化表：用同样方法可以求出其它基本电路的简化表：123123123 1 2 3 1 2 3 1 2 3 1 x 0 0 x 0 0 x 1 x 1 0 x 0 0 x 0 1 0 0 1 1 1 1 1 1 0 电子科大电子科大CATCAT室室2.

22、2.1 基本数学关系基本数学关系组合电路简化表：组合电路简化表：方法：方法：是简单门电路简化表的简单叠加。是简单门电路简化表的简单叠加。注意：注意：每一个门用它的信号输出点的代号命名；每一个门用它的信号输出点的代号命名；一个门输出点的标号应大于其它一切输入线的标号，以便作相容性运算；一个门输出点的标号应大于其它一切输入线的标号，以便作相容性运算；对于每一个顶点与其无关且标号比它小的项均为随意项（对于每一个顶点与其无关且标号比它小的项均为随意项（x)；例：例：123456简化表：简化表： 1 2 3 4 5 6 1 1 x 1 x 0 x 0G4 0 x x 0 1 1 x 1 x 0 x 0G

23、5 0 x x 0 0 0 0 x 1 1G6 1 x 1电子科大电子科大CATCAT室室2.2.1 基本数学关系基本数学关系2.传递传递d矢量矢量概念：概念：是迫使门电路的一个输入承担确定该门电路输出的全部责任。也就是说迫是迫使门电路的一个输入承担确定该门电路输出的全部责任。也就是说迫使门电路的输出唯一地取决于一个输入。使门电路的输出唯一地取决于一个输入。-敏化的赋值条件敏化的赋值条件方法：方法：用用Roth算法中的交运算为工具，从简化表中具有不同输出值的二个矢量相算法中的交运算为工具，从简化表中具有不同输出值的二个矢量相交得到。交得到。布尔交运算布尔交运算Roth交运算交运算0 1 x 0

24、 1 x_ 0 0 0 0 0 0 1 1 1 1 d 1 1 x 0 1 x x 0 1 x 定义：定义：d=1 0 =0 1dd电子科大电子科大CATCAT室室2.2.1 基本数学关系基本数学关系利用利用Roth交运算，可以方便求出各门电路的传递交运算，可以方便求出各门电路的传递d矢量：矢量：或门：或门：123简化表简化表 传递传递d矢量矢量1 2 31 2 31 x 11 1 1 无无d传递，不能敏化传递，不能敏化x 1 1d 0 d 能敏化，赋能敏化，赋00 0 00 d d 能敏化，赋能敏化，赋0同样可得其它门电路的传递同样可得其它门电路的传递d矢量矢量 1 2 31 2 3 1 2

25、 3 d 0 d 1 d d 1 0 d 1 d d 1 d 123123123可见，用计算方法确定了各通路上可见，用计算方法确定了各通路上各种门电路的赋值条件及敏化的故各种门电路的赋值条件及敏化的故障传播关系障传播关系dddd电子科大电子科大CATCAT室室3. 故障初始故障初始 d 矢量矢量概念：概念：为了在故障点得到一个为了在故障点得到一个d矢量而应加的测试矢量，就称为初始矢量而应加的测试矢量，就称为初始d矢量，即为矢量，即为故障表现故障表现 。方法：方法：正常逻辑表现与故障表现作正常逻辑表现与故障表现作Roth 交运算。交运算。例例1：故障在主输入端故障在主输入端1 0=d-故障初始故

26、障初始d矢量矢量例例2：故障在门输出端故障在门输出端正常表现正常表现 故障表现故障表现初始初始d矢量矢量1 2 3 1 2 3 1 2 3 =0 x 0 x x 0 0 x 0 x 0 0 x 0 01 1 11 1 d2.2.1 基本数学关系基本数学关系xS-a-0 d故障表现故障表现正常表现正常表现xS-a-0电子科大电子科大CATCAT室室2.2.1 基本数学关系基本数学关系4. d交交 d三种交运算：三种交运算：集合交运算（变量：集合交运算（变量：0，1，x；0与与1交为空集）；交为空集）；Roth 交运算（变量：交运算（变量：0，1，x；0与与1交为交为d或或 ）；）；Roth d

27、交运算（变量：交运算（变量：0，1，x，d， ；d 新的定义新的定义）；）；Roth d 交运算的定义：交运算的定义：说明：说明： d0 1 x d - d 交为空集交为空集 0 0 0 - d 交无意义交无意义 1 1 1 -d 与与 互换后，再互换后，再 d交交 x 0 1 x d -即为即为 d或或 d d 如如 与与 同时出现，矛盾，剔除同时出现，矛盾，剔除 dddddddd电子科大电子科大CATCAT室室2.2.2 d 交运算例交运算例42346713节点 门树根原始输出d 运算例：运算例：求求1-s-a-0的故障测试的故障测试解：解：（1）初始）初始d矢量：矢量：1 0=d（2）传

28、递）传递d矢量矢量由简化表得：由简化表得：G4= 1 2 3 4 5G5= x x 0 d d (3)用用 Roth d 运算求敏化通路运算求敏化通路 1 2 3 4 5 G4 d G5= x 1 0 d12345xS-a-0 ddd101 2 3 4 5d 1 x d x d（4）由敏化通路得到测试结果）由敏化通路得到测试结果 1-s-a-0，即，即 d=1 T=110;1 无故障测试；无故障测试； T=110;0 1-s-a-0故障测试；故障测试；可见，用可见，用Roth d 交运算可以方便交运算可以方便求出测试求出测试-利用数学工具，而不利用数学工具，而不是人为分析！是人为分析！电子科大

29、电子科大CATCAT室室1.2.2 穷举测试法的实施穷举测试法的实施2.2.3 d算法的实施步骤算法的实施步骤7树根原始输出d 算法的步骤如下：算法的步骤如下：1.初始化：初始化：（1）写出被测电路的简化表；）写出被测电路的简化表；（2）由简化表求出传递）由简化表求出传递d矢量；矢量；（3）写出故障初始）写出故障初始d矢量矢量-t0；（4）活动）活动d矢量矢量-d扇出；扇出；2.d 驱赶驱赶-多维敏化多维敏化方法：方法：将活动矢量与各自将活动矢量与各自d扇出有关的传递扇出有关的传递d矢矢量进行量进行d交运算，并反复进行，将一切敏化通路交运算，并反复进行，将一切敏化通路向前推进，使故障沿一切敏化

30、通路传播下去，一向前推进，使故障沿一切敏化通路传播下去，一直达到电路的一切主输出为止。直达到电路的一切主输出为止。3.相容性运算；相容性运算；4.求出测试矢量；求出测试矢量； t0111 t011 t0112 t0113 t012 t01 t013 t02t0 t03 t0n d算法的拓扑结构算法的拓扑结构电子科大电子科大CATCAT室室2.2.4 d算法举例算法举例-1.初始化初始化以以Schneider电路为例（电路见前）电路为例（电路见前）求：求： 6-s-a-0故障的测试。故障的测试。解：解：1.初始化初始化（1）写出被测电路简化表；）写出被测电路简化表；（2）由简化表作）由简化表作R

31、oth交运算，得传递交运算，得传递d矢量；矢量；（3）由故障表现）由故障表现6-s-a-0 求出初始求出初始d矢量，活动矢量，活动d矢量，矢量，d 扇出；扇出；电子科大电子科大CATCAT室室2.2.4 d算法举例算法举例-2.d驱赶驱赶2.d驱赶驱赶d 驱赶根据拓扑结构进行：驱赶根据拓扑结构进行：（1）t0 与与 G9, G10 作作 Roth d 交运算：交运算： 2 3 6 1 6 9 1 2 3 6 9t0 d G9= d = 0 0 d 0 d d 0 0 0 d d-t01-活动矢量（活动矢量（6，9），需扇出（），需扇出（9，10，12） d 0 d d 0 0 d - 无定义，

32、捨弃无定义，捨弃 2 3 6 4 6 10 2 3 4 6 10t0 d G10= d = 0 0 d 0 d d 0 0 0 d d-t02-活动矢量（活动矢量（6，10），需扇出（），需扇出（9，10，12） d 0 d d 0 0 d - 无定义，捨弃无定义，捨弃由此，得由此，得表表 2.2.6(P46)电子科大电子科大CATCAT室室2.2.4 d算法举例算法举例-2.d驱赶驱赶（2）t01 与与 G10，G12 作作 Roth d 交运算交运算 t02 与与 G9，G12 作作 Roth d 交运算交运算： 1 2 3 6 9 4 6 10 1 2 3 4 6 9 10t01 d G

33、10= d = 0 0 0 d 0 d 0 0 0 0 d -t011-，需扇出（，需扇出（12） d 0 0 0 0 d - 捨弃捨弃 1 2 3 6 9 8 9 10 11 12 1 2 3 6 8 9 10 11 12t01 d G12= d = 0 0 0 d 0 0 0 d 0 0 0 d 0 0 d -捨弃捨弃 0 0 d 0 0 0 0 d 0 d 0 -捨弃捨弃 0 d 0 0 0 0 0 d 0 0 0 -t012，已扇出到，已扇出到12 d 0 0 0 0 0 0 d d 0 0 -捨弃捨弃dddd dddddddddddddd电子科大电子科大CATCAT室室2.2.4 d

34、算法举例算法举例-2.d驱赶驱赶同上可得同上可得 t02 与与 G9，G12 作作 Roth d 交运算：交运算： 1 2 3 4 6 9 10t02 d G9= t021与与t011相同相同-扇出到扇出到12 0 0 0 0 d 2 3 4 6 8 9 10 11 12t02 d G10= t022-已扇出到已扇出到12 0 0 0 d 0 0 d 0 d综上可得综上可得d d电子科大电子科大CATCAT室室2.2.4 d算法举例算法举例-2.d驱赶驱赶（3）t011与与G12作作Roth d 交运算交运算 1 2 3 4 6 9 10 8 9 10 11 12 t011 d G12= d

35、0 0 0 0 d 0 0 0 d ！ 0 0 d 0 需要需要G12的的9和和10构成构成d矢量。矢量。 0 d 0 0 d 0 0 0 为此，通过为此，通过G12的简化表相继作交运算得到：的简化表相继作交运算得到：G12=（00001） （xx1x0) (x1xx0)=(00001) x11x0=0 0d 故有：故有： 1 2 3 4 6 9 10 8 9 10 11 12 1 2 3 4 6 8 9 10 11 12 t011 d G12= d = 0 0 0 0 d 0 0 d 0 0 0 0 d 0 0 d 得得表表 2.2.8已全部驱赶到主输出端已全部驱赶到主输出端12。t0111

36、ddddddddd dddd d电子科大电子科大CATCAT室室2.2.4 d算法举例算法举例-3.相容性运算相容性运算3.相容性运算相容性运算由上面由上面d驱赶，得出驱赶，得出6-s-a-0 故障的三个测试矢量：故障的三个测试矢量：t012, t022, t0111此三个测试是否都是此三个测试是否都是6-s-a-0故障的测试呢？必须作相容性运算（赋值是否矛盾？）故障的测试呢？必须作相容性运算（赋值是否矛盾？）（1）t012的相容性运算的相容性运算 见见表表2.2.9a.选取最大的顶点选取最大的顶点-G11c. 取取G8 3 7 112 5 8 x 1 0-G11(a)相容相容1 X 0-G8

37、(a) 2 矛盾矛盾 1 x 0 -G11(b) 3 矛盾矛盾 x 1 0-G8(b)相容相容 b.取取G10 d.取取G7 4 6 102 4 7 1 x 0-G10(a)相容相容0 0 1-G7 4 矛盾矛盾 x 1 0 -G10(b) 6 矛盾矛盾 可见，可见，t012不能满足相容性条件，即主输入端不能满足内部的赋值条件。不能满足相容性条件，即主输入端不能满足内部的赋值条件。同样，同样，t022也不满足相容性条件。也不满足相容性条件。因此，因此，t012,t022都不是一个测试，而都不是一个测试，而t0111满足相容性条件，是一个测试，满足相容性条件，是一个测试，表表2.2.10。电子科

38、大电子科大CATCAT室室2.2.4 d算法举例算法举例-4.测试矢量测试矢量4.测试矢量测试矢量 1 2 3 4 6 8 9 10 11 12 t0111= 见表见表2.2.8 0 0 0 0 d 0 0 d其中：其中：5=x，7=x 根据相容性运算（表根据相容性运算（表2.2.10)：5=1，7=1 1 2 3 4 5 6 7 8 9 10 11 12 t0111= 0 0 0 0 1 d 1 0 0 d所以有测试：所以有测试： 2路敏化路敏化T=0000；1无故障测试；无故障测试；T=0000；06-s-a-0测试，也可测试测试，也可测试9-s-a-1和和10-s-a-1故障；故障；d

39、dd d电子科大电子科大CATCAT室室2.3 扩展扩展d算法算法基本思想：基本思想：基于多路敏化，并以基于多路敏化，并以d算法为基础（算法为基础（d驱赶和相容性运算），利用驱赶和相容性运算），利用九值集合九值集合运算运算，求出电路的故障测试。，求出电路的故障测试。优点：优点：简洁直观，通用性强。简洁直观，通用性强。电子科大电子科大CATCAT室室2.3.1 九值运算九值运算-1.定义定义1.九值定义及九值集合运算九值定义及九值集合运算九值有：九值有： ，0，1，d， ，F， ，R，定义：定义：空集：空集：单元素集：单元素集：0，1，d，双元素集：双元素集：F=1Ud-与门赋值条件；与门赋值条

40、件； R=1U -与门赋值条件；与门赋值条件； =0U -或门赋值条件；或门赋值条件； =0Ud-或门赋值条件；或门赋值条件；u=0U1UdU =FURU U通集通集双元素集为敏化提供了更为灵活方便的赋值条件，本身就含有多路敏化的概念。双元素集为敏化提供了更为灵活方便的赋值条件，本身就含有多路敏化的概念。ddddRRFFdFR电子科大电子科大CATCAT室室2.3.1 九值运算九值运算-1.九值集合运算九值集合运算2.九值集合运算九值集合运算-扩展扩展d算法的数学基础算法的数学基础（1）交运算）交运算d F=d (1Ud)=d本页中：本页中：F R=(1Ud) (1Ud)=1 F=(0Ud)

41、(1Ud)=d 得表得表2.2.10R =(0Ud) (0Ud)=0d F=d (0Ud)= （2）与运算）与运算dF=d(1Ud)=dUd=dFR=(1Ud)(1Ud)=1UdUdUdd=1UdUdU0=u-通集通集 得得表表2.2.11(P50) = (0Ud)(0Ud)=0U0U0udd=0（3）或运算）或运算d+F=d+(1Ud)=(d+1)U(d+d)=1Ud=Fd+ =d+(0Ud)=(d+0)U(d+d)=dU1=F得得表表2.2.12R+ =(1Ud)+(0Ud)=(1+0)U(1+d)U(d+0)U(d+d)=1U1UdUd=1Ud=R + =(0Ud)+(0Ud)=(0+0

42、)U(0+d)U(d+0)U(d+d)=0UdUdU1=u-通集通集（4）非运算）非运算d=d = =得得表表2.2.13 RRRRRFFFFFdd FF电子科大电子科大CATCAT室室2.3.2 九值函数的原象九值函数的原象-1.概念概念1.概念：概念：一个集合一个集合X经逻辑网络输出一个集合经逻辑网络输出一个集合Y，其函数关系为：其函数关系为：Y=f(X)则，从则，从X Y就称之为就称之为映射映射；而，而，Y=f(X)称之为称之为映射函数映射函数；在上述映射中，取在上述映射中，取X集合的一个子集集合的一个子集X1，映射，映射有有Y集合的子集集合的子集Y1，如果有如果有y y1 x x1 时

43、，使得时，使得f(x)=y则则y1就是集合就是集合X1在映射在映射f(x)=y下的下的象象（正函数）（正函数）反之，如有反之，如有X的子集的子集x2，且，且注：注： -包含包含x X2 y y2 时，使得时，使得f(x)=y则，则， x2就是集合就是集合Y2在映射函数在映射函数f(x)=y下的下的原象原象（反向函数）（反向函数）Y=f(X)X集合集合Y集合集合电子科大电子科大CATCAT室室2.3.2 九值函数的原象九值函数的原象-2.例例2.例：例：上述概念以例说明上述概念以例说明从从X（x1,x2,x3) 到到 Y(y1,y2) 称为称为映射；映射；y1=x1x2y2=x2+x3X的全集为

44、：（的全集为：（000，001，010，.111）如取如取X的一个子集的一个子集X1=（00，11），映射有），映射有Y的子集的子集y1y1=x1x2=00=0y1=x1x2=11=1则则y1(0,1)就是就是X1（00，11）在映射函数）在映射函数y1=x1x2下的下的象象；反之，如有反之，如有y1(0,1)，有，有y1=x1x2=（00，01，10，11）则，则，X1=（00，01，10，11）就是集合）就是集合y1=x1x2=（0，1）在）在y1=x1x2映射下的映射下的原象；原象；求原象是扩展求原象是扩展d算法的基础算法的基础-反向思维！反向思维！x1x3y1=x1x2y2=x2+x3

45、Y=(y1,y2)x2X=(x1,x2,x3)映射函数；映射函数；电子科大电子科大CATCAT室室2.3.2 九值函数的原象九值函数的原象-3.原象的求法原象的求法3.原象的求法原象的求法或门或门说明说明：（：（1）xa表示表示x a，即，即x是集合是集合a中的元素；中的元素；（2）利用）利用表表2.2.12可求出可求出 f=xUy 的原象；的原象；(1) (x+y)d=xd(y0UydUyR)Uyd(x0UxdUxR)=xdyRUydxR -或门输出为或门输出为d的原象的原象因为：因为：R=（0Ud） 即即 yR=y0Uyd；xR=x0Uxd物理概念：物理概念：多路敏化多路敏化原象原象 象象

46、原象原象 象象xydR=0UddxyR=0Uddd注：本页中 R=R或电子科大电子科大CATCAT室室2.3.2 九值函数的原象九值函数的原象-3.原象的求法原象的求法(2) (x+y)d=xd(y0UydUyF)Uyd(x0UxdUxF)=xdyFUydxdF-或门输出为或门输出为d的原象的原象因为：因为：F=(0Ud)即即xF=x0Uxd，yF=y0Uyd物理概念：物理概念：(3) (x+y)F=xFyu+yFxu(4) (x+y)F=xfyF(5) (x+y)R=xRyuUyRxu(6) (x+y)R=xRyR(7) (x+y)0=x0y0(8) (x+y)1=x1yuUxuy1Uxdy

47、dUxdyd或xydF=(0Ud)dxyF=(0Ud)dd00011udd1FuF电子科大电子科大CATCAT室室2.3.2 九值函数的原象九值函数的原象-3.原象的求法原象的求法3.原象的求法原象的求法-与门与门利用利用表表2.2.11用同样方法可求出与门的原象用同样方法可求出与门的原象(1) (xy)d=xdyFUydxF(2) (xy)d=xdyRUxRyd(3) (xy)F=xFyF(4) (xy)F=xFyuUxuyF(5) (xy)R=xRyR(6) (xy)R=xRyuUxuyR(7) (xy)1=x1y1(8) (xy)0=x0yuUxuy0UxdydUxdyd对于多维函数用同

48、样方法也可求出原象！见对于多维函数用同样方法也可求出原象！见P52xydF=1UddUxyF=1Uddd电子科大电子科大CATCAT室室2.3.2 九值函数的原象九值函数的原象-立方表立方表立方表立方表为了使用方便，上述公式可用立方表列出为了使用方便，上述公式可用立方表列出（象）（象）Z = x + y（原象）（原象） （象）（象）Z = x y（原象）（原象）d d Rd d Fd R dd F dd立方立方d d Fd d Rd F dd R dF F uF F FF u FF F uF立方立方F F FF u FR u RR R RR R uR R uR立方立方R R RR u R0 0

49、 01 1 11 1 u0 0 u1 u 10 u 00/1立方立方1 d d0 d d1 d d0 d d电子科大电子科大CATCAT室室2.3.3 故障函数的原象故障函数的原象故障函数的原象故障函数的原象-初始初始d矢量（故障表现）矢量（故障表现）原象原象象象如何根据故障点的故障值如何根据故障点的故障值Y和映射函数和映射函数Z=f(x)的映射值，求出故障函数的原象的映射值，求出故障函数的原象X？其方法和规则如下：其方法和规则如下：（1）当）当Y Z= （空集）（空集） 时，则，时，则，X= ，原象，原象X不存在，不存在，即故障表现即故障表现Z集合中无故障值集合中无故障值Y ；（2）当）当Y

50、 Z=R（0Ud） d=d时，则，时，则，故障函数的原象为：故障函数的原象为：X=F=（1Ud）；）；X（测试（测试)x故障点故障点(故障值故障值Y）D矢量传递方向矢量传递方向故障表现故障表现Z=f(x)X=F=(1Ud)Y=R=(0Ud)xZ=d电子科大电子科大CATCAT室室2.3.3 故障函数的原象故障函数的原象（3）当）当Y Z=R（1Ud） d=d时，则，时，则，X=F=（0Ud）；）；例：例： xS-a-0YXZ故障值：故障值：Y=R=（0Ud)映射值：映射值：Z=d则：则：Y Z=（0Ud) d=d所以：所以：X=F=(1Ud)由与门的由与门的F立方有立方有 X x1 x2 F

51、F F故障函数的原象：故障函数的原象：F=(1Ud)x1,x2是主输入端，只取二值变量是主输入端，只取二值变量所以有所以有故障初始故障初始d矢量：矢量：x1=1, x2=1；x1x2电子科大电子科大CATCAT室室2.3.4 扩展扩展d算法的实施算法的实施1.敏化条件敏化条件（1）与门）与门如故障为如故障为 xrd =1，则敏化到，则敏化到 yd=1（为真）的条件为：（为真）的条件为：m xjF=1 F=1Udj=1j=r如故障为如故障为 xrd=1，则敏化条件为：，则敏化条件为：m xjR=1R=1Udj=1j=rF=(1Ud)F=(1Ud)xrxdF=(1Ud)dyd电子科大电子科大CAT

52、CAT室室2.3.4 扩展扩展d算法的实施算法的实施（2）或门）或门如故障为如故障为 xrd =1，则敏化到，则敏化到 yd=1（为真）的条件为：（为真）的条件为：m xjR=1 R=0Udj=1j=r如故障为如故障为 xrd=1，则敏化条件为：，则敏化条件为：m xjF=1F=0Udj=1j=rR=0Udxxrdyd电子科大电子科大CATCAT室室2.3.4 扩展扩展d算法的实施算法的实施（3）通路）通路敏化条件：敏化条件： v Sri = 1Sri 是各级单门的敏化条件是各级单门的敏化条件i=12.算法及步骤算法及步骤u初始化；初始化；u预处理；预处理；ud驱赶；驱赶；u一致性检查；一致性

53、检查；u判断与处理；判断与处理；电子科大电子科大CATCAT室室2.3.4 扩展扩展d算法的实施流程算法的实施流程扩展扩展d算法流程：算法流程：初始化初始化电路排序，故障表现，列出立方表，电路排序，故障表现，列出立方表，初始矢量初始矢量TC0，通路数，通路数K预处理预处理对传递表进行处理，主输入取二值（对传递表进行处理，主输入取二值（0，1）D驱赶驱赶TC1将测试矢量将测试矢量TC2中主输入变量取二值（中主输入变量取二值（0，1）相容性检验成功吗？相容性检验成功吗？故障遍历完否？故障遍历完否？K-1 KK=0？不成功不成功成功成功未完未完结束结束否否是是另选路径驱赶另选路径驱赶完完例：按扩展例

54、：按扩展d算法算法 流程求解流程求解Schneider 电路电路6-s-a-0故障的故障的 测试。有条件的同学测试。有条件的同学 可编写出该程序。可编写出该程序。电子科大电子科大CATCAT室室2.4 布尔差分法布尔差分法拓扑方法：通路敏化法，拓扑方法：通路敏化法，d算法，扩展算法，扩展d算法等；算法等；敏化通路概念敏化通路概念分析方法：布尔差分法分析方法：布尔差分法-用数学解析法求解测试；用数学解析法求解测试；解析法的优点：普遍性，完备性（单故障测试，多故障测试），通用性；解析法的优点：普遍性，完备性（单故障测试，多故障测试），通用性；电子科大电子科大CATCAT室室2.4 布尔差分法布尔差

55、分法 布尔差分法由布尔差分法由Sellers等人提出，是组合电路测试生成的一种方法。等人提出，是组合电路测试生成的一种方法。其主要特点是将电路描述抽象为数学表达式模型，从而可进行严其主要特点是将电路描述抽象为数学表达式模型，从而可进行严密的数学推导，因而具有较高的理论研究价值。这种方法通过对密的数学推导，因而具有较高的理论研究价值。这种方法通过对数字电路的布尔方程模型进行差分运算，能获得测试矢量集的一数字电路的布尔方程模型进行差分运算，能获得测试矢量集的一般表达式，并能求出所给故障的全部测试矢量，因此具有理论上般表达式，并能求出所给故障的全部测试矢量，因此具有理论上的完备性。的完备性。电子科大

56、电子科大CATCAT室室2.4.1 布尔差分法的基本概念布尔差分法的基本概念布尔差分的定义：布尔差分的定义：一布尔函数：一布尔函数：y(x)=y(x1,x2,.xi,.xn)对对xi的布尔差分定义为：的布尔差分定义为：含义：含义：连续函数的差分（微分）连续函数的差分（微分）dy/dx 表示对应于表示对应于 x 无穷小增量的无穷小增量的 y 的增量。的增量。在布尔代数中，在布尔代数中，x和和y值只能为值只能为 0或或1，因而，因而，x和和y的增量只能为的增量只能为 1。所以有如下关系：。所以有如下关系：),.,.,(),.,.,()(2121ininixxxxyxxxxydxxdyxxydxxd

57、yx)(lim)(0电子科大电子科大CATCAT室室2.4.1 布尔差分法的基本概念布尔差分法的基本概念布尔差分关系表：布尔差分关系表：变量变量关系式关系式可能取值可能取值dxdx= x =xi-xi 1yy=y(x1,x2,xi,xn)0,1,0,1yy=y(x1,x2,xi,xn) 0,1,1,0dydy= y=y-y=y y0,0,1,1差分差分dy/dx= y/ x0,0,1,1异或异或y y0,0,1,1由上表可以看出，布尔差分的定义是正确的，其概念与连续函数的差分完全一样。由上表可以看出，布尔差分的定义是正确的，其概念与连续函数的差分完全一样。注意：在高等数学的微积分中，只有连续函

58、数才能求差分，布尔函数是不连续函数，注意：在高等数学的微积分中，只有连续函数才能求差分，布尔函数是不连续函数， 在布尔空间中也可求差分！在布尔空间中也可求差分！电子科大电子科大CATCAT室室2.4.1 布尔差分法的基本概念布尔差分法的基本概念利用布尔差分求测试的概念：利用布尔差分求测试的概念：如果：如果：表示输出表示输出 y 能响应能响应 xi 的变化的变化-能对能对 xi 敏化，有敏化通路，可求出敏化，有敏化通路，可求出 xi 的故障测试；的故障测试；如果：如果：表示输出表示输出 y 不能响应不能响应 xi 的变化的变化-不能对不能对 xi 敏化，即不能求出敏化，即不能求出 xi 故障测试

59、。故障测试。此结论与第一章的数据域测试的解析法结论是一致的！此结论与第一章的数据域测试的解析法结论是一致的！1),.,.,(),.,.,()(2121ininixxxxyxxxxydxxdy0),.,.,(),.,.,()(2121ininixxxxyxxxxydxxdy电子科大电子科大CATCAT室室2.4.1 布尔差分法的基本概念布尔差分法的基本概念例：利用前面通路敏化法的电路为例例：利用前面通路敏化法的电路为例yxS-a-1x1x2x3x4根据电路图有：根据电路图有：为了求为了求 x1-s-a-1 的故障测试的故障测试y 对对 x1 求布尔差分，有：求布尔差分，有：1)(21 xdxxd

60、y求解布尔差分方程：求解布尔差分方程：解为：解为：X1-s-a-1,故故x1=0 x2=1x3=x4=x测试矢量为：测试矢量为： 0100 0101 0110 0111与前面测试结果相同！利用布尔差分可以求出电路的测试解！与前面测试结果相同！利用布尔差分可以求出电路的测试解！12234yx xxxx112234223421()()dyx xxxxx xxxxxdx电子科大电子科大CATCAT室室2.4.2 布尔差分的特性布尔差分的特性从上述分析可知，利用布尔差分法求解电路的测试，关键在于解布尔差分方程。为了从上述分析可知，利用布尔差分法求解电路的测试，关键在于解布尔差分方程。为了方便差分方程的