【正文】 ）（ 1， 2）（ 3， 6）（ 4， 7）（ 5， 8） ↓ ↓ ↓ ↓ ↓ A B C D E ① 逐行比較原始狀態(tài)表 →填隱含表（圖 78） ③ 最小化狀態(tài)表 （表 712） 2022 華東師范大學計算機系 25 2．化簡舉例 例 1）化簡如下原始狀態(tài)表： Yt Yt+1 / Z X=0 X=1 A B C D E F G C / 0 F / 0 D / 0 D / 1 C / 0 D / 0 C / 0 B / 1 A / 1 G / 0 E / 0 E / 1 G / 0 D / 0 2022 華東師范大學計算機系 26 例 1）化簡原始狀態(tài)表 Yt Yt+1 / Z X=0 X=1 A B C D E F G C / 0 F / 0 D / 0 D / 1 C / 0 D / 0 C / 1 B / 1 A / 1 G / 0 E / 0 E / 1 G / 0 D / 0 ① 作隱含表，找出等價 狀態(tài)對 B C D E F G A B C D E F CF √ BE AE CF CD ED CF等價 ∴ AB等價 AE、 BE次態(tài)循環(huán) ∵ CD不等價 歸納等價狀態(tài)對為： (A,B) (A,E) (B,E) (C,F) 2022 華東師范大學計算機系 27 例 1）化簡原始狀態(tài)表 歸納等價狀態(tài)對為： (A,B) (A,E) (B,E) (C,F) ② 構(gòu)成最大等價類 根據(jù)傳遞性： (A,B) (A,E) (B,E) (A,B,E) ∴ 最大等價類為： (A,B,E) (C,F) (D) (G) a b c d 2022 華東師范大學計算機系 28 例 1）化簡原始狀態(tài)表 ③ 構(gòu)成最小化狀態(tài)表： (A,B,E) (C,F) (D) (G) a b c d Yt Yt+1 / Z X=0 X=1 A B C D E F G C / 0 F / 0 D / 0 D / 1 C / 0 D / 0 C / 1 B / 1 A / 1 G / 0 E / 0 E / 1 G / 0 D / 0 Yt Yt+1 / Z X=0 X=1 a b c d b / 0 c / 0 c / 1 b / 1 a / 1 d / 0 a / 0 c / 0 2022 華東師范大學計算機系 29 167。 輸出不同，打“ ” 狀態(tài)化簡 2022 華東師范大學計算機系 18 167。 狀態(tài)等價 3．等價類 等價類是若干狀態(tài)的集合 ， 在此集合中 ，任何兩個狀態(tài)都是相互等價的 。 次態(tài)相同 狀態(tài)等價 2022 華東師范大學計算機系 12 167。 狀態(tài)分配方法 167。 7 時序電路設(shè)計 167。 7 時序電路設(shè)計 狀態(tài)化簡 狀態(tài)等價 167。 算法狀態(tài)機 167。 狀態(tài)等價 ▽ 設(shè)計步驟： ① 根據(jù) 功能要求構(gòu)成狀態(tài)圖 —— 原始狀態(tài)圖 ② 構(gòu)成最小化狀態(tài)表 狀態(tài)化簡 —— 消除冗余狀態(tài)，降低成本 ☆ 狀態(tài)化簡是建立在狀態(tài)等價基礎(chǔ)上的 2022 華東師范大學計算機系 13 167。 次態(tài)交替： S1的次態(tài)為 S2 S2的次態(tài)為 S1 （ S1， S2） （ S1， S3） → （ S1， S2， S3） ☆ 利用等價定理可進行狀態(tài)化簡 2022 華東師范大學計算機系 17 167。 狀態(tài)化簡 ▽ 方法： 等價類表 隱含表 一 、 等價類表化簡法： 教材 P286討論 2022 華東師范大學計算機系 19 167。 輸出相同，但次態(tài)不同，將次態(tài)填入， 以便進一步判別 ① 列出狀態(tài)表（表 77） 2022 華東師范大學計算機系 22 例 73）化簡原始狀態(tài)表 7 時序電路設(shè)計 167。 不完全定義狀態(tài)表的狀態(tài)化簡 ▽ 特點： 狀態(tài)表中存在不完全確定的次態(tài)或輸出 ▽ 不完全確定 狀態(tài)表的化簡是建立在相容狀態(tài)基礎(chǔ)上的 2022 華東師范大學計算機系 31 167。 次態(tài)交替 狀態(tài)等價 167。 狀態(tài)分配方法 一、狀態(tài)分配 —— 為狀態(tài)分配唯一的二進制編碼 設(shè)：二進制碼位數(shù)為 M 狀態(tài)數(shù)為 N 則： 2M1＜ N≤2 M 二、狀態(tài)分配的合理性 狀態(tài)分配不會影響電路的邏輯功能， 但影響電路實現(xiàn)的復雜度 。 規(guī)則 2： 同一狀態(tài) 在相鄰輸入下的不同次態(tài) 規(guī)則 3： A,B,C 2022 華東師范大學計算機系 48 A： 00， B： 10， C： 01， D： 11 例 4） ③ 狀態(tài)分配 規(guī)則 1： A,C、 B,E、 A,E、 D,F 卡諾圖化簡： D2=F2F1’X’+F2F1X+F3F2’X D1=F3F2+F2F1’X 2022 華東師范大學計算機系 52 例 74）考察表 724所示狀態(tài)表 ? 狀態(tài)分配方案不同，實現(xiàn)成本略有不同 不考慮狀態(tài)分配原則： 35門 ☆ 狀態(tài)分配規(guī)則不一定能產(chǎn)生最佳方案， 但能產(chǎn)生狀態(tài)分配的較好方案 2022 華東師范大學計算機系 53 ▽ 同步時序電路的設(shè)計： （ 1）根據(jù)需求 狀態(tài)圖、狀態(tài)表 （ 2）狀態(tài)分配 狀態(tài)轉(zhuǎn)移表 （ 3）狀態(tài)轉(zhuǎn)移表 激勵表 觸發(fā)器特征表 （ 4）卡諾圖化簡 激勵函數(shù)表達式 輸出函數(shù)表達式 （ 5）電路實現(xiàn) 2022 華東師范大學計算機系 54 同步時序電路設(shè)計的進一步優(yōu)化： （ 1）根據(jù)需求 狀態(tài)圖、狀態(tài)表 （ 2） 狀態(tài)化簡 最小化狀態(tài)表 （ 3） 狀態(tài)分配 得狀態(tài)轉(zhuǎn)移表 （ 4）狀態(tài)轉(zhuǎn)移表 激勵表 觸發(fā)器特征表 （ 5）卡諾圖化簡 激勵函數(shù)表達式 輸出函數(shù)表達式 （ 6）電路實現(xiàn) 2022 華東師范大學計算機系 55 ? 狀態(tài)圖 ☆ 同步時序電路設(shè)計 例 5）試設(shè)計一個同步時序電路，接收串行二 進制代碼，輸入代碼每三位為一組，當 輸入的三位二進制代碼為 011時，電路 輸出為“ 1” 。 激勵表： （ D觸發(fā)器實現(xiàn)） F3F2F1 D3 D2 D1 / Z X=0 X=1 000 001 011 010 110 001, 0 010, 0 010, 0 000, 0 000, 0 011, 0 110, 0 010, 0 000, 0 000, 1 d 01 d 00 10 11 01 00 F3F2 d d 1 10 d d 1 1 1 1 11 F1X d 01 d 00 10 11 01 00 F3F2 d d 10 d d 1 11 F1X D3=F2’F1X D2=F2’X+F1 2022 華東師范大學計算機系 62 例 5） F3F2F1 D3 D2 D1 / Z X=0 X=1 000 001 011 010 110 001, 0 010, 0 010, 0 000, 0 000, 0 011, 0 110, 0 010, 0 000, 0 000, 1 d 1 01 d 00 10 11 01 00 F3F2 d d 10 d d 11 F1X d 01 d 1 00 10 11 01 00 F3F2 d d 10 d d 1 11 F1X D1=F2’F1’ Z=F3X 2022 華東師范大學計算機系 63 例 5） ? 邏輯圖： D3=F2’F1X D2=F2’X+F1 D1=F2’F1’ Z=F3X 3 Q D CP Q’ 2 Q D CP Q’ 1 Q D CP Z F3 F2 F1 CLK X 2022 華東師范大學計算機系 64 例 5） ? 分析討論 根據(jù)激勵函數(shù)畫出包含所有 狀態(tài)的狀態(tài)圖 000 001 010 100 0/0 011 1/0 110 1/0 0/0 1/1 0/0 0/0 1/1 0/0 1/1 1/1 0/0 1/0 101 111 0/0 ? 修改輸出函數(shù)： Z=F3F2F1’X F3F2F1 D3 D2 D1 / Z X=0 X=1 000 001 011 010 110 001, 0 010, 0 010, 0 000, 0 000, 0 011, 0 110, 0 010, 0 000, 0 000, 1 D3=F2’F1X D2=F2’X+F1 D1=F2’F1’ Z=F3X 0/0 1/0 2022 華東師范大學計算機系 65 例 5） ? 修改輸出函數(shù)： Z=F3F2F1’X 3 Q D CP Q’ 2 Q D CP Q’ 1 Q D CP Z F3 F2 F1 CLK X 2022 華東師范大學計算機系 66 例 5） 000 001 011 110 010 100 0/0 1/0 1/0 0/0 1/0 0/0 0/0 1/1 0/0 1/0 1/0 0/0 1/0 101 111 0/0 狀態(tài)圖： 0/0 1/0 2022 華東師范大學計算機系 67 167。 不完全定義狀態(tài)表的狀態(tài)化簡 167。 算法狀態(tài)機 一、 ASM符號 ? 狀態(tài)符號 —— 表示系統(tǒng)狀態(tài) 圖 7－ 24 OUT1 OUT2 A 00 狀態(tài) 狀態(tài)進入 狀態(tài)退出