數?；旌想娐饭收显\斷新方法＊

史賢俊 孔東明

（海軍航空工程學院控制工程系 煙臺 264001）

1 引言

數?；旌想娐饭收显\斷是一個被廣泛關注的前沿課題，它面臨著許多測試上的難點，解決這個問題意義重大而且任務艱巨。

基于DES理論解決數?；旌想娐饭收蠁栴}的關鍵是最小測試集的求取，本文提出一種求取最小測試集的方法。

2 網絡撕裂法

網絡撕裂法的觀點是“將大規模電路撕裂成小網絡，而對每一個子網絡可以單獨求解，不必考慮其他網絡的存在”。撕裂原則是撕裂的兩子電路之間存在耦合關系。

網絡撕裂法的基本思想［1］是按一定的準則將網絡撕裂成若干個子網絡，然后根據測試條件將故障定位于子網絡中，再對子網絡采用相應的診斷方法進行故障定位。一般是在撕裂節點上加上相應的激勵信號，檢測測試節點的電壓或頻率值以確定各部分的工作狀態。

網絡撕裂法進行故障診斷可以分成網絡撕裂、子網絡狀態判定與故障定位3個步驟。

2.1 網絡可撕裂的劃分條件

對于一個大規模網絡，為了便于診斷可將其撕裂成若干子網絡。為了方便故障的準確定位，在撕裂網絡時應遵循下列原則：

1）撕裂后的各個子網絡間沒有拓撲關系和參數之間的耦合；

2）撕裂時，盡量使子網絡的規模小一些因為子網絡的規模越小，故障數就越少，故障的組合數就越少，診斷的準確率就越高；

3）撕裂時，盡量保持各子網絡結構的完整性，同一元件的各個部分不應撕裂，而應將它們化于同一子網絡中。

圖1所示的網絡N可將其撕裂為N1和N2兩個部分，我們取其中的子網絡N1分析，如圖2所示，N1的撕裂節點由可及子集TM（tm∈TM）和不可及子集JT（jt∈JT）兩個部分組成；未撕裂節點由可及子集UM（um∈UM）和不可及子集UU（uu∈UU）兩個部分組成。

圖1 線性網絡N撕裂示意圖

圖2 子網絡N1

可以得出，N1的可及點數m1＝tm＋um，撕裂點數m2＝tm＋jt。因為N1和N2并無耦合關系，則N1的節點電壓方程為

其中Vn＝［VJTVTMVUMVUU］T，In＝［0 ITMIUM0］T，Im＝［IJTITM0 0］T。

ITM為被撕裂可及節點的未知電流。列向量將方程（1）按JT、TM、UM、UU分塊，并消去內節點電壓列向量VUU，以VJT、IJT、Itm為未知變量，整理就可以得到間接可測端點方程：

將方程（2）展開可得到下述矩陣：

可以知道，方程（2）有解的充分必要條件為rank（H）＝rank（HB）＝q，此時子網絡N1可解。

定理1 線性時不變模擬網絡N的連通子網絡N1當滿足：1）m1≥m2；2）rank（YUNJT＋YUMUUC1）＝jt（即混合系數矩陣H滿秩）時，N1有解。

2.2 網絡撕裂法的基本原理

目前在解決大規模復雜電路中使用網絡撕裂法的基本原理為Kron撕裂法，即把一個大型電路撕裂成一系列拓撲獨立的較小電路部分，然后獨立求解［2］。

在模擬電路中的故障診斷一般采用基于網絡撕裂的子網絡級故障診斷的方法［3］，此法通過置換定理，利用電壓比較確定故障子網絡。它不需要去建立故障模型，避免了對KCL方程的校驗，更適用于實際的工程需求。

3 圖論法

在基于DES理論來進行數?；旌想娐饭收显\斷的過程中，最小測試集的求取是關鍵，但是到目前最小測試集的獲取仍沒有一個統一的方法。離散數學中的圖論法能夠方便快捷的獲得被測電路的最小測試集，并且有利于進一步建立故障診斷字典。

3.1 圖論的基本概念

圖論（Graph Theory）是數學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關系。

在基于圖論的最小測試集的尋找過程中，涉及到基本回路的概念：在一條回路中，除了首尾兩個節點之外，每個節點只出現一次，那么這條回路就稱為基本回路［4］。

我們在進行電路故障分析的時候，可以將電路中的各個狀態看成為基本回路中的節點。一個基本回路中，每個節點代表一個事件觸發后電路可能進入的狀態，即將一個事件可能觸發的電路狀態組成一個基本回路。而利用基本回路尋求最小測試集時應遵循以下幾點［5］：

1）如果一個圖只具有一個節點，那么此圖的結點為可診斷故障。這樣的圖為平凡圖。

2）若兩個基本回路只有一個公共結點，則此結點為可診斷故障，由兩事件觸發。

3）若兩事件回路完全相同，則測試集存在冗余，需刪除兩回路的其中之一。

4）若兩回路除去公共節點，各回路或者其中一條回路僅剩余一個節點，則此結點所代表的故障由此兩事件診斷，若公共節點多余一個，可由此兩事件測試是否存在故障。

5）在數字電路中，若相鄰的兩個事件僅僅輸出不同，則兩事件不能同時發生，在求取最小測試集的時候，二者只能取其一。

6）在增加事件的過程中，盡量使得每增加一個事件可以診斷出至少一個故障狀態，直到分區中所有狀態都被診斷為止。

3.2 利用圖論法求取最小測試集［6］

通過圖論法對模擬電路和數字電路分別進行最小測試集的求取：

1）模擬電路

如圖3所示模擬電路。在此電路中，兩個電阻可能處于開路或者短路狀態，可得到電路的狀態集Q，Q＝｛n，o1，o2，s1，s2｝，n 為 正 常狀態；o1，o2分別代表電阻R1，R2處于開路狀態；s1，s2分別代表電阻R1，R2處于短路狀態。

圖3 模擬電路應用

定義事件集Σ：Σ＝｛σ1，σ2，σ3｝，其 中σ1：Vout＝0；σ2：Vout＝Vin；σ3：I＝0。狀態分區T：T＝｛｛n｝，｛o1｝，｛o2｝，｛s1｝，｛s2｝｝。

用基本回路的形式可以描繪出電路的狀態，如圖4所示。

由利用基本回路求取最小測試集的幾點歸論可得：在當前條件下，電路可測，且最小測試集為：minOES（T）＝｛σ1，σ2，σ3｝。

2）數字電路

圖4 模擬電路狀態圖

取圖5作為示例，利用圖論法來求取其最小測試集。

指定電路的狀態集Q：Q＝｛n，m0，n0，p0，q0，m1，n1，p1，q1｝，其中n代表電路正常狀態，Xi代表X（X為m，n，p，q其中之一）處有固定i（i＝0，1）故障。

圖5 數字電路

表1 狀態轉移函數表

根據輸入和輸出的所有可能組合，定義事件集Σ：Σ＝｛σmnpq｜m，n，p，q∈｛0，1｝｝，該集合包含16個事件，可列得電路的轉移函數表，如表1所示。

若電路分區是將電路的狀態集Q中的每一個狀態都作為一個獨立的小單元來對待，那么即使所有的事件都是可觀測到的也無法區分狀態m0，n0和p0。因此，我們需要尋找一個最優的測試分區（取s＝｛m0，n0，p0｝）：

根據狀態轉移函數表可以得到該電路的狀態圖，黑點表示平凡圖節點。在增加事件的過程中，遵循上述所列歸論，直到分區中所有狀態都被診斷，如圖6所示。

此時，僅需要4個事件就可以診斷出分區inf D（T）的所有狀態，即在當前狀態分區inf D（T）和事件集Σ下，電路可測且最小測試集為：

圖6 數字電路狀態圖

4 實例分析

經過研究發現，圖論法中狀態和事件之間成指數關系，這樣的話，如果將其應用到大規模的電路中，將會產生巨大的工作量。在此，設想用網絡撕裂法與圖論法相結合的方法，首先基于網絡分析中的置換定理將整個電路系統用網絡撕裂法分割成為若干個子網絡系統，然后在這些子網絡系統中分別進行圖論法求解，可能會達到減少工作量，提高工作效率，優化最小可測試集提取的目的。

圖7 數?；旌想娐吩\斷舉例

以圖7所示電路圖為實例，具體分析：

在圖中左半部分選取參考節點0、4、6、7、8、10作為電路的測試用可及節點。測試前在節點0、10之間施加4V的激勵電壓，這樣一來，就可以把電路撕裂成S1和S2兩個部分。

繼續在節點7、10分別加上2V和4V的激勵電壓，就可以把S1撕裂成兩個子網絡，虛線分開，可以定位故障處于第一部分。

在完成了網絡撕裂之后，復雜的數?；旌想娐芬呀洷环指畛蓛蓚€簡單的小型模擬電路和獨立的數字電路部分，此時可以依據圖論法分別求得分割后電路各自的最小測試集 minOES（T）n，n＝1，2，…，n，繼而可以方便的求得電路的最小測試集：

minOES（T）＝（minOES（T）s11∩minOES（T）s12）∪minOES（T）s2

5 結語

論文重點闡述了網絡撕裂法和圖論法作用于基于DES理論建模的數?；旌想娐分校摲椒ㄟm用于診斷串聯結構的混合電路。當混合電路并非簡單的串聯結構時，此方法依舊適用，當相對復雜。

［1］Aly E Salama，Janusza A Starzyk，John W Bandler.A unified decomposition approach for fault location in large analog circuits［J］.IEEE Trans.on Circuits and Systems，1984，CAS31（7）：609～622.

［2］趙永堅.撕裂法在電路模擬程序中的應用［J］.微小型計算機開發與應用，1991（3）：19～20，35.

［3］陳圣儉.模擬電路故障診斷理論與工程應用研究［D］.軍械工程學院博士學位論文，1997.

［4］徐潔磐，惠永壽.離散數學及其在計算機中的應用［M］.北京：人民郵電出版社，1985，7.

［5］胡政，黎瓊煒.可測試性技術中的圖論問題及其求解［J］.國防科技大學學報，2000，22（6）.

［6］蔣薇薇，魯昌華，章其波，等.基于圖論的最小測試集的尋找［J］.儀表儀器學報，2003，24（4）.

［7］FENG L，ZHENG H L，LIN T W.A Uniform Approach to Mixed-Signal Circuit Test［J］.International Journal of Circuit Theory and Applications，1997，25：81-93.

［8］陳光禹，潘忠良.可測試性技術［M］.北京：電子工業出版社，1997.