D算法介绍
D算法，是拓扑结构测试中最经典的方法，也是最早实现自动化的测试生成算法之一。是由Roth在1966年提出的，此后又有许多人在此基础上作了改进 ，从而使 D算法达到了实用的阶段。D算法适用于计算机编程操作 ，如用手工计算则显得繁琐。
ATPG
之前介绍了故障模型(Fault Model)，在晶体管级或门级对物理缺陷建模后，为实现测试自动化已奠定好了基础。
那么如果想测试下图电路中H处的SA1，该如何去测试呢？
经过简单的分析可知，通过控制输入端ABC的值，在输出端K点进行观测，如果输出结果与期望一致，则电路没有故障，如果不一致，则说明有故障。通过分析，可以推出应该给A端输入0，B、C端则至少输入一个1，用X来表示既可以选1也可以选0，那么可以得知ABC的输入应为01X/0X1。输入端按顺序组合的0、1和X被称为测试向量（Test Pattern）。对于简单的电路，我们可以自己进行分析，但对于复杂的电路，就必须依赖工具去进行自动化的生成测试向量。今天要介绍的D算法就是来实现测试向量的自动化生成的。
D算法思想
首先在学习算法前，有一些定义需要先了解一下。首先是D算法中定义的5个值：0，1，X，D，D'。其中X既可以是0，也可以是1，表示选什么值都不会对测试有影响。D=1/0，指正常值为1，故障值为0，同理有D'=0/1。在测试某个故障的第一步，是先激活该故障，也就是在故障点形成D或D'。接下来需要将D或D'往输出端传播，使得我们可以观测到结果进而与期望值进行对比，这个过程称之为传播。在往输出端传播的同时，需要确定其它内部节点的值，最终确定所有输入端的值，比如上面例子中通过G4的值来确定G3的值，这个过程称之为合理化。值得注意的是，在测试向量生成过程中，往往有多种选择可以实现同一目标，这时我们需要做选择。另外，在合理化的过程中，有些值的设定可能会影响其它值或是电路，甚至发生冲突，这时我们需要返回到上一次做选择的节点，做出另外一个选择，这个过程称之为回溯。在传播阶段，一个输入端上至少有一个尚未传播至门输出的D或D'，称之为D边界：
在合理化阶段，输出端为已知但输入端还未确定的电路门，称之为J边界：
D算法整合了前面所介绍的故障激活、传播、合理化和回溯等流程，通过定位D边界和J边界然后确定其电路值，并采用电路线路值表格来呈现这些过程的结果，最终得到我们想要的测试向量。
D算法举例
接下来我们以一个较为复杂的电路故障来举例说明通过D算法来产生测试向量的过程。
如图所示，对于这样一个电路，abcdhjf是输入端，G5是输出端，D算法首先是将故障激活，然后将D向输出端传播的同时也向输入端进行合理化，并且每次都进行回溯，检查是否出现矛盾，最终当D传播到输出端时，这时输入端所对应的值即为测试向量，根据下表所示，最终可以确定，测试向量为abcdhjf=11111xx。
更多算法
D算法是第一个完备的ATPG算法,也是当下主流的ATPG算法。它的主要思想是逐级敏化从故障源到电路所有输出的全部可能的通路。但对于测试而言，我们想要的是一个输入组合，而不是内部线路值，因此在D算法之后，又衍生出一些优化算法，如PODEM，FAN，CPT等等，不同算法的思想、方法各有不同，但目的都是相同的。作为ATPG算法的鼻祖，学习D算法的思想的流程对我们将来从事DFT行业是非常有益的。
