基于二叉樹的時(shí)序電路測(cè)試序列設(shè)計(jì)

高澤涵 ，黃 嵐

（廣州大學(xué) 廣東 廣州 510091）

在時(shí)序電路的設(shè)計(jì)或故障檢測(cè)過(guò)程中，需要對(duì)電路進(jìn)行狀態(tài)驗(yàn)證，狀態(tài)驗(yàn)證就是用一個(gè)事先設(shè)計(jì)的測(cè)試序列，對(duì)待測(cè)電路的輸入端進(jìn)行激勵(lì)，同時(shí)檢測(cè)電路的輸出響應(yīng)，判斷電路是否具有全部設(shè)定狀態(tài)，能否實(shí)現(xiàn)設(shè)定的狀態(tài)轉(zhuǎn)換。測(cè)試序列設(shè)計(jì)包括：描述電路狀態(tài)轉(zhuǎn)換信息；確定電路到達(dá)全部預(yù)定狀態(tài)所需的輸入測(cè)試碼；將測(cè)試碼以適當(dāng)算法構(gòu)成狀態(tài)測(cè)試序列。使用測(cè)試序列對(duì)電路輸入端進(jìn)行激勵(lì)，電路具有設(shè)定的全部狀態(tài)，能夠?qū)崿F(xiàn)設(shè)定的狀態(tài)轉(zhuǎn)換功能。則電路設(shè)計(jì)目的達(dá)到或電路無(wú)故障，反之設(shè)計(jì)目的未達(dá)到或電路有故障。

有兩類設(shè)計(jì)時(shí)序電路測(cè)試序列的方法：第一類稱為迭代法，將時(shí)序電路等價(jià)為p維的組合電路迭代模型，考察i個(gè)時(shí)鐘到來(lái)時(shí)pi維組合電路模型的輸入輸出響應(yīng)，并按一定的迭代算法求出該時(shí)序電路的測(cè)試序列。第二類稱為檢測(cè)試驗(yàn)法，通過(guò)對(duì)待測(cè)時(shí)序電路進(jìn)行試驗(yàn)性激勵(lì)，導(dǎo)出一個(gè)測(cè)試序列，宏觀地檢查輸出是否實(shí)現(xiàn)預(yù)定功能[1]。

前者需要建立多個(gè)電路模型，計(jì)算方法復(fù)雜。后者方法簡(jiǎn)單但是需要多次激勵(lì)驗(yàn)證，特別是對(duì)于多層邏輯結(jié)構(gòu)的電路，試驗(yàn)性激勵(lì)將十分繁雜。通過(guò)對(duì)時(shí)序電路狀態(tài)描述，建立電路狀態(tài)二叉樹，利用二叉樹具有的數(shù)據(jù)元素（節(jié)點(diǎn)、分支）的非線性關(guān)系，設(shè)計(jì)時(shí)序電路的測(cè)試序列具有簡(jiǎn)單清晰的特點(diǎn)。

1 電路狀態(tài)描述

時(shí)序電路狀態(tài)二叉樹可以根據(jù)電路狀態(tài)轉(zhuǎn)換表的信息建立。在電路設(shè)計(jì)階段，狀態(tài)轉(zhuǎn)換表可以由所需的狀態(tài)轉(zhuǎn)換圖推出。在已知電路測(cè)試或故障診斷階段，狀態(tài)轉(zhuǎn)換表可以通過(guò)電路狀態(tài)分析推出。例如，圖1所示的時(shí)序電路，由Q1、Q0兩個(gè)JK觸發(fā)器在同一時(shí)鐘CLK控制下翻轉(zhuǎn)，X為輸入信號(hào)，Z為輸出信號(hào)。由電路分析可知：

電路的觸發(fā)器驅(qū)動(dòng)方程為：J1=K1=（XQ0）′；J0=X K0=（X′Q1）′

電 路 的 觸 發(fā) 器 狀 態(tài) 方 程 為 ：Q1N+1=X′Q1′+Q1′Q0′+XQ1Q0；Q0N+1=XQ0′+X′Q1Q0

電路的輸出方程為：Z=X⊕（Q1Q0′）

電路的觸發(fā)器位數(shù)N=2，狀態(tài)數(shù)M=2N=4，4個(gè)狀態(tài)分別為 A=00、B=01、C=10、D=11。

所以，圖1所示時(shí)序電路的狀態(tài)轉(zhuǎn)換功能可以用如圖2所示狀態(tài)圖描述[2]。

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

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

圖1 時(shí)序電路Fig.1 A time sequential circuit

圖2 狀態(tài)圖Fig.2 Status map

表1 狀態(tài)表Tab.1 Status table

表2 狀態(tài)引導(dǎo)表Tab.2 Status boot table

2 電路二叉樹構(gòu)成

二叉樹是一種以節(jié)點(diǎn) （數(shù)據(jù)元素）按分支（樹枝）關(guān)系組織，按分支層次關(guān)系定義的樹型非線性數(shù)據(jù)結(jié)構(gòu)。其基本特點(diǎn)是：第i層最多有2i-1個(gè)節(jié)點(diǎn)，i=1層只有一個(gè)節(jié)點(diǎn)稱為根節(jié)點(diǎn)；每個(gè)節(jié)點(diǎn)最多有兩個(gè)后繼子樹，除根節(jié)點(diǎn)外的所有節(jié)點(diǎn)都有且只有一個(gè)直接前驅(qū)；深度為k的的二叉樹的最大節(jié)點(diǎn)數(shù)為2k-1。如圖3是深度為3的二叉樹[3]。

圖3 典型二叉樹Fig.3 A typical binary tree

二叉樹描述時(shí)序電路時(shí)，用二叉樹節(jié)點(diǎn)Ni代表電路在i時(shí)刻的狀態(tài)，電路初始（或復(fù)位）狀態(tài)稱為根節(jié)點(diǎn)。用二叉樹兩節(jié)點(diǎn)之間的樹枝表示輸入碼的邏輯值，在節(jié)點(diǎn)Ni處輸入碼X=0構(gòu)成左子樹，輸入碼X=1構(gòu)成右子樹，兩棵子樹分別連接下一層的兩個(gè)節(jié)點(diǎn)。所以，節(jié)點(diǎn)Ni到Ni+1之間樹枝的遍歷，在邏輯上代表了電路由狀態(tài)Ni轉(zhuǎn)換到狀態(tài)Ni+1所需的輸入序列Xj。其中，由根節(jié)點(diǎn)N01到節(jié)點(diǎn)Ni所經(jīng)歷的樹枝，組成了電路的一個(gè)測(cè)試序列Xi。Xi的長(zhǎng)度就是二叉樹的層數(shù)，各層的節(jié)點(diǎn)數(shù)N=2i-1按指數(shù)規(guī)律增加。

通電初始時(shí)刻圖1時(shí)序電路在狀態(tài)二叉樹的根節(jié)點(diǎn)N01處，可能是 A、B、C、D中的任意一個(gè)狀態(tài)，可以用節(jié)點(diǎn)向量N01=（ABCD）表示，如圖 4 所示。

圖4 電路狀態(tài)二叉樹Fig.4 A binary tree circuit status

在根節(jié)點(diǎn)N01處：當(dāng)輸入X=0，形成根節(jié)點(diǎn)的左子樹，連接到N11節(jié)點(diǎn)，如圖4所示。由表1可知輸入X=0時(shí)，若輸出Z=1，電路發(fā)生了初態(tài)PS=C到現(xiàn)態(tài)NS=A的轉(zhuǎn)換，記為C0→1A；若輸出 Z=0則電路可能發(fā)生 D0→0B、A0→0C或 B0→0C的狀態(tài)轉(zhuǎn)換。所以，節(jié)點(diǎn)N11處電路狀態(tài)可用節(jié)點(diǎn)向量N11=（A）1（BCC）0表示。其中，節(jié)點(diǎn)向量的分量則表示電路在輸入Xi作用下，當(dāng)輸出為Zi時(shí)的電路狀態(tài)。例如，分量（A）1表示測(cè)得Z=1電路應(yīng)為狀態(tài)A；分量（BCC）0表示測(cè)得Z=0電路有可能是狀態(tài)B或C。

當(dāng)輸入X=1，形成根節(jié)點(diǎn)的右子樹，連接到N12節(jié)點(diǎn)，如圖4所示。由表1可知輸入X=1時(shí)，若Z=0電路發(fā)生了C1→0B的狀態(tài)轉(zhuǎn)換；若輸出Z=1則電路可能發(fā)生B1→1A、A1→1D或D1→1C 的狀態(tài)轉(zhuǎn)換。 用向量 N12= （ACD）1（B）0表示。

電路到達(dá)節(jié)點(diǎn) N11=（A）1（BCC）0后：再輸入 X=0（相當(dāng)于在根節(jié)點(diǎn)N01處輸入序列Xi=00），電路到達(dá)節(jié)點(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），電路到達(dá)節(jié)點(diǎn) N22=（D）11（A）01（BB）00處。

同理， 輸入序列 Xi=10， 電路到達(dá)節(jié)點(diǎn) N23=（BC）10（A）11（C）00；輸入序列 Xi=11，電路到達(dá)節(jié)點(diǎn) N24=（CD）11（B）10（A）01?？梢?，當(dāng)輸入序列長(zhǎng)度為2時(shí)，到達(dá)二叉樹的第二層，有4棵子樹對(duì)應(yīng) 4 個(gè)節(jié)點(diǎn) N21、N22、N23、N24，如圖 4 所示。

依次由根節(jié)點(diǎn)N01處開始，輸入序列為X=000、X=001、X=010、X=011、s=100、X=101、X=110、X=111， 電路到達(dá)節(jié)點(diǎn)N31～N38，……即可以得到時(shí)序電路二叉樹，如圖4所示。其中，輸入序列長(zhǎng)度i是二叉樹的層數(shù)，各層的節(jié)點(diǎn)數(shù)N=2i-1按指數(shù)規(guī)律增加。

在構(gòu)建電路二叉樹過(guò)程中，當(dāng)節(jié)點(diǎn)向量與前級(jí)某節(jié)點(diǎn)向量重復(fù)時(shí)，該節(jié)點(diǎn)是二叉樹的一個(gè)終止節(jié)點(diǎn)。例如：N41與N21重復(fù)、N44與N31重復(fù)、N49與N35重復(fù)，二叉樹不再?gòu)倪@些節(jié)點(diǎn)延伸?？紤]到研究時(shí)序電路二叉樹的目的是確定測(cè)試序列，當(dāng)節(jié)點(diǎn)向量能夠確定電路唯一狀態(tài)（例如，節(jié)點(diǎn)N511處電路狀態(tài)必為C）二叉樹不再?gòu)倪@個(gè)節(jié)點(diǎn)延伸。當(dāng)節(jié)點(diǎn)的輸出序列Z能夠區(qū)分電路全部狀態(tài)，（例如，節(jié)點(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。）二叉樹也不再?gòu)倪@個(gè)節(jié)點(diǎn)延伸[1]。

3 節(jié)點(diǎn)向量與輸入序列

電路二叉樹的一個(gè)節(jié)點(diǎn)向量通常由多個(gè)分量組成，例如向量 N11=（A）1（BCC）0由（A）1和（BCC）0兩個(gè)分量構(gòu)成。 一個(gè)分量通常包含多個(gè)電路狀態(tài)，例如分量 （BCC）0包含B和C兩個(gè)狀態(tài)。有兩個(gè)以上不同狀態(tài)組成的分量稱為非同類分量，由非同類分量構(gòu)成的向量稱為不確定向量，例如N01、N11、N12和N23。

只包含一個(gè)狀態(tài)或僅包含多個(gè)相同狀態(tài)的分量 （例如（A）1和（AA）00）稱為同類分量，由同類分量構(gòu)成的向量稱為同類不確定向量 （例如N21和N22），在同類不確定向量節(jié)點(diǎn)處，總能根據(jù)電路的輸出序列唯一地確定電路達(dá)到的狀態(tài)。所以，由根節(jié)點(diǎn)到同類不確定向量節(jié)點(diǎn)，經(jīng)歷樹枝構(gòu)成的輸入序列稱為引導(dǎo)序列，記為Xh。例如，由N01到達(dá)N22的輸入序列X=01就是圖1電路的一個(gè)引導(dǎo)序列。在引導(dǎo)序列Xh=01作用下，若Z=00則狀態(tài)必為B；Z=01狀態(tài)必為A；Z=11狀態(tài)必為D。

只包含一個(gè)狀態(tài)的同類分量（例如（A）1、（B）100和（C）10）又稱為平凡不確定分量，全部由平凡不確定分量構(gòu)成的向量稱為平凡不確定向量（例如 N38=（B）110（C）111（A）101（D）011），在平凡不確定向量節(jié)點(diǎn)處，電路雖可能有多個(gè)不同狀態(tài)，但根據(jù)輸出序列可以確定電路當(dāng)前狀態(tài)。所以，由根節(jié)點(diǎn)到平凡不確定向量節(jié)點(diǎn)，經(jīng)歷樹枝構(gòu)成的輸入序列稱為區(qū)分序列，記為Xd。例如，由N01到達(dá)N38的輸入序列X=111就是圖1電路的區(qū)分序列。在區(qū)分序列Xd=111作用下，若輸出序列Z=101，則電路狀態(tài)由D到達(dá) A，記為D111→101A；若輸出序列Z=110，則電路狀態(tài)由A到達(dá)B，記為A111→110B；若輸出序列 Z=111，則電路狀態(tài)由B到達(dá)C，記為B111→111C；若輸出序列 Z=011，則電路狀態(tài)由C到達(dá)D，記為C111→011D。區(qū)分序列常用于驗(yàn)證或確定電路所處的狀態(tài)，區(qū)分序列也是引導(dǎo)序列，但并不是每個(gè)時(shí)序電路都存在區(qū)分序列。

利用區(qū)分序列可以生成表3是圖1電路在區(qū)分序列Xd=111作用下的電路狀態(tài)引導(dǎo)表。其中：IS是Xd作用前狀態(tài)，F(xiàn)S是作用后的狀態(tài)。

全部由同一狀態(tài)同類分量構(gòu)成的向量（例如N511=（C）11010（C）01000（CC）00000）稱為同類不確定向量，在同類平凡不確定向量節(jié)點(diǎn)處，電路雖可能有多個(gè)不同的輸出序列，但電路狀態(tài)是唯一的。所以，由根節(jié)點(diǎn)到同類不確定向量節(jié)點(diǎn)，經(jīng)歷樹枝構(gòu)成的輸入序列稱為同步序列，記為Xs。例如，由N01到N511的輸入序列X=01010就是圖1電路的一個(gè)同步序列，在同步序列Xs=01010的激勵(lì)下電路由N01到達(dá)N511，無(wú)論輸出序列Z=11010、Z=01000或Z=00000電路狀態(tài)都為C。同步序列是一個(gè)特殊的引導(dǎo)序列，常用于把電路從未知狀態(tài)引導(dǎo)到一個(gè)已知的狀態(tài)起點(diǎn)。

能夠?qū)㈦娐窂囊阎獱顟B(tài)轉(zhuǎn)換到預(yù)定狀態(tài)的輸入序列X稱為轉(zhuǎn)換序列記為Xt，轉(zhuǎn)換序列由轉(zhuǎn)換碼構(gòu)成。由狀態(tài)轉(zhuǎn)換圖 2 中可見 Xt0=0 是圖 1 電路 C0→1A、A0→0C、B0→0C、D0→0B的轉(zhuǎn)換碼；Xt1=1 是 A1→1D、B1→1A、C1→0B、D1→1C 的轉(zhuǎn)換碼。轉(zhuǎn)換序列常用于核實(shí)電路狀態(tài)轉(zhuǎn)換功能，例如：當(dāng)圖1電路已確認(rèn)引導(dǎo)到C狀態(tài)后，在轉(zhuǎn)換序列Xt10=Xt1-Xt0=10激勵(lì)下，如果輸出序列Z=00表明電路實(shí)現(xiàn)了C1→0B、B0→0C轉(zhuǎn)換[4]。

4 測(cè)試序列與狀態(tài)驗(yàn)證

時(shí)序電路狀態(tài)驗(yàn)證過(guò)程通常包括：狀態(tài)引導(dǎo)階段，采用引導(dǎo)序列將電路從未知狀態(tài)引導(dǎo)到預(yù)定狀態(tài)。狀態(tài)驗(yàn)證階段，采用區(qū)分序列逐一核實(shí)電路具有全部狀態(tài)。狀態(tài)轉(zhuǎn)換驗(yàn)證階段，采用轉(zhuǎn)換序列核實(shí)電路具有全部狀態(tài)轉(zhuǎn)換功能。能夠完成狀態(tài)驗(yàn)證全部過(guò)程的輸入序列，稱為測(cè)試序列。在實(shí)踐中，測(cè)試序列可采用引導(dǎo)序列Xh、區(qū)分序列Xd以及必要的轉(zhuǎn)換序列Xt組成測(cè)試序列，如測(cè)試序列可為X=Xh-Xd-Xt等[1]。

例如，圖1所示電路最直觀的測(cè)試序列可以是X=Xs-4Xd1-4Xt1-2Xt0-Xt10-Xd1-2Xt0。其中，同步序列Xs=01010將電路由未知引導(dǎo)到確定的狀態(tài)C；4組區(qū)分序列Xd1=111分別驗(yàn)證電路具有D、A、B和C4個(gè)狀態(tài)；轉(zhuǎn)換序列4Xt1=1111分別驗(yàn)證電路有 C1→0B、B1→1A、A1→1D、D1→1C 狀態(tài)轉(zhuǎn)換功能；轉(zhuǎn)換序列2Xt0=00分別驗(yàn)證電路有C1→0A、A0→0C狀態(tài)轉(zhuǎn)換功能；轉(zhuǎn)換序列Xt10=10驗(yàn)證電路有C1→0A轉(zhuǎn)換功能；區(qū)分序列Xd1=111將電路由C狀態(tài)引導(dǎo)到D狀態(tài)；轉(zhuǎn)換序列2Xt0=00驗(yàn)證電路有D0→0B轉(zhuǎn)換功能。至此，圖1電路具有的所有狀態(tài)和狀態(tài)轉(zhuǎn)換功能都得到驗(yàn)證。這樣構(gòu)成的測(cè)試序列X=Xs-4Xd1-4Xt1-2Xt0-Xt10-Xd1-2Xt0=01010 111 111 111 111 1111 00 10 111 00長(zhǎng)度達(dá)30層。

實(shí)踐中，在能夠確認(rèn)電路所有狀態(tài)和狀態(tài)轉(zhuǎn)換功能的原則上，測(cè)試序列長(zhǎng)度越短越好。對(duì)于圖1電路的測(cè)試序列也可以是X=Xs-2Xt0-4Xt1-Xd。其中，同步序列Xs=01010引導(dǎo)電路到C，同時(shí)也驗(yàn)證了電路有C狀態(tài)；轉(zhuǎn)換序列2Xt0=00驗(yàn)證電路有C0→1A、A0→0C轉(zhuǎn)換功能，同時(shí)也驗(yàn)證電路有A狀態(tài)；轉(zhuǎn)換序列4Xt1=1111驗(yàn)證電路有C1→0B、B1→1A轉(zhuǎn)換功能，且驗(yàn)證電路有B狀態(tài)，驗(yàn)證電路有A1→1D、D1→1C轉(zhuǎn)換功能，且驗(yàn)證有D狀態(tài)；區(qū)分序列Xd=111引導(dǎo)電路C111→011D到達(dá)狀態(tài)D；轉(zhuǎn)換序列2Xt0=00驗(yàn)證電路有D0→0B、B0→0C轉(zhuǎn)換。這時(shí)測(cè)試序列X=01010 00 1111 111 00長(zhǎng)度僅為16層。在該測(cè)試序列作用下，若電路輸出序列為Z=XXXXX 10 0111 011 00（前5個(gè)輸出可能是11010或01000或00000之一），則圖1電路具有A、B、C、D4個(gè)狀態(tài)，并實(shí)現(xiàn)了圖2設(shè)定全部狀態(tài)轉(zhuǎn)換功能[5]。

5 結(jié) 論

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

[1]沈嗣昌.數(shù)字電路故障診斷 [M].南京：東南大學(xué)出版社，1991.

[2]閻石.數(shù)字電子技術(shù)基礎(chǔ)[M].北京:高等教育出版社，1998.

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，2008.

[4]吳繼娟.數(shù)字邏輯[M].北京:人民郵電出版社，2008.

[5]高澤涵.電子電路故障診斷技術(shù) [M].西安:西安電子科技大學(xué)出版社，2000.

[6]石尚斌，周天健.電網(wǎng)絡(luò)與設(shè)備的計(jì)算機(jī)故障診斷[M].北京:航空工業(yè)出版社，1989.