第五章-同步時序邏輯電路的分析與設(shè)計

第5章同步時序電路

—分析和設(shè)計5.1概述5.2時序邏輯電路的分析方法5.3同步時序邏輯電路的設(shè)計1、定義在數(shù)字電路中，凡是任一時刻的穩(wěn)定輸出不僅決定于該時刻的輸入，而且還和電路原來的狀態(tài)有關(guān)，這樣的電路為時序邏輯電路，簡稱時序電路。5.1概述一、時序邏輯電路的基本概念

xi(i＝1…n)：外部向電路輸入的時序信號，稱為輸入變量。Zi(i＝1…m)：電路產(chǎn)生的輸出時序信號，稱為輸出函數(shù)。yi(i＝1…l)：由電路過去輸入確定的狀態(tài)，稱為狀態(tài)變量。Yi(i＝l…p)：確定電路下一時刻狀態(tài)(次態(tài))函數(shù)，稱為激勵函數(shù)。CP：時鐘脈沖信號，用來確定電路狀態(tài)轉(zhuǎn)換時刻。2、電路的一般結(jié)構(gòu)組合邏輯電路存儲功能............XyZY一、時序邏輯電路的基本概念

3、時序電路的特點：（1）具有記憶功能。（2）時序電路一般由三部分組成:組合邏輯電路：由邏輯門構(gòu)成；存儲器件：由觸發(fā)器組成；反饋線：連接組合邏輯電路與存儲器件的導(dǎo)線；一、時序邏輯電路的基本概念

組合邏輯電路存儲功能............XyZY4、狀態(tài)的概念（1）外部狀態(tài)：時序電路輸出Z的組合；（2）內(nèi)部狀態(tài)：時序電路的內(nèi)部輸入（存儲器的輸出）y的組合；所謂電路輸出與過去的輸入相關(guān)，是通過與電路現(xiàn)有狀態(tài)相關(guān)體現(xiàn)的。就某一時刻而言，通常將該時刻電路的狀態(tài)稱為現(xiàn)態(tài)，記作yn；而將下一時刻電路的狀態(tài)稱為次態(tài)，記作yn+1。一、時序邏輯電路的基本概念

組合邏輯電路存儲功能............XyZY1、按其狀態(tài)改變方式可分為兩種類型。

同步時序邏輯電路：電路中的存儲器件為時鐘控制觸發(fā)器，各觸發(fā)器共用同一時鐘信號，即電路中各觸發(fā)器狀態(tài)的轉(zhuǎn)移時刻，在統(tǒng)一時鐘信號控制下同步發(fā)生。異步時序邏輯電路：電路中的存儲器件可以是時鐘控制觸發(fā)器、非時鐘控制觸發(fā)器或延時元件。電路沒有統(tǒng)一的時鐘信號對狀態(tài)變化進(jìn)行同步控制，輸入信號的變化將直接引起電路狀態(tài)的變化。二、時序邏輯電路的分類2、按輸入信號形式的不同分為：脈沖型：輸入信號是脈沖的有無（信號的持續(xù)時間要受到限制）。電平型：輸入是電平的高低（指信號可以不受限制地保持在某一狀態(tài)）。脈沖型信號電平型信號二、時序邏輯電路的分類3、按照電路輸出與輸人、狀態(tài)的關(guān)系，時序邏輯電路有兩種結(jié)構(gòu)模型。米利（Mealy）型：電路輸出是電路輸入和狀態(tài)變量的函數(shù)。其關(guān)系為

Zi=fi(x1,x2,…,xn,y1,y2,…,yn)

莫爾（Moore）型：電路輸出是電路狀態(tài)變量的函數(shù)。其關(guān)系為

Zi=fi(y1,y2,…,yn)二、時序邏輯電路的分類10T110T2=1xCPZ=y1y210T210T1=1xCPy2y1Mealy型同步時序電路Moore型同步時序電路二、時序邏輯電路的分類組合邏輯電路存儲功能............XyZY三、同步時序邏輯電路的描述1、邏輯方程式——任何一個同步時序邏輯電路的結(jié)構(gòu)和功能可用三組函數(shù)表達(dá)式描述。1)輸出函數(shù)表達(dá)式：Zi=fi(x1,x2,…,xn,y1,y2,…,ym)Mealy型Zi=fi(y1,y2,…,ym)

Moore型2)激勵函數(shù)表達(dá)式（驅(qū)動方程）：Yl=fl（xi，yi）3)次態(tài)函數(shù)表達(dá)式（狀態(tài)方程，特性方程）三、同步時序邏輯電路的描述2、狀態(tài)表：是一種反映同步時序邏輯電路的輸出、次態(tài)與輸入、現(xiàn)態(tài)之間關(guān)系的表格。它能夠完全描述同步時序電路在輸入時序信號作用下的狀態(tài)轉(zhuǎn)移關(guān)系及相應(yīng)的輸出響應(yīng)。yYn+1/Zx=0x=1ABCDD/0B/1B/1A/0C/1A/0D/0B/1yYn+1Zx=0x=1WXYYXXXYW010三、同步時序邏輯電路的描述3、狀態(tài)圖—用圖形的形式反映外輸入、電路的狀態(tài)、狀態(tài)轉(zhuǎn)移的條件和方向。

每個狀態(tài)用一個圓圈來代表，圈內(nèi)注明狀態(tài)的名稱，圈外用矢量表示狀態(tài)的轉(zhuǎn)換方向，在矢量旁注明外輸入的條件和輸出。1/0BDCA0/10/00/01/10/01/01/11y/0w/0x/101010三、同步時序邏輯電路的描述3、狀態(tài)圖——用圖形的形式反映外輸入、電路的狀態(tài)、狀態(tài)轉(zhuǎn)移的條件和方向。yYn+1/Zx=0x=1ABCB/1B/0A/0C/0A/1C/00/1CAB0/01/11/01/00/0狀態(tài)表和狀態(tài)圖之間可以相互轉(zhuǎn)換

X/Z三、同步時序邏輯電路的描述4、時間圖—用信號隨時間變化的規(guī)律來描述各關(guān)鍵點的信號變化情況的圖形。即在時鐘和輸入信號的作用下，描述電路狀態(tài)、輸出狀態(tài)隨時間變化的波形圖。四、完全定義機(jī)和不完全定義機(jī)在時序電路中，如果一個時序機(jī)的狀態(tài)表中所有的次態(tài)、輸出都是確定的，則此時序機(jī)稱為完全定義機(jī)；否則，稱為不完全定義機(jī)。五、有限狀態(tài)機(jī)和無限狀態(tài)機(jī)在時序電路中，如果一個時序機(jī)的狀態(tài)是有限的，稱為有限狀態(tài)機(jī)。否則，為無限狀態(tài)機(jī)。5.2時序邏輯電路的分析一、同步時序電路的一般分析方法

給定的同步時序電路分析電路的組成列出電路的輸出方程列出電路的驅(qū)動方程狀態(tài)轉(zhuǎn)換表、狀態(tài)轉(zhuǎn)換圖求出電路的狀態(tài)方程說明電路的邏輯功能通過觸發(fā)器的特性方程Qn+1=S+RQQn+1=DQn+1=JQ+KQQn+1=T⊕Q例1：分析圖示電路的邏輯功能JCPKJKQQF1F0XZ&&1、電路分析2、輸出方程：Z=XQ0Q1

驅(qū)動方程：J0=K0=X，

J1=K1=XQ03、狀態(tài)方程：4、轉(zhuǎn)換表、轉(zhuǎn)換圖XQ1Q0Q1n+1Q0n+1Z111100000001101100011011010100110001000010100110例1：分析圖示電路的邏輯功能JCPKJKQQF1F0XZ&&5、邏輯功能分析：此電路為一個受X控制的兩位二進(jìn)制計數(shù)器，當(dāng)X=1時，計數(shù)器工作；當(dāng)X=0時，計數(shù)器不工作。4、轉(zhuǎn)換表、轉(zhuǎn)換圖XQ1Q0Q1n+1Q0n+1Z111100000001101100011011010100110001000010100110Q1Q0,X/Z0/0001110011/00/01/10/01/01/00/0JCPKJKQQF1F0XZ&&5、邏輯功能分析：此電路為一個受X控制的兩位二進(jìn)制計數(shù)器，當(dāng)X=1時，計數(shù)器工作；當(dāng)X=0時，計數(shù)器不工作。4、轉(zhuǎn)換表、轉(zhuǎn)換圖XQ1Q0Q1n+1Q0n+1Z1111000000011011000110110101001100010000101001100001101001注意：（1）組成該電路的狀態(tài)是各個觸發(fā)器的組合；（2）不能漏掉任何可能的輸入和現(xiàn)態(tài)的取值組合；（3）輸入和現(xiàn)態(tài)的起始值如果給定了，則可以從給定的值依次計算，如果未給定，則可以自己設(shè)定起始值。畫狀態(tài)轉(zhuǎn)換圖：（1）狀態(tài)轉(zhuǎn)換是現(xiàn)態(tài)到次態(tài)；（2）輸出是現(xiàn)態(tài)的函數(shù)，不是次態(tài)的函數(shù)；（3）只有當(dāng)時鐘脈沖的觸發(fā)沿到來時，相應(yīng)觸發(fā)器才會更新狀態(tài)。例2：分析圖示電路，觸發(fā)器的初始狀態(tài)Q0Q1Q2=001

1、電路分析2、

驅(qū)動方程：D0=Q2

D1=Q0D2=Q1

3、狀態(tài)方程：4、轉(zhuǎn)換表、轉(zhuǎn)換圖Q0Q1Q2Q0n+1Q1n+1Q2n+1001100010001100010001100DCPQDQF2F0DQF14、轉(zhuǎn)換表、轉(zhuǎn)換圖Q0Q1Q2Q0n+1Q1n+1Q2n+1001100010001100010001100DCPQDQF2F0DQF1001100010狀態(tài)圖功能說明：此電路三個觸發(fā)器的Q0Q1Q2的組態(tài)為001、100、010三種，在CP的作用下，循環(huán)變化。例2：分析圖示電路，觸發(fā)器的初始狀態(tài)Q0Q1Q2=001

例3：分析圖示電路1、電路分析2、輸出方程和驅(qū)動方程：

Z=XQ2

4、轉(zhuǎn)換表、轉(zhuǎn)換圖XQ2Q1Q2n+1Q1n+1Z000001010011100101110111000000000000010100101101CPJKQF2JKQF1XZ&&&J1=XQ2J2=XQ1

K1=1K2=X3、狀態(tài)方程4、轉(zhuǎn)換表、轉(zhuǎn)換圖例3：分析圖示電路狀態(tài)圖功能說明：電路連續(xù)輸入三個以上的1后輸出為1，否則輸出為0；故該電路是一個“111”序列檢測器。XQ2Q1Q2n+1Q1n+1Z000001010011100101110111000000000000010100101101000110110/01/11/11/01/00/00/00/0例4：分析圖示電路1、電路分析2、輸出方程和驅(qū)動方程：4、轉(zhuǎn)換表、轉(zhuǎn)換圖XQ2Q1Q2n+1Q1n+1Z0000010100111001011101110001000000000100100110103、狀態(tài)方程XCPDQF1ZDQF2≥1&QQ例4：分析圖示電路XQ2Q1Q2n+1Q1n+1Z000001010011100101110111000100000000010010011010XCPDQF1ZDQF2≥1&QQ000110111/01/10/00/01/01/00/00/0X/Z該電路為“101”序列檢測器4、轉(zhuǎn)換表、轉(zhuǎn)換圖例5：分析圖示電路QX1X2Qn+1Z0000010100111001011101110001011001101011JCPKZX1X2Q≥1=1=1&1、電路分析2、輸出方程和驅(qū)動方程：3、狀態(tài)方程4、轉(zhuǎn)換表、轉(zhuǎn)換圖例5：分析圖示電路QX1X2Qn+1Z0000010100111001011101110001011001101011JCPKZX1X2Q≥1=1=1&3、狀態(tài)方程0111/000/001/110/111/110/001/000/1例5：分析圖示電路JCPKZX1X2Q≥1=1=1&0111/000/001/110/111/110/001/000/1該電路為一個串行加法器，X1為被加數(shù)，X2為加數(shù)；按先低位后高位的順序串行地加到相應(yīng)的輸入端，每位相加產(chǎn)生的進(jìn)位由觸發(fā)器保存下來參與下一位相加，輸出Z為和數(shù)，也是從低位到高位串行地輸出。11011001+舉例：A=1101,B=1001，計算A+B。0110100115.3同步時序邏輯電路的設(shè)計一、同步時序電路的一般步驟

1、根據(jù)邏輯設(shè)計要求，作出狀態(tài)圖和狀態(tài)表（確定輸入變量和輸出變量）。2、狀態(tài)簡化。即消除冗余狀態(tài)，求得最小化狀態(tài)表。3、狀態(tài)編碼。即對每一個狀態(tài)指定一個二進(jìn)制代碼，這一步得到一個二進(jìn)制狀態(tài)表。4、選定觸發(fā)器，并寫出各觸發(fā)器的激勵函數(shù)和輸出函數(shù)的表達(dá)式。5、畫出邏輯電路圖。二、建立原始狀態(tài)圖（或原始狀態(tài)表）1、方法（1）直接構(gòu)圖法。（2）信號序列法。（3）正則表達(dá)式法。（4）SM（時序機(jī)流程圖）法2、建立過程（直接構(gòu)圖法）（1）分析命題、確定電路類型。確定電路的輸入個數(shù)和輸出個數(shù)，并用字母表示之。（2）建立樹型結(jié)構(gòu)的狀態(tài)圖——確定狀態(tài)見的轉(zhuǎn)移關(guān)系和輸出。（3）將原始狀態(tài)圖轉(zhuǎn)換為原始狀態(tài)表。二、建立原始狀態(tài)圖（或原始狀態(tài)表）3、基本思想 根據(jù)文字描述的設(shè)計要求，先假定一個初態(tài)；從這個初態(tài)開始，根據(jù)輸入條件確定輸出和下一個狀態(tài)。

每加入一個輸入，就可確定一個次態(tài)；該次態(tài)可能就是現(xiàn)態(tài)本身，也可能是已有的另一個狀態(tài)或是新增加的一個狀態(tài)。這個過程一直繼續(xù)下去，直至每一個現(xiàn)態(tài)向其次態(tài)的轉(zhuǎn)移都已被考慮，并且不再構(gòu)成新的狀態(tài)。

如果有n個輸入變量，則從每一個狀態(tài)出發(fā)，將2n種不同的轉(zhuǎn)移條件都考慮到。4、確定狀態(tài)的原則：寧多勿漏。二、建立原始狀態(tài)圖（或原始狀態(tài)表）例1：某序列檢測器，有一個輸入端X和一個輸出端Z。從X端輸入一組按時間順序排列的串行二進(jìn)制代碼，當(dāng)輸入序列中出現(xiàn)101時，輸出Z=1，否則Z=0，作出該檢測器的Mealy型和Moore型狀態(tài)圖和狀態(tài)表。序列檢測器XCPZMealy型：S0S2S3S11/00/01/01/10/00/00/01/0S0/0S2/0S0/0S2/0S1/0S1/0S3/1S1/0現(xiàn)態(tài)次態(tài)/輸出X=0X=1S0S1S2S3二、建立原始狀態(tài)圖（或原始狀態(tài)表）序列檢測器XCPZMoore型S0S2S0S2S1S1S3S1現(xiàn)態(tài)次態(tài)輸出X=0X=1S0S1S2S3S0/0S2/0S3/1S1/0101100010001二、建立原始狀態(tài)圖（或原始狀態(tài)表）例2：作出8421BCD碼的錯誤碼檢測器的狀態(tài)表和狀態(tài)圖。8421BCD碼的高位在前，低位在后，串行地加在檢測器的輸入端，若收到非法代碼（1010,1011,1100，1101,1110,1111）時，電路的輸出為1，否則，輸出為0。

不論輸入的代碼是否正確，電路接收到最低位以后均復(fù)位，并開始接收下一個代碼。ADCBEJKFGHILMNP1/00/01/00/01/00/00/00/01/01/00/01/00/00/01/00/01/00/01/00/01/00/11/10/11/10/01/00/11/11/0二、建立原始狀態(tài)圖（或原始狀態(tài)表）ADCBEJKFGHILMNP1/00/01/00/01/00/00/00/01/01/00/01/00/00/01/00/01/00/01/00/01/00/11/10/11/10/01/00/11/11/0現(xiàn)態(tài)次態(tài)輸出X=0X=1ABCDEFGHIJKLMNPB/0D/0J/0F/0H/0A/0A/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)表）例3：某一起爆電路，其輸入為X，輸出為Z，若電路的X端連續(xù)收到四個1信號，則輸出Z=1，使炸藥引爆，試作出起爆電路的狀態(tài)圖和狀態(tài)表。（電路一經(jīng)啟動，則不能停下來。）S0S2S3S10/00/d1/01/1dddd1/01/00/d0/d現(xiàn)態(tài)次態(tài)/輸出X=0X=1S0S1S2S3S0/0d/dd/dd/dS1/0S2/0S3/0d/1二、建立原始狀態(tài)圖（或原始狀態(tài)表）例4：有兩個輸入x1x2，一個輸出z。只有當(dāng)x1輸入三個“1”（或三個以上的1）然后x2輸入一個“1”時，線路才有輸出，即z=1，在同一時間內(nèi)，兩個輸入不能同時為1。ADCB00/001/010/001/000/010/010/000/010/001/000/001/1

說明：這三個“1”并沒有要求連續(xù)輸入，只要中間沒有x2插入即可。而一旦z=1時，線路就要回到原始狀態(tài)。

在其他情況下，不管電路處于哪個狀態(tài)，只要x2輸入為1，電路的輸出z均為0，并返回到初始狀態(tài)。二、建立原始狀態(tài)圖（或原始狀態(tài)表）ADCB00/001/010/001/000/010/010/000/010/001/000/001/1現(xiàn)態(tài)次態(tài)/輸出X1X2=00011110ABCDA/0B/0C/0D/0A/0A/0A/0A/1d/dd/dd/dd/dB/0C/0D/0D/0二、建立原始狀態(tài)圖（或原始狀態(tài)表）例5：給出同步二進(jìn)制串行加法器的狀態(tài)表串行加法器被加數(shù)X1CPZ（和）加數(shù)X2

串行加法器僅需設(shè)置兩個內(nèi)部狀態(tài)，以分別表示有進(jìn)位和無進(jìn)位。a—無進(jìn)位，b—有進(jìn)位11/000/001/110/111/110/001/000/101二、建立原始狀態(tài)圖（或原始狀態(tài)表）現(xiàn)態(tài)次態(tài)/輸出X1X2=00011110aba/0a/1a/1b/0a/1b/0b/0b/111/000/001/110/111/110/001/000/101例5：給出同步二進(jìn)制串行加法器的狀態(tài)表串行加法器被加數(shù)X1CPZ（和）加數(shù)X2三、狀態(tài)表的化簡設(shè)置狀態(tài)的目的是利用這些狀態(tài)記住電路的歷史狀態(tài)，以根據(jù)其后的輸入產(chǎn)生相應(yīng)的輸出。如果所設(shè)置的某兩個狀態(tài)對其后輸入的所有序列產(chǎn)生的輸出序列完全相同，則這兩個狀態(tài)可以合并為一個狀態(tài)。狀態(tài)表的每一行指明了在某一輸入條件下某個狀態(tài)的次態(tài)和電路的輸出。當(dāng)兩行（或多行）所記載的內(nèi)容完全一樣時，說明這兩行所代表的狀態(tài)是相同的。將這兩行合并為一行，不會影響整個電路的邏輯功能。三、狀態(tài)表的化簡1、狀態(tài)表化簡的基本原理如果所設(shè)置的兩個狀態(tài)，對輸入的所有序列產(chǎn)生的輸出序列完全相同，則這兩個狀態(tài)可以合并為一個狀態(tài)。輸出：Z(C，0)=Z(D，0)=0Z(C，1)=Z(D，1)=1次態(tài)：N(C，0)=N(D，0)=AN(C，1)=N(D，1)=D∴C=D這意味著從現(xiàn)態(tài)C或D開始，對于其后的所有輸入序列所產(chǎn)生的輸出序列一定都相同，故C，D可以合并為一個狀態(tài)?，F(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDA/0A/0A/0A/0B/0C/0D/1D/1三、狀態(tài)表的化簡考察表2中的狀態(tài)B和C輸出：Z(B，0)=Z(C，0)=1Z(B，1)=Z(C，1)=0次態(tài)：N(B，0)=C，N(C，0)=BN(B，1)=N(C，1)=E ∴B=C

同理：D=E即若在相同的輸入下，輸出相同，而次態(tài)交錯，這兩個狀態(tài)可以合并為一個狀態(tài)?，F(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDEC/1C/1B/1D/1E/1B/0E/0E/0B/1B/11、狀態(tài)表化簡的基本原理三、狀態(tài)表的化簡考察表3中的狀態(tài)C和F輸出：Z(C，0)=Z(F，0)=0Z(B，1)=Z(C，1)=1次態(tài)：N(B，0)=N(C，0)=CN(B，1)=A，N(C，1)=D

決定C和F是否可以合并的條件是A和D是否相同，若A和D相同，則C和F相同?，F(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDEFE/0A/1C/0B/0D/1C/0D/0F/0A/1A/0C/0D/11、狀態(tài)表化簡的基本原理三、狀態(tài)表的化簡狀態(tài)A和D輸出：Z(A，0)=Z(D，0)=0Z(A，1)=Z(D，1)=0次態(tài)：N(A，0)=E，N(C，0)=BN(A，1)=D，N(D，1)=A

次態(tài)交錯?？梢姡簺Q定A和D是否可以合并的條件是E和B是否相同，若相同，則A和D相同。現(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDEFE/0A/1C/0B/0D/1C/0D/0F/0A/1A/0C/0D/11、狀態(tài)表化簡的基本原理三、狀態(tài)表的化簡狀態(tài)E和B輸出：Z(E，0)=Z(B，0)=1Z(E，1)=Z(B，1)=0次態(tài)：N(E，0)=D，N(B，0)=AN(E，1)=C，N(B，1)=F可見：決定E和B是否可以合并的條件是A和D及C和F是否相同?，F(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDEFE/0A/1C/0B/0D/1C/0D/0F/0A/1A/0C/0D/1BE→AD→CF1、狀態(tài)表化簡的基本原理三、狀態(tài)表的化簡由于這個循環(huán)中的各個狀態(tài)對在不同的現(xiàn)輸入下，所產(chǎn)生的輸出是分別相同的，因而從循環(huán)中的某一狀態(tài)對出發(fā)，都能夠保證在所有的輸入序列下所產(chǎn)生的輸出序列相同，因而，循環(huán)中的各對狀態(tài)是可以合并的。∴B=E，A=D，C=F現(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDEFE/0A/1C/0B/0D/1C/0D/0F/0A/1A/0C/0D/1例如：設(shè)輸入序列為：X=010011001

從C態(tài)出發(fā)的輸出Z為：010100010

從F態(tài)出發(fā)的輸出Z為：010100010即在相同的輸入序列下，輸出相同，故C和F可以合并。1、狀態(tài)表化簡的基本原理三、狀態(tài)表的化簡狀態(tài)表中兩個狀態(tài)可以合并的條件：在所有可能的輸入條件下：（1）它們的輸出相同；（2）它們的次態(tài)滿足下列條件之一： 次態(tài)相同；次態(tài)交錯；指S1的次態(tài)是S2；S2的次態(tài)是S1。次態(tài)循環(huán)；1、狀態(tài)表化簡的基本原理三、狀態(tài)表的化簡（1）最小化狀態(tài)表的特性

◆最小化狀態(tài)表必須覆蓋原始狀態(tài)表—覆蓋性。即原始狀態(tài)表中的任何一個狀態(tài)，至少應(yīng)包含在最小化狀態(tài)表中的一個狀態(tài)中。

◆從最小化狀態(tài)表中的任何一個原始狀態(tài)出發(fā)，在輸入信號的各種可能的取值下，所對應(yīng)的下一狀態(tài)仍然屬于最小化狀態(tài)表中的某一個狀態(tài)——封閉性

◆狀態(tài)表中狀態(tài)的個數(shù)應(yīng)為最少。2、完全定義機(jī)狀態(tài)表的化簡：三、狀態(tài)表的化簡（2）等價的概念：如果所設(shè)置的某兩個狀態(tài)qa，qb對其后輸入的所有序列產(chǎn)生的輸出序列完全相同，則這兩個狀態(tài)稱為等價狀態(tài)。記為{qa，qb}。等價的傳遞性：若q1和q2等價，q2和q3等價，則q1和q3也等價。等價類：等價狀態(tài)的集合。在此集合中，任何兩個狀態(tài)都是相互等價的。最大等價類：若一個等價類不是任何別的等價類的子集，則此等價類稱為最大等價類。2、完全定義機(jī)狀態(tài)表的化簡：三、狀態(tài)表的化簡（3）化簡的步驟：

◆尋找等價狀態(tài)對——檢查所有狀態(tài)之間的等價關(guān)系；

◆形成最大等價類——對全部狀態(tài)進(jìn)行分類、合并，建立最小化狀態(tài)表。（4）化簡的方法

◆觀察法——觀察輸出部分和次態(tài)

2、完全定義機(jī)狀態(tài)表的化簡：2、完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDEC/1C/1B/1D/0D/0B/0E/0E/0B/1B/1（B，C）（D，E）現(xiàn)態(tài)次態(tài)/輸出X=0X=1A'B'C'B'/1B'/1C'/0B'/0C'/0B'/12、完全定義機(jī)狀態(tài)表的化簡：◆隱含表法隱含表是直角三角形網(wǎng)絡(luò)，橫向和縱向格數(shù)相同，每個方格代表一個狀態(tài)對①畫隱含表——缺頭少尾②順序比較③關(guān)聯(lián)比較④列最大等價類⑤最小化狀態(tài)表2、完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)/輸出X1X2=00011110ABCDEFGHD/0C/1C/1D/0C/1D/0G/0B/1D/0D/0D/0B/0F/0D/0G/0D/0F/0E/1E/1A/0E/1A/0A/0E/1A/0F/0A/0F/0A/0F/0A/0A/0BCDEFGHABCDEFG××AF/BD×√GD/AF×AF×DF/AF××BC/AF×DF××BC×DBBG/AF×DG/AF×BC/DFDG/AF××①畫隱含表——缺頭少尾②順序比較③關(guān)聯(lián)比較④列最大等價類⑤最小化狀態(tài)表√√√列最大等價類：（A，F(xiàn)）（B，C）（B，H）（C，H）（A，F(xiàn)）（B，C，H）（D）（E）（G）

A’B’C’D’E’2、完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)/輸出X1X2=00011110A’B’C’D’E’C’/0B’/1C’/0B’/1E’/0C’/0C’/0B’/0A’/0E’/0A’/0D’/1A’/0D’/1A’/0A’/0A’/0A’/0A’/0A’/0①畫隱含表——缺頭少尾②順序比較③關(guān)聯(lián)比較④列最大等價類⑤最小化狀態(tài)表列最大等價類：（A，F(xiàn)）（B，C）（B，H）（C，H）（A，F(xiàn)）（B，C，H）（D）（E）（G）

A’B’C’D’E’現(xiàn)態(tài)次態(tài)/輸出X1X2=00011110ABCDEFGHD/0C/1C/1D/0C/1D/0G/0B/1D/0D/0D/0B/0F/0D/0G/0D/0F/0E/1E/1A/0E/1A/0A/0E/1A/0F/0A/0F/0A/0F/0A/0A/02、完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDEFGHE/0A/1C/0B/0D/1C/0H/1C/1D/0F/0A/1A/0C/0D/1G/1B/1BCDEFGHABCDEFG××BE××××××AD/FC×××××AD×××××××××××HC/BGBE→AD→FC令Q1=（A，D）

Q2=（B，E）

Q3=（C，F(xiàn)）

G=G，H=H現(xiàn)態(tài)次態(tài)/輸出X=0X=1Q1Q2Q3GHQ2/0Q1/0Q3/0H/1Q3/1Q1/0Q3/0Q1/0G/1Q2/1三、狀態(tài)表的化簡（1）狀態(tài)相容及相容類相容的條件：在所有可能的輸入條件下：（1）它們的輸出相同；（2）它們的次態(tài)滿足下列條件之一： 次態(tài)相同；次態(tài)交錯；指S1的次態(tài)是S2；S2的次態(tài)是S1。次態(tài)循環(huán)；注意：對于一方給定，一方不給定的次態(tài)和輸出，均作相同處理。相容狀態(tài)無傳遞性。3、不完全定義機(jī)狀態(tài)表的化簡：三、狀態(tài)表的化簡（1）狀態(tài)相容及相容類相容類：所有狀態(tài)之間都是兩兩相容的狀態(tài)集合。最大相容類：不是其他相容類的子集的一個相容類。狀態(tài)合并圖：將原始狀態(tài)表中所有的狀態(tài)以點的形式均勻地標(biāo)在一個圓周上，然后把所有相容狀態(tài)用線段連接起來，凡所有頂點之間都有連線的狀態(tài)就構(gòu)成一個最大相容類。3、不完全定義機(jī)狀態(tài)表的化簡：三、狀態(tài)表的化簡（2）化簡的方法①畫隱含表，尋找相容狀態(tài)對；②畫狀態(tài)合并圖；③作最小化狀態(tài)表；這一步的任務(wù)要從上面求得的最大相容類中選出一組能夠覆蓋原始狀態(tài)表全部狀態(tài)且數(shù)目最少的相容類，它們必須滿足：覆蓋性：該組相容類應(yīng)能夠覆蓋原始狀態(tài)表中全部狀態(tài)。最小性：該組相容類的數(shù)目應(yīng)為最少。閉合性：該組相容類中的任何一個相容類，它在原始狀態(tài)表中任一輸入條件下產(chǎn)生的次態(tài)應(yīng)該屬于該組內(nèi)的某一個相容類。3、不完全定義機(jī)狀態(tài)表的化簡：3、不完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)輸出X=0X=1ABCDECddDEdCBdD1dd0d①畫隱含表——缺頭少尾②順序比較③關(guān)聯(lián)比較④列最大相容類⑤最小化狀態(tài)表BCDEABCD√√×CE√√CD√BD√√√√ABCDE最大相容類：（A，B，C，E）（B，C，D，E）3、不完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)輸出X=0X=1ABCDECddDEdCBdD1dd0d⑤最小化狀態(tài)表最大相容類：（A，B，C，E）（B，C，D，E）對于本例，滿足覆蓋和最小這兩個條件的相容類有：(A,B,C,E)(B,C,D,E)(1)(A,E)(B,C,D)(2)(A,B,C)(D,E)(3)(A)(B,C,D,E)(4)若選擇（2），則不滿足閉合條件相容狀態(tài)集次態(tài)X=0X=1A，EB，C，DCEddDdDCBd（1），（3），（4）三種方案都滿足閉合條件3、不完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)輸出X=0X=1ABCDECddDEdCBdD1dd0d(A,B,C,E)(B,C,D,E)(1)(A,E)(B,C,D)(2)(A,B,C)(D,E)(3)(A)(B,C,D,E)(4)若選擇（1）相容狀態(tài)集次態(tài)X=0X=1ABCEBCDECEDECBDCBD現(xiàn)態(tài)次態(tài)輸出X=0X=1S1S2S1S2S2S2S210d3、不完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)輸出X=0X=1ABCDECddDEdCBdD1dd0d(A,B,C,E)(B,C,D,E)(1)(A,E)(B,C,D)(2)(A,B,C)(D,E)(3)(A)(B,C,D,E)(4)若選擇（3）相容狀態(tài)集次態(tài)X=0X=1ABCDECDECBD不完全確定的狀態(tài)表的最小化狀態(tài)表不是唯一的現(xiàn)態(tài)次態(tài)輸出X=0X=1S1S2S1S2S1S210三、狀態(tài)表的化簡（2）化簡的方法①畫隱含表，尋找相容狀態(tài)對；②畫狀態(tài)合并圖；③作最小化狀態(tài)表；3、不完全定義機(jī)狀態(tài)表的化簡：現(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDED/dE/0D/0C/dC/1A/dA/dB/dC/dB/d四、狀態(tài)編碼1、概念：根據(jù)最小化狀態(tài)表的狀態(tài)數(shù)，確定觸發(fā)器的個數(shù)，并指定每個狀態(tài)的二進(jìn)制代碼。對同步時序電路，一般情況下，狀態(tài)分配不影響電路的可靠性，僅僅影響電路的復(fù)雜程度。常用的狀態(tài)分配方法：建立通用方程；相鄰狀態(tài)分配法；減少相關(guān)法；四、狀態(tài)編碼2、狀態(tài)編碼規(guī)則：——相鄰狀態(tài)分配法（1）在同一輸入條件下，具有相同次態(tài)的現(xiàn)態(tài)，應(yīng)盡可能分配相鄰的二進(jìn)制代碼（即兩個二進(jìn)制代碼中只有一位數(shù)碼不同，其余各位均相同）——次態(tài)相同，現(xiàn)態(tài)編碼應(yīng)相鄰。（2）同一現(xiàn)態(tài)下，在相鄰輸入條件下的不同次態(tài)，應(yīng)盡可能分配相鄰的二進(jìn)制代碼——同一現(xiàn)態(tài)，次態(tài)編碼應(yīng)相鄰。（3）在所有輸入條件下，具有相同輸出的現(xiàn)態(tài)應(yīng)盡可能分配相鄰的二進(jìn)制代碼——輸出相同，現(xiàn)態(tài)編碼應(yīng)相鄰。（4）將狀態(tài)表中出現(xiàn)次數(shù)最多的狀態(tài)分配邏輯0。其重要性依次遞減。四、狀態(tài)編碼2、狀態(tài)編碼規(guī)則：（1）次態(tài)相同，現(xiàn)態(tài)編碼應(yīng)相鄰。（2）同一現(xiàn)態(tài)，次態(tài)編碼應(yīng)相鄰。（3）輸出相同，現(xiàn)態(tài)編碼應(yīng)相鄰。（4）將狀態(tài)表中出現(xiàn)次數(shù)最多的狀態(tài)分配邏輯0?，F(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDC/0A/0A/1B/1B/0A/1D/1C/1由規(guī)則1：B—C由規(guī)則2：B—C，A—D由規(guī)則3：C—D由規(guī)則4：A分配邏輯000BCDA110110y2y1y2n+1y1n+1/ZX=0X=10001111011/000/000/101/101/000/110/111/1四、狀態(tài)編碼2、狀態(tài)編碼規(guī)則：（1）次態(tài)相同，現(xiàn)態(tài)編碼應(yīng)相鄰。（2）同一現(xiàn)態(tài)，次態(tài)編碼應(yīng)相鄰。（3）輸出相同，現(xiàn)態(tài)編碼應(yīng)相鄰。（4）將狀態(tài)表中出現(xiàn)次數(shù)最多的狀態(tài)分配邏輯0?，F(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDC/0C/0B/0A/1D/0A/0D/0B/1由規(guī)則1：A—B，A—C由規(guī)則2：C—D，A—CB—D，A—B由規(guī)則3：A—B，A—C，B—C由規(guī)則4：A或B或C分配邏輯000110110y2y1y2n+1y1n+1/ZX=0X=10001111001/001/010/000/111/000/011/010/1BCDA四、狀態(tài)編碼2、狀態(tài)編碼規(guī)則：（1）次態(tài)相同，現(xiàn)態(tài)編碼應(yīng)相鄰。（2）同一現(xiàn)態(tài)，次態(tài)編碼應(yīng)相鄰。（3）輸出相同，現(xiàn)態(tài)編碼應(yīng)相鄰。（4）將狀態(tài)表中出現(xiàn)次數(shù)最多的狀態(tài)分配邏輯0?，F(xiàn)態(tài)次態(tài)/輸出X=0X=1ABCDEE/0A/1E/0A/0D/0B/0D/1A/0B/1C/0由規(guī)則1：A—C，B—DA—D由規(guī)則2：B—E，A—DA—E，A—B，C—D由規(guī)則3：A—C，A—E由規(guī)則4：A分配邏輯0000001010100y3y2y1y3n+1y2n+1y1n+1/ZX=0X=1000110100010001001/0000/1001/0000/0010/0110/0010/1000/0110/1100/0ACBDE110四、狀態(tài)編碼說明：（1）該方法的要點是直接從狀態(tài)表上確定全部所需要的相鄰關(guān)系，畫出相鄰圖，再按相鄰圖來分配各個狀態(tài)。（2）這種方法的基本思想：在選擇狀態(tài)編碼時，盡可能地使次態(tài)和輸出函數(shù)在卡諾圖上“1”單元的分布為相鄰，以便形成更大的圈。（3）這是一種經(jīng)驗方法，且三條規(guī)則是分別實施的，未能從總體上加以考慮，因此，所得的編碼往往不是最佳的，故稱它為“次佳”。五、選定觸發(fā)器、求出激勵函數(shù)和輸出函數(shù)表達(dá)式由二進(jìn)制狀態(tài)表和觸發(fā)器的激勵表出發(fā)求出激勵函數(shù)和輸出函數(shù)。y2y1y2n+1y1n+1/ZX=0X=10001111011/