Unit11DesignSequentialCircuitswithFlipFlopsSequentialcircuitDesign獲得原始狀態圖和原始狀態表（DerivationofStateGraphsandTables）狀態表化簡（ReductionofStateTables）狀態分配（StateAssignment）Someexamples

（1）根據需求狀態圖、狀態表（2）最小化狀態圖、狀態表

（3）狀態編碼（分配）

得狀態轉移表（4）狀態轉移表激勵表

觸發器特征表（5）卡諾圖化簡

激勵函數表達式

輸出函數表達式（6）電路實現（7）檢查無關項狀態圖、狀態表SequentialCircuitsDesign

構造原始狀態圖和狀態表1）根據文字描述的設計要求，先假定一個初態；2）從這個初態開始，每加入一個輸入取值，就可確定其次態和輸出；3）該次態可能是現態本身，也可能是已有的另一個狀態，或是新增加的一個狀態。4）這個過程持續下去，直至每一個現態向其次態的轉換都已被考慮，并且不再構成新的狀態。1.直接構圖法例1：給出同步模5可逆計數器的狀態表同步模5可逆計數器XCPZX=0:加計數X=1:減計數Z:進位、借位輸出標志現態Qn+1/ZQnX=0X=1ab

/0e

/1bc/0a

/0cd

/0b

/0de

/0c

/0ea/1d/0構造原始狀態圖和狀態表原始狀態圖（Mealy型）原始狀態表1）根據文字描述的設計要求，先假定一個初態；2）從這個初態開始，每加入一個輸入取值，就可確定其次態和輸出；3）該次態可能是現態本身，也可能是已有的另一個狀態，或是新增加的一個狀態。4）這個過程持續下去，直至每一個現態向其次態的轉換都已被考慮，并且不再構成新的狀態。直接構圖法0/00/01/01/00/11/11/01/0X/Zbcdea0/00/0例2：給出同步二進制串行加法器的狀態表設加法器內部狀態a——無進位b——有進位同步二進制串行加法器X1CPZX2010110011101001000/011/000/1X1X2/Zab01/110/101/010/011/1現態Qn+1/ZQnX1X2=00X1X2=01X1X2=10X1X2=11aa

/0a

/1a

/1b/0ba

/1b/0b/0b/1構造原始狀態圖和狀態表原始狀態圖（Mealy型）原始狀態表例3：序列檢測——給出同步Mealy型101序列檢測器的狀態表（1）狀態設定

S0——初始狀態，表示收到1位數據：“0”

S1——表示收到1位數據：“1”

S2——表示收到2位數據：“10”

S3——表示收到3位數據：“101”，此時輸出標志Z=1.可重疊檢測不可重疊檢測101序列檢測器XCPZ只標記感興趣的子串構造原始狀態圖和狀態表X:010101101Z:000101001X:010101011Z:000100010構造原始狀態圖和狀態表S0“0”X=0X=1X=0X=1X=0X=1“10”“101”X=0X=1“1”S1S0S2S1S0S3S1S2(Z=1)S0“0”X=0X=1X=0X=1X=0X=1“10”“101”X=0X=1“1”S1S0S2S1S0S3S1S0(Z=1)狀態轉換分析（Mealy型）狀態設定：S0——0；S1——1；

S2——10；S3——101，且Z=1可重疊檢測不可重疊檢測0/01/00/01/01/10/00/01/0X/ZS2S0S1S3現態Qn+1/ZQnX=0X=1S0S0/0S1/0S1S2/0S1/0S2S0/0S3/1S3S0/0S1/00/01/00/01/01/10/00/01/0X/ZS2S0S1S3現態Qn+1/ZQnX=0X=1S0S0/0S1/0S1S2/0S1/0S2S0/0S3/1S3S2/0S1/0構造原始狀態圖和狀態表原始狀態表可重疊檢測不可重疊檢測原始狀態圖（Mealy型）SequentialCircuitsDesign

（1）根據需求狀態圖、狀態表（2）最小化狀態圖、狀態表（3）狀態編碼（分配）

得狀態轉移表（4）狀態轉移表

激勵表

觸發器特征表（5）卡諾圖化簡

激勵函數表達式

輸出函數表達式（6）電路實現（7）檢查無關項狀態圖、狀態表時序電路的兩個狀態Si和Sj，如果它們對每一個輸入所產生的輸出完全相同，且它們的次態等價，則這兩個狀態是等價的（可以合并為一個狀態）——狀態化簡（一）完全定義狀態表的化簡方法利用觸發器設計時序邏輯_狀態表化簡2.狀態表的化簡K次劃分法（略）隱含（蘊含）表法倆倆比較原始狀態表中的所有狀態，找出能合并、不能合并、能否合并待定的狀態對。追蹤能否合并待定的狀態對，直至確定它們能合并或不能合并，從而找到原始狀態表中的所有等價狀態對?；谶@些等價狀態對確定最大等價狀態類，獲得原始狀態表的最小覆蓋集，建立最簡狀態表隱含表(蘊含)法利用觸發器設計時序邏輯_狀態表化簡狀態表中的任意兩個狀態Si和Sj

同時滿足下列兩個條件，它們可以合并為一個狀態在所有不同的現輸入下，現輸出分別相同在所有不同的現輸入下，次態分別為下列情況之一（1）兩個次態完全相同（2）兩個次態為其現態本身或交錯（3）兩個次態為狀態對封閉鏈中的一個狀態對（4）兩個次態的某一后續狀態對可以合并等價狀態的判定條件狀態合并的必要條件利用觸發器設計時序邏輯_狀態表化簡隱含表(蘊含)法現態Qn+1/ZQnX=0X=1ac

/0b/1bf/0a

/1cd

/0g/0dd

/1e

/0ec

/0e

/1fd/0g

/0gc

/1d

/0①建立隱含表②比較③追蹤cfaebe狀態對封閉連gfedcbabcde

fcfXXXXbeXXXXaecfXXXXXXXX

decd

X等價狀態對:{a,b}、{a,e}{b,e}、{c,f}豎列橫排掐頭去尾原始狀態表④獲得最大等價狀態類等價狀態類的定義——

If:Si≡Sj,

Sj

≡Sm

Then:Si≡Sj≡Sm,即

{Si,Sj,Sm}最大等價狀態類——

某一等價狀態類不屬于其他任何等價狀態類等價狀態對:{a,b}、{a,e}{b,e}、{c,f}最大等價狀態類:{a,b,e}、{c,f}q1={a,b,e}q2={c,f}q3=dq4=gLet最小覆蓋集：{q1,q2,q3,

q4}現態Qn+1/ZQnX=0X=1ac

/0b/1bf/0a

/1cd

/0g/0dd

/1e

/0ec

/0e

/1fd/0g

/0gc

/1d

/0原始狀態表現態Qn+1/ZQnX=0X=1ac

/0b/1bf/0a

/1cd

/0g/0dd

/1e

/0ec

/0e

/1fd/0g

/0gc

/1d

/0現態Qn+1/ZQnX=0X=1q1q2

/0q1/1q1q2

/0q1/1q2q3

/0q4/0q3q3

/1q1

/0q1q2

/0q1

/1q2q3/0q4

/0q4q2

/1q3

/0現態Qn+1/ZQnX=0X=1q1q2

/0q1/1q2q3

/0q4/0q3q3

/1q1

/0q4q2

/1q3

/0化簡后的狀態表利用觸發器設計時序邏輯_狀態表化簡隱含表(蘊含)法q1={a,b,e}q2={c,f}q3=dq4=gSequentialCircuitsDesign

（1）根據需求狀態圖、狀態表（2）最小化狀態圖、狀態表

（3）狀態編碼（分配）

得狀態轉移表（4）狀態轉移表

激勵表

觸發器特征表（5）卡諾圖化簡

激勵函數表達式

輸出函數表達式（6）電路實現（7）檢查無關項狀態圖、狀態表1.同一輸入下，相同的次態所對應的現態應該給予相鄰編碼2.同一現態在不同輸入下所對應的次態應給予相鄰編碼3.給定輸入下，輸出完全相同，現態編碼應相鄰規則目的：盡量使卡諾圖中更多的“1”(或“0”)相鄰注意:初始狀態一般可以放在卡諾圖的0號單元格里

優先滿足規則1和規則2狀態編碼盡量按照相鄰原則給予對于多輸出函數,規則3可以適當調高優先級一種經驗法利用觸發器設計時序邏輯_狀態表分配利用觸發器設計時序邏輯_狀態表分配現態Qn+1/ZQnX=0X=1ac

/0d/0bc/0a

/0cb

/0d/0da

/1b

/1

1:次態相同，現態編碼應相鄰

x=0時,次態(c,c)→現態a,bx=1時,次態(d,d)→現態a,cab,ac應相鄰

2：同一現態對應的次態編碼應相鄰

現態次態

a

→(c,d)

b→(c,a)

c→(b,d)

d→(a,b)cd,ca,bd,ab應相鄰

3：輸出相同，現態編碼應相鄰

現態輸出

a,b,c0

ab,ac,bc應相鄰

(a,b),(a,c)應相鄰,滿足規則1,2,3利用觸發器設計時序邏輯_狀態表分配a

——00,b

——01c——10,d

——11dcba0101狀態分配很難找到一個最佳的狀態分配方案對一種類型的觸發器是最好的分配方案，對另一種類型的觸發器卻不一定是最好。利用觸發器設計時序邏輯_狀態編碼例：利用JK觸發器設計110序列檢測器110

序列檢測器XCPZCPX:011011101Z:0001

000

10（1）狀態設定

S0——初始狀態，表示收到1位數據：“0”

S1——表示收到1位數據：“1”

S2——表示收到2位數據：“11”

S3——表示收到3位數據：“110”，此時輸出標志Z=1.1.

獲得原始狀態圖和原始狀態表（2）分析狀態轉換情況0/01/01/01/00/10/00/01/0X/ZS3S2S0S1（3）原始狀態圖（Mealy型）（4）原始狀態表S0“0”X=0X=1X=1X=0X=1X=0“11”“110”X=0X=1“1”S1S0S2S0S2S3S1S0(Z=1)現態Qn+1/ZQnX=0X=1S0S0/0S1/0S1S0/0S2/0S2S3/1S2/0S3S0/0S1/0S0——初始狀態，表示收到1位數據：“0”S1——表示收到1位數據：“1”S2——表示收到2位數據：“11”S3——表示收到3位數據：“110”，此時輸出Z=1.利用觸發器設計時序邏輯_狀態編碼2.狀態化簡3.狀態分配

使用

2個JK觸發器現態Qn+1/ZQnX=0X=1S0S0/0S1/0S1S0/0S2/0S2S3/1S2/0S3S0/0S1/0√

√現態Qn+1/ZQnX=0X=1S0S0/0S1/0S1S0/0S2/0S2S0/1S2/04.狀態轉換真值表

y2y1S0——00S1——10S2——11輸入現態次態觸發器輸出XY2nY1nY2n+1Y1n+1J2K2J1k1Z000000X0X001000X10X001100X1X11100101X0X011011X01X011111X0X00001XXXXXXX101XXXXXXX利用觸發器設計時序邏輯_狀態編碼5.卡諾圖化簡XXX1XXX00001111001XY2nY1n00XX11XX0001111001XY2nY1nJ2=XK2=X1XX00XX00001111001XY2nY1nX0XXX1XX0001111001XY2nY1n00X001X00001111001XY2nY1nJ1=XY2nK1=XZ=XY1n4.狀態轉換真值表利用觸發器設計時序邏輯_狀態編碼輸入現態次態觸發器輸出XY2nY1nY2n+1Y1n+1J2K2J1k1Z000000X0X001000X10X001100X1X11100101X0X011011X01X011111X0X00001XXXXXXX101XXXXXXX7.檢查無關項J1=XY2nK1=XJ2=XK2=XY1n+1

=XY2nY1n+XY1n=X(Y1n+Y2n)Y2n+1

=

XY2n+XY2n

=X

1100X=0X=101電路可以自啟動K2Q2Q2CKcp

K1

Q1Q1CKJ2J1ZXY2Y16.電路實現例：利用T觸發器設計一個同步模8可逆計數器利用觸發器設計同步時序邏輯_例1同步模8可逆計數器XCPZ0/00/00/00/00/00/00/00/11/01/01/01/01/01/01/01/1X/Z需要3個T觸發器1.

原始狀態圖及狀態表X=0:加法；X=1:減法Z：進位及借位輸入現態次態輸入輸出XQ3nQ2nQ1nQ3n+1Q