組合電路的測試生成

1、第二章 組合電路的測試生成2.1 組合電路的測試生成組合電路的測試生成（Test Generation）就是對給定電路的給定故障來確定測試的過程。測試生成要解決的兩個主要問題是：一是保證故障在其源處的可觀性，二是能把故障效應(yīng)傳播到電路某一原始輸出端。另外故障覆蓋率與測試成本也是測試生成要考慮的重要因素。測試生成的方法比較多，但是應(yīng)用時都有局限性，因此測試生成過程是測試環(huán)節(jié)的一個瓶頸。測試生成按測試矢量的確定方法可分為確定性測試生成和非確定性測試生成。確定性測試生成就是采用算法自動生成測試矢量的方法，用此種方法進行測試生成時，測試生成器一般需要測試情形（test view）描述。測試情形是門級的

2、電路描述，它是實際的電路結(jié)構(gòu)（晶體管級描述）的一種近似表達。采用測試情形可以簡化測試生成過程，大量實驗表明，在門級生成的測試矢量，可以檢測出大多數(shù)晶體管級的缺陷。非確定性測試生成是一種由人工進行的測試生成，也就是測試人員根據(jù)被測對象的功能、測試經(jīng)驗，用人工產(chǎn)生測試矢量；另一種是用軟件或電路產(chǎn)生隨機測試矢量，對電路進行窮舉或偽窮舉測試。測試生成方法按其生成的手段可歸為兩大類：代數(shù)法及算法。代數(shù)法是根據(jù)描述電路功能的布爾等式求解出測試矢量，其主要缺點是占用存儲空間大，當(dāng)電路復(fù)雜時，不存在或很難求得布爾等式。算法則是使用各種電路機理跟蹤、敏化路徑，使得故障效應(yīng)傳播到電路的原始輸出，然后給原始輸入分配

3、滿足故障傳播和生成條件的值。代數(shù)方法的測試生成典型的例子就是采用布爾差分法，本章我們把它用到組合電路種，但是也可以用到時序電路中，不過對于大規(guī)模集成電路，則該方法難以有效。但是該方法使得路徑敏化的理論得到系統(tǒng)化，因此布爾差分法和布爾微分法在測試理論中占有重要地位，是進行理論研究的必要工具和基礎(chǔ)。Goel提出算法的執(zhí)行時間與電路中門的個數(shù)的平方成正比。由于測試生成的如此復(fù)雜，就有一些迭代方法的提出，最著名的是方法是D算法，PODEM算法，F(xiàn)an算法和SOCRATES算法。所有的算法都基于四個最主要的操作過程：激活（excitation）、敏化（sensitization）、確認（justific

4、ation）和蘊涵（implication）。2.2 異或法2.2.1 異或法（Exclusive-OR method）異或法是測試生成最簡單的方法，它是根據(jù)描述電路的功能函數(shù)求解出測試矢量的代數(shù)方法。無故障時電路開關(guān)函數(shù)為f，有故障p/d時電路的開關(guān)函數(shù)記為fp/d，應(yīng)用代數(shù)運算就可得到故障p/d的所有測試集，我們用Fp/d表示：Fp/d就是滿足上式條件的最小項的集合。 異或法直觀，但是計算過程冗長、繁瑣，對于重聚的扇出電路有可能找不到測試生成，在實際中他只是作為驗證的方法。圖2.1對于圖2.1中的故障1/0，其最小項，也就是說1/0故障的測試矢量式110。對于故障3/0，有其最小項有，因此

5、故障3/0的測試向量應(yīng)為001，010，011。圖2.1中的電路比較簡單，因此用異或法確定其測試向量較為簡單，對于圖2.2中的電路，如果用異或法則計算過程就比較冗長繁瑣。圖2.2圖2.2中的電路故障6/0，其測試矢量可見故障6/0的測試矢量是比較多的，對于實際中的電路還要比圖2.2中的電路復(fù)雜，異或法可能就不具實用性。對于有重聚的扇出電路可能找不到測試生成，實際中只是作為驗證方法。2.2.2 不可測故障一故障p/d如果存在至少一個測試矢量的話，則說此故障是可測的。但是對于重聚的扇出的電路，并非所有的故障都是可測試的，這樣的故障叫做不可測故障。對于圖2.3(a)中的故障13/0，就是屬于不可測故

6、障。圖2.3 不可測故障因此故障13/0不存在測試矢量，這就提出了一個問題：如何確認不可測故障。這需要研究邏輯電路中的冗余問題，一電路具有冗余是指，該電路存在且只存在一條線，該線被去掉或由適當(dāng)?shù)倪壿嫵?shù)（0或1）代替后，實現(xiàn)的功能不變。如圖2.3（a）中，線13用0代替后所得的電路2.3（b）實現(xiàn)的功能與2.3（a）相同，因此線13是冗余的。不可測故障只存在于具有冗余的電路中，其判斷方法如下：i代表電路中的冗余線，如果i可以去掉或由一邏輯常數(shù)a（a為0或1，但不能既為0又為1）代替的話，那么故障i/a是不可測的，但故障是可測的；如果i可由a和代替的話，那么故障i/a和均不可測。冗余也是在電路設(shè)

7、計中所需要注意的一個問題，因為冗余不但增加了電路的復(fù)雜程度，還有可能給電路的測試帶來困難。2.2.3 多輸出電路實際中大多數(shù)電路輸出端不止一個，也就是說電路實現(xiàn)不止一個功能。圖2.4描述了一個二輸出端子的電路，當(dāng)對這樣的電路生成測試矢量時，兩個輸出函數(shù)都應(yīng)該考慮。假定Fp/d表示故障p/d所有可能的測試矢量的布爾函數(shù)表達，就有：F1p/d和F2p/d分別表示對故障p/d在f1,f2輸出端所有的測試矢量。對于圖2.4中電路的故障1/0：0圖2.4 多輸出電路F21/00，因此故障1/0在f2不可觀。一般來說，如果一電路具有m個輸出的端子，對于故障p/d測試矢量就為：2.3 布爾差分法2.3.1布

8、爾一階差分布爾差分法是組合邏輯電路測試矢量生成的一種代數(shù)方法，其描述嚴格而簡潔，物理意義清晰，因而在研究組合邏輯電路測試的理論和方法時具有重要的意義。為了敘述方便，本節(jié)中采用下述符號：對于開關(guān)函數(shù)（布爾函數(shù)），定義：布爾函數(shù)對變量xi的偏差分定義為上式的意義是：當(dāng)xi變化時，其對應(yīng)的的異或結(jié)果為1時，相應(yīng)的電路輸出反映了xi的變化，即xi是可測的，反之xi是不可測的。對此函數(shù)可推導(dǎo)出以下性質(zhì)：(i)這里的表示的反，xi是自變量(ii) (iii) (iv) (v) (vi)如果與xi無關(guān)，那么：2.3.2布爾一階差分法檢測電路的故障圖2.5對于如圖2.5所示的組合電路中的故障f2/1，用布爾差

9、分法來檢測時，先將其實現(xiàn)的功能f對變量f2求差分。求解其測試矢量時，應(yīng)該根據(jù)下面兩式來確定：上面兩式合并起來可得：即：1上式的解為：x1x2x3x4=0000,0001,0010,0100,0101,0110,1000,1001,1010，其中任意一個都是故障f2/1的測試矢量。布爾差分的結(jié)果如果為1，則表明fi的變化將導(dǎo)致函數(shù)的值的變化；否則fi的變化對的值無影響。因此我們可以建立檢測s-a-0故障的邏輯等式：；即：對于fk的s-a-1故障，其檢測時的邏輯等式為：；即：利用上面的等式可以求解出其測試矢量。2.3.3 高階布爾差分一階布爾差分主要用來求單故障測試矢量集。如果要求多故障的測試矢量

10、集，就必須引入高階布爾差分的概念。這里主要敘述二階布爾差分及其雙故障測試矢量集的求法。更高階的布爾差分和多故障測試矢量集產(chǎn)生的方法可依此類推。函數(shù)其對變量xi的一階偏差分和一階微差分相同，即：而對于二階布爾偏差分的定義為：二階布爾微差分定義為：二階布爾偏差分與二階布爾微分的關(guān)系為：檢測雙故障的測試集為：其中，為0或1，。 2.4 路徑敏化法一維路徑敏化法是測試生成的第一個方法，其原理是從故障點到輸出之間敏化一條路徑，將故障效應(yīng)傳播到輸出端，其步驟如下：1）推導(dǎo)測試矢量，使得故障在其源點可觀。例如，對于s-a-1故障，在其源處出現(xiàn)的條件是邏輯“0”；2）選擇一條路徑，沿此路徑，故障效應(yīng)可傳播到電

11、路輸出；3）對于選定的路徑上的元件，給定輸入變量，使得該元件的輸出值僅由路徑上連接到該元件的輸入線確定；4）確定故障及故障傳播到輸出端的輸入變量的條件。這四個步驟實際上是確定性測試生成的主要過程，分別是故障激活、敏化或傳播、確認和蘊涵。2.4.1 確定性算法的基本過程為了對一條線上的SA故障進行測試生成，首先要對故障進行激活（excite or provoke），然后敏化（sensitize）此結(jié)果到輸出端，接著對電路中其它線的值確認（justify），再就是對其它門的值蘊涵（implication）。圖2.6 路徑敏化法示例激活 激活某一條線上的故障就是控制該線，使得其值為故障的補碼，這等效

12、于把故障信號置于該線上。例如要激活圖2.6中的故障，應(yīng)該控制門4的輸入使得。敏化（傳播） 敏化或傳播就是選擇一條路徑，沿此路徑可把故障信息從其源處傳播到原始輸出。此條路徑叫敏化路徑或者是傳播路徑。例如圖2.6中，故障的傳播路徑只能是。有些故障可能具有不止一條敏化路徑。確認 通過對電路中其它線的賦值，確定電路中這些線的邏輯值。例如圖2.6中，要把敏化到f5，須對f1賦值，要把故障效應(yīng)傳播到原始輸出Z，則必須要對f3賦值。蘊涵 通過確認電路中線的值，尋找電路中非敏化路徑上門的輸入或輸出值的過程。如果先確定的是該門的輸入值，那么確定其輸出值的過程就叫向前蘊涵，如果先確定的是該門的輸出值，則尋找其輸入

13、端的過程叫向后蘊涵。一致性（consistency）檢查 在敏化與確認的過程中，必須檢查某些線要賦的值與先前已賦的值是否有矛盾，這個過程叫做一致性經(jīng)常。如果有矛盾，則需要重新處理。2.4.2 路徑敏化法應(yīng)用的實例例2.1 對于圖2.6中的故障12/1，我們來研究路徑敏化法對其的測試生成。12/1故障激活的條件是，f4是門4的輸出，要使就必須使門4的輸入滿足下面的條件：選擇敏化路徑：。故障要從f4傳播到f5，必須確認門5的另一個輸入（或門），故障要從f5傳播到f6，得確認門6得另一個輸入（與門），總結(jié)得： 上式的求解實際上是向后跟蹤路徑敏化要完成的任務(wù)。再考慮到電路元件要實現(xiàn)的功能，系統(tǒng)輸入就采

14、取以下形式：，上式是多解的，每一個解都是特定故障的測試矢量。例如輸入1110111就是一解，當(dāng)對電路無故障施加此輸入時，輸出Z也為0，而因為有故障12/1的存在，實際電路的輸出為1，因此故障在其輸出端是可觀的。例2.1中的電路是無扇出的電路，采用的是單路徑的敏化方法。但是對于有扇出的電路，采用單路徑敏化可能行不通。例如圖2.7所示的電路，對于故障a/1，可以有兩條單敏化路徑或。故障激活時，x1和x2應(yīng)使得a為0，；對G2的輸入確認應(yīng)該使得，對G4的輸入確認使得，對G3的輸入蘊涵得，這顯然與激活條件矛盾。同樣對這條路徑敏化時也會出現(xiàn)不一致。因此單路徑敏化不能進行測試生成。圖2.7 單路徑敏化的反

15、例（a）單路徑敏化 （b）雙路徑敏化但是這個電路還有第三條敏化路徑，如圖2.7(b)所示為雙路徑敏化。顯然當(dāng)激活故障時，故障效應(yīng)沿雙路徑可傳播到Z。無故障時Z=0，有故障時Z=1?？傊瘸鰧β窂矫艋挠绊懣蓺w納為三種情況：1 單一路徑或多路徑均可產(chǎn)生測試；2 只有單一路徑產(chǎn)生測試；3 只有多路徑產(chǎn)生測試；對于扇出電路，為了避免路徑敏化法推導(dǎo)測試矢量所遇到的問題，給出下列提示：1 先試用單一路徑法推導(dǎo)測試矢量，如果無測試矢量，則再用步驟2：2 試用多路徑推導(dǎo)測試矢量。檢驗每一個可能測試矢量的有效性，如果確實找到并檢驗了此測試矢量，則停止測試生成；3 在沒有找到測試矢量前，所有組合的多路徑都應(yīng)該

16、進行檢查。2.5 D算法D算法基于集合理論，1966念由Roth正式提出，它是關(guān)于非冗余組合電路測試生成的第一個算法，屬于多路徑算法。除了用到多路徑掃描法的幾個主要操作過程中之外，還發(fā)展了一系列術(shù)語。2.5.1 D算法的關(guān)鍵術(shù)語1.d立方（d-cube）D算法的基礎(chǔ)是布爾函數(shù)的d立方，d立方是通過奇異立方來求的，因此我們先介紹一下奇異立方的概念。邏輯函數(shù)除最小項以外的其它表示項，叫奇異立方。任一邏輯函數(shù)都可用若干奇異立方來表示。例如函數(shù)可以用奇異立方（x11）和（1x0）描述。事實上函數(shù)的奇異立方就是函數(shù)的真值表壓縮表示法。為了表示奇異立方，要用到符號0，1和x，這里的變量x可代表0或1。圖2

17、.8(a)是一與非門的奇異立方表示，圖2.8(b)是對一兩輸入與門、兩輸入或非門、兩輸入或門組成的電路的奇異立方表示。圖2.8 電路的奇異立方表示討論奇異立方的目的是為了引入d立方。d立方由符號O、l、x和d表示，d可為O或l，的表示值則相反。d立方表示了數(shù)字電路的特征，由兩個具有不同輸出的奇異立方相交運算得到，其運算符合以下規(guī)律 因此，對一個兩輸入與非門，其奇異立方為 與 我們通過運算得到其d立方 2.故障的原始d立方(Primitive d cube) 故障的原始d立方用于確定一給定故障的存在，包含兩方面內(nèi)容: 1）使得故障效應(yīng)傳播到輸出的輸入方式。輸入信號方式應(yīng)使得故障在其源處激活，還應(yīng)

18、使得該故障信號傳播到輸出。 2）輸出應(yīng)有符號d和。d表示電路無故障時輸出為1，有故障時輸出為0; 反之。故障的原始d立方可由上述的d立方運算規(guī)律求得。假定表示電路無故障時的d立方，表示電路有故障時的奇異d立方，則有其中、的下標l、0分別表示電路的輸出為1或0。 例2.2 求圖2.8(b)中故障30的原始d立方。解：電路正常時的奇異立方1和0，電路有故障30時的奇異立方，分別表示如下再對1與0一一求交得d：或 再將輸出信號補上，得故障d立方為(0xD)和(x0D)?？梢钥闯龉收系脑糳立方就是故障激活的條件。 3.故障的傳播d立方(Propagate d-cube) 把電路輸入端的故障效應(yīng)傳播到

19、電路輸出端的最小輸入條件叫做傳播d立方，它表明了敏化路徑的敏化條件，也是對被測電路的結(jié)構(gòu)描述。簡單門的傳播d立方，可以直接觀察寫出。圖2.9表示了幾種基本門電路的傳播d立方。圖2.9 基本門電路的傳播d立方一般地，對于線上的傳播d立方，可以用以下兩種方法求解： (1)把=O時，電路的奇異立方0和=l時電路的奇異立方l相交運算； (2)把=l時，電路的奇異立方0和=O時電路的奇異立方1相交運算： 其結(jié)果就是傳播d立方，它是成對出現(xiàn)的，且d互補。物理意義是，能夠作為dd傳播條件的必可作傳播，能夠做d傳播的必可作一d傳播。4.d驅(qū)趕(d drive) 逐級將故障信號d()從故障點敏化至原始輸出端的過

20、程叫d驅(qū)趕(d drive)。d驅(qū)趕的具體做法是將輸入端有d()信號而輸出值尚未值確定的元件的傳播d立方同測試立方作求交運算，使該元件輸出d或信號。如果該交存在，說明本次驅(qū)趕成功，否則不成功。驅(qū)趕過程中的求交運算按表2.1進行。d交運算是建立敏化通路數(shù)學(xué)工具，Roth對d交的定義示于表2.1，并用算符表示。在表2.1中，表示d交為空，y表示d交無意義，其準確含義將在具體進行d交運算時解釋。表2.1 Roth d交定義01xDD00f0yy1f11yyx01xDDDyyDDyDyyDyD2.5.2 d算法的基本步驟1)建立失效的原始d立方PDCF(Primitive d-cube for fai

21、lure),激活故障； 2)選擇敏化路徑； 3)沿敏化路徑傳播PDCF，一次一個門按表2.1進行相交運算，直到原始輸出，也就是d驅(qū)趕，驅(qū)趕過程中對電路中節(jié)點賦值，對原始輸入確認； 4)如果d或出現(xiàn)在原始輸入，驅(qū)趕成功，否則返回至步驟2： 5)一致性檢查，若成功則確定測試矢量，否則,則無測試生成。D算法流程圖如圖2.10所示。圖2.10 d算法流程圖2.5.3 d算法舉例例2.3 對圖2.11所示電路中的故障，求其測試生成。解：首先，對電路中所有節(jié)點賦值x以初始化； 其次，對門2建立原始d立方，過程見例2.2。推導(dǎo)門1和門3的奇異立方，對門4推導(dǎo)傳播d立方。敏化路徑為，原始d立方我們選擇。圖2.

22、11 d算法故障f2=0的測試生成然后開始d驅(qū)趕，先是對故障d立方C0與定義門4的d立方C1作求交運算，結(jié)果為C2再計算門5的d立方c3與c2的交分析立方c4，表明被測電路的節(jié)點9有d出現(xiàn)，d驅(qū)趕完成。進行向后操作，立方c4能夠與門l和門3的奇異立方相交，結(jié)果為結(jié)果立方C8說明：輸入模式為x1x2x3x4=1010時，故障f2=0的效應(yīng)可傳播到電路輸出端，也就是說輸入1010是故障f2=0的測試矢量。2.6 PODEM算法 經(jīng)典的D算法能夠?qū)Ψ侨哂嗟慕M合邏輯電路的故障找到測試矢量，但對于重聚的扇出電路。如奇偶檢測電路、表決電路、誤碼校正及檢測電路等，由于工作量大，以致很難付諸實施。其主要問題是

23、返回的操作次數(shù)太多，原因是d驅(qū)趕及向后的線確認涉及到選擇過程，這可能導(dǎo)致對門賦值時的賦值相互矛盾，一旦矛盾出現(xiàn)，就得返回原先的判斷點重新進行敏化路徑和賦值。如圖2.12(a)所示電路中的DO故障，由D算法的線確認和相容性檢查我們得到測試矢量為：ABC=001，但此測試矢量并不能檢測DO故障，因為不管D0是否存在，原始輸出Y保持為0。因此必須尋找另外一個測試矢量來檢測該故障，這就是我們所說的向后操作。 圖2.12 (a)測試矢量與測試故障效應(yīng)相矛盾 (b)返回操作找到了一新的測試矢量新的測試矢量ABC=101，故障在其源處效應(yīng)為10，即d(無故障時為1，有故障時為O)，在原始輸出端可觀察到d，也

24、就是說，新的測試矢量既可以使得故障在其源處再現(xiàn)，又可以在原始輸出Y測試到故障DO的效應(yīng)。但對于大規(guī)模集成電路而言，返回操作使得這種試探矛盾的過程太多，而真正的有效操作較少為了解決這個問題，就產(chǎn)生了各種改進的算法，PODEM算法就是其中之一。PODEM(path oriented decision making)算法首先由Goel提出，實際上是一個程序，它使用了D算法的一些術(shù)語，吸收了窮舉法的優(yōu)點，對D算法作了有益的改進。2.6.1 PODEM算法PODEM算法的思路對激活的故障向后追蹤到原始輸入，搜索所有可能的輸入變量，只要找到一個符合要求的輸人組合即可作為測試矢量，算法即告結(jié)束。對于一確定的

25、故障，首先是確定目標，然后對連接到門的輸入線選擇原始輸入向量。如圖2.13所示電路AB是原始輸入PI,Y是原始輸出PO,對圖中的s-a-O故障，首先要確定的目標是，確定輸入使得無故障時Y為0，有故障時Y為l，為達到這個目的，必須確定AB=11。目標：Y=01 測試：AB=11圖2.13 PODEM算法目標設(shè)定 對每一個門都重復(fù)此過程，一直到原始輸入端，然后對此原始輸入賦所需要的值(其余的原始輸入保持不變)。對于原始輸入的每一個新的賦值，如果在原始輸出可觀察到故障效應(yīng)，就對有故障及無故障的電路進行模擬，這樣就建立了一條從故障源處到原始輸出的敏化路徑。如果在原始輸出沒觀察到故障效應(yīng)，就選擇一條向前

26、的故障傳播路徑，此路徑的物理長度最短，對每一個門重新確定目標。物理長度最短的意思是指，從故障源處到原始輸出的路徑上門的個數(shù)最少。由于原始輸入的選值具有隨機型，那么按什么變量次序來窮舉輸入矢量才能較快地得到所需要的測試矢量呢？PODEM算法中采用分支判決樹的方法來解決此問題。圖2.14 PODEM算法中的分支判決樹 圖2.14就是PODEM算法中的分支判決樹的流程圖。A，B，C，D，E，分別表示原始輸入，由于每個原始輸人只有兩種可能的值，因此可以對每個原始輸入進行兩種試探。當(dāng)選擇1時，執(zhí)行右分支，否則執(zhí)行左分支，對下一個原始輸入賦值時，如果第一個分支無測試，則過程返回到先前的節(jié)點，最后就形成圖中的二分樹其中的所謂的無測試可能是兩種情形：一是故障沒有激活，二是故障的路徑?jīng)]有得到敏化。如果一原始輸入的兩種值都已試探過，其結(jié)果都是無測試，則刪掉此節(jié)點，同時也刪掉前一個原始輸入的選值，也不對后一個原始輸入選值。每次從一節(jié)點選取第二分支時，就作