第四章同步時(shí)序邏輯電路.

1、1第四章 同步時(shí)序邏輯電路張光河Email: 計(jì)劃授課時(shí)間:2周2大綱 4.1 同步時(shí)序邏輯電路模型同步時(shí)序邏輯電路模型 4.2 觸發(fā)器觸發(fā)器 4.3 同步時(shí)序邏輯電路分析同步時(shí)序邏輯電路分析 4.4 同步時(shí)序邏輯電路設(shè)計(jì)同步時(shí)序邏輯電路設(shè)計(jì) 4.5同步時(shí)序邏輯電路設(shè)計(jì)舉例同步時(shí)序邏輯電路設(shè)計(jì)舉例34.1 同步時(shí)序邏輯電路模型同步時(shí)序邏輯電路模型 4.1.1 同步時(shí)序邏輯電路的結(jié)構(gòu)同步時(shí)序邏輯電路的結(jié)構(gòu) 4.1.2 同步時(shí)序邏輯電路的描述同步時(shí)序邏輯電路的描述4時(shí)序邏輯電路的定義 若一個(gè)邏輯電路在任何時(shí)刻產(chǎn)生的穩(wěn)定輸出不僅與該時(shí)刻電路的輸入信號(hào)有關(guān)，而且與電路過去的輸入信號(hào)有關(guān)，則稱該電路為時(shí)

2、序邏輯電路。 由于時(shí)序邏輯電路的輸出不僅取決于當(dāng)時(shí)的輸入，而且還與電路過去的輸入有關(guān)，因此，電路必須具有記憶功能，以便保存過去的輸入信息5時(shí)序邏輯電路的一般結(jié)構(gòu)存儲(chǔ)電路存儲(chǔ)電路x1xnZ1Zmys y1 Y1 Yr CP由組合電路和存儲(chǔ)電路兩部分組成，通過反饋回路將兩部分連成一個(gè)整體。6時(shí)序邏輯電路的一般結(jié)構(gòu)存儲(chǔ)電路存儲(chǔ)電路x1xnZ1Zmys y1 Y1 Yr CP由組合電路和存儲(chǔ)電路兩部分組成，通過反饋回路將兩部分連成一個(gè)整體。X1Xn：外部向時(shí)序：外部向時(shí)序電路輸入的信號(hào)，通電路輸入的信號(hào)，通常稱為輸入變量常稱為輸入變量(或或組合電路的外部輸入組合電路的外部輸入信號(hào)信號(hào))。7時(shí)序邏輯電路

3、的一般結(jié)構(gòu)存儲(chǔ)電路存儲(chǔ)電路x1xnZ1Zmys y1 Y1 Yr CP由組合電路和存儲(chǔ)電路兩部分組成，通過反饋回路將兩部分連成一個(gè)整體。Z1Zm）：時(shí)序電路產(chǎn)）：時(shí)序電路產(chǎn)生的輸出信號(hào)，通常生的輸出信號(hào)，通常稱為輸出函數(shù)稱為輸出函數(shù) (或組合或組合電路的外部輸出信號(hào)電路的外部輸出信號(hào))。8時(shí)序邏輯電路的一般結(jié)構(gòu)存儲(chǔ)電路存儲(chǔ)電路x1xnZ1Zmys y1 Y1 Yr CP由組合電路和存儲(chǔ)電路兩部分組成，通過反饋回路將兩部分連成一個(gè)整體。y1ys：由電路過去輸入確定的狀態(tài)，稱為狀態(tài)變量。：由電路過去輸入確定的狀態(tài)，稱為狀態(tài)變量。 所謂電路輸出與過去的輸入相關(guān)，是通過現(xiàn)有狀態(tài)所謂電路輸出與過去的輸入

4、相關(guān)，是通過現(xiàn)有狀態(tài)體現(xiàn)的。就某一時(shí)刻而言，通常將該時(shí)刻電路的狀體現(xiàn)的。就某一時(shí)刻而言，通常將該時(shí)刻電路的狀態(tài)稱為現(xiàn)態(tài)，記作態(tài)稱為現(xiàn)態(tài)，記作ykn，簡(jiǎn)記為，簡(jiǎn)記為yk ；而將下一時(shí)刻；而將下一時(shí)刻電路的狀態(tài)稱為次態(tài)，記作電路的狀態(tài)稱為次態(tài)，記作ykn+1。yk又稱為組合電又稱為組合電路的內(nèi)部輸入信號(hào)。路的內(nèi)部輸入信號(hào)。 9時(shí)序邏輯電路的一般結(jié)構(gòu)存儲(chǔ)電路存儲(chǔ)電路x1xnZ1Zmys y1 Y1 Yr CP由組合電路和存儲(chǔ)電路兩部分組成，通過反饋回路將兩部分連成一個(gè)整體。Y1Yr：時(shí)序電路中的激勵(lì)時(shí)序電路中的激勵(lì)信號(hào)，它是確定電路信號(hào)，它是確定電路下一時(shí)刻狀態(tài)下一時(shí)刻狀態(tài)(即次態(tài)即次態(tài))的函的函數(shù)

5、，通常稱為激勵(lì)函數(shù)。數(shù)，通常稱為激勵(lì)函數(shù)。10時(shí)序邏輯電路的一般結(jié)構(gòu)存儲(chǔ)電路存儲(chǔ)電路x1xnZ1Zmys y1 Y1 Yr CP由組合電路和存儲(chǔ)電路兩部分組成，通過反饋回路將兩部分連成一個(gè)整體。CP：時(shí)鐘脈沖信號(hào)，用來確時(shí)鐘脈沖信號(hào)，用來確定電路狀態(tài)轉(zhuǎn)換時(shí)刻，定電路狀態(tài)轉(zhuǎn)換時(shí)刻， 并實(shí)現(xiàn)等狀態(tài)時(shí)間并實(shí)現(xiàn)等狀態(tài)時(shí)間(只在同只在同步時(shí)序電路中存在步時(shí)序電路中存在)。11時(shí)序邏輯電路的特征 電路由組合電路和存儲(chǔ)電路組成，具有對(duì)過去輸入進(jìn)行記憶的功能； 電路中包含反饋回路，通過反饋使電路功能與“時(shí)序”相關(guān)； 電路的輸出由電路當(dāng)時(shí)的輸入和狀態(tài)(過去的輸入)共同決定。12同步時(shí)序邏輯電路的定義 電路中的存

6、儲(chǔ)器件為時(shí)鐘控制觸發(fā)器，各觸發(fā)器共用同一時(shí)鐘信號(hào)，即電路中各觸發(fā)器狀態(tài)的轉(zhuǎn)換時(shí)刻在同一時(shí)鐘信號(hào)控制下同步發(fā)生。 若把某個(gè)時(shí)鐘脈沖到來之前電路所處的狀態(tài)作為現(xiàn)態(tài)，則該時(shí)鐘脈沖作用后的電路的狀態(tài)便稱為次態(tài)，前一個(gè)脈沖的次態(tài)即后一個(gè)脈沖的現(xiàn)態(tài)。13同步時(shí)序邏輯電路的分類 Mealy型 Moore型14Mealy型 若時(shí)序邏輯電路的輸出是電路輸入和狀態(tài)的函數(shù)，則稱為Mealy型時(shí)序邏輯電路。15Moore型 若時(shí)序邏輯電路的輸出僅僅是電路狀態(tài)的函數(shù)，則稱為Moore型時(shí)序邏輯電路。若一個(gè)時(shí)序邏輯電路沒有專門的外部輸出信號(hào)而是電路狀態(tài)作為輸出，則可視為Moore型電路的特殊情況。16同步時(shí)序電路的描述方

7、法 狀態(tài)表 狀態(tài)圖17狀態(tài)表 是一種反映同步時(shí)序電路的輸出Z、次態(tài)yn+1和電路輸入X、現(xiàn)態(tài)y之間關(guān)系的表格。它能夠完全描述同步時(shí)序邏輯電路在輸入時(shí)序信號(hào)作用下的狀態(tài)轉(zhuǎn)移關(guān)系及相應(yīng)的輸出響應(yīng)。 作狀態(tài)表時(shí)，在表格的左邊上到下列出電路的全部狀態(tài)；在表格的上邊從左到右列出一位輸入的全部取值組合。18兩種狀態(tài)表 對(duì)于Mealy型表格的中間列出不同狀態(tài)在不同輸入取值組合下的次態(tài)和輸出。對(duì)于Moore型電路，由于輸出僅于狀態(tài)直接相關(guān)，所以在表格中單獨(dú)作為一列。Mealy型狀態(tài)表格式現(xiàn)態(tài)次態(tài)/輸出輸入Xyyn+1/ZMoore型狀態(tài)表格式現(xiàn)態(tài)次態(tài)輸出輸入Xyyn+1Z19狀態(tài)圖 是一種反映同步時(shí)序邏輯電路

8、狀態(tài)轉(zhuǎn)換規(guī)律及相應(yīng)輸入、輸出取值關(guān)系的有向圖。圖中圓圈表示電路的狀態(tài)，連接圓圈的有向線段表示狀態(tài)的轉(zhuǎn)換關(guān)系，箭頭的起點(diǎn)表示現(xiàn)態(tài)，終點(diǎn)表示次態(tài)。20兩種狀態(tài)圖 Mealy型電路狀態(tài)圖的形式如下圖a所示。圖中，在有向箭頭的旁邊標(biāo)出發(fā)生該轉(zhuǎn)換的輸入條件以及在該輸入和現(xiàn)態(tài)下的相應(yīng)輸出。 Moore型電路狀態(tài)圖的形式如下圖b所示，除了把電路輸出標(biāo)在圓圈內(nèi)的狀態(tài)右下方之外，其他和Mealy型電路相同。21大綱 4.1 同步時(shí)序邏輯電路模型同步時(shí)序邏輯電路模型 4.2 觸發(fā)器觸發(fā)器 4.3 同步時(shí)序邏輯電路分析同步時(shí)序邏輯電路分析 4.4 同步時(shí)序邏輯電路設(shè)計(jì)同步時(shí)序邏輯電路設(shè)計(jì) 4.5同步時(shí)序邏輯電路設(shè)計(jì)

9、舉例同步時(shí)序邏輯電路設(shè)計(jì)舉例224.2 觸發(fā)器觸發(fā)器 4.2.0 概述概述 4.2.1 RS觸發(fā)器觸發(fā)器 4.2.2 D觸發(fā)器觸發(fā)器 4.2.3 JK觸發(fā)器觸發(fā)器 4.2.4 T觸發(fā)器觸發(fā)器23觸發(fā)器定義及功能 觸發(fā)器是一種具有記憶功能的電子器件。觸發(fā)器是一種具有記憶功能的電子器件。就其結(jié)構(gòu)而言，都是由邏輯門加上適當(dāng)?shù)木推浣Y(jié)構(gòu)而言，都是由邏輯門加上適當(dāng)?shù)姆答伨€耦合而成。反饋線耦合而成。 觸發(fā)器能用來存儲(chǔ)一位二進(jìn)制信息。觸發(fā)器能用來存儲(chǔ)一位二進(jìn)制信息。24觸發(fā)器的特點(diǎn) 有兩個(gè)互補(bǔ)的輸出端 Q 和 。 有兩個(gè)穩(wěn)定狀態(tài)。通常將 Q = 1和 = 0 稱為“1”狀態(tài)，而把Q = 0和 = 1稱為“0”

10、 狀態(tài)。當(dāng)輸入信號(hào)不發(fā)生變化時(shí)，觸發(fā)器狀態(tài)穩(wěn)定不變。 在一定輸入信號(hào)作用下，觸發(fā)器可以從一個(gè)穩(wěn)定狀態(tài)轉(zhuǎn)移到另一個(gè)穩(wěn)定狀態(tài)。QQQ25現(xiàn)態(tài)與次態(tài) 現(xiàn)態(tài):輸入信號(hào)作用前的狀態(tài)。記作 Qn 和 , 一般簡(jiǎn)記為Q和 次態(tài):輸入信號(hào)作用后的狀態(tài)，記作 Qn+1和nQQ1nQ26九要素 邏輯符號(hào) 電路圖 工作原理 功能表 狀態(tài)表 狀態(tài)圖 特征方程 激勵(lì)表 時(shí)序圖274.2.1 RS觸發(fā)器觸發(fā)器 基本R-S觸發(fā)器 時(shí)鐘控制R-S觸發(fā)器28基本R-S觸發(fā)器的定義 基本R-S觸發(fā)器是直接復(fù)位置位觸發(fā)器的簡(jiǎn)稱，由于它是構(gòu)成各種功能觸發(fā)器的基本部件，有時(shí)也稱為鎖存器。29基本R-S觸發(fā)器的特點(diǎn) 基本R-S觸發(fā)器的優(yōu)

11、點(diǎn)是結(jié)構(gòu)簡(jiǎn)單。 不僅可作為記憶元件獨(dú)立使用，而且由于它具有直接復(fù)位、置位功能，因而被作為各種性能完善的觸發(fā)器的基本組成部分。 由于R、S之間的約束關(guān)系，以及不能進(jìn)行定時(shí)控制，使它的使用受到一定限制。30基本R-S觸發(fā)器的分類 用或非門構(gòu)成的基本R-S觸發(fā)器 用與非門構(gòu)成的基本R-S觸發(fā)器31用或非門構(gòu)成的基本R-S觸發(fā)器 由兩個(gè)或非門交叉耦合組成，其邏輯圖和邏輯符號(hào)分別如圖(a)和圖(b)所示。該電路的輸入是正脈沖或高電平有效，故邏輯符號(hào)的輸入端未加小圓圈。32邏輯功能 下表給出了由或非門構(gòu)成的R-S觸發(fā)器的邏輯功能。R SQn+1功能說明0 00 11 01 1Q10d不變置 1置 0不定基

12、本R-S觸發(fā)器功能表次態(tài)方程和約束方程如下： (次態(tài)方程)R S = 0(約束方程)QRSQn133用與非門構(gòu)成的基本R-S觸發(fā)器 由兩個(gè)與非門交叉耦合構(gòu)成，其邏輯圖和邏輯符號(hào)分別如下圖 (a)和(b)所示。 R稱為置0端或者復(fù)位端，S稱為置1端或置位端；邏輯符號(hào)輸入端加的小圓圈表示低電平或負(fù)脈沖有效。34工作原理狀態(tài)不變狀態(tài)不變置置1,S稱為置數(shù)端稱為置數(shù)端置置0,R稱為清零端稱為清零端不允許不允許10, 10, 1, 1) 1 (11nnQQQQSR、則、若01, 0111nnQQQQ、則、若10, 1, 0)3(11nnQQSR、則01, 0, 1)2(11nnQQSR、則11, 0,

13、0)4(11nnQQSR、則35邏輯功能及其描述 與非門構(gòu)成的基本R-S觸發(fā)器功能表。表中d表示觸發(fā)器次態(tài)不確定。該表又稱為次態(tài)真值表。R SQn+1功能說明0 0d不允許0 10置01 01置11 1Qn保持36狀態(tài)表及狀態(tài)圖 Q Qn n Q Qn+1n+1RS=00RS=00RS=01RS=01RS=11RS=11RS=10RS=10 0 0 d d 0 0 0 0 1 1 1 1 d d 0 0 1 1 1 1狀態(tài)表狀態(tài)圖011 1 RS=1001 37次態(tài)方程和約束方程 若把觸發(fā)器次態(tài) Qn+1表示成現(xiàn)態(tài)Q和輸入R、S的函數(shù)，則卡諾圖如下：因?yàn)镽、S不允許同時(shí)為0，所以輸入必須滿足約

14、束條件：R + S = 1 (約束方程)用卡諾圖化簡(jiǎn)后，可得到該觸發(fā)器的次態(tài)方程： RQSQn138激勵(lì)表 Q Qn nQQn+1n+1 R S R S 0 0 0 0 d 1 d 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 d 1 d39波形圖 反映觸發(fā)器輸入信號(hào)取值和狀態(tài)之間對(duì)應(yīng)關(guān)系的圖形稱為波形圖。RSQQ置1置0置1置1置1保持不允許40時(shí)鐘控制R-S觸發(fā)器 時(shí)鐘控制R-S觸發(fā)器的邏輯圖和邏輯符號(hào)如圖(a)、（b）所示。與非門G1、G2構(gòu)成基本R-S觸發(fā)器；與非門G3、G4組成控制電路，通常稱為控制門。41工作原理 當(dāng)時(shí)鐘脈沖沒有到來（即C=

15、0）時(shí)，不管R、S端為何值，兩個(gè)控制門的輸出均為1，觸發(fā)器狀態(tài)保持不變。 當(dāng)時(shí)鐘脈沖到來（即C=1）時(shí)，輸入端R、S的值 可以通過控制門作用于上面的基本R-S觸發(fā)器。42具體過程 R=0, S=0：控制門G3、G4的輸出均為1，觸發(fā)器狀態(tài)保持不變； R=0, S=1：控制門G3、G4的輸出分別為1和0，觸發(fā)器狀態(tài)置成1狀態(tài)； R=1, S=0：控制門G3、G4的輸出分別為0和1，觸發(fā)器狀態(tài)置成0狀態(tài)； R=1，S=1：控制門G3、G4的輸出均為0，觸發(fā)器狀態(tài)不確定，這是不允許的。43功能表 時(shí)鐘控制R-S觸發(fā)器的工作過程是由時(shí)鐘信號(hào)C和輸入信號(hào)R、S共同作用的；時(shí)鐘C控制轉(zhuǎn)換時(shí)間，輸入R和S確

16、定轉(zhuǎn)換后的狀態(tài)。 R S R S Q Qn+1n+1功能說明功能說明0 00 0Q Qn n保持保持0 10 11 1置置1 11 01 00 0置置0 01 11 1d d不允許不允許44狀態(tài)表及狀態(tài)圖 Qn Qn+1RS=00RS=01RS=11RS=10 0 0 1 d 0 1 1 1 d 0狀態(tài)表狀態(tài)表狀態(tài)圖狀態(tài)圖010/0/01/10/45次態(tài)卡諾圖及方程次態(tài)次態(tài)Q Qn+1n+1的卡諾圖的卡諾圖約束條件 01SRQRSQnn次態(tài)次態(tài)方程方程 Qn00011110001d0111d0RS46激勵(lì)表QnQn+1 R S0 0 d 00 1 0 11 0 1 01 1 0 d47波形圖C

17、 PRSQQ不變不變不變不變不變不變置1置0置1置0不變48空翻問題 “空翻”是指在同一個(gè)時(shí)鐘脈沖作用期間觸發(fā)器狀態(tài)發(fā)生兩次或兩次以上變化的現(xiàn)象。 因?yàn)樵跁r(shí)鐘脈沖作用期間，輸入信號(hào)直接控制著觸發(fā)器狀態(tài)的變化。即當(dāng)時(shí)鐘C為1時(shí)，輸入信號(hào)R、S發(fā)生變化，觸發(fā)器狀態(tài)會(huì)跟著變化，從而使得一個(gè)時(shí)鐘脈沖作用期間引起多次翻轉(zhuǎn)。 改進(jìn)觸發(fā)器的電路結(jié)構(gòu)。如：主從R-S觸發(fā)器。49主從RS觸發(fā)器 Q CP R S 從觸 發(fā)器 & & & & 1 Q Q Q SD 主觸 發(fā)器 & & & & RD (a) (a) 邏輯電路邏輯電路(b) (b) 邏輯符

18、號(hào)邏輯符號(hào) 504.2.2 D觸發(fā)器觸發(fā)器 對(duì)時(shí)鐘控制R-S觸發(fā)器的控制電路稍加修改，使之變成如下圖(a)所示的形式，這樣便形成了只有一個(gè)輸入端的D觸發(fā)器。其邏輯符號(hào)如圖 (b)所示。RS51消除不確定現(xiàn)象 修改后，控制電路在時(shí)鐘脈沖作用期間(C=1時(shí))，將輸入信號(hào)D轉(zhuǎn)換成一對(duì)互補(bǔ)信號(hào)送至基本R-S觸發(fā)器的兩個(gè)輸入端，使基本R-S觸發(fā)器的兩個(gè)輸入信號(hào)只可能是01或者10兩種組合，從而消除了狀態(tài)不確定現(xiàn)象，解決了對(duì)輸入的約束問題。 52工作原理 當(dāng)無時(shí)鐘脈沖作用（即C=0）時(shí)，控制電路被封鎖，無論D為何值，與非門G3、G4輸出均為1，觸發(fā)器狀態(tài)保持不變。 當(dāng)時(shí)鐘脈沖作用（即C=1 ）時(shí)，若D=0

19、，則門G4輸出為1，門G3輸出為0，觸發(fā)器狀態(tài)被置0；若D=1，則門G4輸出為0，門G3輸出為1，觸發(fā)器狀態(tài)被置1。53功能表和狀態(tài)表狀態(tài)表狀態(tài)表 Q Qn n Q Qn+1n+1D=0D=0D=1D=1 0 0 0 0 1 1 1 1 0 0 1 1 DQn+10101D 觸發(fā)器功能表觸發(fā)器功能表54狀態(tài)圖及次態(tài)方程和激勵(lì)表DQn1次態(tài)方程次態(tài)方程 0 1 D=1/ 0/ 0/ 1/ 狀態(tài)圖狀態(tài)圖激勵(lì)表激勵(lì)表 Q Qn nQ Qn+1n+1D D0 00 00 00 10 11 11 01 00 01 11 11 155波形圖Q QD DCPCP56空翻CPDQ57維持阻塞D觸發(fā)器邏輯符號(hào)邏

20、輯符號(hào)次態(tài)方程次態(tài)方程DQn1DCPDRDSQQ58 CP D Q Q 波形圖594.2.3 JK觸發(fā)器觸發(fā)器 在時(shí)鐘控制R-S觸發(fā)器中增加兩條反饋線，將觸發(fā)器的輸出Q和交叉反饋到兩個(gè)控制門的輸入端，并把原來的輸入端S改成J，R改成K，即可改進(jìn)成J-K觸發(fā)器。 J-K觸發(fā)器的邏輯圖和邏輯符號(hào)如下圖所示。Q60工作原理無時(shí)鐘脈沖 (CP=0)時(shí)，觸發(fā)器保持原來狀態(tài)不變。時(shí)鐘脈沖作用(CP=1)時(shí)，與J、K相關(guān)。 J=0,K=0：觸發(fā)器狀態(tài)不變。觸發(fā)器狀態(tài)不變。 J=0,K=1：若原來處于0狀態(tài)，觸發(fā)器保持0狀態(tài)不變；若原來處于1狀態(tài)，觸發(fā)器狀態(tài)置成0。即JK =01時(shí)，觸發(fā)器次態(tài)一定為時(shí)，觸發(fā)器

21、次態(tài)一定為0狀態(tài)。狀態(tài)。 J=1,K=0：若原來處于0狀態(tài)，觸發(fā)器狀態(tài)置成1；若原來處于1狀態(tài)，觸發(fā)器保持1態(tài)不變。即JK =10時(shí)，觸發(fā)器次態(tài)一定為時(shí)，觸發(fā)器次態(tài)一定為1狀狀態(tài)。態(tài)。 J=1,K=1：若原來處于0狀態(tài)，觸發(fā)器置成1 狀態(tài)；若原來處于1狀態(tài)，觸發(fā)器置成0狀態(tài)。 即JK =11時(shí)，觸發(fā)器的次態(tài)與現(xiàn)態(tài)相反。時(shí)，觸發(fā)器的次態(tài)與現(xiàn)態(tài)相反。61CP=0或CP=1和JK=00 CP=0，G3，G4輸出為0，狀態(tài)不變。要使其狀態(tài)發(fā)生變化需CP=1； CP=1時(shí)，JK=00，G3，G4輸出為0，保持。62CP=1和JK=01時(shí)：1CP10001,1011. 01,0111n311n34nnQQ

22、GQQQQGQQGJK、，輸出為時(shí)，、，輸出為時(shí)，輸出為置置0 063CP=1和JK=10時(shí)：1CP01001,0111, 01,1011n411n43nnQQGQQQQGQQGJK、，輸出為時(shí)，、，輸出為時(shí)，輸出為置置1 164CP=1和JK=11時(shí)：1CP101001,01011, 0,1111n4311n43nnQQGGQQQQGGQQJK、，輸出為，輸出為時(shí)，、，輸出為，輸出為時(shí)，翻轉(zhuǎn)翻轉(zhuǎn)65功能表和狀態(tài)表功能表功能表J KQn+1功能說明功能說明0 00 11 01 1Q01Q不變不變置置 0置置 1翻轉(zhuǎn)翻轉(zhuǎn)Q Qn n Q Qn+1n+1JK=00JK=00 JK=01JK=01J

23、K=11JK=11JK=10JK=10 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1狀態(tài)表狀態(tài)表66狀態(tài)圖及次態(tài)方程和激勵(lì)表QKQJQn1次態(tài)方程次態(tài)方程 0 1 JK=10，11 01，11 00 01 00 10 狀態(tài)圖狀態(tài)圖激勵(lì)表激勵(lì)表 Q Qn nQ Qn+1n+1J KJ K0 00 00 d0 d0 10 11 d1 d1 01 0d 1d 11 11 1d 0d 067波形圖CPJKQQ68J-K觸發(fā)器空翻現(xiàn)象Q QK KJ JCPCP69主從JK觸發(fā)器G1 G2J K CP G7 主 G8G5 G6 G3 從 G4Q Q1G9Qm Qm&

24、;邏輯符號(hào)邏輯符號(hào)CPJKQQDRDS70波形圖CPJKQ714.2.4 T觸發(fā)器觸發(fā)器 T觸發(fā)器又稱為計(jì)數(shù)觸發(fā)器。如果把J-K觸發(fā)器的兩個(gè)輸入端J和K連接起來，并把連接在一起的輸入端用符號(hào)T表示，就構(gòu)成了T觸發(fā)器。相應(yīng)的邏輯圖和邏輯符號(hào)分別如圖(a)和圖(b)所示。72T觸發(fā)器次態(tài)方程及功能表T10Qn+1QQ功能說明功能說明不不 變變翻翻 轉(zhuǎn)轉(zhuǎn)T T觸發(fā)器功能表觸發(fā)器功能表T觸發(fā)器的邏輯功能可直接由J-K觸發(fā)器的次態(tài)方程導(dǎo)出。J-K觸發(fā)器的次態(tài)方程為:將該方程中的J和K均用T代替后，即可得到T觸發(fā)器的次態(tài)方程：根據(jù)次態(tài)方程，可列出T觸發(fā)器的功能表如下表所示:QKQJQ1)(nQTQTQ1)

25、(n功能：功能： 當(dāng)當(dāng)T=0T=0時(shí)，觸發(fā)器狀態(tài)保持時(shí)，觸發(fā)器狀態(tài)保持不變；不變； 當(dāng)當(dāng)T=1T=1時(shí)，在時(shí)鐘脈沖作用時(shí)，在時(shí)鐘脈沖作用下狀態(tài)翻轉(zhuǎn)，相當(dāng)于一位二進(jìn)下狀態(tài)翻轉(zhuǎn)，相當(dāng)于一位二進(jìn)制計(jì)數(shù)器。制計(jì)數(shù)器。73狀態(tài)表和狀態(tài)圖狀態(tài)表狀態(tài)表 Qn Qn+1 T=0 T=1 0 0 1 1 1 0狀態(tài)圖狀態(tài)圖01T=110074激勵(lì)表和次態(tài)方程QTQTQTQn 1次態(tài)方程次態(tài)方程激勵(lì)表激勵(lì)表Q Qn nQ Qn+1n+1T T0 00 00 00 10 11 11 01 01 11 11 10 075TCPQQ1CPQQT觸發(fā)器T觸發(fā)器76大綱 4.1 同步時(shí)序邏輯電路模型同步時(shí)序邏輯電路模型 4

26、.2 觸發(fā)器觸發(fā)器 4.3 同步時(shí)序邏輯電路分析同步時(shí)序邏輯電路分析 4.4 同步時(shí)序邏輯電路設(shè)計(jì)同步時(shí)序邏輯電路設(shè)計(jì) 4.5同步時(shí)序邏輯電路設(shè)計(jì)舉例同步時(shí)序邏輯電路設(shè)計(jì)舉例774.3 同步時(shí)序邏輯電路分析同步時(shí)序邏輯電路分析 就是對(duì)一個(gè)給定的時(shí)序邏輯電路，研究在一系列輸入信號(hào)作用下，電路將會(huì)產(chǎn)生怎樣的輸出，進(jìn)而說明該電路的邏輯功能。78分析步驟 (1)根據(jù)給定的同步時(shí)序電路,寫出輸出函數(shù)和激勵(lì)函數(shù)表達(dá)式。 (2)建立狀態(tài)轉(zhuǎn)移真值表。 (3)作出時(shí)序電路的狀態(tài)表，畫出狀態(tài)圖。 (4)用文字和時(shí)間圖描述電路的邏輯功能。79示例一 分析如圖所示電路,說明電路邏輯功能。 80第一步 寫出輸出函數(shù)表達(dá)

27、式和激勵(lì)函數(shù)表達(dá)式：1212122111yyxyyxZyxKJKJ81第二步 建立狀態(tài)轉(zhuǎn)移真值表：y2(n+1) y1 (n+1) 0 11 01 10 01 10 00 11 00 0 1 11 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 11 1 1 10 0 1 10 00 11 01 1 0 00 11 01 100001111J2 K2 J1 K1次 態(tài)激勵(lì)函數(shù)現(xiàn)態(tài)y2 y1輸入x00011000Z82第三步 作出時(shí)序電路的狀態(tài)表，畫出狀態(tài)圖：現(xiàn) 態(tài)y2 y1次態(tài) y2(n+1) y1 (n+1) /ZX=0X=1 0 0 0 1 1 0 1 1 0/01

28、/00/00/00/11/01/01/183第四步84示例二 分析如圖所示電路,說明電路邏輯功能85簡(jiǎn)要分析 該電路的存儲(chǔ)電路是兩個(gè)J-K觸發(fā)器，組合電路是一個(gè)異或門，電路的輸入為x，電路的狀態(tài)(即觸發(fā)器狀態(tài))用y2、y1表示。該電路 的狀態(tài)變量就是電路的輸出，因此，它屬于Moore型電路的特例。86第一步 由邏輯電路圖可知，各觸發(fā)器的激勵(lì)函數(shù)表達(dá)式為:J1 = K1 = 1J2 = K2 = xy187輸入x現(xiàn)態(tài)y2 y1激勵(lì)函數(shù)次 態(tài)J2 K2 J1 K1y2(n+1) y1 (n+1) 000011110 00 11 01 1 0 00 11 01 10 0 1 11 1 1 1 0 0

29、 1 1 1 1 1 1 1 1 1 1 0 0 1 11 1 1 10 0 1 10 11 01 10 01 10 00 11 0第二步88次態(tài)真值表的填寫方法。89第三步現(xiàn)現(xiàn) 態(tài)態(tài)y y2 2 y y1 1次態(tài)次態(tài) y y2 2(n+1)(n+1) y y1 1 (n+1)(n+1) X=0X=0X=1X=1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 0 1 090第四步 由狀態(tài)圖可以看出給定的電路是一個(gè)2位二進(jìn)制可逆計(jì)數(shù)器 當(dāng)輸入x=0時(shí)，可逆計(jì)數(shù)器進(jìn)

30、行加法計(jì)數(shù)，其計(jì)數(shù)時(shí)序?yàn)椋?0001101100 當(dāng)輸入x=1時(shí)，可逆計(jì)數(shù)器進(jìn)行減法計(jì)數(shù)，其計(jì)數(shù)時(shí)序?yàn)椋?01110010091例三 分析如圖所示電路,說明其邏輯功能。92分析 該電路的存儲(chǔ)電路由兩個(gè)D觸發(fā)器構(gòu)成，組合電路包括一個(gè)與門和一個(gè)或非門。電路有一個(gè)輸入X和一個(gè)輸出Z。輸出Z和輸入X及電路狀態(tài)均有直接聯(lián)系，因此屬于Mealy型。93第一步 根據(jù)上圖，列出各觸發(fā)器的激勵(lì)函數(shù)表達(dá)式：12122)(yyXyyXD12yyXZXD 194第二步 列出電路次態(tài)真值表：輸 入x現(xiàn)態(tài)y2 y1激勵(lì)變量D2 D1次 態(tài)y2n+1 y1n+1 000011110 00 11 01 10 00 11 01

31、 10 01 00 00 00 10 10 1 0 10 01 00 00 00 10 10 10 195第三步 作出狀態(tài)表和狀態(tài)圖：現(xiàn) 態(tài)y2 y1次態(tài) y2(n+1) y1 (n+1) /ZX=0X=1 0 0 0 1 1 1 1 0 000 100 000 000 010 010 010 01196第四步設(shè)電路初態(tài)為“00”，輸入x為脈沖信號(hào)，其輸入序列為010110100。根據(jù)狀態(tài)圖可作出電路的狀態(tài)響應(yīng)序列和輸出響應(yīng)序列如下： CP： 1 2 3 4 5 6 7 8 9 x： 0 1 0 1 1 0 1 0 0 y2： 0 0 0 1 0 0 1 0 1 y1 ： 0 0 1 0 1

32、1 0 1 0y2（n+1）：0 0 1 0 0 1 0 1 0y1（n+1）：0 1 0 1 1 0 1 0 0 Z ：0 0 0 1 0 0 1 0 097作出時(shí)間圖由時(shí)間圖可以看出，一旦輸入x出現(xiàn)信號(hào)“101”，輸出Z便產(chǎn)生一個(gè)相應(yīng)的1，在其他情況下輸出Z為0。因此，該時(shí)序電路是一個(gè)“101”序列檢測(cè)器。98例四 分析如圖所示電路,說明其邏輯功能。99簡(jiǎn)要分析 該電路的存儲(chǔ)電路為該電路的存儲(chǔ)電路為J-K觸發(fā)器，組合電路觸發(fā)器，組合電路由門電路構(gòu)成，電路有兩個(gè)輸入端由門電路構(gòu)成，電路有兩個(gè)輸入端x1和和x2，一個(gè)輸出端一個(gè)輸出端Z。輸出。輸出Z與輸入和狀態(tài)有直接與輸入和狀態(tài)有直接關(guān)系，屬于

33、關(guān)系，屬于Mealy型電路。型電路。100第一步 由邏輯電路圖可知，該觸發(fā)器的輸出函數(shù)由邏輯電路圖可知，該觸發(fā)器的輸出函數(shù)的表達(dá)式為：的表達(dá)式為：yXXZ2121XXJ21XXK101第二步 把激勵(lì)函數(shù)表達(dá)式代入觸發(fā)器的次態(tài)方程，得到電路的次態(tài)方程組。該電路的存儲(chǔ)電路只有一個(gè)觸發(fā)器，因此電路只有一個(gè)次態(tài)方程。根據(jù)J-K觸發(fā)器的次態(tài)方程和電路的激勵(lì)函數(shù)表達(dá)式，可導(dǎo)出電路的次態(tài)方程如下：yxyxxxyxyxyxxyxxyxxykyJ212121212121)(102第三步 作出該電路的狀態(tài)表和狀態(tài)圖現(xiàn)現(xiàn) 態(tài)態(tài)y y次態(tài)次態(tài) / /輸出輸出( (y y(n+1)(n+1)/ Z)/ Z)X X1 1

34、 X X2 2 =00=00X X1 1 X X2 2 =01=01X X1 1 X X2 2 =11=11X X1 1 X X2 2 =10=100 01 10 00 00 01 1 0 01 11 10 01 10 0 1 11 10 01 1 1 10 0 103第四步 設(shè)初態(tài)為“0”，輸入x1為00110110，輸入x2為01011100，可作出電路的輸出狀態(tài)響應(yīng)序列如下：時(shí)鐘節(jié)拍：1 2 3 4 5 6 7 8輸入x1 ： 0 0 1 1 0 1 1 0輸入x2 ： 0 1 0 1 1 1 0 0狀態(tài)y： “0” 0 0 0 1 1 1 1輸出Z： 0 1 1 0 0 1 0 110

35、4時(shí)間圖105功能描述 由時(shí)間圖中的0、1符號(hào)可以看出，該電路實(shí)現(xiàn)了串行加法器的功能。其中x1為被加數(shù)， x2為加數(shù)，它們按照先低位后高位的順序串行地加到相應(yīng)的輸入端。每位加產(chǎn)生的進(jìn)位由觸發(fā)器保存下來參加下一位相加，輸出Z為和數(shù)，也是從低位到高位串行地輸出的。106大綱 4.1 同步時(shí)序邏輯電路模型同步時(shí)序邏輯電路模型 4.2 觸發(fā)器觸發(fā)器 4.3 同步時(shí)序邏輯電路分析同步時(shí)序邏輯電路分析 4.4 同步時(shí)序邏輯電路設(shè)計(jì)同步時(shí)序邏輯電路設(shè)計(jì) 4.5同步時(shí)序邏輯電路設(shè)計(jì)舉例同步時(shí)序邏輯電路設(shè)計(jì)舉例1074.4 同步時(shí)序邏輯電路設(shè)計(jì)同步時(shí)序邏輯電路設(shè)計(jì) 4.4.1 建立原始狀態(tài)圖和狀態(tài)表建立原始狀態(tài)

36、圖和狀態(tài)表 4.4.2 狀態(tài)化簡(jiǎn)狀態(tài)化簡(jiǎn) 4.4.3 狀態(tài)編碼狀態(tài)編碼 4.4.4 確定激勵(lì)函數(shù)和輸出函數(shù)確定激勵(lì)函數(shù)和輸出函數(shù) 4.4.5 畫邏輯電路圖畫邏輯電路圖108設(shè)計(jì)步驟109建立原始狀態(tài)圖和狀態(tài)表 確定電路模型 設(shè)立初始狀態(tài) 根據(jù)需要記憶的信息增加新的狀態(tài) 確定各時(shí)刻電路的輸出110示例一 某模5加1和加2計(jì)數(shù)器有一個(gè)輸入x和一個(gè)輸出Z。輸入x為加1、加2控制信號(hào)，當(dāng)x=0時(shí)，計(jì)數(shù)器在時(shí)鐘脈沖作用下進(jìn)行加1計(jì)數(shù)；當(dāng)x=1時(shí)，計(jì)數(shù)器在時(shí)鐘脈沖作用下進(jìn)行加2計(jì)數(shù)。當(dāng)電路計(jì)滿5個(gè)狀態(tài)后，輸出Z產(chǎn)生一個(gè)1信號(hào)作為進(jìn)位輸出，平時(shí)Z輸出為0。試建立該計(jì)數(shù)器的Mealy型原始狀態(tài)圖和狀態(tài)表。11

37、1示例一解答 假設(shè)模5計(jì)數(shù)器的5個(gè)狀態(tài)分別用0、l、2、3、4表示，其中0為初始狀態(tài)。根據(jù)題意可作出原始狀態(tài)圖如右圖所示，相應(yīng)的原始狀態(tài)表如右表所示。 輸入輸入狀態(tài)狀態(tài)X=0X=0X=1X=10 01/01/02/02/01 12/02/03/03/02 23/03/04/04/03 34/04/00/10/14 40/10/11/11/1112示例二 某序列檢測(cè)器有一個(gè)輸入端x和一個(gè)輸出端Z。輸入端x輸入一串隨機(jī)的二進(jìn)制代碼，當(dāng)輸入序列中出現(xiàn)011時(shí)，輸出Z產(chǎn)生一個(gè)1輸出，平時(shí)Z輸出0。典型輸入、輸出序列如下。 輸入x： l 0 1 0 1 1 1 0 0 1 1 0 輸出Z： 0 0 0

38、0 0 1 0 0 0 0 1 0 試作出該序列檢測(cè)器的原始狀態(tài)圖和原始狀態(tài)表。113示例二解答 設(shè)電路的初始狀態(tài)為A。當(dāng)處在初始狀態(tài)下電路輸入為0時(shí)，輸出Z為0，由于輸入0是序列“011”中的第一個(gè)信號(hào)，所以應(yīng)該用一個(gè)狀態(tài)將它記住，假定用狀態(tài)B記住收到了第一個(gè)0，則在狀態(tài)A輸入0時(shí)應(yīng)轉(zhuǎn)向狀態(tài)B；當(dāng)處在初始狀態(tài)A電路輸入為1時(shí)，輸出Z為0，由于輸入1不是序列“011”的第一個(gè)信號(hào)，故不需要記住，可令其停留在狀態(tài)A。該轉(zhuǎn)換關(guān)系如圖(a)所示。114示例二解答 當(dāng)電路處于狀態(tài)B時(shí)，若輸入x為0，則它不是序列“011”的第二個(gè)信號(hào)，但仍可作為序列中的第一個(gè)信號(hào)，故可令電路輸出為0，停留在狀態(tài)B；若輸

39、入x為1，則意味著收到了序列“011”的前面兩位01，可用一個(gè)新的狀態(tài)C將它記住，故此時(shí)電路輸出為0，轉(zhuǎn)向狀態(tài)C。部分狀態(tài)圖如圖(b)所示。115示例二解答 當(dāng)電路處于狀態(tài)C時(shí)，若輸入x為0，則收到的連續(xù)3位代碼為010，不是關(guān)心的序列011，但此時(shí)輸入的0依然可以作為序列的第一個(gè)信號(hào)，故此時(shí)應(yīng)輸出0，轉(zhuǎn)向狀態(tài)B；若輸入x為1，則表示收到了序列011，可用一個(gè)新的狀態(tài)D記住，此時(shí)應(yīng)輸出1，轉(zhuǎn)向狀態(tài)D。部分狀態(tài)圖如圖(c)所示。116示例二解答 當(dāng)電路處于狀態(tài)D時(shí)，若輸入x為0，則應(yīng)輸出0，轉(zhuǎn)向狀態(tài)B；若輸入x為l，則應(yīng)輸出0，轉(zhuǎn)向狀態(tài)A。至此，得到了該序列檢測(cè)器完整的Mealy型狀態(tài)圖，如圖(

40、d)所示。相應(yīng)的原始狀態(tài)表如右所示。 117示例二狀態(tài)圖 在建立序列檢測(cè)器的原始狀態(tài)圖時(shí)，可以先根據(jù)序列中要記憶的信息設(shè)立好每一個(gè)狀態(tài)，并建立起當(dāng)輸入信號(hào)正好按指定序列變化時(shí)各狀態(tài)的相互關(guān)系；然后再確定每個(gè)狀態(tài)下輸入出現(xiàn)不同取值時(shí)的輸出和狀態(tài)轉(zhuǎn)移方向，即可得到一個(gè)完整的狀態(tài)圖。118示例三 設(shè)計(jì)一個(gè)用于引爆控制的同步時(shí)序電路，該電路有一個(gè)輸入端x和一個(gè)輸出端Z。平時(shí)輸入x始終為0，一旦需要引爆，則從x連續(xù)輸入4個(gè)1信號(hào)(不被0間斷)，電路收到第四個(gè)1后在輸出端Z產(chǎn)生一個(gè)1信號(hào)點(diǎn)火引爆，該電路連同引爆裝置一起被炸毀。試建立該電路的Mealy型狀態(tài)圖和狀態(tài)表。119示例三解答 該電路實(shí)際上是一個(gè)用

41、于特殊場(chǎng)所的“1111”序列檢測(cè)器。它與一般序列檢測(cè)器有兩點(diǎn)不同。一是輸入帶有約束條件，即一旦輸入出現(xiàn)1，則一定是不被0間斷的連續(xù)4個(gè)l；二是收到4個(gè)1后產(chǎn)生的引爆信號(hào)，同時(shí)使電路毀，故此時(shí)不再存在次態(tài)問題。120示例三解答 設(shè)狀態(tài)A表示電路初始狀態(tài)，狀態(tài)B表示收到了第一個(gè)1輸入，狀態(tài)C表示收到了連續(xù)2個(gè)1輸入，狀態(tài)D表示收到了連續(xù)3個(gè)1輸入。 根據(jù)題意，A狀態(tài)下x為1時(shí)，輸出為0轉(zhuǎn)向狀態(tài)B；B狀態(tài)下x為1時(shí)，輸出為0轉(zhuǎn)向狀態(tài)C；C狀態(tài)下x為1時(shí)，輸出為0轉(zhuǎn)向狀態(tài)D；而D狀態(tài)下x為1時(shí)，輸出為1，次態(tài)隨意(實(shí)際上已不存在次態(tài))。 其次，A狀態(tài)下x為0時(shí)，可令輸出為0，停留在狀態(tài)A，而B、C、D

42、這3個(gè)狀態(tài)下由于x不會(huì)為0，故可令輸出和次態(tài)作為無關(guān)處理。121狀態(tài)圖及狀態(tài)表 輸入輸入狀態(tài)狀態(tài)X=0X=0X=1X=1A AA/0A/0B/0B/0B Bd/dd/dC/0C/0C Cd/dd/dD/0D/0D Dd/dd/dd/1d/1 據(jù)此，可得到該電路的Mealy型原始狀態(tài)圖如下圖所示，原始狀態(tài)表如下表所示。圖表中用“d”表示不確定次態(tài)或不確定輸出。122狀態(tài)化簡(jiǎn) 消去多余狀態(tài) 最小化狀態(tài)表 狀態(tài)數(shù)最少 滿足邏輯命題全部要求123狀態(tài)化簡(jiǎn)方法分類 觀察法 隱含表法124狀態(tài)表分類 完全確定狀態(tài)表 不完全確定狀態(tài)表125等效狀態(tài)和等效類 假設(shè)狀態(tài)Si和Sj是完全確定狀態(tài)表中的兩個(gè)狀態(tài)，如

43、果對(duì)于所有可能的輸入序列，分別從Si和Sj出發(fā)，所得到的輸出響應(yīng)序列完全相同，則狀態(tài)Si和Sj是等效的，記作(Si，Sj)，或者說，狀態(tài)Si和Sj是等效對(duì)。126 即假若S1和S2等效，S2和S3等效，那么，一定有S1和S3等效。 記作 (S1，S2)，(S2，S3)(S1，S3)127等效類 所謂等效類是指由若干彼此等效的狀態(tài)構(gòu)成的集合。在一個(gè)等效類中的任意兩個(gè)狀態(tài)都是等效的。根據(jù)等效狀態(tài)的傳遞性，可以從等效對(duì)中尋找出等效類。 例如，由(S1，S2)和(S2，S3)可以推出(S1，S3)，進(jìn)而可知S1、S2、S3屬于同一等效類，記作 (S1，S2)，(S2，S3)S1，S2，S3。128最大

44、等效類 如果一個(gè)等效類不是任何其他等效類的子集，則該等效類稱為最大等效類。 原始狀態(tài)表的化簡(jiǎn)過程，就是尋找最大等效類，然后將每個(gè)最大等效類中的所有狀態(tài)合并為一個(gè)新的狀態(tài)，從而得到最小化狀態(tài)表的過程。簡(jiǎn)化后的狀態(tài)數(shù)等于最大等效類的個(gè)數(shù)。129隱含表化簡(jiǎn)步驟 作隱含表 尋找等效狀態(tài)對(duì) 確定最大等效類 合并最大等效類中的狀態(tài)130示例一 化簡(jiǎn)所示原始狀態(tài)表化簡(jiǎn)所示原始狀態(tài)表 輸入輸入狀態(tài)狀態(tài)X=0X=0X=1X=1A AC/0C/0B/1B/1B BF/0F/0A/1A/1C CF/0F/0G/0G/0D DD/1D/1E/0E/0E EC/0C/0E/1E/1F FC/0C/0G/0G/0G GC

45、/1C/1D/0D/0131 由于原始狀態(tài)表中有A-G共7個(gè)狀態(tài)，所以隱含表的橫向和縱向各有6個(gè)方格?？v向從上到下依次為B-G，橫向從左到右依次為AF。表中每個(gè)方格代表一個(gè)狀態(tài)對(duì)，如左上角的方格代表狀態(tài)對(duì)A和B，右下角的方格代表狀態(tài)對(duì)F和G。第一步:作隱含表B BC CD DE EF FG GA AB BC CD DE EF F132第二步:尋找等效對(duì) 首先進(jìn)行順序比較，根據(jù)等效狀態(tài)的判斷標(biāo)準(zhǔn)，依次檢查每個(gè)狀態(tài)對(duì)，可得到順序比較結(jié)果如下頁(yè)圖所示。 例如，狀態(tài)表中C和F滿足狀態(tài)等效條件，所以，在隱含表的相應(yīng)方格內(nèi)填入“”；狀態(tài)A和C不滿足等效條件，故在隱含表的相應(yīng)方格內(nèi)填入“”；狀態(tài)A和E雖然滿

46、足輸出相同這個(gè)條件，但它們的次態(tài)在x=1時(shí)為B和E，由于當(dāng)前尚不能確定B和E是否等效，因此，將BE填人相應(yīng)方格中。133比較結(jié)果 輸入輸入狀態(tài)狀態(tài)X=0X=0X=1X=1A AC/0C/0B/1B/1B BF/0F/0A/1A/1C CF/0F/0G/0G/0D DD/1D/1E/0E/0E EC/0C/0E/1E/1F FC/0C/0G/0G/0G GC/1C/1D/0D/0B BCFCFC C D D E EBEBEAEAEC CF FF F G G CDCDDEDEA A B B C C D D E E F F根據(jù)輸出根據(jù)輸出7 7個(gè)狀態(tài)分成個(gè)狀態(tài)分成3 3組：組：CC，F(xiàn)FAA，B B

47、，EEDD，GG組內(nèi)狀態(tài)才有可能等效。組內(nèi)狀態(tài)才有可能等效。134關(guān)聯(lián)比較BCFCDEBEAECFFGCDDEABCDEFAEBECF 135關(guān)聯(lián)比較結(jié)果 狀態(tài)D、C對(duì)應(yīng)的方格中含有CD和DE，而狀態(tài)C、D對(duì)應(yīng)的方格已標(biāo)以“X”號(hào)，這表明狀態(tài)C和D不等效。因此，可以判斷狀態(tài)D和G不等效，它所對(duì)應(yīng)的方格應(yīng)增加記號(hào)“”。 由圖的隱含表可知，原始狀態(tài)表中的7個(gè)狀態(tài)共有四個(gè)等效對(duì)： (A，B)，(A，E)，(B，E)，(C，F(xiàn))。BCFC D EBEAECF F G CDDE ABCDEF136求出最大等效類 由所得到的四個(gè)等效對(duì)可知，等效對(duì)(A，B)，(A，E)， (B，E)構(gòu)成一個(gè)最大等效類A，B

48、，E。 等效對(duì)(C，F(xiàn))不包含在任何其他等效類中，所以，它也是一個(gè)最大等效類。其次，狀態(tài)D和G不和任何其他狀態(tài)等效，故它們各自構(gòu)成一個(gè)最大等效類。由此可見，原始狀態(tài)表中的7個(gè)狀態(tài)共構(gòu)成四個(gè)最大等效類，分別表示如下： A，B，E，C，F(xiàn)，D，G137作出最小化狀態(tài)表 將最大等效類A，B，E、C，F(xiàn)、D、G分別用新的字母a、b、c、d表示，并代入比較結(jié)果所示狀態(tài)表中，即可得到化簡(jiǎn)后的最小化狀態(tài)表如下表所示。 輸入狀態(tài)X=0X=1ab/0a/1bb/0d/0cc/1a/0db/1c/0138不完全確定狀態(tài)表的化簡(jiǎn) 不完全確定狀態(tài)表中存在不確定的次態(tài)或輸出。 不完全確定狀態(tài)表的化簡(jiǎn)是建立在相容狀態(tài)基礎(chǔ)

49、上的。139相容狀態(tài) 假定狀態(tài)Si和Sj是不完全確定狀態(tài)表中的兩個(gè)狀態(tài)，如果對(duì)于所有的有效輸入序列，分別從狀態(tài)Si和SJ出發(fā)，所得到的輸出響應(yīng)序列(除不確定的那些位之外)是完全相同的，那么，狀態(tài)Si和Sj是相容的，或者說狀態(tài)Si和Sj是相容對(duì)，記作(Si，Sj)。 輸入序列所得到的狀態(tài)響應(yīng)序列除最后一個(gè)次態(tài)外，其他次態(tài)都是確定的，那么這個(gè)輸入序列對(duì)狀態(tài)S是有效的。 有效輸入序列是指有效輸入序列的長(zhǎng)度和結(jié)構(gòu)是任意的。140相容的條件 假定狀態(tài)Si和Sj是不完全確定狀態(tài)表中的兩個(gè)現(xiàn)態(tài)，那么，狀態(tài)Si和Sj相容的條件，可歸納為在一位輸入的各種取值組合下滿足如下兩條。 第一:它們的輸出完全相同， 或者

50、其中的一個(gè)(或兩個(gè)) 輸出不確定。 第二:它們的次態(tài)屬于下列情況之一： a次態(tài)相同； b次態(tài)交錯(cuò)或?yàn)楦髯缘默F(xiàn)態(tài)； c次態(tài)循環(huán)或?yàn)橄嗳輰?duì)； d其中的一個(gè)(或兩個(gè))為不確定狀態(tài)。141相容狀態(tài)不具有傳遞性 即不能由S1和S2相容、S2和S3相容，推出S1和S3也相容。 因?yàn)榕袛鄡蓚€(gè)狀態(tài)是否相容時(shí)，對(duì)于不給定的輸出和不給定的次態(tài)可以隨意指定的緣故。142相容類 相容類是由彼此相容的狀態(tài)構(gòu)成的集合。處于同一相容類中的所有狀態(tài)之間都是兩兩相容的。 例如，若有相容對(duì)(S1，S2)、(S2，S3)和(S1，S3)，則可構(gòu)成相容類S1，S2，S3。143最大相容類 若一個(gè)相容類不是任何其他相容類的子集，則該相

51、容類稱為最大相容類。由于相容狀態(tài)無傳遞性，所以，同一原始狀態(tài)表的各最大相容類之間可能存在相同狀態(tài)，即同一狀態(tài)可能出現(xiàn)在不同的最大相容類中。144不完全確定狀態(tài)表的化簡(jiǎn)步驟 作隱含表。作隱含表。 利用狀態(tài)合并圖，求出最大相容類。利用狀態(tài)合并圖，求出最大相容類。 利用閉覆蓋表，求最小閉覆蓋。利用閉覆蓋表，求最小閉覆蓋。 作出最小化狀態(tài)表。作出最小化狀態(tài)表。145作隱含表尋找相容狀態(tài)對(duì) 首先依次判別每個(gè)狀態(tài)對(duì)的相容關(guān)系，并將判斷結(jié)果標(biāo)注到隱含表中。 若某個(gè)狀態(tài)對(duì)相容，則在相應(yīng)方格中填入“”；若某個(gè)狀態(tài)對(duì)是不相容的，則在相應(yīng)方格中填入“”； 若兩個(gè)狀態(tài)的輸出相同(或者不確定)，而其次態(tài)尚不能直接確定是

52、否相容，則在相應(yīng)方格中填入與之相關(guān)的次態(tài)對(duì)。146關(guān)聯(lián)比較 在順序比較完成后，可利用已建立的隱含表繼續(xù)追蹤待確定的狀態(tài)，即進(jìn)行關(guān)聯(lián)比較。 如果與之關(guān)聯(lián)的次態(tài)對(duì)都是相容的，則原狀態(tài)對(duì)是相容的；只要某方格中填入的次態(tài)對(duì)中有一對(duì)不相容，則該方格所對(duì)應(yīng)的狀態(tài)對(duì)不相容，在該方格中填人標(biāo)記“”。 逐個(gè)檢查，直至判斷出所有狀態(tài)對(duì)相容或不相容為止，即可列出原始狀態(tài)表中的全部相容對(duì)。 147求最大相容類 為了方便地找到最大相容類，可以借助于狀態(tài)合并圖。 狀態(tài)合并圖是一種將不完全確定狀態(tài)表的狀態(tài)，以“點(diǎn)”的形式均勻地繪在圓周上，然后把所有相容對(duì)都用線段連接起來而得到的圖。在這種圖中，圓周上的點(diǎn)表示狀態(tài)， 點(diǎn)與點(diǎn)之

53、間的連線表示兩狀態(tài)之間的相容關(guān)系， 所有點(diǎn)之間都有連線的多邊形就構(gòu)成一個(gè)最大相容類。148求最小閉覆蓋 這一步與化簡(jiǎn)完全確定狀態(tài)表差別較大。要想求出不完全給定狀態(tài)表的最小化狀態(tài)表，必須從最大相容類(或相容類)中選出一個(gè)相容類的集合，該相容類集合必須滿足以下3個(gè)條件： 覆蓋性，即所選相容類集合應(yīng)包含原始狀態(tài)表的全部狀態(tài)。 最小性，即所選相容類集合中相容類個(gè)數(shù)應(yīng)最少。 閉合性，即所選相容類集合中的任一相容類，在原始狀態(tài)表中任一輸入條件下產(chǎn)生的次態(tài)應(yīng)該屬于該集合中的某一個(gè)相容類。 149最小閉覆蓋 同時(shí)具備最小、閉合和覆蓋3個(gè)條件的相容類(包括最大相容類)集合，稱為最小閉覆蓋。150閉覆蓋表 所謂閉

54、覆蓋表是指反映閉合和覆蓋這兩個(gè)性質(zhì)的表，該表包括兩部分，一部分反映相容類集合的狀態(tài)覆蓋情況，另一部分反映相容類的閉合關(guān)系。 閉覆蓋表的畫法是：在表的左邊自上而下列出所選相容類，表的中間覆蓋部分自左到右列出全部狀態(tài)，表的右邊閉合部列出各相容類在輸入各種取值組合下的次態(tài)組合。必須指出，這里所說的相容類包括最大相容類和它們的子類。151最大相容類狀態(tài)合并圖示例 3個(gè)、4個(gè)和5個(gè)狀態(tài)的最大相容類狀態(tài)合并圖。152作出最小化狀態(tài)表 選出一個(gè)最小閉覆蓋之后，將最小閉覆蓋中的每個(gè)相容類用一個(gè)新的狀態(tài)符號(hào)表示，再將其代人原始狀態(tài)表中，即可得到與原始狀態(tài)表功能相同的最小化狀態(tài)表。153例4.8(Page 121) 化簡(jiǎn)如表所示的狀態(tài)表:現(xiàn)態(tài)次態(tài)輸出X=0X=1ABD0BBD