【正文】 2022 華東師范大學計算機系 1 ? 倒數(shù)行 6： C211=（ S2， S3） C211=（ S1， S3） 本章錯誤 ▼ P286 ? 倒數(shù)行 8： C111=（ S0， S1） C111=（ S0， S2） 2022 華東師范大學計算機系 2 本章錯誤 ▼ P294 ? 表 719 10列： S2/1 S2/0 S1/1 S1/0 S0/0 S0/0 2022 華東師范大學計算機系 3 本章錯誤 ▼ P295 ? 行 3： F2F1’X F2F1’ ? 表 721， X=1 D1列： 1/0 1/0 0/0 0/0 1/0 1/0 0/1 1/0 2022 華東師范大學計算機系 4 本章錯誤 ▼ P297 ? 表 723 行 5： D B/0 E/1 D B/0 E/0 ▼ P306 ? 行 行 倒數(shù)行 3： 1000 2022 華東師范大學計算機系 5 本章錯誤 ▼ P311 ? 行 15： =(F3F2) =(F3F2’)’ ? 圖 7 47 a)改為： 00 01 11 10 0 0 1 1 d d 00 01 11 10 0 1 1 d d ? 圖 7 47 b)改為： 2022 華東師范大學計算機系 6 本章錯誤 ▼ P318 ? 右矩形 1： CTLN’ CTCN’ ? 右菱形 3： TCHR TCRH ▼ P325 ? 倒數(shù)行 7： U6B(LS112)=22ns U6B(LS112)=20ns 2022 華東師范大學計算機系 7 ▽ 同步時序電路的設計： （ 1）根據(jù)需求 狀態(tài)圖、狀態(tài)表 （ 2）狀態(tài)分配 狀態(tài)轉移表 （ 3）狀態(tài)轉移表 激勵表 觸發(fā)器特征表 （ 4）卡諾圖化簡 激勵函數(shù)表達式 輸出函數(shù)表達式 （ 5）電路實現(xiàn) 2022 華東師范大學計算機系 8 同步時序電路設計的進一步優(yōu)化： （ 1）根據(jù)需求 狀態(tài)圖、狀態(tài)表 （ 2） 狀態(tài)化簡 最小化狀態(tài)表 （ 3） 狀態(tài)分配 得狀態(tài)轉移表 （ 4）狀態(tài)轉移表 激勵表 觸發(fā)器特征表 （ 5）卡諾圖化簡 激勵函數(shù)表達式 輸出函數(shù)表達式 （ 6）電路實現(xiàn) 2022 華東師范大學計算機系 9 167。 7 時序電路設計 狀態(tài)化簡 狀態(tài)分配 復雜時序電路的設計 2022 華東師范大學計算機系 10 167。 7 時序電路設計 167。 狀態(tài)等價 167。 狀態(tài)化簡 167。 不完全定義狀態(tài)表的狀態(tài)化簡 167。 狀態(tài)分配方法 167。 算法狀態(tài)機 167。 鏈接時序機 2022 華東師范大學計算機系 11 167。 7 時序電路設計 167。 狀態(tài)等價 2022 華東師范大學計算機系 12 167。 狀態(tài)等價 ▽ 設計步驟： ① 根據(jù) 功能要求構成狀態(tài)圖 —— 原始狀態(tài)圖 ② 構成最小化狀態(tài)表 狀態(tài)化簡 —— 消除冗余狀態(tài)，降低成本 ☆ 狀態(tài)化簡是建立在狀態(tài)等價基礎上的 2022 華東師范大學計算機系 13 167。 狀態(tài)等價 1．狀態(tài)等價定理 ? S1與 S2等價： 當且僅當兩狀態(tài)每種可能的輸入序 列其輸出相等且次態(tài)等價，則稱： S1與 S2等價，記作（ S S2）。 2022 華東師范大學計算機系 14 1．狀態(tài)等價定理 ? 等價條件： ① 輸出相同 ② 次態(tài)等價（滿足下列條件之一）： 次態(tài)相同 次態(tài)交替： S1的次態(tài)為 S2 S2的次態(tài)為 S1 次態(tài)循環(huán)： S1和 S2的次態(tài)為 S3和 S4 S3和 S4的次態(tài)為 S1和 S2 2022 華東師范大學計算機系 15 167。 狀態(tài)等價 2． 等價性質： ① 對稱性：若 S1=S2， 則 S2=S1 ② 自反性：對任何狀態(tài) ， S1=S1 ③ 傳遞性：若 S1=S2， 且 S2=S3， 則 S1=S3 2022 華東師范大學計算機系 16 167。 狀態(tài)等價 3．等價類 等價類是若干狀態(tài)的集合 ， 在此集合中 ，任何兩個狀態(tài)都是相互等價的 。 （ S1， S2） （ S1， S3） → （ S1， S2， S3） ☆ 利用等價定理可進行狀態(tài)化簡 2022 華東師范大學計算機系 17 167。 7 時序電路設計 167。 狀態(tài)等價 167。 狀態(tài)化簡 2022 華東師范大學計算機系 18 167。 狀態(tài)化簡 ▽ 方法： 等價類表 隱含表 一 、 等價類表化簡法： 教材 P286討論 2022 華東師范大學計算機系 19 167。 狀態(tài)化簡 二 、 隱含表化簡法 —— 提供一種識別冗余狀態(tài)的圖形 化方法 隱含表：圖 71 每個方格代表一對隱含的等價 可能性 2022 華東師范大學計算機系 20 二、隱含表化簡法 1． 化簡步驟： ① 作隱含表 ， 尋找等價對 ② 根據(jù)等價性質 ， 構成最大等價類 ③ 將最大等價類中的狀態(tài)合并 ， 得到 最小化狀態(tài)表 2022 華東師范大學計算機系 21 二、隱含表化簡法 2． 化簡舉例 例 71） 化簡 P288 圖 74狀態(tài)圖 ② 作隱含表 ③ 填隱含表（圖 75), 對所有狀態(tài)進行比較： 狀態(tài)等價，打“ √” 輸出不同，打“ ” 輸出相同，但次態(tài)不同，將次態(tài)填入， 以便進一步判別 ① 列出狀態(tài)表（表 77） 2022 華東師范大學計算機系 22 例 73）化簡原始狀態(tài)表 對所有狀態(tài)進行比較，找出等價狀態(tài)對 B C D E A B C D BC AE AE BC CD BE,AC BC DC,AB ∵ DC不等價 ∴ AD不 等價 AE、 BC次態(tài)循環(huán) ∴ AE、 BC等價 ∵ CD不等價 ∴ DE不等價 ④ 歸納等價狀態(tài)對為： （ A,E）（ B,C） 2022 華東師范大學計算機系 23 例 71） 化簡圖 74狀態(tài)圖 ⑥ 狀態(tài)合并，作 : 最小化狀態(tài)表（表 79） 狀態(tài)圖（圖 77） ⑤ 歸納最大等價類： （ A， E），（ B， C），（ D） ↓ ↓ ↓ S0 S1 S2 2022 華東師范大學計算機系 24 2．化簡舉例 例 72） 化簡 P290 表 710狀態(tài)表 ② 進一步比較隱含表中尚未確定項 逐個比較，除去不等價狀態(tài)對 歸納等價狀態(tài)對為： （ 0）（ 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) ② 構成最大等價類 根據(jù)傳遞性： (A,B) (A,E) (B,E) (A,B,E) ∴ 最大等價類為： (A,B,E) (C,F) (D) (G) a b c d 2022 華東師范大學計算機系 28