基于二叉樹(shù)的時(shí)序電路測試序列設計

摘要：為了實(shí)現時(shí)序電路狀態(tài)驗證和故障檢測，需要事先設計一個(gè)輸入測試序列?；?a class="contentlabel" href="http://dyxdggzs.com/news/listbylabel/label/二叉樹(shù)">二叉樹(shù)節點(diǎn)和樹(shù)枝的特性，建立時(shí)序電路狀態(tài)二又樹(shù)，按照電路二叉樹(shù)節點(diǎn)(狀態(tài))與樹(shù)枝(輸入)的層次邏輯關(guān)系，可以直觀(guān)和便捷地設計出時(shí)序電路測試序列。用測試序列激勵待測電路，可以驗證電路是否具有全部預定狀態(tài)，是否能夠實(shí)現預定狀態(tài)轉換。
關(guān)鍵詞：二叉樹(shù)；時(shí)序電路；測試序列；狀態(tài)驗證；故障檢測

在時(shí)序電路的設計或故障檢測過(guò)程中，需要對電路進(jìn)行狀態(tài)驗證，狀態(tài)驗證就是用一個(gè)事先設計的測試序列，對待測電路的輸入端進(jìn)行激勵，同時(shí)檢測電路的輸出響應，判斷電路是否具有全部設定狀態(tài)，能否實(shí)現設定的狀態(tài)轉換。測試序列設計包括：描述電路狀態(tài)轉換信息；確定電路到達全部預定狀態(tài)所需的輸入測試碼；將測試碼以適當算法構成狀態(tài)測試序列。使用測試序列對電路輸入端進(jìn)行激勵，電路具
有設定的全部狀態(tài)，能夠實(shí)現設定的狀態(tài)轉換功能。則電路設計目的達到或電路無(wú)故障，反之設計目的未達到或電路有故障。
有兩類(lèi)設計時(shí)序電路測試序列的方法：第一類(lèi)稱(chēng)為迭代法，將時(shí)序電路等價(jià)為p維的組合電路迭代模型，考察i個(gè)時(shí)鐘到來(lái)時(shí)pi維組合電路模型的輸入輸出響應，并按一定的迭代算法求出該時(shí)序電路的測試序列。第二類(lèi)稱(chēng)為檢測試驗法，通過(guò)對待測時(shí)序電路進(jìn)行試驗性激勵，導出一個(gè)測試序列，宏觀(guān)地檢查輸出是否實(shí)現預定功能。
前者需要建立多個(gè)電路模型，計算方法復雜。后者方法簡(jiǎn)單但是需要多次激勵驗證，特別是對于多層邏輯結構的電路，試驗性激勵將十分繁雜。通過(guò)對時(shí)序電路狀態(tài)描述，建立電路狀態(tài)二叉樹(shù)，利用二叉樹(shù)具有的數據元素(節點(diǎn)、分支)的非線(xiàn)性關(guān)系，設計時(shí)序電路的測試序列具有簡(jiǎn)單清晰的特點(diǎn)。

1 電路狀態(tài)描述
時(shí)序電路狀態(tài)二叉樹(shù)可以根據電路狀態(tài)轉換表的信息建立。在電路設計階段，狀態(tài)轉換表可以由所需的狀態(tài)轉換圖推出。在已知電路測試或故障診斷階段，狀態(tài)轉換表可以通過(guò)電路狀態(tài)分析推出。例如，圖1所示的時(shí)序電路，由Q1、Q0兩個(gè)JK觸發(fā)器在同一時(shí)鐘CLK控制下翻轉，X為輸入信號，Z為輸出信號。由電路分析可知：
電路的觸發(fā)器驅動(dòng)方程為：J1=K1=(XQ0)’；J0=X K0=(X’Q1)’
電路的觸發(fā)器狀態(tài)方程為：；
電路的輸出方程為：
電路的觸發(fā)器位數N=2，狀態(tài)數M=2N=4，4個(gè)狀態(tài)分別為A=00、B=01、C=10、D=11。
所以，圖1所示時(shí)序電路的狀態(tài)轉換功能可以用如圖2所示狀態(tài)圖描述。

設：PS為初態(tài)，NS為現態(tài)，圖1所示時(shí)序電路的狀態(tài)轉換功能也可以用如表1所示狀態(tài)表來(lái)描述。

狀態(tài)表描述了電路在輸入X作用下，輸出Z以及電路狀態(tài)NS與輸入X之間的邏輯關(guān)系，包涵了電路狀態(tài)驗證和故障檢測所需的全部測試碼，原則上可以直接使用狀態(tài)表的信息設計出電路的測試序列。但是，狀態(tài)表中描述測試碼與時(shí)序電路狀態(tài)的邏輯層次關(guān)系不明顯，沒(méi)有直接反映出電路狀態(tài)與輸入的多層邏輯關(guān)系。所以，設計具有多層邏輯關(guān)系電路的輸入測試序列，僅狀態(tài)表信息有一定難度。

2 電路二叉樹(shù)構成
二叉樹(shù)是一種以節點(diǎn)(數據元素)按分支(樹(shù)枝)關(guān)系組織，按分支層次關(guān)系定義的樹(shù)型非線(xiàn)性數據結構。其基本特點(diǎn)是：第i層最多有2i-1個(gè)節點(diǎn)，i=1層只有一個(gè)節點(diǎn)稱(chēng)為根節點(diǎn)；每個(gè)節點(diǎn)最多有兩個(gè)后繼子樹(shù)，除根節點(diǎn)外的所有節點(diǎn)都有且只有一個(gè)直接前驅?zhuān)簧疃葹閗的的二叉樹(shù)的最大節點(diǎn)數為2k-1。如圖3是深度為3的二叉樹(shù)。

二叉樹(shù)描述時(shí)序電路時(shí)，用二叉樹(shù)節點(diǎn)Ni代表電路在i時(shí)刻的狀態(tài)，電路初始(或復位)狀態(tài)稱(chēng)為根節點(diǎn)。用二叉樹(shù)兩節點(diǎn)之間的樹(shù)枝表示輸入碼的邏輯值，在節點(diǎn)Ni處輸入碼X=0構成左子樹(shù)，輸入碼X=1構成右子樹(shù)，兩棵子樹(shù)分別連接下一層的兩個(gè)節點(diǎn)。所以，節點(diǎn)Ni到Ni+1之間樹(shù)枝的遍歷，在邏輯上代表了電路由狀態(tài)Ni轉換到狀態(tài)Ni+1所需的輸入序列Xi。其中，由根節點(diǎn)N01到節點(diǎn)Ni所經(jīng)歷的樹(shù)枝，組成了電路的一個(gè)測試序列Xi。Xi的長(cháng)度就是二叉樹(shù)的層數，各層的節點(diǎn)數N=2i-1按指數規律增加。
通電初始時(shí)刻圖1時(shí)序電路在狀態(tài)二叉樹(shù)的根節點(diǎn)N01處，可能是A、B、C、D中的任意一個(gè)狀態(tài)，可以用節點(diǎn)向量N01=(ABCD)表示，如圖4所示。

在根節點(diǎn)N01處：當輸入X=0，形成根節點(diǎn)的左子樹(shù)，連接到N11節點(diǎn)，如圖4所示。由表1可知輸入X=0時(shí)，若輸出Z=1，電路發(fā)生了初態(tài)PS=C到現態(tài)NS=A的轉換，記為C0→1A；若輸出Z=0則電路可能發(fā)生D0→0B、A0→0C或B0→0C的狀態(tài)轉換。所以，節點(diǎn)N11處電路狀態(tài)可用節點(diǎn)向量N11=(A)1(BCC)0表示。其中，節點(diǎn)向量的分量則表示電路在輸入Xi作用下，當輸出為Zi時(shí)的電路狀態(tài)。例如，分量(A)1表示測得Z=1電路應為狀態(tài)A；分量(BCC)0表示測得Z=0電路有可能是狀態(tài)B或C。
當輸入X=1，形成根節點(diǎn)的右子樹(shù)，連接到N12節點(diǎn)，如圖4所示。由表1可知輸入X=1時(shí)，若Z=0電路發(fā)生了C1→0B的狀態(tài)轉換；若輸出Z=1則電路可能發(fā)生B1→1A、A1→1D或D1→1C的狀態(tài)轉換。用向量N12=(ACD)1(B)0表示。
電路到達節點(diǎn)N11=(A)1(BCC)0后：再輸入X=0(相當于在根節點(diǎn)N01處輸入序列Xi=00)，電路到達節點(diǎn)N21=(C)10(C)00(AA)01處，如圖4所示。其中，分量(C)10表示在輸入序列X=00作用下，若輸出序列Z=10電路狀態(tài)為C；分量(C)00表示在輸入序列X=00作用下，若輸出序列Z=00電路狀態(tài)也為C；分量(AA)01表示在輸入序列X=00作用下，若輸出序列Z=01電路狀態(tài)為A。若再輸入X=1(即N01處輸入序列Xi=01)，電路到達節點(diǎn)N22=(D)11(A)01(BB)00處。
同理，輸入序列Xi=10，電路到達節點(diǎn)N23=(BC)10(A)11(C)00；輸入序列Xi=11，電路到達節點(diǎn)N24=(CD)11(B)10(A)01?？梢?jiàn)，當輸入序列長(cháng)度為2時(shí)，到達二叉樹(shù)的第二層，有4棵子樹(shù)對應4個(gè)節點(diǎn)N21、N22、N23、N24，如圖4所示。
依次由根節點(diǎn)N01處開(kāi)始，輸入序列為X=000、X=001、X=010、X=011、s=100、X=101、X=110、X=111，電路到達節點(diǎn)N31～N38，……即可以得到時(shí)序電路二叉樹(shù)，如圖4所示。其中，輸入序列長(cháng)度i是二叉樹(shù)的層數，各層的節點(diǎn)數N=2i-1按指數規律增加。
在構建電路二叉樹(shù)過(guò)程中，當節點(diǎn)向量與前級某節點(diǎn)向量重復時(shí)，該節點(diǎn)是二叉樹(shù)的一個(gè)終止節點(diǎn)。例如：N41與N21重復、N44與N31重復、N49與N35重復，二叉樹(shù)不再從這些節點(diǎn)延伸?？紤]到研究時(shí)序電路二叉樹(shù)的目的是確定測試序列，當節點(diǎn)向量能夠確定電路唯一狀態(tài)(例如，節點(diǎn)N511處電路狀態(tài)必為C)二叉樹(shù)不再從這個(gè)節點(diǎn)延伸。當節點(diǎn)的輸出序列Z能夠區分電路全部狀態(tài)，(例如，節點(diǎn)N38處電路向量N38=(B)110(C)111(A)101(D)011，表明在輸入序列X=111作用下，若Z=110電路狀態(tài)必為B，若Z=111電路狀態(tài)必為C，若Z=101電路狀態(tài)必為A，若Z=011電路狀態(tài)必為D。)二叉樹(shù)也不再從這個(gè)節點(diǎn)延伸。

3 節點(diǎn)向量與輸入序列
電路二叉樹(shù)的一個(gè)節點(diǎn)向量通常由多個(gè)分量組成，例如向量N11=(A)1(BCC)。由(A)1和(BCC)0兩個(gè)分量構成。一個(gè)分量通常包含多個(gè)電路狀態(tài)，例如分量(BCC)0包含B和C兩個(gè)狀態(tài)。有兩個(gè)以上不同狀態(tài)組成的分量稱(chēng)為非同類(lèi)分量，由非同類(lèi)分量構成的向量稱(chēng)為不確定向量，例如N01、N11、N12和N23。
只包含一個(gè)狀態(tài)或僅包含多個(gè)相同狀態(tài)的分量(例如(A)1和(AA)00)稱(chēng)為同類(lèi)分量，由同類(lèi)分量構成的向量稱(chēng)為同類(lèi)不確定向量(例如N21和N22)，在同類(lèi)不確定向量節點(diǎn)處，總能根據電路的輸出序列唯一地確定電路達到的狀態(tài)。所以，由根節點(diǎn)到同類(lèi)不確定向量節點(diǎn)，經(jīng)歷樹(shù)枝構成的輸入序列稱(chēng)為引導序列，記為Xh。例如，由N01到達N22的輸入序列X=01就是圖1電路的一個(gè)引導序列。在引導序列Xh=01作用下，若Z=00則狀態(tài)必為B；Z=01狀態(tài)必為A；Z=11狀態(tài)必為D。
只包含一個(gè)狀態(tài)的同類(lèi)分量(例如(A)1、(B)100和(C)10)又稱(chēng)為平凡不確定分量，全部由平凡不確定分量構成的向量稱(chēng)為平凡不確定向量(例如N38=(B)110(C)111(A)101(D)011)，在平凡不確定向量節點(diǎn)處，電路雖可能有多個(gè)不同狀態(tài)，但根據輸出序列可以確定電路當前狀態(tài)。所以，由根節點(diǎn)到平凡不確定向量節點(diǎn)，經(jīng)歷樹(shù)枝構成的輸入序列稱(chēng)為區分序列，記為Xd。例如，由N01到達N38的輸入序列X=111就是圖1電路的區分序列。在區分序列Xd=111作用下，若輸出序列Z=101，則電路狀態(tài)由D到達A，記為D111→101A；若輸出序列Z=110，則電路狀態(tài)由A到達B，記為A111→110B；若輸出序列Z=111，則電路狀態(tài)由B到達C，記為B111→111C；若輸出序列Z=011，則電路狀態(tài)由C到達D，記為C111→ 011D。區分序列常用于驗證或確定電路所處的狀態(tài)，區分序列也是引導序列，但并不是每個(gè)時(shí)序電路都存在區分序列。
利用區分序列可以生成表3是圖1電路在區分序列Xd=111作用下的電路狀態(tài)引導表。其中：IS是Xd作用前狀態(tài)，FS是作用后的狀態(tài)。
全部由同一狀態(tài)同類(lèi)分量構成的向量(例如N511=(C)11010(C)01000(CC)00000)稱(chēng)為同類(lèi)不確定向量，在同類(lèi)平凡不確定向量節點(diǎn)處，電路雖可能有多個(gè)不同的輸出序列，但電路狀態(tài)是唯一的。所以，由根節點(diǎn)到同類(lèi)不確定向量節點(diǎn)，經(jīng)歷樹(shù)枝構成的輸入序列稱(chēng)為同步序列，記為Xs。例如，由N01到N511的輸入序列X=01010就是圖1電路的一個(gè)同步序列，在同步序列Xs=01010的激勵下電路由N01到達N511，無(wú)論輸出序列Z=11010、Z=01000或Z=00000電路狀態(tài)都為C。同步序列是一個(gè)特殊的引導序列，常用于把電路從未知狀態(tài)引導到一個(gè)已知的狀態(tài)起點(diǎn)。
能夠將電路從已知狀態(tài)轉換到預定狀態(tài)的輸入序列X稱(chēng)為轉換序列記為Xt，轉換序列由轉換碼構成。由狀態(tài)轉換圖2中可見(jiàn)Xt0=0是圖1電路C0→1A、A0→0C、B0→0C、D0→0B的轉換碼；Xt1=1是A1→1D、B1→1A、C1→0B、D1→1C的轉換碼。轉換序列常用于核實(shí)電路狀態(tài)轉換功能，例如：當圖1電路已確認引導到C狀態(tài)后，在轉換序列Xt10=Xt1-Xt0=10激勵下，如果輸出序列Z=00表明電路實(shí)現了C1→0B、B0→0C轉換。

4 測試序列與狀態(tài)驗證
時(shí)序電路狀態(tài)驗證過(guò)程通常包括：狀態(tài)引導階段，采用引導序列將電路從未知狀態(tài)引導到預定狀態(tài)。狀態(tài)驗證階段，采用區分序列逐一核實(shí)電路具有全部狀態(tài)。狀態(tài)轉換驗證階段，采用轉換序列核實(shí)電路具有全部狀態(tài)轉換功能。能夠完成狀態(tài)驗證全部過(guò)程的輸入序列，稱(chēng)為測試序列。在實(shí)踐中，測試序列可采用引導序列Xh、區分序列Xd以及必要的轉換序列Xt組成測試序列，如測試序列可為X=Xh-Xd-Xt等。
例如，圖1所示電路最直觀(guān)的測試序列可以是X=Xs-4Xd1-4Xt1-2Xt0-Xt10-Xd1-2Xt0。其中，同步序列Xs=01010將電路由來(lái)知引導到確定的狀態(tài)C；4組區分序列Xd1=111分別驗證電路具有D、A、B和C4個(gè)狀態(tài)；轉換序列4Xt1=1111分別驗證電路有C1→0B、B1→1A、A1→1D、D1→1C狀態(tài)轉換功能；轉換序列2Xt0=00分別驗證電路有C1→0A、A0→0C狀態(tài)轉換功能；轉換序列Xt10=10驗證電路有C1→0A轉換功能；區分序列Xd1=111將電路由C狀態(tài)引導到D狀態(tài)；轉換序列2Xt0=00驗證電路有D0→0B轉換功能。至此，圖1電路具有的所有狀態(tài)和狀態(tài)轉換功能都得到驗證。這樣構成的測試序列X=Xs-4Xd1-4Xt1-2Xt0-Xt10-Xd1-2Xt0=01010 111 111 111 111 1111 0010 111 00長(cháng)度達30層。
實(shí)踐中，在能夠確認電路所有狀態(tài)和狀態(tài)轉換功能的原則上，測試序列長(cháng)度越短越好。對于圖1電路的測試序列也可以是X=Xs-2Xt0-4Xt1-Xd。其中，同步序列Xs=01010引導電路到C，同時(shí)也驗證了電路有C狀態(tài)；轉換序列2Xt0=00驗證電路有C0→1A、A0→0C轉換功能，同時(shí)也驗證電路有A狀態(tài)；轉換序列4Xt1=1111驗證電路有C1→0B、B1→1A轉換功能，且驗證電路有B狀態(tài)，驗證電路有A1→1D、D1→1C轉換功能，且驗證有D狀態(tài)；區分序列Xd=111引導電路C111→011D到達狀態(tài)D；轉換序列2Xt0=00驗證電路有D0→0B、B0→0C轉換。這時(shí)測試序列X=01010 00 1111 111 00長(cháng)度僅為16層。在該測試序列作用下，若電路輸出序列為Z=XXXXX 10 0111 01100(前5個(gè)輸出可能是11010或01000或00000之一)，則圖1電路具有A、B、C、D 4個(gè)狀態(tài)，并實(shí)現了圖2設定全部狀態(tài)轉換功能。

5 結論
通過(guò)建立時(shí)序電路的狀態(tài)二叉樹(shù)，可以得到該時(shí)序電路的測試序列X，在測試序列X的作用下，電路將產(chǎn)生一個(gè)輸出序列Z。如果無(wú)故障電路在X作用下輸出序列為Zo，有故障電路在X作用下的輸出序列為Zf，顯然Zo≠Zf。在正常序列Zo和故障序列Zf中0、1的個(gè)數和分布規律不同。因此，檢測輸出序列Z的0、1個(gè)數以及分布規律就可以確定電路是否有故障。在實(shí)踐中并不是所有的時(shí)序電路都可以是先找到一個(gè)完整的測試序列，有時(shí)必須根據電路在前一個(gè)序列作用下的輸出序列來(lái)決定繼續檢測所需的測試序列。