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

1、 了解時(shí)序電路的基本結(jié)構(gòu)、分類和常用的描述方法； 熟悉各種觸發(fā)器的功能和使用； 熟練掌握同步時(shí)序電路分析和設(shè)計(jì)的基本方法； 熟悉狀態(tài)圖的建立，狀態(tài)簡(jiǎn)化和狀態(tài)分配的各個(gè)重要環(huán)節(jié)。一個(gè)電路在任何時(shí)刻的穩(wěn)定輸出不僅與該時(shí)刻電路的輸入信號(hào)有關(guān)，而且與該電路過去的輸入有關(guān)，這樣的電路稱為時(shí)序電路。時(shí)序電路由組合電路和存儲(chǔ)(記憶)器件及反饋回路三部分組成，見下圖.x1z1組合電路存儲(chǔ)器件xnzmyry1Y1Ylx1 . xn：時(shí)序電路的輸入或外部輸入；時(shí)序電路的輸入或外部輸入；z1 . zm：時(shí)序電路的輸出或外部輸出；時(shí)序電路的輸出或外部輸出；y1. yr：時(shí)序電路的狀態(tài)或內(nèi)部輸入；時(shí)序電路的狀態(tài)或內(nèi)部輸

2、入；Y1 . Yl：時(shí)序電路的激勵(lì)或內(nèi)部輸出；時(shí)序電路的激勵(lì)或內(nèi)部輸出；狀態(tài)狀態(tài)：過去的輸入已不存在，但可以通過存儲(chǔ)器件把它們記錄下來，稱之為狀態(tài)。記錄下來的信息可能和過去的輸入完全一樣，也可能是經(jīng)過了組合電路加工處理后的結(jié)果。我們把某一時(shí)刻之前的狀態(tài)稱為現(xiàn)態(tài)，把這一時(shí)刻之后的狀態(tài)稱為次態(tài)，現(xiàn)態(tài)和次態(tài)是一個(gè)相對(duì)的概念，分別用y(n)(或y)和y(n+1)表示。時(shí)序電路的邏輯函數(shù)由下列方程組成：時(shí)序電路的邏輯函數(shù)由下列方程組成：Zi= fi (x1,， xn ; y1,， yr ) , i=1, , mYj= gj (x1,， xn ; y1,， yr ) , j=1, , l兩種時(shí)序電路類型見

3、下圖：(a) 同步時(shí)序電路x1z1組合電路存儲(chǔ)器件或延時(shí)器件xnzmyry1Y1Yl(b) 異步時(shí)序電路x1z1組合電路存儲(chǔ)器件xnzmyry1Y1Yl時(shí)鐘狀態(tài)表與狀態(tài)圖是用來表示同步時(shí)序電路的輸入、輸出、現(xiàn)態(tài)、次態(tài)之間轉(zhuǎn)移關(guān)系的兩種常用工具。如果同步時(shí)序電路的輸出是輸入和現(xiàn)態(tài)的函數(shù)，即Zi= fi (x1,， xn ; y1,， yr ) , i=1, , m ，則稱該電路為Mealy型電路。Mealy 型電路狀態(tài)表現(xiàn)態(tài)次態(tài) / 輸出輸入xyy(n+1)/Z該表表明：處在狀態(tài)y的同步時(shí)序電路，當(dāng)輸入為x時(shí)，輸出為z，且在時(shí)鐘脈沖作用下，電路進(jìn)入次態(tài)y(n+1)。某Mealy 型電路狀態(tài)表現(xiàn)

4、態(tài)次態(tài) / 輸出(y(n+1)/Z)x = 0yA / 0A / 0B / 0 x = 1B / 0C / 0A / 1ABC狀態(tài)圖是一種反映同步時(shí)序電路狀態(tài)轉(zhuǎn)移規(guī)律和輸入、輸出取值關(guān)系的有向圖。yx/zy(n+1)Mealy型電路狀態(tài)圖某Mealy型電路狀態(tài)圖ACB0/01/00/00/01/01/1如果同步時(shí)序電路的輸出僅是現(xiàn)態(tài)的函數(shù), 即Zi= fi (y1, yr ) , i=1, , m , 則稱電路為Moore型電路。它的電路結(jié)構(gòu)圖可表示為:x1組合電路xnyry1Y1Yl存儲(chǔ)器件組合電路z1zmMoore 型電路狀態(tài)表現(xiàn) 態(tài)次 態(tài)輸入xyy(n+1)Z輸 出該表表明：當(dāng)電路處于狀

5、態(tài)y時(shí)，輸出為z，若輸入為x，則在時(shí)鐘脈沖作用下，電路進(jìn)入次態(tài)y(n+1)。某Moore 型電路狀態(tài)表現(xiàn) 態(tài)次 態(tài) y(n+1)x = 0yCBBx = 1ABC輸 出ZBCA010Moore型電路狀態(tài)圖某Moore型電路狀態(tài)圖y/zxy(n+1)ZC/0A/0B/1010110觸發(fā)器是一種存儲(chǔ)元件，在電路中用來記憶電路過去的輸入情況。一個(gè)觸發(fā)器具有兩種穩(wěn)定的狀態(tài),一個(gè)稱之為 0狀態(tài)，另一種稱之為1狀態(tài)。在任何時(shí)刻,觸發(fā)器只處于一個(gè)穩(wěn)定狀態(tài),當(dāng)觸發(fā)脈沖作用時(shí),觸發(fā)器可以從一種狀態(tài)翻轉(zhuǎn)到另一種狀態(tài)。在輸入信號(hào)取消后，能將獲得的新狀態(tài)保存下來。常用的觸發(fā)器有RS觸發(fā)器, D觸發(fā)器，J K觸發(fā)器和T

6、觸發(fā)器?；綬S觸發(fā)器可 由兩個(gè)與非門交叉耦合組成，其邏輯圖和邏輯符號(hào)如下：&G1RQG2SQ011100QRSQR：清零端 S：置1端 低電平有效基本RS觸發(fā)器的輸入與狀態(tài)（Q端）之間的邏輯關(guān)系可用觸發(fā)器的功能表來描述。R SQ(n+1)功能說明0 00 11 01 1d 0 1Q不定置 0置 1不變基本RS觸發(fā)器功能表基本RS觸發(fā)器的次態(tài)方程為：Q(n+1)SRQ其約束條件為：R+S=1基本RS觸發(fā)器的一個(gè)重要特性：如果一端輸入持續(xù)為1的條件下，另一端連續(xù)出現(xiàn)多個(gè)置0或置1信號(hào)，只有第一個(gè)置0或置1信號(hào)起作用。利用這一特性可消除機(jī)械開關(guān)的觸點(diǎn)抖動(dòng)。000 01 11 1001RSQ

7、0Q(n+1)dd0111基本RS觸發(fā)器的動(dòng)作特點(diǎn)： 輸入信號(hào)在全部作用時(shí)間內(nèi)都直接改變輸出端Q和 的狀態(tài)。Q在數(shù)字系統(tǒng)中，通常要求觸發(fā)器按一定的時(shí)間節(jié)拍動(dòng)作，即讓輸入信號(hào)的作用受到時(shí)鐘脈沖的控制，為此出現(xiàn)了帶時(shí)鐘控制的R-S觸發(fā)器&G1RQG2SQ&CPG3G4QRSQCP110101100R：清零端 S：置1端 高電平有效當(dāng)CP為0時(shí)，不論R，S為何值，觸發(fā)器的狀態(tài)保持不變；當(dāng)CP為1（時(shí)鐘信號(hào)到來）時(shí)，觸發(fā)器的狀態(tài)取取決于R和S，工作原理與RS觸發(fā)器相同。鐘控觸發(fā)器的功能表和狀態(tài)表如下：R SQ(n+1)功能說明0 00 11 01 1Q 1 0d不變置 1置 0不定鐘控

8、RS觸發(fā)器功能表現(xiàn) 態(tài)Q次 態(tài) Q(n+1)0 1010111dd00RS=001 11 0鐘控RS觸發(fā)器狀態(tài)表0100, 1000, 01RS0110鐘控RS觸發(fā)器狀態(tài)圖空翻空翻：時(shí)鐘信號(hào)作用期間，如果輸入信號(hào)發(fā)生變化，觸發(fā)器狀態(tài)會(huì)跟著變化，從而在一次時(shí)鐘信號(hào)作用期間，可能引起觸發(fā)器多次翻轉(zhuǎn)。鐘控RS觸發(fā)器的狀態(tài)方程為：Q(n+1)SRQRS = 0 (約束條件)100 01 11 1001RSQdQ(n+1)01100d鐘控R-S觸發(fā)器存在次態(tài)不能確定和空翻兩個(gè)問題。11如果使鐘控RS觸發(fā)器的R和S端始終處于互補(bǔ)狀態(tài), 則可消去次態(tài)不能確定的問題, 這就形成了所謂的D觸發(fā)器, 其邏輯圖的邏

9、輯符號(hào)如下:QQCD001110011101100&G1(R)QG2DQ&CPG3G4(S)當(dāng)CP=0時(shí)，D觸發(fā)器的狀態(tài)不變；當(dāng)CP=1時(shí)，D觸發(fā)器的狀態(tài)取決于D。D觸發(fā)器的功能表和狀態(tài)表如下：DQ(n+1)0101QQ(n+1)010011D0D1D觸發(fā)器功能表D觸發(fā)器狀態(tài)表D觸發(fā)器的次態(tài)方程為：Q(n+1)D狀態(tài)圖為：0101D10D觸發(fā)器結(jié)構(gòu)簡(jiǎn)單, 但仍然存在空翻現(xiàn)象。實(shí)際使用的D觸發(fā)器是一種維持阻塞型D觸發(fā)器, 可以防止空翻的發(fā)生。置”1”維持線置”1”阻塞線置”0”阻塞線置”0”維持線&QSDQ&CPRDD&DCPSDRDQQ維持阻塞D觸發(fā)器:

10、CP上升沿將D可靠置入，無空翻現(xiàn)象。JK觸發(fā)器有兩個(gè)輸入端，即克服了RS觸發(fā)器的約束問題，使用上又比D觸發(fā)器靈活。其邏輯圖與邏輯符號(hào)如下：QQJKC0111Q1100Q1Q(n+1)=0QQ11111001100&G1KQG2JQ&CPG3G4Q(n+1)=1Q0R S當(dāng)CP0時(shí)，JK觸發(fā)器的狀態(tài)保持不變；當(dāng)CP1時(shí)， 若J=K=0, 則G3=G4=1, 觸發(fā)器保持原狀態(tài)； 若J=1, K=0, 則G3=1, G4=Q, 使觸發(fā)器置1； 若J=0, K=1, 則G3=Q, G4=1, 使觸發(fā)器置0； 若J=K=1, 則G3=Q, G4=Q, 使觸發(fā)器翻轉(zhuǎn)；JK觸發(fā)器功能表和狀態(tài)

11、表如下：JK觸發(fā)器功能表QQ(n+1)0 10101001011JK=001 11 0JK觸發(fā)器狀態(tài)表J KQ(n+1)功能說明0 00 11 01 1Q 0 1Q不變置 0置 1翻轉(zhuǎn)JK觸發(fā)器的次態(tài)方程為：Q(n+1)JQKQ狀態(tài)圖為：0100, 01JK10, 1101, 1100, 10為防止空翻，實(shí)際數(shù)字電路中使用的JK觸發(fā)器是主從式集成JK觸發(fā)器，它使用前沿采樣，后沿定局的方式，無空翻，功能較全，使用靈活。000 01 11 1001JKQ1Q(n+1)010110主從JK觸發(fā)器:KJCP&QSDQ&RD&1（從）（主）CP前沿采樣，后沿定態(tài)；無空翻現(xiàn)象。JC

12、PSDRDQQKT觸發(fā)器實(shí)際上是JK觸發(fā)器的一種特殊形式。如果把JK觸發(fā)器的JK端連在一起就形成了T觸發(fā)器。因此T觸發(fā)器的次態(tài)方程為：Q(n+1)TQTQ其功能表和狀態(tài)表是JK觸發(fā)器功能表和狀態(tài)表的一部分。T觸發(fā)器又稱計(jì)數(shù)觸發(fā)器。上升沿觸發(fā)下降沿觸發(fā)對(duì)一個(gè)給定的時(shí)序邏輯電路，研究在一系列輸入信號(hào)作用下，電路將會(huì)產(chǎn)生怎樣的輸出，進(jìn)而說明該電路的邏輯功能。實(shí)際上是要求出電路的狀態(tài)表、狀態(tài)圖或時(shí)間圖，并作出功能評(píng)述。通過了解電路的特點(diǎn)，有助于改進(jìn)電路的設(shè)計(jì)。邏輯電路圖輸出函數(shù)和激勵(lì)函數(shù)表達(dá)式 觸發(fā)器次態(tài)方程觸發(fā)器功能表狀態(tài)表和狀態(tài)圖用時(shí)間圖和文字描述電路邏輯功能列出狀態(tài)轉(zhuǎn)移真值表 電路次態(tài)方程組用表

13、格法分析下圖所示的同步是序邏輯電路1K1J1CK2J2CY2Y1CP1X：寫出輸出函數(shù)和激勵(lì)函數(shù)表達(dá)式。J1=K1=1 J2=K2=x y1：列同狀態(tài)轉(zhuǎn)移真值表?，F(xiàn) 態(tài)y2 y1 激 勵(lì) 函 數(shù)J2K2J1K1次 態(tài)y2 (n+1) y1 (n+1)000011110 00 11 01 10 00 11 01 1010110100101101011111111111111110 11 01 10 01 10 00 11 0輸 入x作出狀態(tài)表和狀態(tài)圖。次 態(tài) y2 (n+1)y1 (n+1)0 00 11 01 1現(xiàn) 態(tài) y2 y1 x = 0 x = 10 11 01 10 01 10 00

14、11 00001101101100110 x用時(shí)間圖和文字描述電路和邏輯功能。當(dāng)x=0時(shí),該電路進(jìn)行加1計(jì)數(shù),計(jì)數(shù)序列為:00011011當(dāng)x=1時(shí),該電路進(jìn)行減1計(jì)數(shù),計(jì)數(shù)序列為:00111001時(shí)間圖的作法：時(shí)間圖的作法： 選定一個(gè)典型的輸入序列； 根據(jù)選定的典型輸入序列，求出狀態(tài)響應(yīng)序列(和輸出響應(yīng)序列)輸入序列為：x=11110000,初態(tài)： y2y1=00 CP: 12345678 x: 11110000 y2: 01100011 y1: 01010101y2(n+1): 11000110 y1(n+1): 10101010 畫時(shí)間圖:11110000y1y2x12345678CP試

15、用代數(shù)法分析下圖所示的同步時(shí)序邏輯電路。1D1CD2Cy2CPx&y1z寫出輸出函數(shù)和激勵(lì)函數(shù)表達(dá)式。Z=x y2 y1D2 = x + y2 + y1 = x y2 y1D1 = x把激勵(lì)函數(shù)表達(dá)式代入觸發(fā)器的次態(tài)方程，得到電路的次態(tài)方程組。Q1(n+1)D1 xQ2(n+1)D2 x y2 y1根據(jù)次態(tài)方程組和輸出函數(shù)表達(dá)式作出狀態(tài)表和狀態(tài)圖。次態(tài)/輸出( y2 (n+1) y1 (n+1)/Z)0 00 11 11 0現(xiàn) 態(tài) y2 y1 x = 0 x = 100/010/000/000/001/001/001/001/1000110111/0 x/z0/00/00/01/01/

16、10/01/0：作出時(shí)間圖，并說明電路的邏輯功能。典型輸入序列：x = 01011101初態(tài)： y2 y1= 00狀態(tài)響應(yīng)序列和輸出響應(yīng)序列為： CP: 12345678 x: 01011101 y2: 00010001 y1: 00101110y2(n+1): 00100010 y1(n+1): 01011101 Z: 00010001CPxy2y1Z12346785功能說明：功能說明：該電路是一個(gè)101序列檢測(cè)器。同步時(shí)序邏輯電路設(shè)計(jì)又稱同步時(shí)序邏輯電路綜合，其基本指導(dǎo)思想是用盡可能少的觸發(fā)器和門電路來完成設(shè)計(jì)。同步時(shí)序電路設(shè)計(jì)的一般步驟為：同步時(shí)序電路設(shè)計(jì)的一般步驟為：1. 根據(jù)邏輯要求

17、，作原始狀態(tài)圖和狀態(tài)表；2. 對(duì)原始狀態(tài)表化簡(jiǎn)；3. 狀態(tài)編碼；4. 選定觸發(fā)器，求出輸出函數(shù)和激勵(lì)函數(shù)表達(dá)式；5. 畫出邏輯電路圖。狀態(tài)圖是同步時(shí)序電路設(shè)計(jì)的依據(jù)，它必須正確反映設(shè)計(jì)要求。狀態(tài)圖的構(gòu)成沒有統(tǒng)一的方法，關(guān)鍵是要充分正確地理解設(shè)計(jì)要求，明確電路的輸入條件和輸出要求，輸入和輸出關(guān)系，以及狀態(tài)的轉(zhuǎn)換關(guān)系。原始狀態(tài)圖建立的一般過程為：原始狀態(tài)圖建立的一般過程為：假定一個(gè)初始狀態(tài)，由此出發(fā)，每加入一個(gè)輸入信號(hào)，則記憶其次態(tài)，并標(biāo)出其相應(yīng)的輸出值。次態(tài)可能為現(xiàn)態(tài)、已有狀態(tài)或新的狀態(tài)，直到?jīng)]有新的狀態(tài)為止。每個(gè)狀態(tài)的各種可能的輸入值都要考慮到。例例4.3: 某序列檢測(cè)器有一個(gè)輸入端x和一個(gè)輸

18、出端Z。從x端輸入一組按時(shí)間順序排列的串行二進(jìn)制碼。當(dāng)輸入序列中出現(xiàn)101時(shí)，輸出Z1，否則 Z0。試作出該序列檢測(cè)器的Mealy型和Moore型原始狀態(tài)圖和狀態(tài)表。S0S1S2S31/11/00/00/00/01/00/01/0電路的電路的Mealy 型狀態(tài)表型狀態(tài)表現(xiàn)態(tài)次態(tài)/輸出x=0 x=1S0S1S2S3S0/0S2/0S0/0S2/0S1/0S1/0S3/1S1/0電路的電路的 Moore 型狀態(tài)表型狀態(tài)表現(xiàn)態(tài)次 態(tài)x=0 x=1S0S1S2S3S0S2S0S2S1S1S3S1輸 出Z0001S0/0 S1/0S2/0S3/110100101例例4.4: 假設(shè)某同步時(shí)序電路，用于檢測(cè)

19、串行輸入的8421BCD碼，其輸入的順序是先高位后低位，當(dāng)出現(xiàn)非法數(shù)字(即輸入1010，1011，1100，1101，1110，1111)時(shí)，電路的輸出為1。試作出該時(shí)序電路的Mealy型原始狀態(tài)圖和狀態(tài)表。FDABCEG0/01/00/01/00/01/00/01/0解：解：HDAB1/00/0CEI0/00/01/01/0FG0/01/0NJKP0/00/01/01/0LM0/01/00/01/00/01/00/01/00/01/00/01/00/11/10/11/10/11/1電路的原始狀態(tài)圖現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDEFGHIJKLMNPB/0D/0J/0F/0H/0A/0A

20、/0A/0A/0L/0N/0A/0A/1A/1A/1C/0E/0K/0G/0I/0A/0A/0A/0A/0M/0P/0A/0A/1A/1A/1電路的原始狀態(tài)電路的原始狀態(tài)表表例例4.5：假設(shè)有一個(gè)三位二進(jìn)制加、減法器（模8計(jì)數(shù)器），當(dāng)X輸入為1時(shí)，實(shí)現(xiàn)加1計(jì)數(shù)；當(dāng)X為0時(shí)，實(shí)現(xiàn)減1計(jì)數(shù)，試作出該電路的Moore型原始狀態(tài)圖和狀態(tài)表。解：解：000111110101100011010001000001010011100101110111當(dāng)X為0時(shí)：當(dāng)X為1時(shí)：計(jì)數(shù)器的輸出可為狀態(tài)本身，亦可看作外部輸出。1 000110001101010111100011111111100000000原始狀態(tài)圖原

21、始狀態(tài)圖現(xiàn)態(tài)次態(tài)x=0 x=1000001010011100101110111111000001010011100101110001010011100101110111000原始狀態(tài)表原始狀態(tài)表一般情況下，原始狀態(tài)圖和原始狀態(tài)表中存在著多余的狀態(tài)。狀態(tài)個(gè)數(shù)越多，電路中所需的觸發(fā)器的數(shù)目也越多，制造成本就越高。為降低制造成本，需要去掉多余的狀態(tài)，即要進(jìn)行狀態(tài)狀態(tài)化簡(jiǎn)化簡(jiǎn)。所謂狀態(tài)化簡(jiǎn)狀態(tài)化簡(jiǎn)，就是要獲得一個(gè)最小化的狀態(tài)表。這個(gè)表不僅能正確地反映設(shè)計(jì)的全部要求，而且狀態(tài)的數(shù)目最少。完全確定狀態(tài)表完全確定狀態(tài)表： 狀態(tài)表中的次態(tài)和輸出都有確定的 狀態(tài)和確定的輸出值。等效狀態(tài)：等效狀態(tài)：設(shè)狀態(tài)S1和S

22、2是完全確定狀態(tài)表中的兩個(gè)狀態(tài),如果對(duì)于所有可能的輸入序列，分別從狀態(tài)S1和狀態(tài)S2出發(fā)，所得到的輸出響應(yīng)序列完全相同，則狀態(tài)S1和S2是等效的，記作(S1, S2) . 或說，狀態(tài)S1和S2是等效對(duì)。等效狀態(tài)可以合并。S1S1S2S2S3S3S4S40/00/00/10/11/11/1 等效狀態(tài)傳遞性：(S1,S2), (S2,S3)(S1,S3) 等效類： 彼此等效的狀態(tài)集合 最大等效類： 不被其它等效類所包含的等效類。一個(gè)狀態(tài)也可能是一個(gè)最大等效類。狀態(tài)簡(jiǎn)化的任務(wù)是要在原始狀態(tài)表中找出全部最大等效類(最大等效類集合)，并將每一個(gè)最大等效類用一個(gè)狀態(tài)來表示，從而得到最小化狀態(tài)表。判別方法：

23、判別方法：第一、它們的輸出完全相同； 假定狀態(tài)S1和S2是完全確定原始狀態(tài)表中的兩個(gè)現(xiàn)態(tài)，那么S1和S2等效的條件可歸納為在輸入的各種取值組合下：(1) 次態(tài)相同； 第二、它們的次態(tài)滿足下列條件之一，即(2) 次態(tài)交錯(cuò)；(3) 次態(tài)循環(huán)；(4) 次態(tài)對(duì)等效。 SiSj1/0Sl0/10/1Sk1/0次態(tài)相同次態(tài)相同或交錯(cuò) SiSj0/01/01/0Sk0/0次態(tài)交錯(cuò)或相同或循環(huán) SiSj1/01/0SkSl0/00/00/10/1Sm1/01/0次態(tài)交錯(cuò)或等效(Sk,Sl等效) SiSj1/01/0SlSk0/10/11. 觀察法化簡(jiǎn)觀察法化簡(jiǎn)例例4.6：簡(jiǎn)化下表所示的狀態(tài)表現(xiàn)態(tài)次態(tài)/輸出x=

24、0 x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/1解：解： A和B，C和D的輸出完全相等； C和D在輸入的各種取值組合下，次態(tài)相同，因此C和D等效； 最大等效類為A，B，C,D,分別用A, B, C表示； A和B在x=1時(shí)的次態(tài)不滿足四條件之一，因此A和B不等效;現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/1最小化狀態(tài)表為：現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCA/0A/0A/0B/0C/0C/1現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/12. 隱含表法化簡(jiǎn)隱含表法化簡(jiǎn)例例4.7：化簡(jiǎn)下表所示的狀態(tài)表現(xiàn)態(tài)

25、次態(tài)/輸出x=0 x=1ABCDEFGC/0F/0D/0D/1C/0D/0C/1B/1A/1G/0E/0E/1G/0D/0解：解： 作隱含表作隱含表 順序比較，尋找等效順序比較，尋找等效狀態(tài)對(duì)狀態(tài)對(duì) 狀態(tài)對(duì)等效，打狀態(tài)對(duì)等效，打“ “ ”； 狀態(tài)對(duì)不等效，打狀態(tài)對(duì)不等效，打 “ ”“ ”； 狀態(tài)對(duì)是否等效需進(jìn)狀態(tài)對(duì)是否等效需進(jìn)一步檢查，則標(biāo)記次態(tài)一步檢查，則標(biāo)記次態(tài)對(duì)。對(duì)。ABCDEFGFEDCBCFBEAECFCDDE現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDEFGC/0F/0D/0D/1C/0D/0C/1B/1A/1G/0E/0E/1G/0D/0ABCDEFGFEDCBCFBEAECFCDDE

26、處于循環(huán)鏈中的每一個(gè)狀態(tài)對(duì)都是等效狀態(tài)對(duì),一共四個(gè)等效對(duì) (A,B), (A,E), (B,E), (C,F)。 關(guān)聯(lián)比較，確定等效狀態(tài)對(duì)AEBECFABCF現(xiàn)態(tài)次態(tài)/輸出x=0 x=1abcdb/0c/0c/1b/1a/1d/0a/0c/0確定最大等效類，作最小化狀態(tài)表確定最大等效類，作最小化狀態(tài)表: 四個(gè)等效對(duì) (A,B), (A,E), (B,E), (C,F) 四個(gè)最大等效類 (A,B,E), (C,F), (D), (G) 令以上四個(gè)最大等效類依次為a, b, c, d.現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDEFGC/0F/0D/0D/1C/0D/0C/1B/1A/1G/0E/0E/1

27、G/0D/0不完全確定狀態(tài)表不完全確定狀態(tài)表： 狀態(tài)表中存在不確定的次態(tài)或輸出，這些不確定的次態(tài)或輸出將有利于狀態(tài)簡(jiǎn)化。 相容狀態(tài)：設(shè)狀態(tài)S1和S2是不完全確定狀態(tài)表中的兩個(gè)狀態(tài)，如果對(duì)于所有的有效輸入序列，分別從狀態(tài)S1和S2出發(fā)，所得到的輸出響應(yīng)序列(除不確定的那些位之外)是完全相同的，那么狀態(tài)S1和S2是相容的，或者說狀態(tài)S1和S2是相容對(duì)，記作(S1,S2)。相容狀態(tài)可以合并。例: 設(shè)計(jì)一個(gè)“1111”序列檢測(cè)器，使其成為爆炸裝置的引爆控制器。假定工作條件為：平時(shí)無1輸入，Z一直處于0狀態(tài)；當(dāng)連續(xù)輸入4個(gè)1時(shí)（不允許出現(xiàn)0），Z=1引爆，整個(gè)裝置不存在。 ADBC1/01/01/00/

28、00/d0/d0/d1/1dddd現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDA/0d/dd/dd/dB/0C/0D/0d/1 相容狀態(tài)無傳遞性： SiSj1/10/00/00/0Sk0/0Sl1/01/dSi和Sj相容；Sj和Sk相容；但Si和Sk不相容。最大相容類：不被其它相容類所包含的相容類相容類：彼此相容的狀態(tài)集合判別方法：判別方法：在不完全確定狀態(tài)表中判斷兩個(gè)狀態(tài)是否相容也是根據(jù)表中給出的次態(tài)和輸出來決定的。假定狀態(tài)Si和Sj是不完全確定狀態(tài)表中的兩個(gè)現(xiàn)態(tài)，那么狀態(tài)Si和Sj相容的條件可歸納為在輸入的各種取值組合下:第一、它們的輸出完全相同，或者其中的一個(gè)(或兩個(gè)) 輸出為任意值。第二、它們

29、的次態(tài)滿足下列條件之一：(1) 次態(tài)相同；(2) 次態(tài)交錯(cuò)；(3) 次態(tài)循環(huán)；(4) 其中的一個(gè)(或兩個(gè))為任意狀態(tài);(5) 次態(tài)相容；例例4.8：簡(jiǎn)化下表所示的狀態(tài)表現(xiàn) 態(tài)次 態(tài)x=0 x=1ABCDEFBBAdFdDDEEdC輸 出0d111d解：解： 作隱含表； 順序比較， 尋找相容對(duì)；ABDEABCDEFEDCBDEBFAFCE CECDCD現(xiàn) 態(tài)次 態(tài)x=0 x=1ABCDEFBBAdFdDDEEdC輸 出0d111dCEAF CFCE DFCE 以上三步與確定狀態(tài)表的化簡(jiǎn)相同 關(guān)聯(lián)比較，確定相容對(duì)；ABDEABCDEFEDCBDEBFAFCE CECDCDAFCD BCAB DE

30、BDDE BEBFCD 全部相容對(duì)：(A,B), (A,F), (B,C), (B,D), (B,E), (B,F), (C,D), (C,E), (C,F), (D,F), (D,E), (E,F)。 作狀態(tài)合并圖，求最大相容類。S1S2S33狀態(tài)相容S4S1S2S34狀態(tài)相容S1S2S3S4S55狀態(tài)相容ABCDFE本例狀態(tài)合并圖，最大相容類是(A,B,F), (B,C,D,E,F)。全部相容狀態(tài)對(duì)：(A,B), (A,F), (B,C), (B,D), (B,E), (B,F), (C,D), (C,E), (C,F), (D,F), (D,E), (E,F)。作最小化狀態(tài)表作最小化狀態(tài)

31、表: 最小化狀態(tài)表(又稱最小閉覆蓋) 應(yīng)滿足下列三個(gè)條件： 覆蓋性所選相容類集合應(yīng)包含原始狀態(tài)表中的全部狀態(tài)。 最小性所選相容類集合中相容類的個(gè)數(shù)應(yīng)最少。 閉合性所選相容類集合中的任一相容類的所有隱含條件（在原始狀態(tài)表中任一輸入條件下產(chǎn)生的次態(tài)）都必須屬于該集合中某一個(gè)（最好是一個(gè)不是兩個(gè)）相容類采用閉覆蓋表來反映所選相容類集合的覆蓋和閉合情況。本例的閉覆蓋表為CDE最大相 容類ABFBCDEFA B C D EF 覆蓋閉合x=0 x=1BABFCD現(xiàn)態(tài)次態(tài)x=0 x=1ABCDEFBBAdFdDDEEdC輸出0d111d所選相容類集合所選相容類集合(A,B,F), A,B,F), (B,C,

32、D,E,F) (B,C,D,E,F) 滿足最小閉覆滿足最小閉覆蓋條件，令蓋條件，令A(yù) A表示表示(A,B,F)A,B,F)，C C表示表示( (B,C,D,E,F)B,C,D,E,F)可得：可得：現(xiàn) 態(tài)次 態(tài)x=0 x=1ACA,CACC輸 出01現(xiàn) 態(tài)次 態(tài)x=0 x=1ACdACC輸 出01由于該表中只有兩個(gè)狀態(tài)，進(jìn)一步可以得到：由于該表中只有兩個(gè)狀態(tài)，進(jìn)一步可以得到：現(xiàn)態(tài)次態(tài)x=0 x=1ABCDEFBBAdFdDDEEdC輸出0d111dCDE最大相 容類ABFBCDEFABCDEF 覆蓋閉合x=0 x=1BABFCD例：例：化簡(jiǎn)下表所示的狀態(tài)表現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDED

33、/dE/0D/0C/dC/1A/dA/dB/dC/dB/d解解： 作隱含表，尋找相容狀態(tài)對(duì)ABCDEDCBABDEACCECDACABCDABDEBCBC由上圖得相容狀態(tài)對(duì)為(A,B), (A,C), (A,D), (A,E), (B,C), (C,D), (D,E)ABDEBC ACAB BDAC CE AEABCDADBC CDAC現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d 作狀態(tài)合并圖，尋找最大相容類ABCDE得最大相容類為(A,B,C), (A,C,D), (A,D,E) 作最小化狀態(tài)表若選相容類集合為(A,B,C), (A,D,

34、E)則下表表明它不滿足閉合要求相容類ABCADEA B C D E 覆蓋閉合x=0 x=1DECD ABCABABCDE現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d(A,B,C), (A,C,D), (A,D,E)但如果選相容類 (A,B,C)和 (D,E)則能滿足最小閉覆蓋的要求相容類ABCDEA B C D EA B CD E覆蓋閉合x=0 x=1DECBCABABCDE現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d令A(yù)=(A,B,C), B=(D,E), 進(jìn)一步可得：現(xiàn)態(tài)次態(tài)/輸出x

35、=0 x=1ABB /0A /1A/dA/d尋找最小閉覆蓋通常不是一件容易的事情，其結(jié)果往往不唯一?，F(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d給最小化狀態(tài)表中的每一個(gè)狀態(tài)指定一個(gè)二進(jìn)制代碼，形成二進(jìn)制狀態(tài)表。通常情況下，狀態(tài)編碼的方案不一樣，所得到的輸出函數(shù)和激勵(lì)函數(shù)的表達(dá)式也不同，由此而設(shè)計(jì)出來的電路復(fù)雜度也不同。狀態(tài)分配的任務(wù)是： 決定編碼的長(zhǎng)度；尋找一種最佳的或接近最佳的狀態(tài)分配方案。設(shè)最小化狀態(tài)表中的狀態(tài)數(shù)為N，編碼長(zhǎng)度為n，N和n的關(guān)系為 2n-1N2n用2n種組合來對(duì)N個(gè)狀態(tài)進(jìn)行分配時(shí)，可能出現(xiàn)的分配方案的總數(shù)Ks為! )2(

36、!2AKNnnNns例如例如，n=2, N=4時(shí) 有方案狀態(tài)12345678910 11 12ABCD00 10 01 11 00 01 10 11 00 10 01 1101 11 00 10 10 11 00 01 11 01 10 0011 01 10 00 11 10 01 00 01 11 00 1010 00 11 01 01 00 11 10 10 00 11 01方案狀態(tài)13 14 15 16 17 18 19 20 21 22 23 24ABCD00 01 10 11 00 10 01 11 00 01 10 1111 10 01 00 10 00 11 01 01 00 1

37、1 1010 11 00 01 01 11 00 10 10 11 00 0101 00 11 10 11 01 10 00 11 10 01 00但是，在Ks種方案中只有三種是獨(dú)立的(真正不相同的)方案!)!2()!12(=KnNnnu然而，當(dāng)n較大時(shí)，Ku仍然很大，要真正找到最佳的分配方案是十分困難的，況且分配方案的好壞還與所采用的觸發(fā)器的類型有關(guān)。因此，實(shí)際應(yīng)用時(shí)都是采用工程的方法，依據(jù)以下四條件原則來進(jìn)行狀態(tài)分配。狀態(tài)分配的基本原則有四條：狀態(tài)分配的基本原則有四條：(1) 在相同輸入條件下具有相同次態(tài)的現(xiàn)態(tài)，應(yīng)盡可能給這些現(xiàn)態(tài)分配相鄰的二進(jìn)制代碼；(2) 同一現(xiàn)態(tài)在不同輸入條件下的次態(tài)

38、應(yīng)盡可能分配相鄰的二進(jìn)制代碼；(3) 輸出完全相同完全相同的現(xiàn)態(tài)應(yīng)盡可能分配相鄰的二進(jìn)制代碼；(4) 最小化狀態(tài)表中出現(xiàn)次數(shù)最多的狀態(tài)或初始狀態(tài)應(yīng)分配邏輯0。一般情況下，第一條原則較為重要，需優(yōu)先考慮，其次要考慮由前三條原則得到的應(yīng)分配相鄰代碼的狀態(tài)對(duì)出現(xiàn)的次數(shù)，次數(shù)多的狀態(tài)對(duì)應(yīng)優(yōu)先分配相鄰的二進(jìn)制代碼。例例4.9：對(duì)下表所示的狀態(tài)表進(jìn)行狀態(tài)分配現(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDC/0C/0B/0A/1D/0A/0D/0B/1解：解： 確定n=2 確定分配 由規(guī)則(1)得A和B,A和C應(yīng)相鄰； 由規(guī)則(2)得C和D,C和A,B和D,A和B應(yīng)相鄰； 由規(guī)則(3)得A,B,C 三者應(yīng)相鄰,即AB

39、,AC,BC應(yīng)相鄰； 由規(guī)則(4)得A分配為邏輯0?，F(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDC/0C/0B/0A/1D/0A/0D/0B/1ABDC0101y2y1A:B:C:D:y2 y100100111 由規(guī)則(1)得A和B,A和C應(yīng)相鄰； 由規(guī)則(2)得C和D,C和A,B和D,A和B應(yīng)相鄰； 由規(guī)則(3)得A,B,C 三者應(yīng)相鄰,即A和B,A和C,B和C應(yīng)相鄰； 由規(guī)則(4)得A分配為邏輯0。最后我們可以得到二進(jìn)制狀態(tài)表現(xiàn)態(tài)y2 y1次態(tài)y2(n+1)y1(n+1)/輸出x=0 x=10001111001/010/000/101/011/011/010/100/0注意：注意：有時(shí)滿足分配原則

40、的分配方案不唯一，這時(shí)可任選一種?，F(xiàn)態(tài)次態(tài)/輸出x=0 x=1ABCDC/0C/0B/0A/1D/0A/0D/0B/11. 觸發(fā)器的激勵(lì)表觸發(fā)器的激勵(lì)表觸發(fā)器的激勵(lì)表反映觸發(fā)器從某種現(xiàn)態(tài)轉(zhuǎn)換 到某種次態(tài)時(shí)，對(duì)觸發(fā)器輸入(激勵(lì))的要求。在這種表中，現(xiàn)態(tài)和次態(tài)作為自變量，輸入(激勵(lì))作為因變量。觸發(fā)器的激勵(lì)表可由觸發(fā)器的狀態(tài)表直接推出。Q Q(n+1)RSd001100d00011011Q Q(n+1)D010100011011R-S觸發(fā)器激勵(lì)表D觸發(fā)器激勵(lì)表Q Q(n+1)JK0d1dd1d000011011Q Q(n+1)T011000011011J-K觸發(fā)器激勵(lì)表T觸發(fā)器激勵(lì)表2. 確定激勵(lì)

41、函數(shù)確定激勵(lì)函數(shù)兩種方法兩種方法：根據(jù)次態(tài)方程來確定和通過激勵(lì)表來確定。常采用后一種方法。例例4.10：若用D觸發(fā)器實(shí)現(xiàn)下表所示的二進(jìn)制狀態(tài)表， 試寫出激勵(lì)和輸出函數(shù)?，F(xiàn)態(tài) y2 y1次態(tài)y2(n+1)y1(n+1)/輸出Zx=0 x=10001111010/000/001/100/101/000/110/111/1解：解： 確定激勵(lì)函數(shù)現(xiàn)態(tài) y2 y1次態(tài)y2(n+1) y1(n+1)0001111000011110輸入x激勵(lì)函數(shù)D2 D11000010001001011100001000100101100001111Q Q(n+1)D010100011011現(xiàn)態(tài)y2 y1y2(n+1)y1

42、(n+1)/輸出Zx=0 x=10 00 11 11 010/000/001/100/101/000/110/111/11000000101y1xy211101010D22122Dxyyyx現(xiàn)態(tài) y2 y1次態(tài)y2(n+1) y1(n+1)0001111000011110輸入x激勵(lì)函數(shù)D2 D11 00 00 10 00 10 01 01 11 00 00 10 00 10 01 01 1000011110010000101y1xy211101100D11121DyxyyxZ=y2+xy10110000101y1xy211101011Z 確定輸出函數(shù)現(xiàn)態(tài)y2 y1y2(n+1)y1(n+1)/

43、輸出Zx=0 x=10 00 11 11 010/000/001/100/101/000/110/111/1例例4.11：若用J-K觸發(fā)器實(shí)現(xiàn)下表所示的二進(jìn)制狀態(tài)表， 試寫出激勵(lì)和輸出函數(shù)?，F(xiàn)態(tài) y2 y1次態(tài)y2(n+1)y1(n+1)/輸出Zx=0 x=10001111011/000/000/101/001/000/110/111/0解：解： 確定激勵(lì)函數(shù)現(xiàn)態(tài) y2 y1次態(tài)y2(n+1) y1(n+1)0001111000011110輸入x激勵(lì)函數(shù)J2K2J1K111000001010010111 d 1 d0 d d 1d 1 d 1d 1 1 d0 d 1 d0 d d 1d 0 d

44、 1d 0 1 d00001111現(xiàn)態(tài)y2 y1y2(n+1)y1(n+1)/輸出Zx=0 x=10 00 11 11 011/000/000/101/001/000/110/111/0Q Q(n+1)JK0d1dd1d000011011J1=112Jyx現(xiàn)態(tài) y2 y1次態(tài)y2(n+1) y1(n+1)0001111000011110輸入x激勵(lì)函數(shù)J2K2J1K111000001010010111 d 1 d0 d d 1d 1 d 1d 1 1 d0 d 1 d0 d d 1d 0 d 1d 0 1 d00001111xy21dd0000101y11110d0d0J2xy2d11d0001

45、01y111100d0dK2xy211dd000101y1111011ddJ1xy2dd11000101y11110dd11K1x2KK1=1Z=y2y1+xy10010000101y1xy211100011Z 確定輸出函數(shù)現(xiàn)態(tài)y2 y1y2(n+1)y1(n+1)/輸出Zx=0 x=10 00 11 11 011/000/000/101/001/000/110/111/0先畫出觸發(fā)器并給觸發(fā)器編號(hào)，再根據(jù)激勵(lì)函數(shù)和輸出函數(shù)畫出組合邏輯部分的電路，最后畫出同步時(shí)鐘信號(hào)線。1D1CD2Cy2CPx&y1z1y21&y1 11=Dy2122122+=+Dxyyyxyxyyx)+(=

46、+ =Z21121yxyyyxy例如：例如： 例例4.12：設(shè)計(jì)一個(gè)“ 111”序列檢測(cè)器，用來檢測(cè)串行二進(jìn)制序列，要求每當(dāng)連續(xù)輸入3個(gè)(或3個(gè)以上)1時(shí)，檢測(cè)器輸出為1，否則輸出為0。其典型輸入輸出序列如下：輸入x：0111011110輸出Z：0001000110解：解： 作狀態(tài)圖和狀態(tài)表0A0/00/00/00/0B1/0D1/11/1C1/0現(xiàn) 態(tài)次態(tài)/輸出Zx=0 x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/1 狀態(tài)化簡(jiǎn)用觀察法可得最大等效類為：(A), (B), (C,D)令C(C,D),可得下列最簡(jiǎn)狀態(tài)表現(xiàn) 態(tài)次態(tài)/輸出Zx=0 x=1ABCA/0A/0A/0B/0

47、C/0C/1現(xiàn) 態(tài)次態(tài)/輸出Zx=0 x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/1狀態(tài)分配： BC， AB，AC應(yīng)相鄰 AB，AC應(yīng)相鄰 AB應(yīng)相鄰 A應(yīng)為邏輯0ACB0101y1y2現(xiàn) 態(tài)次態(tài)/輸出Zx=0 x=1ABCA/0A/0A/0B/0C/0C/1現(xiàn)態(tài)y2 y1次態(tài)y2(n+1)y1(n+1)/輸出Zx=0 x=100011100/000/000/001/011/011/1現(xiàn) 態(tài)次態(tài)/輸出Zx=0 x=1ABCA/0A/0A/0B/0C/0C/1ACB0101y1y2現(xiàn)態(tài) y2 y1次 態(tài)y2(n+1y1(n+1)0001111000011110輸 入x激勵(lì)函數(shù)J2

48、 K2 J1 K1000000dd011111dd0d0d0dd1d1d1dddd0d1d1dd0d0d0dddd00001111輸 出Z000d001dQ Q(n+1)JK0d1dd1d000011011確定激勵(lì)函數(shù)和輸出函數(shù)表達(dá)式：選用JK觸發(fā)器xy20dd0000101y11110d0d1J2xy2dd1d000101y11110dd0dK2xy20ddd000101y11110d1ddJ1xy2dd11000101y11110dd00K1xy20d00000101y11110d010ZJ2=xy1, k2=xJ1=x, k1=xZ=xy2 現(xiàn)態(tài) y2 y1000111100001111

49、0 輸入x激勵(lì)函數(shù)J2 K2 J1 K10d0d0dd1d1d1dddd0d1d1dd0d0d0dddd00001111輸 出Z000d001d 畫電路圖K1CK2Cy2CPxy1zy2&y11&J1J2J2=xy1, k2=xJ1=x, k1=xZ=xy2 分析： 由于電路有冗余狀態(tài)“10”，一旦電路進(jìn)入“10”狀態(tài)，不管輸入為0還是1，經(jīng)過一個(gè)時(shí)鐘周期后，電路應(yīng)自動(dòng)進(jìn)入有效狀態(tài)，否則電路存在“掛起”現(xiàn)象。分析方法為： 確定無效狀態(tài)的次態(tài)，由于無效狀態(tài)的次態(tài)為d，所以在化簡(jiǎn)的卡諾圖中，被卡諾圈圈起的d為1，沒有被卡諾圈圈起的d為0。然后判斷無效狀態(tài)的次態(tài)是否為有效狀態(tài)或是否存在“掛起”現(xiàn)象。xy200d0000101y1111000d1J2xy2d11d000101y111100d0dK2xy200dd000101y1111011ddJ1xy2d111000101y111100d00K1xy20000000101y111101010Z現(xiàn)態(tài) y2 y1次 態(tài)y2(n+1y1(n+1)0001111000011110輸 入x激勵(lì)函數(shù)J2 K2 J1 K100000000011111110d