第四同步時序邏輯電路

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

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

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

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

5、態(tài)y時，輸出為z，若輸入為x，則在時鐘脈沖作用下，電路進入次態(tài)y(n+1)。某Moore 型電路狀態(tài)表現 態(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ā)器是一種存儲元件，在電路中用來記憶電路過去的輸入情況。一個觸發(fā)器具有兩種穩(wěn)定的狀態(tài),一個稱之為 0狀態(tài)，另一種稱之為1狀態(tài)。在任何時刻,觸發(fā)器只處于一個穩(wěn)定狀態(tài),當觸發(fā)脈沖作用時,觸發(fā)器可以從一種狀態(tài)翻轉到另一種狀態(tài)。在輸入信號取消后，能將獲得的新狀態(tài)保存下來。常用的觸發(fā)器有RS觸發(fā)器, D觸發(fā)器，J K觸發(fā)器和T

6、觸發(fā)器?；綬S觸發(fā)器可 由兩個與非門交叉耦合組成，其邏輯圖和邏輯符號如下：&G1RQG2SQ011100QRSQR：清零端 S：置1端 低電平有效基本RS觸發(fā)器的輸入與狀態(tài)（Q端）之間的邏輯關系可用觸發(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ā)器的一個重要特性：如果一端輸入持續(xù)為1的條件下，另一端連續(xù)出現多個置0或置1信號，只有第一個置0或置1信號起作用。利用這一特性可消除機械開關的觸點抖動。000 01 11 1001RSQ

7、0Q(n+1)dd0111基本RS觸發(fā)器的動作特點： 輸入信號在全部作用時間內都直接改變輸出端Q和 的狀態(tài)。Q在數字系統(tǒng)中，通常要求觸發(fā)器按一定的時間節(jié)拍動作，即讓輸入信號的作用受到時鐘脈沖的控制，為此出現了帶時鐘控制的R-S觸發(fā)器&G1RQG2SQ&CPG3G4QRSQCP110101100R：清零端 S：置1端 高電平有效當CP為0時，不論R，S為何值，觸發(fā)器的狀態(tài)保持不變；當CP為1（時鐘信號到來）時，觸發(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ā)器功能表現 態(tài)Q次 態(tài) Q(n+1)0 1010111dd00RS=001 11 0鐘控RS觸發(fā)器狀態(tài)表0100, 1000, 01RS0110鐘控RS觸發(fā)器狀態(tài)圖空翻空翻：時鐘信號作用期間，如果輸入信號發(fā)生變化，觸發(fā)器狀態(tài)會跟著變化，從而在一次時鐘信號作用期間，可能引起觸發(fā)器多次翻轉。鐘控RS觸發(fā)器的狀態(tài)方程為：Q(n+1)SRQRS = 0 (約束條件)100 01 11 1001RSQdQ(n+1)01100d鐘控R-S觸發(fā)器存在次態(tài)不能確定和空翻兩個問題。11如果使鐘控RS觸發(fā)器的R和S端始終處于互補狀態(tài), 則可消去次態(tài)不能確定的問題, 這就形成了所謂的D觸發(fā)器, 其邏輯圖的邏

9、輯符號如下:QQCD001110011101100&G1(R)QG2DQ&CPG3G4(S)當CP=0時，D觸發(fā)器的狀態(tài)不變；當CP=1時，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ā)器結構簡單, 但仍然存在空翻現象。實際使用的D觸發(fā)器是一種維持阻塞型D觸發(fā)器, 可以防止空翻的發(fā)生。置”1”維持線置”1”阻塞線置”0”阻塞線置”0”維持線&QSDQ&CPRDD&DCPSDRDQQ維持阻塞D觸發(fā)器:

10、CP上升沿將D可靠置入，無空翻現象。JK觸發(fā)器有兩個輸入端，即克服了RS觸發(fā)器的約束問題，使用上又比D觸發(fā)器靈活。其邏輯圖與邏輯符號如下：QQJKC0111Q1100Q1Q(n+1)=0QQ11111001100&G1KQG2JQ&CPG3G4Q(n+1)=1Q0R S當CP0時，JK觸發(fā)器的狀態(tài)保持不變；當CP1時， 若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ā)器翻轉；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翻轉JK觸發(fā)器的次態(tài)方程為：Q(n+1)JQKQ狀態(tài)圖為：0100, 01JK10, 1101, 1100, 10為防止空翻，實際數字電路中使用的JK觸發(fā)器是主從式集成JK觸發(fā)器，它使用前沿采樣，后沿定局的方式，無空翻，功能較全，使用靈活。000 01 11 1001JKQ1Q(n+1)010110主從JK觸發(fā)器:KJCP&QSDQ&RD&1（從）（主）CP前沿采樣，后沿定態(tài)；無空翻現象。JC

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

13、格法分析下圖所示的同步是序邏輯電路1K1J1CK2J2CY2Y1CP1X：寫出輸出函數和激勵函數表達式。J1=K1=1 J2=K2=x y1：列同狀態(tài)轉移真值表?，F 態(tài)y2 y1 激 勵 函 數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現 態(tài) y2 y1 x = 0 x = 10 11 01 10 01 10 00

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

15、用代數法分析下圖所示的同步時序邏輯電路。1D1CD2Cy2CPx&y1z寫出輸出函數和激勵函數表達式。Z=x y2 y1D2 = x + y2 + y1 = x y2 y1D1 = x把激勵函數表達式代入觸發(fā)器的次態(tài)方程，得到電路的次態(tài)方程組。Q1(n+1)D1 xQ2(n+1)D2 x y2 y1根據次態(tài)方程組和輸出函數表達式作出狀態(tài)表和狀態(tài)圖。次態(tài)/輸出( y2 (n+1) y1 (n+1)/Z)0 00 11 11 0現 態(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：作出時間圖，并說明電路的邏輯功能。典型輸入序列：x = 01011101初態(tài)： y2 y1= 00狀態(tài)響應序列和輸出響應序列為： CP: 12345678 x: 01011101 y2: 00010001 y1: 00101110y2(n+1): 00100010 y1(n+1): 01011101 Z: 00010001CPxy2y1Z12346785功能說明：功能說明：該電路是一個101序列檢測器。同步時序邏輯電路設計又稱同步時序邏輯電路綜合，其基本指導思想是用盡可能少的觸發(fā)器和門電路來完成設計。同步時序電路設計的一般步驟為：同步時序電路設計的一般步驟為：1. 根據邏輯要求

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

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

19、串行輸入的8421BCD碼，其輸入的順序是先高位后低位，當出現非法數字(即輸入1010，1011，1100，1101，1110，1111)時，電路的輸出為1。試作出該時序電路的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)圖現態(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：假設有一個三位二進制加、減法器（模8計數器），當X輸入為1時，實現加1計數；當X為0時，實現減1計數，試作出該電路的Moore型原始狀態(tài)圖和狀態(tài)表。解：解：000111110101100011010001000001010011100101110111當X為0時：當X為1時：計數器的輸出可為狀態(tài)本身，亦可看作外部輸出。1 000110001101010111100011111111100000000原始狀態(tài)圖原

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

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

23、判別方法：第一、它們的輸出完全相同； 假定狀態(tài)S1和S2是完全確定原始狀態(tài)表中的兩個現態(tài)，那么S1和S2等效的條件可歸納為在輸入的各種取值組合下：(1) 次態(tài)相同； 第二、它們的次態(tài)滿足下列條件之一，即(2) 次態(tài)交錯；(3) 次態(tài)循環(huán)；(4) 次態(tài)對等效。 SiSj1/0Sl0/10/1Sk1/0次態(tài)相同次態(tài)相同或交錯 SiSj0/01/01/0Sk0/0次態(tài)交錯或相同或循環(huán) SiSj1/01/0SkSl0/00/00/10/1Sm1/01/0次態(tài)交錯或等效(Sk,Sl等效) SiSj1/01/0SlSk0/10/11. 觀察法化簡觀察法化簡例例4.6：簡化下表所示的狀態(tài)表現態(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時的次態(tài)不滿足四條件之一，因此A和B不等效;現態(tài)次態(tài)/輸出x=0 x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/1最小化狀態(tài)表為：現態(tài)次態(tài)/輸出x=0 x=1ABCA/0A/0A/0B/0C/0C/1現態(tài)次態(tài)/輸出x=0 x=1ABCDA/0A/0A/0A/0B/0C/0D/1D/12. 隱含表法化簡隱含表法化簡例例4.7：化簡下表所示的狀態(tài)表現態(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)對狀態(tài)對 狀態(tài)對等效，打狀態(tài)對等效，打“ “ ”； 狀態(tài)對不等效，打狀態(tài)對不等效，打 “ ”“ ”； 狀態(tài)對是否等效需進狀態(tài)對是否等效需進一步檢查，則標記次態(tài)一步檢查，則標記次態(tài)對。對。ABCDEFGFEDCBCFBEAECFCDDE現態(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)鏈中的每一個狀態(tài)對都是等效狀態(tài)對,一共四個等效對 (A,B), (A,E), (B,E), (C,F)。 關聯比較，確定等效狀態(tài)對AEBECFABCF現態(tài)次態(tài)/輸出x=0 x=1abcdb/0c/0c/1b/1a/1d/0a/0c/0確定最大等效類，作最小化狀態(tài)表確定最大等效類，作最小化狀態(tài)表: 四個等效對 (A,B), (A,E), (B,E), (C,F) 四個最大等效類 (A,B,E), (C,F), (D), (G) 令以上四個最大等效類依次為a, b, c, d.現態(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)簡化。 相容狀態(tài)：設狀態(tài)S1和S2是不完全確定狀態(tài)表中的兩個狀態(tài)，如果對于所有的有效輸入序列，分別從狀態(tài)S1和S2出發(fā)，所得到的輸出響應序列(除不確定的那些位之外)是完全相同的，那么狀態(tài)S1和S2是相容的，或者說狀態(tài)S1和S2是相容對，記作(S1,S2)。相容狀態(tài)可以合并。例: 設計一個“1111”序列檢測器，使其成為爆炸裝置的引爆控制器。假定工作條件為：平時無1輸入，Z一直處于0狀態(tài)；當連續(xù)輸入4個1時（不允許出現0），Z=1引爆，整個裝置不存在。 ADBC1/01/01/00/

28、00/d0/d0/d1/1dddd現態(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)表中判斷兩個狀態(tài)是否相容也是根據表中給出的次態(tài)和輸出來決定的。假定狀態(tài)Si和Sj是不完全確定狀態(tài)表中的兩個現態(tài)，那么狀態(tài)Si和Sj相容的條件可歸納為在輸入的各種取值組合下:第一、它們的輸出完全相同，或者其中的一個(或兩個) 輸出為任意值。第二、它們

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

30、BDDE BEBFCD 全部相容對：(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)對：(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)表(又稱最小閉覆蓋) 應滿足下列三個條件： 覆蓋性所選相容類集合應包含原始狀態(tài)表中的全部狀態(tài)。 最小性所選相容類集合中相容類的個數應最少。 閉合性所選相容類集合中的任一相容類的所有隱含條件（在原始狀態(tài)表中任一輸入條件下產生的次態(tài)）都必須屬于該集合中某一個（最好是一個不是兩個）相容類采用閉覆蓋表來反映所選相容類集合的覆蓋和閉合情況。本例的閉覆蓋表為CDE最大相 容類ABFBCDEFA B C D EF 覆蓋閉合x=0 x=1BABFCD現態(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 A表示表示(A,B,F)A,B,F)，C C表示表示( (B,C,D,E,F)B,C,D,E,F)可得：可得：現 態(tài)次 態(tài)x=0 x=1ACA,CACC輸 出01現 態(tài)次 態(tài)x=0 x=1ACdACC輸 出01由于該表中只有兩個狀態(tài)，進一步可以得到：由于該表中只有兩個狀態(tài)，進一步可以得到：現態(tài)次態(tài)x=0 x=1ABCDEFBBAdFdDDEEdC輸出0d111dCDE最大相 容類ABFBCDEFABCDEF 覆蓋閉合x=0 x=1BABFCD例：例：化簡下表所示的狀態(tài)表現態(tài)次態(tài)/輸出x=0 x=1ABCDED

33、/dE/0D/0C/dC/1A/dA/dB/dC/dB/d解解： 作隱含表，尋找相容狀態(tài)對ABCDEDCBABDEACCECDACABCDABDEBCBC由上圖得相容狀態(tài)對為(A,B), (A,C), (A,D), (A,E), (B,C), (C,D), (D,E)ABDEBC ACAB BDAC CE AEABCDADBC CDAC現態(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現態(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現態(tài)次態(tài)/輸出x=0 x=1ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d令A=(A,B,C), B=(D,E), 進一步可得：現態(tài)次態(tài)/輸出x

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

36、!2AKNnnNns例如例如，n=2, N=4時 有方案狀態(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種方案中只有三種是獨立的(真正不相同的)方案!)!2()!12(=KnNnnu然而，當n較大時，Ku仍然很大，要真正找到最佳的分配方案是十分困難的，況且分配方案的好壞還與所采用的觸發(fā)器的類型有關。因此，實際應用時都是采用工程的方法，依據以下四條件原則來進行狀態(tài)分配。狀態(tài)分配的基本原則有四條：狀態(tài)分配的基本原則有四條：(1) 在相同輸入條件下具有相同次態(tài)的現態(tài)，應盡可能給這些現態(tài)分配相鄰的二進制代碼；(2) 同一現態(tài)在不同輸入條件下的次態(tài)

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

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

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

41、函數確定激勵函數兩種方法兩種方法：根據次態(tài)方程來確定和通過激勵表來確定。常采用后一種方法。例例4.10：若用D觸發(fā)器實現下表所示的二進制狀態(tài)表， 試寫出激勵和輸出函數?，F態(tài) y2 y1次態(tài)y2(n+1)y1(n+1)/輸出Zx=0 x=10001111010/000/001/100/101/000/110/111/1解：解： 確定激勵函數現態(tài) y2 y1次態(tài)y2(n+1) y1(n+1)0001111000011110輸入x激勵函數D2 D11000010001001011100001000100101100001111Q Q(n+1)D010100011011現態(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現態(tài) y2 y1次態(tài)y2(n+1) y1(n+1)0001111000011110輸入x激勵函數D2 D11 00 00 10 00 10 01 01 11 00 00 10 00 10 01 01 1000011110010000101y1xy211101100D11121DyxyyxZ=y2+xy10110000101y1xy211101011Z 確定輸出函數現態(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ā)器實現下表所示的二進制狀態(tài)表， 試寫出激勵和輸出函數?，F態(tài) y2 y1次態(tài)y2(n+1)y1(n+1)/輸出Zx=0 x=10001111011/000/000/101/001/000/110/111/0解：解： 確定激勵函數現態(tài) y2 y1次態(tài)y2(n+1) y1(n+1)0001111000011110輸入x激勵函數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現態(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現態(tài) y2 y1次態(tài)y2(n+1) y1(n+1)0001111000011110輸入x激勵函數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 確定輸出函數現態(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ā)器編號，再根據激勵函數和輸出函數畫出組合邏輯部分的電路，最后畫出同步時鐘信號線。1D1CD2Cy2CPx&y1z1y21&y1 11=Dy2122122+=+Dxyyyxyxyyx)+(=

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

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

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

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