【正文】 75), 對所有狀態(tài)進(jìn)行比較： 對所有狀態(tài)進(jìn)行比較，找出等價狀態(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 華東師范大學(xué)計算機(jī)系 23 例 71） 化簡圖 74狀態(tài)圖 ⑥ 狀態(tài)合并，作 : 最小化狀態(tài)表（表 79） 狀態(tài)圖（圖 77） ⑤ 歸納最大等價類： （ A， E），（ B， C），（ D） ↓ ↓ ↓ S0 S1 S2 2022 華東師范大學(xué)計算機(jī)系 24 2．化簡舉例 例 72） 化簡 P290 表 710狀態(tài)表 ② 進(jìn)一步比較隱含表中尚未確定項(xiàng) 狀態(tài)等價 167。 不完全定義狀態(tài)表的狀態(tài)化簡 一、狀態(tài)相容 1. 相容狀態(tài)： 對于所有的有效輸入序列，分別從狀態(tài) SA和 SB出發(fā)，所得到的輸出響應(yīng)序列是 完全相同的（不確定狀態(tài)可任意指定）， 那么狀態(tài) SA和 SB是相容的，即 SA和 SB為相 容對，記作： {SA， SB}。 次態(tài)循環(huán) 2022 華東師范大學(xué)計算機(jī)系 33 一、狀態(tài)相容 2. 相容類 狀態(tài)相容與狀態(tài)等價性質(zhì)一樣，具有相容類和最大相容類的性質(zhì) ? 不同點(diǎn)： ① 不具備傳遞性，即在相容類中所有 狀態(tài)之間都分別是兩兩相容的； ② ∵ 不具備傳遞性 ∴ 若干個最大相容類可能包含公共 狀態(tài) 2022 華東師范大學(xué)計算機(jī)系 34 一、狀態(tài)相容 3. 相容性質(zhì) 相容類集合必須滿足覆蓋、閉合和最小三個條件 ? 覆蓋 —— 指相容類集合中包含了原狀態(tài) 表的全部狀態(tài) ? 閉合 —— 指在一個相容類集合中，任一 相容類在各種輸入取值下的次 態(tài)組合，都必須屬于該集合中 某一相容類 ? 最小 —— 指滿足覆蓋和閉合的相容類數(shù) 目達(dá)到最少 2022 華東師范大學(xué)計算機(jī)系 35 一、狀態(tài)相容 4. 化簡步驟： ① 作隱含表 尋找相容狀態(tài)對 ② 利用狀態(tài)合并圖 尋找最大相容類 ③ 作最小化狀態(tài)表 ? 狀態(tài)合并圖 ① 以點(diǎn)表示狀態(tài)，均勻分布在圓周上 ② 將各相容對用線段連接 ③ 找出所有點(diǎn)之間都有連線的多邊形 構(gòu)成一個最大相容類 2022 華東師范大學(xué)計算機(jī)系 36 167。 狀態(tài)化簡 167。 —— 尋找較為合理的分配方案 2022 華東師范大學(xué)計算機(jī)系 46 167。 規(guī)則 3： 在所有輸入取值下均有相同輸出的 現(xiàn)態(tài) 2022 華東師范大學(xué)計算機(jī)系 47 三、狀態(tài)分配算法 2. 狀態(tài)分配實(shí)例 例 4）為如下狀態(tài)表建 立狀態(tài)轉(zhuǎn)移表 Y Y+ / Z X=0 X=1 A B C D C / 0 C / 0 B / 0 A / 1 D / 0 A / 0 D / 0 B / 1 ① 確定狀態(tài)變量位數(shù) ∵ 22=4 ∴ 取 2位狀態(tài)變量 ② 應(yīng)分配相鄰代碼的狀態(tài)： 規(guī)則 1： A,B、 A,C 規(guī)則 2： A,C、 C,D、 A,F、 B,E、 D,E ☆ A,C B,E出現(xiàn) 2次，優(yōu)先考慮 ② 多種分配方案： 方案一：圖 718 (a) 表 725 方案二： (b) 方案三： (c) 2022 華東師范大學(xué)計算機(jī)系 50 例 74）考察表 724所示狀態(tài)表 ③ 采用 D觸發(fā)器實(shí)現(xiàn)各方案 P299 例，方案一： F3F2F1 D3 D2 D1 X=0 X=1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 方案一： 28門 A B C D E F G 0/0 1/0 0/0 0/0 1/0 1/0 0/0 1/0 0/0 1/1 0/0 1/0 0/0 1/0 初態(tài) 0 1 00 01 10 11 X/Z 2022 華東師范大學(xué)計算機(jī)系 56 例 5） ? 狀態(tài)表 A B C D E F G 0/0 1/0 0/0 0/0 1/0 1/0 0/0 1/0 0/0 1/1 0/0 1/0 0/0 1/0 初態(tài) 0 1 00 01 10 11 Y Y+ / Z X=0 X=1 A B C D E F G B, 0 C, 0 D, 0 E, 0 F, 0 G, 0 A, 0 A, 0 A, 0 A, 1 A, 0 A, 0 A, 0 A, 0 2022 華東師范大學(xué)計算機(jī)系 57 例 5） ? 最小化狀態(tài)表 Y Y+ / Z X=0 X=1 A B C D E F G B, 0 D, 0 F, 0 A, 0 A, 0 A, 0 A, 0 C, 0 E, 0 G, 0 A, 0 A, 1 A, 0 A, 0 B C D E F G A B C D E F BD CE BF CG AB AC AB AC AB AC DF EG AD AE AD AE AD AE AF AG AF AG AF AG X X X X X X ? ? ? ? 等價類 : (D, F) (D, G) (G, F) (D, F, G) 2022 華東師范大學(xué)計算機(jī)系 58 例 5） 最大等價類 : (A) (B) (C) (D, F, G) (E) ? ? ? ? ? a b c d e Y Y+ / Z X=0 X=1 A B C D E F G B, 0 D, 0 F, 0 A, 0 A, 0 A, 0 A, 0 C, 0 E, 0 G, 0 A, 0 A, 1 A, 0 A, 0 Y Y+ / Z X=0 X=1 a b c d e 最小化狀態(tài)表： b, 0 c, 0 d, 0 e, 0 d, 0 d, 0 a, 0 a, 0 a, 0 a, 1 2022 華東師范大學(xué)計算機(jī)系 59 例 5） ? 狀態(tài)分配 ∵ 22523 ∴ 用三位二進(jìn)制代碼表示一個狀態(tài) 1 0 10 11 01 00 F3F2 F1 Y Y+ / Z X=0 X=1 a b c d e b, 0 d, 0 d, 0 a, 0 a, 0 c, 0 e, 0 d, 0 a, 0 a, 1 根據(jù)： 7 時序電路設(shè)計 167。 狀態(tài)分配方法 167。 選擇塊可由 ASM塊共享： 圖 735 計數(shù)時鐘取 1MHz（ 1us) 當(dāng)出現(xiàn)故障，無 ECHO信號返回時，利用該信號復(fù)位系統(tǒng)。 現(xiàn)態(tài) 010： F3 F3+ J3 K3 XMIT’ ECHO ERST’ 0 1 1 d (XMIT’ ECHO ERST’)’ 0 0 0 d ∴ 圖 746(e) J3卡諾圖： 010小格填入 XMIT’ ECHO ERST’ ? 化簡，得激勵函數(shù)和輸出函數(shù)表達(dá)式 P311 （ 9）電路圖 圖 748 （ 10）時序圖 圖 749 2022 華東師范大學(xué)計算機(jī)系 87 167。 不完全定義狀態(tài)表的狀態(tài)化簡 167。 鏈接時序機(jī) ? 鏈接時序機(jī)： 一個電路的輸出成為另一個電路的輸入； 而另一個電路的輸出又成為第一個電路的 輸入，則該時序機(jī)稱為鏈接時序機(jī)。 串行鏈接： 圖 750 圖 752 計算機(jī)模擬器與繪圖儀接口鏈接關(guān)系： （部分 ASM圖） 圖 757 輸入信號： XFR 啟動（模擬中斷處理程序入口） INTH 中斷請求 RPYH 接口應(yīng)答 TCH 緩沖區(qū)滿（要求 CPU停止送數(shù)） RPYH 方法一：分析狀態(tài)表 規(guī)則 1： {A,G} 4 {C,D} 4 {E,F} 4 {F,G} 8 {C,E} 4 {A,B} 4 {B,C,D} 8 利用卡諾圖分配 圖 760 2022 華東師范大學(xué)計算機(jī)系 98 例 78）設(shè)計繪圖儀接口，并模擬計算機(jī)進(jìn)行調(diào)試。 B?B（ RPYH=0） A?B（ XFR=1） ∴ {A,B} 4 C?E（ RPYH=0,TCH=1） E?E（ TCH=1） ∴ {C,E} 4 RPYH 現(xiàn)態(tài) 100： INTH F3 F3+ J3 K3 MEV 0 1 0 d 1 1 1 1 d 0 INTH’ ∴ 圖 761 K3卡諾圖： 100小格填入 INTH’ 2022 華東師范大學(xué)計算機(jī)系 101 例 78）設(shè)計繪圖儀接口，并模擬計算機(jī)進(jìn)行調(diào)試。 輸出信號： DOSH 繪圖儀數(shù)據(jù)選通 TCH 緩沖器滿 RPYH 接口應(yīng)答 INTH 中斷請求