【正文】 ? 規(guī)則 1： {B,C}?4 {D,F}?4 {D,E} {C,D}?2 規(guī)則 2： {C,D} {A,D E} {E,F} 規(guī)則 3： {A,C,E} ? 利用卡諾圖分配 圖 745 （ 6）狀態(tài)轉(zhuǎn)移表 表 729 （ 7）激勵(lì)表（用 JK觸發(fā)器實(shí)現(xiàn)） [略 ] 2022 華東師范大學(xué)計(jì)算機(jī)系 84 例 77）測量超聲波發(fā)生器發(fā)射端到目的地的距離 （ 8）卡諾圖化簡 激勵(lì)函數(shù)表達(dá)式 輸出函數(shù)表達(dá)式 ? 分析表 729： ? J1K1： 現(xiàn)態(tài) 011： XMIT F1 F1+ 0 1 1 1 1 0 J1 K1 MEV d 0 d 1 XMIT ∴ 圖 746(b)K1卡諾圖： 011小格填入 XMIT 2022 華東師范大學(xué)計(jì)算機(jī)系 85 例 77）測量超聲波發(fā)生器發(fā)射端到目的地的距離 ? J2K2： ASM 圖的循環(huán)描述： 圖 736 2022 華東師范大學(xué)計(jì)算機(jī)系 76 167。 狀態(tài)等價(jià) 167。 方案二： 27門 規(guī)則 2： C,D、 A,C、 B,D、 A,B 狀態(tài)分配方法 三、狀態(tài)分配算法 1. 狀態(tài)分配規(guī)則 如下情況，應(yīng)分配相鄰的二進(jìn)制代碼 不完全定義狀態(tài)表的狀態(tài)化簡 二、化簡舉例 例 2）化簡狀態(tài)表 現(xiàn)態(tài) 次態(tài) / 輸出 00 01 10 11 A B C D E C， 0 ， D， 0 C， 0 B， 0 ， E， 0 B， 1 A， 1 ， A， 0 B， 0 ， E， 0 A， 0 ， D， 1 ， ， E， 1 ① 作隱含表 B C D E A B C D √ CD AE CB AB DE AB DB CB AE ? 歸納相容狀態(tài)對： {A， B} {A， C} {D， C} 2022 華東師范大學(xué)計(jì)算機(jī)系 37 例 2）化簡狀態(tài)表 ② 作狀態(tài)合并圖 {A， B} {A， C} {D， C} A B C D E ∴ 最大相容類： {A， B} {D， C} {E} S0 S1 S2 2022 華東師范大學(xué)計(jì)算機(jī)系 38 例 2） 現(xiàn)態(tài) 次態(tài) / 輸出 00 01 10 11 A B C D E C， 0 ， D， 0 C， 0 B， 0 ， E， 0 B， 1 A， 1 ， A， 0 B， 0 ， E， 0 A， 0 ， D， 1 ， ， E， 1 ③ 作最小化狀態(tài)表 {A， B} {D， C} {E} S0 S1 S2 現(xiàn)態(tài) 次態(tài) / 輸出 00 01 10 11 S0 S1 S2 S1， 0 S1， 0 S0， 0 S2， 0 S0， 1 ， S0， 0 S2， 0 S0， 0 S1， 1 ， S2， 1 2022 華東師范大學(xué)計(jì)算機(jī)系 39 二、化簡舉例 例 73）化簡狀態(tài)表 現(xiàn)態(tài) 次態(tài) / 輸出 00 01 10 11 A B C D E F G ， A， 0 E， 0 ， C， 0 D， 1 E， 1 D， 0 C， 0 A， 0 ， ， B， 0 ， F， 0 ， E， 0 C， 0 ， ， A， 0 C， 1 D， 1 ， G， 1 F， 1 E， 1 C， 1 ① 作隱含表 B C D E F G A B C D E F CD AD EF CF CG CF BD CE AF AE AC DG AC DF ? 相容狀態(tài)對： {A,B}{C,D}{C,E}{D,E}{G,F} CE CE GF GE AC CG DE CE 2022 華東師范大學(xué)計(jì)算機(jī)系 40 例 73）化簡狀態(tài)表 ② 作狀態(tài)合并圖 {A,B} {C,D} {C,E} {D,E} {G,F} ∴ 最大相容類： {A,B}{C,E,D}{F,G} S0 S1 S2 A B C D E F G ③ 作最小化狀態(tài)表 （表 719） 2022 華東師范大學(xué)計(jì)算機(jī)系 41 二、化簡舉例 例 3）化簡狀態(tài)表 現(xiàn)態(tài) 次態(tài) 輸出 X=0 X=1 Z A B C D E F B B A F D D E E C 0 1 1 1 ① 作隱含表 B C D E F A B C D E √ CD AB DE DE ? 相容狀態(tài)對： {A,B}{A,F}{B,C}{B,D}{B,E} {B,F}{C,D}{C,E}{C,F}{D,E}{D,F}{E,F} CE AF CE BF CD √ √ √ 2022 華東師范大學(xué)計(jì)算機(jī)系 42 例 73）化簡狀態(tài)表 ② 作狀態(tài)合并圖 {A,B} {A,F} {B,C} {B,D} {B,E} {B,F} {C,D} {C,E} {C,F} {D,E} {D,F} {E,F} ∴ 最大相容類： {B,C,D,E,F}{A,B,F} a b A B C D E F 2022 華東師范大學(xué)計(jì)算機(jī)系 43 例 73）化簡狀態(tài)表 現(xiàn)態(tài) 次態(tài) 輸出 X=0 X=1 Z A B C D E F B B A F D D E E C 0 1 1 1 ③ 作最小化狀態(tài)表 {A,B,F} {B,C,D,E,F} a b 現(xiàn)態(tài) 次態(tài) 輸出 X=0 X=1 Z a b a b b 0 1 2022 華東師范大學(xué)計(jì)算機(jī)系 44 167。 狀態(tài)化簡 167。 狀態(tài)等價(jià)，打“ √” 狀態(tài)等價(jià) 2． 等價(jià)性質(zhì)： ① 對稱性：若 S1=S2， 則 S2=S1 ② 自反性：對任何狀態(tài) ， S1=S1 ③ 傳遞性：若 S1=S2， 且 S2=S3， 則 S1=S3 2022 華東師范大學(xué)計(jì)算機(jī)系 16 167。 7 時(shí)序電路設(shè)計(jì) 167。 復(fù)雜時(shí)序電路的設(shè)計(jì) 2022 華東師范大學(xué)計(jì)算機(jī)系 10 167。 狀態(tài)分配 鏈接時(shí)序機(jī) 2022 華東師范大學(xué)計(jì)算機(jī)系 11 167。 次態(tài)循環(huán)： S1和 S2的次態(tài)為 S3和 S4 S3和 S4的次態(tài)為 S1和 S2 2022 華東師范大學(xué)計(jì)算機(jī)系 15 167。 狀態(tài)化簡 二 、 隱含表化簡法 —— 提供一種識(shí)別冗余狀態(tài)的圖形 化方法 隱含表：圖 71 每個(gè)方格代表一對隱含的等價(jià) 可能性 2022 華東師范大學(xué)計(jì)算機(jī)系 20 二、隱含表化簡法 1． 化簡步驟： ① 作隱含表 ， 尋找等價(jià)對 ② 根據(jù)等價(jià)性質(zhì) ， 構(gòu)成最大等價(jià)類 ③ 將最大等價(jià)類中的狀態(tài)合并 ， 得到 最小化狀態(tài)表 2022 華東師范大學(xué)計(jì)算機(jī)系 21 二、隱含表化簡法 2． 化簡舉例 例 71） 化簡 P288 圖 74狀態(tài)圖 ② 作隱含表 ③ 填隱含表（圖 75), 對所有狀態(tài)進(jìn)行比較： 狀態(tài)等價(jià) 167。 次態(tài)循環(huán) 2022 華東師范大學(xué)計(jì)算機(jī)系 33 一、狀態(tài)相容 2. 相容類 狀態(tài)相容與狀態(tài)等價(jià)性質(zhì)一樣，具有相容類和最大相容類的性質(zhì) ? 不同點(diǎn)： ① 不具備傳遞性，即在相容類中所有 狀態(tài)之間都分別是兩兩相容的； ② ∵ 不具備傳遞性 ∴ 若干個(gè)最大相容類可能包含公共 狀態(tài) 2022 華東師范大學(xué)計(jì)算機(jī)系 34 一、狀態(tài)相容 3. 相容性質(zhì) 相容類集合必須滿足覆蓋、閉合和最小三個(gè)條件 ? 覆蓋 —— 指相容類集合中包含了原狀態(tài) 表的全部狀態(tài) ? 閉合 —— 指在一個(gè)相容類集合中，任一 相容類在各種輸入取值下的次 態(tài)組合，都必須屬于該集合中 某一相容類 ? 最小 —— 指滿足覆蓋和閉合的相容類數(shù) 目達(dá)到最少 2022 華東師范大學(xué)計(jì)算機(jī)系 35 一、狀態(tài)相容 4. 化簡步驟： ① 作隱含表 尋找相容狀態(tài)對 ② 利用狀態(tài)合并圖 尋找最大相容類 ③ 作最小化狀態(tài)表 ? 狀態(tài)合并圖 ① 以點(diǎn)表示狀態(tài)，均勻分布在圓周上 ② 將各相容對用線段連接 ③ 找出所有點(diǎn)之間都有連線的多邊形 構(gòu)成一個(gè)最大相容類 2022 華東師范大學(xué)計(jì)算機(jī)系 36 167。 —— 尋找較為合理的分配方案 2022 華東師范大學(xué)計(jì)算機(jī)系 46 167。 規(guī)則 1： A,B、 A,C 方案一： 28門 7 時(shí)序電路設(shè)計(jì) 167。 選擇塊可由 ASM塊共享： 圖 735 當(dāng)出現(xiàn)故障，無 ECHO信號(hào)返回時(shí)，利用該信號(hào)復(fù)位系統(tǒng)。 不完全定義狀態(tài)表的狀態(tài)化簡 167。 串行鏈接： 圖 750 計(jì)算機(jī)模擬器與繪圖儀接口鏈接關(guān)系： （部分 ASM圖） 圖 757 RPYH B?B（ RPYH=0） A?B（ XFR=1） ∴ {A,B} 4 RPYH 輸出信號(hào)： DOSH 繪圖儀數(shù)據(jù)選通 TCH 緩沖器滿 RPYH 接口應(yīng)答 INTH 中斷請求