D算法，是拓?fù)浣Y(jié)構(gòu)測試中最經(jīng)典的方法，也是最早實(shí)現(xiàn)自動化的測試生成算法之一。是由Roth在1966年提出的，此后又有許多人在此基礎(chǔ)上作了改進(jìn) ，從而使 D算法達(dá)到了實(shí)用的階段。D算法適用于計算機(jī)編程操作 ，如用手工計算則顯得繁瑣。

ATPG

之前介紹了故障模型(Fault Model)，在晶體管級或門級對物理缺陷建模后，為實(shí)現(xiàn)測試自動化已奠定好了基礎(chǔ)。

那么如果想測試下圖電路中H處的SA1，該如何去測試呢？

經(jīng)過簡單的分析可知，通過控制輸入端ABC的值，在輸出端K點(diǎn)進(jìn)行觀測，如果輸出結(jié)果與期望一致，則電路沒有故障，如果不一致，則說明有故障。通過分析，可以推出應(yīng)該給A端輸入0，B、C端則至少輸入一個1，用X來表示既可以選1也可以選0，那么可以得知ABC的輸入應(yīng)為01X/0X1。輸入端按順序組合的0、1和X被稱為測試向量（Test Pattern）。對于簡單的電路，我們可以自己進(jìn)行分析，但對于復(fù)雜的電路，就必須依賴工具去進(jìn)行自動化的生成測試向量。今天要介紹的D算法就是來實(shí)現(xiàn)測試向量的自動化生成的。

D算法思想

首先在學(xué)習(xí)算法前，有一些定義需要先了解一下。首先是D算法中定義的5個值：0，1，X，D，D'。其中X既可以是0，也可以是1，表示選什么值都不會對測試有影響。D=1/0，指正常值為1，故障值為0，同理有D'=0/1。在測試某個故障的第一步，是先激活該故障，也就是在故障點(diǎn)形成D或D'。接下來需要將D或D'往輸出端傳播，使得我們可以觀測到結(jié)果進(jìn)而與期望值進(jìn)行對比，這個過程稱之為傳播。在往輸出端傳播的同時，需要確定其它內(nèi)部節(jié)點(diǎn)的值，最終確定所有輸入端的值，比如上面例子中通過G4的值來確定G3的值，這個過程稱之為合理化。值得注意的是，在測試向量生成過程中，往往有多種選擇可以實(shí)現(xiàn)同一目標(biāo)，這時我們需要做選擇。另外，在合理化的過程中，有些值的設(shè)定可能會影響其它值或是電路，甚至發(fā)生沖突，這時我們需要返回到上一次做選擇的節(jié)點(diǎn)，做出另外一個選擇，這個過程稱之為回溯。在傳播階段，一個輸入端上至少有一個尚未傳播至門輸出的D或D'，稱之為D邊界：

在合理化階段，輸出端為已知但輸入端還未確定的電路門，稱之為J邊界：

D算法整合了前面所介紹的故障激活、傳播、合理化和回溯等流程，通過定位D邊界和J邊界然后確定其電路值，并采用電路線路值表格來呈現(xiàn)這些過程的結(jié)果，最終得到我們想要的測試向量。

D算法舉例

接下來我們以一個較為復(fù)雜的電路故障來舉例說明通過D算法來產(chǎn)生測試向量的過程。

如圖所示，對于這樣一個電路，abcdhjf是輸入端，G5是輸出端，D算法首先是將故障激活，然后將D向輸出端傳播的同時也向輸入端進(jìn)行合理化，并且每次都進(jìn)行回溯，檢查是否出現(xiàn)矛盾，最終當(dāng)D傳播到輸出端時，這時輸入端所對應(yīng)的值即為測試向量，根據(jù)下表所示，最終可以確定，測試向量為abcdhjf=11111xx。

?更多算法

D算法是第一個完備的ATPG算法,也是當(dāng)下主流的ATPG算法。它的主要思想是逐級敏化從故障源到電路所有輸出的全部可能的通路。但對于測試而言，我們想要的是一個輸入組合，而不是內(nèi)部線路值，因此在D算法之后，又衍生出一些優(yōu)化算法，如PODEM，F(xiàn)AN，CPT等等，不同算法的思想、方法各有不同，但目的都是相同的。作為ATPG算法的鼻祖，學(xué)習(xí)D算法的思想的流程對我們將來從事DFT行業(yè)是非常有益的。