第2章電子電路故障

1、第第2章組合電路測試與故障診斷章組合電路測試與故障診斷什么叫算法？什么叫算法？第第2.1節(jié)節(jié) 通路敏化通路敏化u基本概念基本概念-什么是敏化通路？什么是敏化通路？u敏化通路法的實施步驟及舉例敏化通路法的實施步驟及舉例u關(guān)于一維敏化與多維敏化的討論關(guān)于一維敏化與多維敏化的討論第第2.2節(jié)節(jié) d 算法算法ud 算法的基本思想算法的基本思想ud算法的數(shù)學工具算法的數(shù)學工具ud算法的實施步驟及舉例算法的實施步驟及舉例第第2.3節(jié)節(jié) 擴展擴展 d 算法算法 u擴展擴展 d 算法的數(shù)學工具算法的數(shù)學工具u擴展擴展 d 算法的實施步驟及舉例算法的實施步驟及舉例第第2.4節(jié)節(jié) 布爾差分法布爾差分法布爾差分的基

2、本概念布爾差分的基本概念布爾差分的特性布爾差分的特性求解布爾差分的方法求解布爾差分的方法故障測試故障測試電子科大電子科大CATCAT室室第第2.1節(jié)節(jié) 通路敏化通路敏化2.1.1. 通路敏化的基本定義通路敏化的基本定義 1.Eldred在在1959年提出了第一篇關(guān)于組合電路的測試報告，開始年提出了第一篇關(guān)于組合電路的測試報告，開始 了數(shù)字系統(tǒng)故障診斷的研究。了數(shù)字系統(tǒng)故障診斷的研究。 2.D.B.Armstrong根據(jù)根據(jù)Eldred的基本思想，在的基本思想，在1966年提出了一維通年提出了一維通 路敏化的方法，其主要思路是對多級門電路尋找一條從故障點到路敏化的方法，其主要思路是對多級門電路尋

3、找一條從故障點到可及輸出端的敏化通路，使在可及端可以觀察到故障信號?？杉拜敵龆说拿艋?，使在可及端可以觀察到故障信號。 3.1967年年Schneidr用例子指出單通路敏化法并不能找出所有的故障。用例子指出單通路敏化法并不能找出所有的故障。 4.同年同年Roth提出了多通路敏化法的提出了多通路敏化法的D算法算法 電子科大電子科大CATCAT室室第第2.1節(jié)節(jié) 通路敏化通路敏化2.1.1. 通路敏化的基本定義通路敏化的基本定義 算法的定義：算法的定義：一個問題一個問題無二義性無二義性解的解的過程（時間和空間）過程（時間和空間） 是利用計算機解決一切問題的基礎！是利用計算機解決一切問題的基礎！主

4、輸入端：主輸入端：一條輸入線，若不受電路其它任何一條線饋給信號，這個輸入端就稱一條輸入線，若不受電路其它任何一條線饋給信號，這個輸入端就稱之為主輸入端，也稱原始輸入端；之為主輸入端，也稱原始輸入端；主輸出端：主輸出端：一條通到電路外部去的信號線稱為主輸出端，也稱原始輸出端；一條通到電路外部去的信號線稱為主輸出端，也稱原始輸出端；通路：通路：在組合電路中，從一個主輸入端經(jīng)內(nèi)部信號線通到主輸出端而不含有環(huán)路在組合電路中，從一個主輸入端經(jīng)內(nèi)部信號線通到主輸出端而不含有環(huán)路（無反饋線）的通路（定向信流圖）；（無反饋線）的通路（定向信流圖）；敏化通路：敏化通路：對一條通路中所有門電路的一切輸入適當賦值（

5、與門賦對一條通路中所有門電路的一切輸入適當賦值（與門賦“1”，或門賦，或門賦“0”)，使該通路上的邏輯變化能沿該通路傳輸?shù)街鬏敵龆?，這樣的通路就稱，使該通路上的邏輯變化能沿該通路傳輸?shù)街鬏敵龆?，這樣的通路就稱之為敏化通路；之為敏化通路；電子科大電子科大CATCAT室室第第2.1節(jié)節(jié) 通路敏化通路敏化2.1.1. 通路敏化的基本定義通路敏化的基本定義例：例：u主輸入端主輸入端：x1,x2,x3u主輸出端主輸出端：yu通路通路：a f h , b d f h , b e g h , c g hu敏化通路敏化通路：敏化：敏化 a f h 通路通路賦值：賦值：d = 1 ，g = 0敏化：敏化：a f

6、 h 通路上的邏輯變化都能傳輸?shù)街鬏敵龆送飞系倪壿嬜兓寄軅鬏數(shù)街鬏敵龆?y（故障傳播或前相跟蹤故障傳播或前相跟蹤）u賦值條件檢查賦值條件檢查：賦值條件能否在主輸入端實現(xiàn)（：賦值條件能否在主輸入端實現(xiàn)（一致性檢查或后相跟蹤一致性檢查或后相跟蹤）由由 g = 0，必須，必須 e = 1 或或 c = 1 或二者均為或二者均為 1由由 d = 1，必須，必須 b = 1 即即 e = 1綜上：綜上：e = 1 即即 x2 = 1 c = x (隨意）隨意）利用敏化通路進行利用敏化通路進行測試測試-可測試可測試 a f h 通路上的故障通路上的故障T=（01x) ; 0無故障；無故障；T=(01x

7、) ; 1a,f,h-s-a-1 故障測試故障測試T=（11x) ; 1無故障無故障T=(11x) ; 0a,f,h-s-a-0 故障測試故障測試x1x2x3abcfghde電子科大電子科大CATCAT室室2.1.2 通路敏化法通路敏化法1.基本思想：利用敏化通路原理基本思想：利用敏化通路原理2.數(shù)學關(guān)系數(shù)學關(guān)系u故障算子故障算子D-故障表示故障表示D 可為可為 “1”，也可為，也可為 “0”。在同一系統(tǒng)中應統(tǒng)一在同一系統(tǒng)中應統(tǒng)一；若若 ，則，則 ;若若 ，則，則；D 故障賦值故障賦值為了測試，在故障點應將為了測試，在故障點應將 D 賦于故障相反值：賦于故障相反值：在在 D = 0 的系統(tǒng)中的

8、系統(tǒng)中對于故障對于故障 s-a-0 則故障賦值則故障賦值 對于故障對于故障 s-a-1 則故障賦值則故障賦值 u為了故障傳播，引入為了故障傳播，引入 算子算子或門：或門： 或門賦值條件或門賦值條件與門：與門： 與門賦值條件與門賦值條件 1D0D1D0D1D0DDD或D1110DDDDD0100DDDDD電子科大電子科大CATCAT室室2.1.2 通路敏化法通路敏化法3.3.通路敏化法的實施步驟通路敏化法的實施步驟u故障表現(xiàn)故障表現(xiàn)-故障賦值故障賦值u故障傳播（通路敏化，前相跟蹤）故障傳播（通路敏化，前相跟蹤）-敏化條件敏化條件u一致性檢查（后相跟蹤）一致性檢查（后相跟蹤）-敏化條件能否在主輸入

9、端實現(xiàn)敏化條件能否在主輸入端實現(xiàn)u測試確定測試確定-測試函數(shù)的尋求測試函數(shù)的尋求4.4.舉例：舉例：用通路敏化法求用通路敏化法求 1_s_a_1 1_s_a_1 的測試的測試（1 1）故障表現(xiàn)）故障表現(xiàn)系統(tǒng)定義：系統(tǒng)定義： D = 0D = 0對于對于 1_s_a_1 1_s_a_1 故障故障， 則則 故障表現(xiàn)為故障表現(xiàn)為 D D ； 1_s_a_0 1_s_a_0 故障，故障， 則則 故障表現(xiàn)為故障表現(xiàn)為 ； x1x2x3x4123456879101112yxDDD110D電子科大電子科大CATCAT室室2.1.2 通路敏化法通路敏化法（2）故障傳播）故障傳播通路通路 L1-L10-L12

10、敏化（見圖）：與門賦敏化（見圖）：與門賦“1”，即，即 L5 和和 L8 賦賦 “1”； 或門賦或門賦“0”，即，即 L11 賦賦 “0”；D 傳播到主輸出端，仍為傳播到主輸出端，仍為 D；（3）一致性檢查）一致性檢查由賦值：由賦值：L5=1，則要求，則要求 L2 = x2 = 1； L8=1，則要求，則要求 L7=1，即，即 x2 或或 x3 或或 x4 為為 1； L11=0，則要求，則要求 L9=L7=1，即，即 x2 或或 x3 或或 x4 為為 1；綜上：綜上：x2 = 1，x3 = x4 = x，在主輸入端可實現(xiàn)敏化條件；，在主輸入端可實現(xiàn)敏化條件；（4）測試確定）測試確定綜上可得

11、綜上可得 x1-s-a-1故障的測試如下：故障的測試如下：T=（01xx）；）；0 無故障測試；無故障測試； T=（01xx）；）；1 x1,L10,L12-s-a-1故障測試；故障測試；優(yōu)點：優(yōu)點：簡單，存儲空間小，有拓撲的直觀性。簡單，存儲空間小，有拓撲的直觀性。電子科大電子科大CATCAT室室2.1.2 通路敏化法通路敏化法 自從自從1966年年Armstrong提出一維通路敏化提出一維通路敏化法以來，數(shù)字電路測試矢量自動生成理法以來，數(shù)字電路測試矢量自動生成理論的研究課題經(jīng)歷了一個從雛型到成熟、論的研究課題經(jīng)歷了一個從雛型到成熟、從理論到應用、從實用到完備的發(fā)展歷從理論到應用、從實用到

12、完備的發(fā)展歷程。程。 電子科大電子科大CATCAT室室2.1.3 討論討論問題：問題：上面分析的是一維敏化，即每次只敏化一條通路。但一維敏化是不是一種算法上面分析的是一維敏化，即每次只敏化一條通路。但一維敏化是不是一種算法呢？先看幾個例子：呢？先看幾個例子：例例1：無扇出的樹形電路無扇出的樹形電路故障：故障：a = x3 = D通路：通路：a b c (一維敏化）一維敏化）敏化：敏化：x4 = 1 x1 = 0 或或 x2 = 0 = 0 或或 =0 =0 或或 =0一致性檢查通過一致性檢查通過測試：測試：T=00D11111；D 無故障測試無故障測試 T=00D11111； a,b,c-s-

13、a-1 故障測試故障測試結(jié)論：結(jié)論：由于無扇出電路輸入端是獨立的，賦值自由，不相互約束。因此，每條通路的由于無扇出電路輸入端是獨立的，賦值自由，不相互約束。因此，每條通路的一維敏化都是成功的，可求出電路的最小完備測試集。一維敏化都是成功的，可求出電路的最小完備測試集。x1x2x3x4abc00 x0005x6x7x8x5x6x7x8xD電子科大電子科大CATCAT室室2.1.3 討論討論例例2：有扇出匯聚電路有扇出匯聚電路故障：故障：h-s-a-0 ( =1)敏化通路（一維）：敏化通路（一維）：h j lx1=a=1g=0 x2=b=1c=0h= =1d=0h j l 敏化不成功！敏化不成功！

14、敏化通路（一維）：敏化通路（一維）：h k m 敏化成功！敏化成功！結(jié)論：結(jié)論：對有扇出匯聚電路，一維敏化可能成功，也可能不成功！對有扇出匯聚電路，一維敏化可能成功，也可能不成功！x1x2x3x4abcdefghjklmy1y2x11000000矛盾矛盾DDDD電子科大電子科大CATCAT室室2.1.3 討論討論例例3：Schneider電路電路故障表現(xiàn)：故障表現(xiàn)：6-s-a-0 敏化通路（一維）：敏化通路（一維）：L6-L9-L12敏化條件：敏化條件：由由 6-s-a-0， 有：有：x2=0 ,x3=0 ;由由L10=0 及及 L6=0，必須，必須 x4=1；由由L11=0 及及 x3=0，

15、必須，必須 L7=1，即必須，即必須，x2=0,x4=0 x4矛盾，敏化不成功！矛盾，敏化不成功！敏化通路（一維）：敏化通路（一維）：L6-L10-L12由于電路是完全對稱的，由于電路是完全對稱的，x3矛盾，敏化也不成功！矛盾，敏化也不成功！x1x2x3x4x61091187000D12D5DDDD電子科大電子科大CATCAT室室2.1.3 討論討論多維敏化：同時對多條通路進行敏化。多維敏化：同時對多條通路進行敏化。上例：同時對上例：同時對L6-L9-L12 及及L6-L10-L12 兩兩條通路進行敏化，條通路進行敏化，故障表現(xiàn)：故障表現(xiàn)：6-s-a-0( )-x2=0，x3=0；敏化條件：敏

16、化條件：L11=0，因，因 x3=0，所以，所以 L7=1-x2=0，x4=0；L8=0， 因因 x2=0，所以，所以 L5=1-x1=0，x3=0；多維敏化成功！多維敏化成功！測試：測試：T=（0000）；）；1 無故障測試；無故障測試；T=（0000）；）；06-s-a-0故障測試；故障測試；x1x2x3x4x61091187000D12D5DDD電子科大電子科大CATCAT室室2.1.3 討論討論結(jié)論：結(jié)論：通路敏化是數(shù)字系統(tǒng)測試的基礎，但一維敏化不是一種算法，通路敏化是數(shù)字系統(tǒng)測試的基礎，但一維敏化不是一種算法， 而多維敏化而多維敏化才才是一種算法。是一種算法。多維敏化的實施：多維敏化

17、的實施：多路同時敏化有多種組合，因此，需要多路同時敏化有多種組合，因此，需要遍歷遍歷，反復搜索反復搜索和計算和計算。用人工的方法是十分困難的，甚至是不可能的，必須借助于計。用人工的方法是十分困難的，甚至是不可能的，必須借助于計算機進行測試，即利用算法進行算機進行測試，即利用算法進行計算機輔助測試（計算機輔助測試（CAT）：組合電路測：組合電路測試算法有：試算法有：*d 算法算法*擴展擴展d 算法算法*布爾差分法布爾差分法*等效笵式法等效笵式法-ENF*SPOOF法法 等等。等等。電子科大電子科大CATCAT室室2.2 d算法算法u1966年提出的算法，可以認為是拓撲結(jié)構(gòu)測試中最經(jīng)典的方年提出的

18、算法，可以認為是拓撲結(jié)構(gòu)測試中最經(jīng)典的方法，也是最早實現(xiàn)自動化的測試生成算法之一。它是完備的測試算法，法，也是最早實現(xiàn)自動化的測試生成算法之一。它是完備的測試算法，它可以檢測非冗余電路中所有可以檢測的故障。雖然它是在世紀它可以檢測非冗余電路中所有可以檢測的故障。雖然它是在世紀年代提出的，而且被該經(jīng)過多次，但是，許多新的測試方法都是在它年代提出的，而且被該經(jīng)過多次，但是，許多新的測試方法都是在它的基礎上發(fā)展起來的。而且一直沿用至今。的基礎上發(fā)展起來的。而且一直沿用至今。uD算法在具體應用時，計算工作量很大，尤其是對大型的組合電路算法在具體應用時，計算工作量很大，尤其是對大型的組合電路計算時間很長

19、計算時間很長,原因是在作敏化通路的選擇時其隨意性太大，特別是在考原因是在作敏化通路的選擇時其隨意性太大，特別是在考慮多通路敏化時各種組合的情況太多，然而真正慮多通路敏化時各種組合的情況太多，然而真正“有效有效”的選擇往往較的選擇往往較少，做了大量的返回操作。少，做了大量的返回操作。u改進的算法，如改進的算法，如PODEM和和FAN算法，有效地減小了返回次數(shù)，提算法，有效地減小了返回次數(shù)，提高了效率。高了效率。 電子科大電子科大CATCAT室室2.2 d算法算法d 算法又稱為多維敏化，其基本思想：算法又稱為多維敏化，其基本思想：從故障位置到電路的一切輸出端的全部從故障位置到電路的一切輸出端的全部

20、通路進行多維敏化！通路進行多維敏化！電子科大電子科大CATCAT室室2.2.1 基本數(shù)學關(guān)系基本數(shù)學關(guān)系 1.簡化表簡化表-d 算法的基礎算法的基礎(電路描述）電路描述）簡化表是由真值表求簡化表是由真值表求質(zhì)蘊涵項質(zhì)蘊涵項的方法整理出來的一種形式比真值表的方法整理出來的一種形式比真值表更緊奏更緊奏的一個的一個表，但不能丟失任何信息。表，但不能丟失任何信息。例：一或門例：一或門質(zhì)蘊涵項質(zhì)蘊涵項真值表真值表簡化表簡化表x1 x2 y1 2 3_0 0 01 x 10 1 1x 1 11 0 10 0 01 1 1x1x2123y12121122112112120()() 2yx xx xx xx

21、xxxx xx XXxyx x電子科大電子科大CATCAT室室2.2.1 基本數(shù)學關(guān)系基本數(shù)學關(guān)系可見：可見：u簡化表比真值表簡單，且電路愈復雜，簡化愈多；簡化表比真值表簡單，且電路愈復雜，簡化愈多；u簡化表中每一行稱為一個矢量，表示電路的輸入簡化表中每一行稱為一個矢量，表示電路的輸入/輸出的因果關(guān)系；輸出的因果關(guān)系；用同樣方法可以求出其它基本電路的簡化表：用同樣方法可以求出其它基本電路的簡化表：123123123 1 2 3 1 2 3 1 2 3 1 x 0 0 x 0 0 x 1 x 1 0 x 0 0 x 0 1 0 0 1 1 1 1 1 1 0 電子科大電子科大CATCAT室室2.

22、2.1 基本數(shù)學關(guān)系基本數(shù)學關(guān)系組合電路簡化表：組合電路簡化表：方法：方法：是簡單門電路簡化表的簡單疊加。是簡單門電路簡化表的簡單疊加。注意：注意：每一個門用它的信號輸出點的代號命名；每一個門用它的信號輸出點的代號命名；一個門輸出點的標號應大于其它一切輸入線的標號，以便作相容性運算；一個門輸出點的標號應大于其它一切輸入線的標號，以便作相容性運算；對于每一個頂點與其無關(guān)且標號比它小的項均為隨意項（對于每一個頂點與其無關(guān)且標號比它小的項均為隨意項（x)；例：例：123456簡化表：簡化表： 1 2 3 4 5 6 1 1 x 1 x 0 x 0G4 0 x x 0 1 1 x 1 x 0 x 0G

23、5 0 x x 0 0 0 0 x 1 1G6 1 x 1電子科大電子科大CATCAT室室2.2.1 基本數(shù)學關(guān)系基本數(shù)學關(guān)系2.傳遞傳遞d矢量矢量概念：概念：是迫使門電路的一個輸入承擔確定該門電路輸出的全部責任。也就是說迫是迫使門電路的一個輸入承擔確定該門電路輸出的全部責任。也就是說迫使門電路的輸出唯一地取決于一個輸入。使門電路的輸出唯一地取決于一個輸入。-敏化的賦值條件敏化的賦值條件方法：方法：用用Roth算法中的交運算為工具，從簡化表中具有不同輸出值的二個矢量相算法中的交運算為工具，從簡化表中具有不同輸出值的二個矢量相交得到。交得到。布爾交運算布爾交運算Roth交運算交運算0 1 x 0

24、 1 x_ 0 0 0 0 0 0 1 1 1 1 d 1 1 x 0 1 x x 0 1 x 定義：定義：d=1 0 =0 1dd電子科大電子科大CATCAT室室2.2.1 基本數(shù)學關(guān)系基本數(shù)學關(guān)系利用利用Roth交運算，可以方便求出各門電路的傳遞交運算，可以方便求出各門電路的傳遞d矢量：矢量：或門：或門：123簡化表簡化表 傳遞傳遞d矢量矢量1 2 31 2 31 x 11 1 1 無無d傳遞，不能敏化傳遞，不能敏化x 1 1d 0 d 能敏化，賦能敏化，賦00 0 00 d d 能敏化，賦能敏化，賦0同樣可得其它門電路的傳遞同樣可得其它門電路的傳遞d矢量矢量 1 2 31 2 3 1 2

25、 3 d 0 d 1 d d 1 0 d 1 d d 1 d 123123123可見，用計算方法確定了各通路上可見，用計算方法確定了各通路上各種門電路的賦值條件及敏化的故各種門電路的賦值條件及敏化的故障傳播關(guān)系障傳播關(guān)系dddd電子科大電子科大CATCAT室室3. 故障初始故障初始 d 矢量矢量概念：概念：為了在故障點得到一個為了在故障點得到一個d矢量而應加的測試矢量，就稱為初始矢量而應加的測試矢量，就稱為初始d矢量，即為矢量，即為故障表現(xiàn)故障表現(xiàn) 。方法：方法：正常邏輯表現(xiàn)與故障表現(xiàn)作正常邏輯表現(xiàn)與故障表現(xiàn)作Roth 交運算。交運算。例例1：故障在主輸入端故障在主輸入端1 0=d-故障初始故

26、障初始d矢量矢量例例2：故障在門輸出端故障在門輸出端正常表現(xiàn)正常表現(xiàn) 故障表現(xiàn)故障表現(xiàn)初始初始d矢量矢量1 2 3 1 2 3 1 2 3 =0 x 0 x x 0 0 x 0 x 0 0 x 0 01 1 11 1 d2.2.1 基本數(shù)學關(guān)系基本數(shù)學關(guān)系xS-a-0 d故障表現(xiàn)故障表現(xiàn)正常表現(xiàn)正常表現(xiàn)xS-a-0電子科大電子科大CATCAT室室2.2.1 基本數(shù)學關(guān)系基本數(shù)學關(guān)系4. d交交 d三種交運算：三種交運算：集合交運算（變量：集合交運算（變量：0，1，x；0與與1交為空集）；交為空集）；Roth 交運算（變量：交運算（變量：0，1，x；0與與1交為交為d或或 ）；）；Roth d

27、交運算（變量：交運算（變量：0，1，x，d， ；d 新的定義新的定義）；）；Roth d 交運算的定義：交運算的定義：說明：說明： d0 1 x d - d 交為空集交為空集 0 0 0 - d 交無意義交無意義 1 1 1 -d 與與 互換后，再互換后，再 d交交 x 0 1 x d -即為即為 d或或 d d 如如 與與 同時出現(xiàn)，矛盾，剔除同時出現(xiàn)，矛盾，剔除 dddddddd電子科大電子科大CATCAT室室2.2.2 d 交運算例交運算例42346713節(jié)點 門樹根原始輸出d 運算例：運算例：求求1-s-a-0的故障測試的故障測試解：解：（1）初始）初始d矢量：矢量：1 0=d（2）傳

28、遞）傳遞d矢量矢量由簡化表得：由簡化表得：G4= 1 2 3 4 5G5= x x 0 d d (3)用用 Roth d 運算求敏化通路運算求敏化通路 1 2 3 4 5 G4 d G5= x 1 0 d12345xS-a-0 ddd101 2 3 4 5d 1 x d x d（4）由敏化通路得到測試結(jié)果）由敏化通路得到測試結(jié)果 1-s-a-0，即，即 d=1 T=110;1 無故障測試；無故障測試； T=110;0 1-s-a-0故障測試；故障測試；可見，用可見，用Roth d 交運算可以方便交運算可以方便求出測試求出測試-利用數(shù)學工具，而不利用數(shù)學工具，而不是人為分析！是人為分析！電子科大

29、電子科大CATCAT室室1.2.2 窮舉測試法的實施窮舉測試法的實施2.2.3 d算法的實施步驟算法的實施步驟7樹根原始輸出d 算法的步驟如下：算法的步驟如下：1.初始化：初始化：（1）寫出被測電路的簡化表；）寫出被測電路的簡化表；（2）由簡化表求出傳遞）由簡化表求出傳遞d矢量；矢量；（3）寫出故障初始）寫出故障初始d矢量矢量-t0；（4）活動）活動d矢量矢量-d扇出；扇出；2.d 驅(qū)趕驅(qū)趕-多維敏化多維敏化方法：方法：將活動矢量與各自將活動矢量與各自d扇出有關(guān)的傳遞扇出有關(guān)的傳遞d矢矢量進行量進行d交運算，并反復進行，將一切敏化通路交運算，并反復進行，將一切敏化通路向前推進，使故障沿一切敏化

30、通路傳播下去，一向前推進，使故障沿一切敏化通路傳播下去，一直達到電路的一切主輸出為止。直達到電路的一切主輸出為止。3.相容性運算；相容性運算；4.求出測試矢量；求出測試矢量； t0111 t011 t0112 t0113 t012 t01 t013 t02t0 t03 t0n d算法的拓撲結(jié)構(gòu)算法的拓撲結(jié)構(gòu)電子科大電子科大CATCAT室室2.2.4 d算法舉例算法舉例-1.初始化初始化以以Schneider電路為例（電路見前）電路為例（電路見前）求：求： 6-s-a-0故障的測試。故障的測試。解：解：1.初始化初始化（1）寫出被測電路簡化表；）寫出被測電路簡化表；（2）由簡化表作）由簡化表作R

31、oth交運算，得傳遞交運算，得傳遞d矢量；矢量；（3）由故障表現(xiàn)）由故障表現(xiàn)6-s-a-0 求出初始求出初始d矢量，活動矢量，活動d矢量，矢量，d 扇出；扇出；電子科大電子科大CATCAT室室2.2.4 d算法舉例算法舉例-2.d驅(qū)趕驅(qū)趕2.d驅(qū)趕驅(qū)趕d 驅(qū)趕根據(jù)拓撲結(jié)構(gòu)進行：驅(qū)趕根據(jù)拓撲結(jié)構(gòu)進行：（1）t0 與與 G9, G10 作作 Roth d 交運算：交運算： 2 3 6 1 6 9 1 2 3 6 9t0 d G9= d = 0 0 d 0 d d 0 0 0 d d-t01-活動矢量（活動矢量（6，9），需扇出（），需扇出（9，10，12） d 0 d d 0 0 d - 無定義，

32、捨棄無定義，捨棄 2 3 6 4 6 10 2 3 4 6 10t0 d G10= d = 0 0 d 0 d d 0 0 0 d d-t02-活動矢量（活動矢量（6，10），需扇出（），需扇出（9，10，12） d 0 d d 0 0 d - 無定義，捨棄無定義，捨棄由此，得由此，得表表 2.2.6(P46)電子科大電子科大CATCAT室室2.2.4 d算法舉例算法舉例-2.d驅(qū)趕驅(qū)趕（2）t01 與與 G10，G12 作作 Roth d 交運算交運算 t02 與與 G9，G12 作作 Roth d 交運算交運算： 1 2 3 6 9 4 6 10 1 2 3 4 6 9 10t01 d G

33、10= d = 0 0 0 d 0 d 0 0 0 0 d -t011-，需扇出（，需扇出（12） d 0 0 0 0 d - 捨棄捨棄 1 2 3 6 9 8 9 10 11 12 1 2 3 6 8 9 10 11 12t01 d G12= d = 0 0 0 d 0 0 0 d 0 0 0 d 0 0 d -捨棄捨棄 0 0 d 0 0 0 0 d 0 d 0 -捨棄捨棄 0 d 0 0 0 0 0 d 0 0 0 -t012，已扇出到，已扇出到12 d 0 0 0 0 0 0 d d 0 0 -捨棄捨棄dddd dddddddddddddd電子科大電子科大CATCAT室室2.2.4 d

34、算法舉例算法舉例-2.d驅(qū)趕驅(qū)趕同上可得同上可得 t02 與與 G9，G12 作作 Roth d 交運算：交運算： 1 2 3 4 6 9 10t02 d G9= t021與與t011相同相同-扇出到扇出到12 0 0 0 0 d 2 3 4 6 8 9 10 11 12t02 d G10= t022-已扇出到已扇出到12 0 0 0 d 0 0 d 0 d綜上可得綜上可得d d電子科大電子科大CATCAT室室2.2.4 d算法舉例算法舉例-2.d驅(qū)趕驅(qū)趕（3）t011與與G12作作Roth d 交運算交運算 1 2 3 4 6 9 10 8 9 10 11 12 t011 d G12= d

35、0 0 0 0 d 0 0 0 d ！ 0 0 d 0 需要需要G12的的9和和10構(gòu)成構(gòu)成d矢量。矢量。 0 d 0 0 d 0 0 0 為此，通過為此，通過G12的簡化表相繼作交運算得到：的簡化表相繼作交運算得到：G12=（00001） （xx1x0) (x1xx0)=(00001) x11x0=0 0d 故有：故有： 1 2 3 4 6 9 10 8 9 10 11 12 1 2 3 4 6 8 9 10 11 12 t011 d G12= d = 0 0 0 0 d 0 0 d 0 0 0 0 d 0 0 d 得得表表 2.2.8已全部驅(qū)趕到主輸出端已全部驅(qū)趕到主輸出端12。t0111

36、ddddddddd dddd d電子科大電子科大CATCAT室室2.2.4 d算法舉例算法舉例-3.相容性運算相容性運算3.相容性運算相容性運算由上面由上面d驅(qū)趕，得出驅(qū)趕，得出6-s-a-0 故障的三個測試矢量：故障的三個測試矢量：t012, t022, t0111此三個測試是否都是此三個測試是否都是6-s-a-0故障的測試呢？必須作相容性運算（賦值是否矛盾？）故障的測試呢？必須作相容性運算（賦值是否矛盾？）（1）t012的相容性運算的相容性運算 見見表表2.2.9a.選取最大的頂點選取最大的頂點-G11c. 取取G8 3 7 112 5 8 x 1 0-G11(a)相容相容1 X 0-G8

37、(a) 2 矛盾矛盾 1 x 0 -G11(b) 3 矛盾矛盾 x 1 0-G8(b)相容相容 b.取取G10 d.取取G7 4 6 102 4 7 1 x 0-G10(a)相容相容0 0 1-G7 4 矛盾矛盾 x 1 0 -G10(b) 6 矛盾矛盾 可見，可見，t012不能滿足相容性條件，即主輸入端不能滿足內(nèi)部的賦值條件。不能滿足相容性條件，即主輸入端不能滿足內(nèi)部的賦值條件。同樣，同樣，t022也不滿足相容性條件。也不滿足相容性條件。因此，因此，t012,t022都不是一個測試，而都不是一個測試，而t0111滿足相容性條件，是一個測試，滿足相容性條件，是一個測試，表表2.2.10。電子科

38、大電子科大CATCAT室室2.2.4 d算法舉例算法舉例-4.測試矢量測試矢量4.測試矢量測試矢量 1 2 3 4 6 8 9 10 11 12 t0111= 見表見表2.2.8 0 0 0 0 d 0 0 d其中：其中：5=x，7=x 根據(jù)相容性運算（表根據(jù)相容性運算（表2.2.10)：5=1，7=1 1 2 3 4 5 6 7 8 9 10 11 12 t0111= 0 0 0 0 1 d 1 0 0 d所以有測試：所以有測試： 2路敏化路敏化T=0000；1無故障測試；無故障測試；T=0000；06-s-a-0測試，也可測試測試，也可測試9-s-a-1和和10-s-a-1故障；故障；d

39、dd d電子科大電子科大CATCAT室室2.3 擴展擴展d算法算法基本思想：基本思想：基于多路敏化，并以基于多路敏化，并以d算法為基礎（算法為基礎（d驅(qū)趕和相容性運算），利用驅(qū)趕和相容性運算），利用九值集合九值集合運算運算，求出電路的故障測試。，求出電路的故障測試。優(yōu)點：優(yōu)點：簡潔直觀，通用性強。簡潔直觀，通用性強。電子科大電子科大CATCAT室室2.3.1 九值運算九值運算-1.定義定義1.九值定義及九值集合運算九值定義及九值集合運算九值有：九值有： ，0，1，d， ，F(xiàn)， ，R，定義：定義：空集：空集：單元素集：單元素集：0，1，d，雙元素集：雙元素集：F=1Ud-與門賦值條件；與門賦值條

40、件； R=1U -與門賦值條件；與門賦值條件； =0U -或門賦值條件；或門賦值條件； =0Ud-或門賦值條件；或門賦值條件；u=0U1UdU =FURU U通集通集雙元素集為敏化提供了更為靈活方便的賦值條件，本身就含有多路敏化的概念。雙元素集為敏化提供了更為靈活方便的賦值條件，本身就含有多路敏化的概念。ddddRRFFdFR電子科大電子科大CATCAT室室2.3.1 九值運算九值運算-1.九值集合運算九值集合運算2.九值集合運算九值集合運算-擴展擴展d算法的數(shù)學基礎算法的數(shù)學基礎（1）交運算）交運算d F=d (1Ud)=d本頁中：本頁中：F R=(1Ud) (1Ud)=1 F=(0Ud)

41、(1Ud)=d 得表得表2.2.10R =(0Ud) (0Ud)=0d F=d (0Ud)= （2）與運算）與運算dF=d(1Ud)=dUd=dFR=(1Ud)(1Ud)=1UdUdUdd=1UdUdU0=u-通集通集 得得表表2.2.11(P50) = (0Ud)(0Ud)=0U0U0udd=0（3）或運算）或運算d+F=d+(1Ud)=(d+1)U(d+d)=1Ud=Fd+ =d+(0Ud)=(d+0)U(d+d)=dU1=F得得表表2.2.12R+ =(1Ud)+(0Ud)=(1+0)U(1+d)U(d+0)U(d+d)=1U1UdUd=1Ud=R + =(0Ud)+(0Ud)=(0+0

42、)U(0+d)U(d+0)U(d+d)=0UdUdU1=u-通集通集（4）非運算）非運算d=d = =得得表表2.2.13 RRRRRFFFFFdd FF電子科大電子科大CATCAT室室2.3.2 九值函數(shù)的原象九值函數(shù)的原象-1.概念概念1.概念：概念：一個集合一個集合X經(jīng)邏輯網(wǎng)絡輸出一個集合經(jīng)邏輯網(wǎng)絡輸出一個集合Y，其函數(shù)關(guān)系為：其函數(shù)關(guān)系為：Y=f(X)則，從則，從X Y就稱之為就稱之為映射映射；而，而，Y=f(X)稱之為稱之為映射函數(shù)映射函數(shù)；在上述映射中，取在上述映射中，取X集合的一個子集集合的一個子集X1，映射，映射有有Y集合的子集集合的子集Y1，如果有如果有y y1 x x1 時

43、，使得時，使得f(x)=y則則y1就是集合就是集合X1在映射在映射f(x)=y下的下的象象（正函數(shù)）（正函數(shù)）反之，如有反之，如有X的子集的子集x2，且，且注：注： -包含包含x X2 y y2 時，使得時，使得f(x)=y則，則， x2就是集合就是集合Y2在映射函數(shù)在映射函數(shù)f(x)=y下的下的原象原象（反向函數(shù)）（反向函數(shù)）Y=f(X)X集合集合Y集合集合電子科大電子科大CATCAT室室2.3.2 九值函數(shù)的原象九值函數(shù)的原象-2.例例2.例：例：上述概念以例說明上述概念以例說明從從X（x1,x2,x3) 到到 Y(y1,y2) 稱為稱為映射；映射；y1=x1x2y2=x2+x3X的全集為

44、：（的全集為：（000，001，010，.111）如取如取X的一個子集的一個子集X1=（00，11），映射有），映射有Y的子集的子集y1y1=x1x2=00=0y1=x1x2=11=1則則y1(0,1)就是就是X1（00，11）在映射函數(shù)）在映射函數(shù)y1=x1x2下的下的象象；反之，如有反之，如有y1(0,1)，有，有y1=x1x2=（00，01，10，11）則，則，X1=（00，01，10，11）就是集合）就是集合y1=x1x2=（0，1）在）在y1=x1x2映射下的映射下的原象；原象；求原象是擴展求原象是擴展d算法的基礎算法的基礎-反向思維！反向思維！x1x3y1=x1x2y2=x2+x3

45、Y=(y1,y2)x2X=(x1,x2,x3)映射函數(shù)；映射函數(shù)；電子科大電子科大CATCAT室室2.3.2 九值函數(shù)的原象九值函數(shù)的原象-3.原象的求法原象的求法3.原象的求法原象的求法或門或門說明說明：（：（1）xa表示表示x a，即，即x是集合是集合a中的元素；中的元素；（2）利用）利用表表2.2.12可求出可求出 f=xUy 的原象；的原象；(1) (x+y)d=xd(y0UydUyR)Uyd(x0UxdUxR)=xdyRUydxR -或門輸出為或門輸出為d的原象的原象因為：因為：R=（0Ud） 即即 yR=y0Uyd；xR=x0Uxd物理概念：物理概念：多路敏化多路敏化原象原象 象象

46、原象原象 象象xydR=0UddxyR=0Uddd注：本頁中 R=R或電子科大電子科大CATCAT室室2.3.2 九值函數(shù)的原象九值函數(shù)的原象-3.原象的求法原象的求法(2) (x+y)d=xd(y0UydUyF)Uyd(x0UxdUxF)=xdyFUydxdF-或門輸出為或門輸出為d的原象的原象因為：因為：F=(0Ud)即即xF=x0Uxd，yF=y0Uyd物理概念：物理概念：(3) (x+y)F=xFyu+yFxu(4) (x+y)F=xfyF(5) (x+y)R=xRyuUyRxu(6) (x+y)R=xRyR(7) (x+y)0=x0y0(8) (x+y)1=x1yuUxuy1Uxdy

47、dUxdyd或xydF=(0Ud)dxyF=(0Ud)dd00011udd1FuF電子科大電子科大CATCAT室室2.3.2 九值函數(shù)的原象九值函數(shù)的原象-3.原象的求法原象的求法3.原象的求法原象的求法-與門與門利用利用表表2.2.11用同樣方法可求出與門的原象用同樣方法可求出與門的原象(1) (xy)d=xdyFUydxF(2) (xy)d=xdyRUxRyd(3) (xy)F=xFyF(4) (xy)F=xFyuUxuyF(5) (xy)R=xRyR(6) (xy)R=xRyuUxuyR(7) (xy)1=x1y1(8) (xy)0=x0yuUxuy0UxdydUxdyd對于多維函數(shù)用同

48、樣方法也可求出原象！見對于多維函數(shù)用同樣方法也可求出原象！見P52xydF=1UddUxyF=1Uddd電子科大電子科大CATCAT室室2.3.2 九值函數(shù)的原象九值函數(shù)的原象-立方表立方表立方表立方表為了使用方便，上述公式可用立方表列出為了使用方便，上述公式可用立方表列出（象）（象）Z = x + y（原象）（原象） （象）（象）Z = x y（原象）（原象）d d Rd d Fd R dd F dd立方立方d d Fd d Rd F dd R dF F uF F FF u FF F uF立方立方F F FF u FR u RR R RR R uR R uR立方立方R R RR u R0 0

49、 01 1 11 1 u0 0 u1 u 10 u 00/1立方立方1 d d0 d d1 d d0 d d電子科大電子科大CATCAT室室2.3.3 故障函數(shù)的原象故障函數(shù)的原象故障函數(shù)的原象故障函數(shù)的原象-初始初始d矢量（故障表現(xiàn)）矢量（故障表現(xiàn)）原象原象象象如何根據(jù)故障點的故障值如何根據(jù)故障點的故障值Y和映射函數(shù)和映射函數(shù)Z=f(x)的映射值，求出故障函數(shù)的原象的映射值，求出故障函數(shù)的原象X？其方法和規(guī)則如下：其方法和規(guī)則如下：（1）當）當Y Z= （空集）（空集） 時，則，時，則，X= ，原象，原象X不存在，不存在，即故障表現(xiàn)即故障表現(xiàn)Z集合中無故障值集合中無故障值Y ；（2）當）當Y

50、 Z=R（0Ud） d=d時，則，時，則，故障函數(shù)的原象為：故障函數(shù)的原象為：X=F=（1Ud）；）；X（測試（測試)x故障點故障點(故障值故障值Y）D矢量傳遞方向矢量傳遞方向故障表現(xiàn)故障表現(xiàn)Z=f(x)X=F=(1Ud)Y=R=(0Ud)xZ=d電子科大電子科大CATCAT室室2.3.3 故障函數(shù)的原象故障函數(shù)的原象（3）當）當Y Z=R（1Ud） d=d時，則，時，則，X=F=（0Ud）；）；例：例： xS-a-0YXZ故障值：故障值：Y=R=（0Ud)映射值：映射值：Z=d則：則：Y Z=（0Ud) d=d所以：所以：X=F=(1Ud)由與門的由與門的F立方有立方有 X x1 x2 F

51、F F故障函數(shù)的原象：故障函數(shù)的原象：F=(1Ud)x1,x2是主輸入端，只取二值變量是主輸入端，只取二值變量所以有所以有故障初始故障初始d矢量：矢量：x1=1, x2=1；x1x2電子科大電子科大CATCAT室室2.3.4 擴展擴展d算法的實施算法的實施1.敏化條件敏化條件（1）與門）與門如故障為如故障為 xrd =1，則敏化到，則敏化到 yd=1（為真）的條件為：（為真）的條件為：m xjF=1 F=1Udj=1j=r如故障為如故障為 xrd=1，則敏化條件為：，則敏化條件為：m xjR=1R=1Udj=1j=rF=(1Ud)F=(1Ud)xrxdF=(1Ud)dyd電子科大電子科大CAT

52、CAT室室2.3.4 擴展擴展d算法的實施算法的實施（2）或門）或門如故障為如故障為 xrd =1，則敏化到，則敏化到 yd=1（為真）的條件為：（為真）的條件為：m xjR=1 R=0Udj=1j=r如故障為如故障為 xrd=1，則敏化條件為：，則敏化條件為：m xjF=1F=0Udj=1j=rR=0Udxxrdyd電子科大電子科大CATCAT室室2.3.4 擴展擴展d算法的實施算法的實施（3）通路）通路敏化條件：敏化條件： v Sri = 1Sri 是各級單門的敏化條件是各級單門的敏化條件i=12.算法及步驟算法及步驟u初始化；初始化；u預處理；預處理；ud驅(qū)趕；驅(qū)趕；u一致性檢查；一致性

53、檢查；u判斷與處理；判斷與處理；電子科大電子科大CATCAT室室2.3.4 擴展擴展d算法的實施流程算法的實施流程擴展擴展d算法流程：算法流程：初始化初始化電路排序，故障表現(xiàn)，列出立方表，電路排序，故障表現(xiàn)，列出立方表，初始矢量初始矢量TC0，通路數(shù)，通路數(shù)K預處理預處理對傳遞表進行處理，主輸入取二值（對傳遞表進行處理，主輸入取二值（0，1）D驅(qū)趕驅(qū)趕TC1將測試矢量將測試矢量TC2中主輸入變量取二值（中主輸入變量取二值（0，1）相容性檢驗成功嗎？相容性檢驗成功嗎？故障遍歷完否？故障遍歷完否？K-1 KK=0？不成功不成功成功成功未完未完結(jié)束結(jié)束否否是是另選路徑驅(qū)趕另選路徑驅(qū)趕完完例：按擴展例

54、：按擴展d算法算法 流程求解流程求解Schneider 電路電路6-s-a-0故障的故障的 測試。有條件的同學測試。有條件的同學 可編寫出該程序。可編寫出該程序。電子科大電子科大CATCAT室室2.4 布爾差分法布爾差分法拓撲方法：通路敏化法，拓撲方法：通路敏化法，d算法，擴展算法，擴展d算法等；算法等；敏化通路概念敏化通路概念分析方法：布爾差分法分析方法：布爾差分法-用數(shù)學解析法求解測試；用數(shù)學解析法求解測試；解析法的優(yōu)點：普遍性，完備性（單故障測試，多故障測試），通用性；解析法的優(yōu)點：普遍性，完備性（單故障測試，多故障測試），通用性；電子科大電子科大CATCAT室室2.4 布爾差分法布爾差

55、分法 布爾差分法由布爾差分法由Sellers等人提出，是組合電路測試生成的一種方法。等人提出，是組合電路測試生成的一種方法。其主要特點是將電路描述抽象為數(shù)學表達式模型，從而可進行嚴其主要特點是將電路描述抽象為數(shù)學表達式模型，從而可進行嚴密的數(shù)學推導，因而具有較高的理論研究價值。這種方法通過對密的數(shù)學推導，因而具有較高的理論研究價值。這種方法通過對數(shù)字電路的布爾方程模型進行差分運算，能獲得測試矢量集的一數(shù)字電路的布爾方程模型進行差分運算，能獲得測試矢量集的一般表達式，并能求出所給故障的全部測試矢量，因此具有理論上般表達式，并能求出所給故障的全部測試矢量，因此具有理論上的完備性。的完備性。電子科大

56、電子科大CATCAT室室2.4.1 布爾差分法的基本概念布爾差分法的基本概念布爾差分的定義：布爾差分的定義：一布爾函數(shù)：一布爾函數(shù)：y(x)=y(x1,x2,.xi,.xn)對對xi的布爾差分定義為：的布爾差分定義為：含義：含義：連續(xù)函數(shù)的差分（微分）連續(xù)函數(shù)的差分（微分）dy/dx 表示對應于表示對應于 x 無窮小增量的無窮小增量的 y 的增量。的增量。在布爾代數(shù)中，在布爾代數(shù)中，x和和y值只能為值只能為 0或或1，因而，因而，x和和y的增量只能為的增量只能為 1。所以有如下關(guān)系：。所以有如下關(guān)系：),.,.,(),.,.,()(2121ininixxxxyxxxxydxxdyxxydxxd

57、yx)(lim)(0電子科大電子科大CATCAT室室2.4.1 布爾差分法的基本概念布爾差分法的基本概念布爾差分關(guān)系表：布爾差分關(guān)系表：變量變量關(guān)系式關(guān)系式可能取值可能取值dxdx= x =xi-xi 1yy=y(x1,x2,xi,xn)0,1,0,1yy=y(x1,x2,xi,xn) 0,1,1,0dydy= y=y-y=y y0,0,1,1差分差分dy/dx= y/ x0,0,1,1異或異或y y0,0,1,1由上表可以看出，布爾差分的定義是正確的，其概念與連續(xù)函數(shù)的差分完全一樣。由上表可以看出，布爾差分的定義是正確的，其概念與連續(xù)函數(shù)的差分完全一樣。注意：在高等數(shù)學的微積分中，只有連續(xù)函

58、數(shù)才能求差分，布爾函數(shù)是不連續(xù)函數(shù)，注意：在高等數(shù)學的微積分中，只有連續(xù)函數(shù)才能求差分，布爾函數(shù)是不連續(xù)函數(shù)， 在布爾空間中也可求差分！在布爾空間中也可求差分！電子科大電子科大CATCAT室室2.4.1 布爾差分法的基本概念布爾差分法的基本概念利用布爾差分求測試的概念：利用布爾差分求測試的概念：如果：如果：表示輸出表示輸出 y 能響應能響應 xi 的變化的變化-能對能對 xi 敏化，有敏化通路，可求出敏化，有敏化通路，可求出 xi 的故障測試；的故障測試；如果：如果：表示輸出表示輸出 y 不能響應不能響應 xi 的變化的變化-不能對不能對 xi 敏化，即不能求出敏化，即不能求出 xi 故障測試

59、。故障測試。此結(jié)論與第一章的數(shù)據(jù)域測試的解析法結(jié)論是一致的！此結(jié)論與第一章的數(shù)據(jù)域測試的解析法結(jié)論是一致的！1),.,.,(),.,.,()(2121ininixxxxyxxxxydxxdy0),.,.,(),.,.,()(2121ininixxxxyxxxxydxxdy電子科大電子科大CATCAT室室2.4.1 布爾差分法的基本概念布爾差分法的基本概念例：利用前面通路敏化法的電路為例例：利用前面通路敏化法的電路為例yxS-a-1x1x2x3x4根據(jù)電路圖有：根據(jù)電路圖有：為了求為了求 x1-s-a-1 的故障測試的故障測試y 對對 x1 求布爾差分，有：求布爾差分，有：1)(21 xdxxd

60、y求解布爾差分方程：求解布爾差分方程：解為：解為：X1-s-a-1,故故x1=0 x2=1x3=x4=x測試矢量為：測試矢量為： 0100 0101 0110 0111與前面測試結(jié)果相同！利用布爾差分可以求出電路的測試解！與前面測試結(jié)果相同！利用布爾差分可以求出電路的測試解！12234yx xxxx112234223421()()dyx xxxxx xxxxxdx電子科大電子科大CATCAT室室2.4.2 布爾差分的特性布爾差分的特性從上述分析可知，利用布爾差分法求解電路的測試，關(guān)鍵在于解布爾差分方程。為了從上述分析可知，利用布爾差分法求解電路的測試，關(guān)鍵在于解布爾差分方程。為了方便差分方程的