表7.9 D算法执行过程
tc a b c d e f g h i j k l 操作 DF CF
0   0 X   D     pdcf1(es-a-1) G φ
1  0 0 X   D D     D驱赶(G) J,I φ
2 1 0 0 X   D D D   D驱赶(J) L,I φ
3 1 0 0 X   D D  D 0 D D驱赶(L) I  
4 1 0 0 X   D D X 0 D 0 D 一致性操作(K1) I  
5      1 0     一致性操作(I) I φ
       φ     失败    
3 1 0 0 X   D D  D 0 D 回溯 I K
6 1 0 0 X   D D 0 X D 0 D 一致性操作(K2) I H
7 1 0 0 1   D XD 0 X D 0 D 一致性操作(H) I φ

  D算法对一个故障寻找一个测试向量。如果在选D立方时次序不同,有可能找出的测试向量不同。
  在电路中存在再会聚路径时,只要在选传播D立方时也使用二维D立方或多维D立方,就可实现多路径的敏化。读者可以按照D算法步骤求图7.8 电路的测试向量。可以证明,对于任何非冗余组合电路,都可以用D算法找到测试码。
  对于复杂电路,D算法的时间开销往往很大。为了减少失败的几率,减少回溯次数,常采用一些启发式措施:
  (1)DF中选取离输出端较近的元件;
  (2)CF中选取离输入端较近的元件,选取已知输入端值较多的元件;
  (3)pdc中选取D和
D一致的D立方。
  (4)二重或多重D立方仅当需要时才引入。
  (5)一致性操作用到pdc时选取未知信号为非D者。
  
D算法是一个经典的算法,几乎所有的测试码生成软件都采用D算法。但是D算法也存在不少问题:(1)也不是所有故障都能检测出来,(2)算法中出现大量回溯过程,致使算法运行时间较长。因此许多人在D算法的基础上又提出许多新的算法,因篇幅所限,本书不作介绍。同学们在学习时,要着重理解其基本思想。