一，简介

         测试生成：一是保证故障在其源处的再现，二是把故障效应传播到电路的某一原始输出

          组合电路的测试生成是一个NP-complete 问题

          所有的算法都基于4 个最主要的操作过程：激活（excitation）、敏化（sensitization）、确认（justification）和蕴涵（implication）。

二，异或法

       1, 异或法

            f (x)   ⊕   f_f (x)  = 1 ,     l类似 fault  ⊕   truth  = 1 ,   求解pattern

       2，不可检测故障       

具有故障冗余的电路是指，该电路存在且只存在一条线，当这条线被去掉并用适当
的逻辑常数（0 或1）代替时，它所实现的功能不变，否则就称该电路是非故障冗余电路。

对于组合电路，不可测故障只存在于重聚的扇出分支或路径上，判断方法如下：假定i
是电路中的冗余线，如果i 可以去掉并由逻辑常数g （g 为0 或1，但不能既为0 又为1）代
替，那么故障i /g 是不可测故障，但故障i /g 是可测故障；如果 i由 g 与g 均可代替，则故障
i /g 是不可测故障。

3,  多输出电路

对于多输出电路，每个输出都可以使用    F_p/d = f(x) ⊕  f_p/d(x) , 如果为零，则表示此处p处stuck at d不可观测。

对于m输出，则有   F^p/d  = F₁^p/d  +   F₂^p/d  + ...  +   F_m^p/d

_{三，布尔差分法}

         _{逻辑综合要大量用到布尔函数的特殊形式----开关函数。}

        1，f (x₁,..., x_i = 0,..., x_n )  ⊕ f (x₁,..., x_i =1,..., x_n ) =1   ,     布尔函数F(x) = F(x₁,..., x_i ,..., x_n )   对 变量 x_i的差分定义为

                                                    dF(x) / dx_i    =   F(X_i)   ⊕  F(X_i^-)

              如果 s-a-0,  则  x_i  (dF(x) / dx_i )  =   1,    如果 s-a-1,  则  x_i^- (dF(x) / dx_i )  =   1     。  这个结论，我也没弄明白，可能是跟开关函数的Shannon 展开式有关。

                                 f (x₁, x₂ ,..., x_n ) = x_i f (x₁, x₂ ,..., x_i =1, x_n ) + x_i^- f (x₁, x₂ ,..., x_i = 0, x_n )

四，路径敏化法

        路径敏化法（path-sensitizing method）的原理是从故障源处到原始输出之间寻找一条路径，这条路径就称为敏化路径（sensitized path），沿着这条路径，故障效应可从源处传播到原始输出，也就是故障效应可观。

        1，激活故障  2，敏化传播   3，确认（向前追踪）  4，蕴含（向后追踪）   5，一致性检查

               主要过程：为了对一条线的上的SSA 故障进行测试生成，首先对故障激活，然后把此故障激活后的效应沿路径敏化到原始输出，如果故障激活后的效应在原始输出可观察到，则对敏化路径上的其他线的值

                               予以确认，再对不在敏化路径上的其他门逻辑值予以蕴涵，最后获得原始输入的值，也就是测试图形

         2，无扇出的路径敏化

        3，有扇出的路径敏化 

扇出分支对路径敏化的影响可归纳为3 种情况：
单路径或多路径均可产生测试图形；
只有单路径可产生测试图形；
只有多路径可产生测试图形。

五， D算法

      1，奇异立方                

               函数的奇异立方就是函数真值表的压缩表示法。

       2，D立方                              

              d 表示电路无故障时输出为1，有故障时输出为0； d^-反之

              

              把元器件输入端的故障效应传播到元器件输出端的最小输入条件叫做传播d 立方（propagate d-cube），它表明了建立敏化路径的条件，也是对被测电路的结构描述。

              d 驱赶：逐级将故障信号d(d^-)从故障源处敏化至原始输出的过程叫 d驱赶（d drive）

               d 交运算是建立敏化路径的数学工具

                

             3，D算法的基本步骤

                （1） 建立失效的d立方，激活故障

                （2）选择敏化路径

                （3）沿敏化路径传播PDCF，按d交运算驱赶，驱赶过程中对电路节点赋值

                （4）如果d或d- 出现在原始输出，则驱赶成功

                  (5)   进行一致性检查

 六,  PODEM算法

          PODEM（Path Oriented Decision Making）算法首先由Goel 提出，实际上是一个程序，它使用了D 算法的一些术语，吸收了穷举法的优点，对D 算法进行了有益的改进。

           PODEM 算法的思路：对激活的故障向后追踪到原始输入，搜索所有可能的原始输入赋值，只要找到一个符合要求的即可作为测试图形，算法即结束。对于确定的故障，

           首先是确定目标，然后对连接到门的输入线选择原始输入赋值

 

七，其它算法

          1，FAN算法            

FAN（fan-out-oriented）算法发展了PODEM 算法的向后追踪概念，对PODEM 算法的穷
举过程中无测试的分支予以剔除，主要思路是：
向后追踪不仅仅止于原始输入，也可以止于中间节点；
生成过程中不仅仅是满足一个目标，而是采用多路径向后追踪步骤尽可能同时满足多
个目标。
为了达到上述目的，FAN 算法采取了以下措施：
在算法的每一步，尽可能多地确定可以惟一蕴涵的信号的值；
对被测故障惟一确定或蕴涵的信号赋值d 或d ；
向后追踪止于主线，只在最后对主线进行线确认；
当D 域只包含一个元器件时，敏化路径惟一地确定；
选择多路径敏化，其效率比单路径敏化高；
在多路径向后追踪过程中，如果目标在扇出节点上赋值出现不一致，停止向后追踪，
对扇出节点赋不同的值。