1、12 D算法是一種用形式化運算求測試碼的多路徑敏化法，是在立方體理論基礎(chǔ)上實現(xiàn)的路徑敏化，是首先出現(xiàn)的完全的測試碼生成算法。由于其計算機可操作性和解決問題的通用性而得到廣泛的應(yīng)用。 基本思想：同單路徑敏化法，使故障點的正常值與故障值形成差異，并將它敏化至輸出端。同時確定輸入向量和其他信號值以確保各信號值的一致性。 采用立方體運算，考慮多路徑情況。3 立方體：n變量的二值布爾函數(shù)可看成是一個n維單位立方體的2n個頂點。每個頂點對應(yīng)一個最小項，乘積項（線段、平面等）則表示為奇異立方。 D立方： ：正常值為1，故障值為0，用來表示s-a-0; ：正常值為0，故障值為1，用來表示s-a-1。DD4 定

2、義兩個相同維數(shù)的立方體的交運算： 其中每個元素的交運算規(guī)則如上表所示，若有一個或幾個元素相交結(jié)果為 ，則表示該立方不存在。11,ijaaijijnn,5 定義：在元件輸出處可產(chǎn)生錯誤信號 的最小輸入條件。 運算：pdcf交，表明故障元件輸入和輸出之間的關(guān)系。設(shè)無故障立方體的集合為G，故障立方體的集合為B。G中輸出為0的表示為g0，輸出為1的表示為g1；B中輸出為0的表示為b0，輸出為1的表示為b1。 Pdcf交規(guī)則：輸入部分的規(guī)則同一般立方體交運算；輸出部分的規(guī)則如下表：也即：/D D1001,gbD gbD6 設(shè)一個與門在故障狀態(tài)下表現(xiàn)為或門的性質(zhì)，求其pdcf。解：正常狀態(tài)下的G和故障狀態(tài)

3、下的B分別為：先對g1和b0作pdcf交： 結(jié)果為空。再對g0和b1作pdcf交：得該與門的故障D立方為：1 1 1000D0011xxxD001 101xxD001110 xxD001 1xxxD0110DD7 定義：將元件輸入端的若干錯誤信號傳播至輸出端的最小輸入條件，表示對故障信號的傳播特性。 計算：求 即xi線上 故障傳播至輸出端仍為 的條件；求 即xi線上 故障傳播至輸出端變?yōu)?的條件；構(gòu)造傳播D立方（x1,x2,f）。 0011|,iixxT D DD Dgg D D D D 0110|,iixxT D DD Dgg D DD D8 定義：對電路中各個信號結(jié)點依次排列，它們的動態(tài)狀

4、態(tài)取值組成含有 或 的值向量。 它是經(jīng)過運算的D立方，如： 測試D立方是在運算過程中各結(jié)點邏輯值（包括D值）的動態(tài)列表。未確定值的結(jié)點均以X值表示。DD, , , , ,1,0,0,1,a b c d e f gD DD9 定義：逐級將故障信號 敏化至可測輸出端的過程。 思路：將輸入有 而輸出未定的元件（稱為D激活元件）的傳播D立方同測試立方作交運算（規(guī)則見下表），使其輸出 或 ，即將 驅(qū)趕通過該元件。如交存在，說明驅(qū)趕成功，否則驅(qū)趕失敗。 D D D DDD D D0100011101DDxDDDDDDxDDx10從激活元件AI選出EI，將EI的傳播D立方與前一次測試立方tcI-1相交。如交

5、存在，構(gòu)造tcI，表示 已通過元件EI，進入步驟2。如果交不存在，則轉(zhuǎn)入3。從AI中刪去EI，增加新的激活元件形成AI+1，重復(fù)步驟1直至到達輸出端。從AI中另選元件EI，重復(fù)步驟1。如AI中所有元件均敏化失敗，則退回到AI-1。 D D11 向前的D驅(qū)趕完成后，要進行向后的一致性檢查，檢查所獲測試立方是否與各元件的奇異立方一致。 方法：將D驅(qū)趕中尚未用過的元件的奇異立方與測試立方作交運算。如有一個元件找不到一致的奇異立方，則一致性檢查未通過，應(yīng)退回上一步。 蘊含：在D驅(qū)趕中確定了某些線上的值，從而唯一確定了有些元件的輸出值。 方法：將與新確定值有關(guān)的各元件的奇異立方同測試立方求交。 前向蘊含

6、：輸入值先確定，求交后確定輸出值； 后向蘊含：輸出值先確定，求交后確定輸入值。12準(zhǔn)備工作：電路結(jié)點編號；輸入全部元件的立方體和傳播D立方；建立故障表，輸入各故障D立方。選定一個故障形成故障傳播D立方作為初始測試立方tc0。在激活元件A0中任選一個作為E0，求其傳播D立方，并求傳播D立方與tc0的交運算。若交存在，即表示與tc0一致，得 tc1 = tc0T(D)；若不一致則退回，另選一傳播D立方。若該元件全部傳播D立方與不一致，則從A0中另選一個元件作為E0。在新激活元件A1中任選一個作E1，重復(fù)上述步驟，直至D被驅(qū)趕至輸出端。13 以下圖為例，用D算法求e(s-a-1)的測試碼。解：與該故

7、障有關(guān)的元件為E，其故障D立方為：00cdexDxD14所有元件的原始立方：00001111001111100010100011001000011100001111010abcdefghijklxxxxxxxxxxxx001E：F：G：H：I：J:K:L:15所有元件的傳播D立方：:1111:0000:0000:1111:1111:0000abcdefghijklEDDDDDDDDFDDDDGDDDDDDDDHDDDDDDDDIDDDDJDDDDDDDDKDDDDDDDDLDDDDDDDD1617012233000100100010000100100abcdefghijkltcxxxDxxxx