组合电路求测试码的D算法

组合电路求测试码的D算法D算法〔D-algorithm〕是一种用形式化运算求测试码的多路径敏化法。D算法的根本思想与单路径敏化法同。也是把故障传播到输出端、同时确定输入向量和其他信号值，区别在于D算法采用立方体运算，并考虑到多路径的情况。一、D立方及其运算

1、布尔函数的立方体表示

设布尔函数的一般表达式为：y=f(X1,X2,……Xi……Xn)其中y〔=0/1/u〕为输入变量,Xi(=0/1/X)为输入变量。令每一个输入变量和一个坐标轴相对应，那么可得到函数y的空间图形，即立方体表示。输入为三变量时，卡诺图和立方体符号的对立关系如以下图：一、D立方及其运算

记号D和~D1/0---

D正常=1,故障=0，即故障s-a-00/1---

~D正常=0,故障=1，即故障s-a-1

2、故障原始D立方(pdcf)

故障原始D立方(pdcf)表示故障点作为输出端的元件，当输出端为D或~D时的输入端向量组成的立方体集合。

求pdcf的方法:无故障元件覆盖G与有故障元件覆盖B作pdcf交.一、D立方及其运算pdcf交的规那么:1>输入局部pdcf交的规那么如右表2>输出局部pdcf交的规那么如下表3>假设步骤1，2中交的结果出现q那么故障原始D立方为空GB01X00q01q11X01x一、D立方及其运算一、D立方及其运算一、D立方及其运算3、传播D立方(pdc)〔描述一个元件对D/~D的传播特性〕元件的输入和输出端都有D/~D出现一重传播D立方(pdc)〔输入方只有一个D/~D〕求法：1>求元件的质覆盖G(输出为0的g0,输出为1的g1)2>g0,g1作pdc交(规那么如下表〕一、D立方及其运算例:与非门质覆盖G已给出g1与g0作pdc交{~D1|D,1~D|D}相反:g0与g1作pdc交{D1|~D,1D|~D}两者互补表示任一输入端为1时,可以将D/~D传到输出端。假设有一个输入端为1时，另一个输入端的D或~D可以传到输出端，分别为~D或D一、D立方及其运算多重传播D立方〔输入方有两个以上D/~D〕求法:1>先对元件的质覆盖中的各个立方体两两相交,得到各个面，进而求出立方复合体K=C∪〔C∩C〕2>g0,g1作pdc交(规那么同一重传播D立方〕例：与非门多重传播D立方一、D立方及其运算

4、测试D立方:对电路中的各信号依次排列

求各个路径上D的传播的一种运算，一般是测试立方与其它立方体〔包括故障原始D立方．传播D立方，质立方等〕作D交，得到新的测试D立方。5、D交:二、D算法用D立方运算实现的敏化路径法步骤：1》根据故障原始D立方确定一个初始测试D立方．初始测试D立方中包含故障点的D或~D2》从初始测试D立方出发，将故障D或~D向输出端传播，称D驱赶。传播时根据测试D立方中的D或~D查找相应信号节点的负载元件．对这些元件进行计算：用测试D立方与元件的传播D立方作D交，从而得到新的测试D立方。对每个测试D立方需要作D驱赶的负载元件的集合，称为D前沿。3》D驱赶过程中，对某些己经能够确定的值要及早确定．称为求蕴函。同时要对没有赋值的信号节点确定值，称为线确认。在求蕴函线确认的过程中要检查所求的值是否有予盾，统称为一致性操作或C驱赶。在每次求得新的测试D立方时都要做一致性操作的元件集合称为C前沿．4》D驱赶和一致性操作过程中都会出现测试D立方为空。这时要回溯，返回最近的选择点重新进行D驱赶和一致性操作5》如果D/~D出现在输出端，输入端的值也已经确定，同时一致性操作也已成功，那么D算法成功．找到测试向量。如果在回溯过程中已无任何选择可能，那么算法失败，未找到测试。二、D算法例：以下图，求e点s-a-1的测试向量二、D算法先求故障e的故障原始D立方，以及各原件的质覆盖和传播D立方二、D算法D算法执行过程如下表：二、D算法(1)开始，将故障e的一个故障D立方{0X|~D}作为初始测试D立方tc0,其D前沿为{G}，C前沿为空。(2)做D驱赶，用G的传播D立方{0~D|~D}与tc0作D交,得tc1,g的负载原件有J和I，作为新的D前沿，C前沿仍为空。(3)选J做D驱赶，用J的传播D立方{1~D|D}与tc1作D交,得tc2,又得新的D前沿元素L，放入D前沿栏中，C前沿仍为空。(4)选L做D驱赶，得tc3。D到达输出端，但C前沿中有K，需要做一致性操作。(5)选K的一个质立方与tc3作D交,得tc4。这时D前沿中又有元素I，再做一致性操作。(6)选I的质立方{1|0}与tc4作D交,结果为空。(7)回溯到tc3，选