【正文】 比較， 2）關(guān)聯(lián)比較，找出原始狀態(tài)表中的全部等效狀態(tài)。 1)順序比較；使用等效狀態(tài)判斷條件，把原始狀態(tài)表每一個狀態(tài) 分別依次 與其他所有的狀態(tài)進(jìn)行比較，將比較結(jié)果標(biāo)注在隱含表中的相應(yīng)方格內(nèi)。每個狀態(tài)對的比較結(jié)果有 3種情況：一、 是等效的，在相應(yīng)方格內(nèi)填上“ √”標(biāo)記； 二、 是不等效的，在相應(yīng)方格內(nèi)填上“”標(biāo)記； 三、 是有待于進(jìn)一步比較的狀態(tài)對，對于這種情況，在隱含表相應(yīng)方格內(nèi)填上相比較的兩個狀態(tài)的次態(tài)。 2）關(guān)聯(lián)比較： 處理在順序比較中尚未確定等效的狀態(tài)對。在關(guān)聯(lián)比較時，首先要確定隱含表中的哪些次態(tài)需要進(jìn)一步比較，以確定是否等效，并由此確定原狀態(tài)對是否等效。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 找出最大等效類。在找出原始狀態(tài)表中的所有等效對以后，使用等效狀態(tài)的傳遞性，確定等效類。 求出最大等效類。 做出最小化狀態(tài)表。根據(jù)找出的最大等效類，將每個最大等效類中包含的狀態(tài)中任意選擇一個狀態(tài)留下，其余的狀態(tài)去掉，構(gòu)成最小化狀態(tài)表。 將每個最大等效類分別命名作為一個狀現(xiàn)狀命名，構(gòu)成最小化狀態(tài)表。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 例 47 化簡表 421所示的原始狀態(tài)表。 解：表 421是有 7個狀態(tài)的原始狀態(tài)表。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 1 、畫隱含表， 1）順序比較，找出所有的等效狀態(tài)對。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 2）進(jìn)行關(guān)聯(lián)比較， 等效狀態(tài)對：（ A， B)， (A， E)， (B， E)， (C， F)， D， G 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 等效狀態(tài)對：（ A， B)， (A， E)， (B， E)， (C， F)， D， G 等效類；由所得到的 3個等效對 (A， B)， (A， E)， (B，E)構(gòu)成一個等效類 {A， B， E}。 (C， F)是等效類。狀態(tài) D和 G不與任何其他狀態(tài)等效，它們各自是等效類。 因此，共有 4個等效類為： {A， B， E}， {C， F}， {D}， {G} 最大等效類：這 4個等效類都不是另外的等效類的子集。因此，這 4個等效類是最大等效類。 最小化狀態(tài)表。最大等效類 {A， B， E}， {C， F}， {D}， {G}分別用字母 a、 b、 c、 d表示，可得到化簡后的最小化狀態(tài)表。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 不完全確定狀態(tài)表的化簡是建立在 相容狀態(tài) 的概念之上的。 1） 相容狀態(tài)： 假設(shè) Si和 Sj是不完全確定狀態(tài)表中的兩個狀態(tài)，如果對于所有 有效的輸入序列 ，分別從 Si和 Sj出發(fā)，所得到的 輸出響應(yīng)完全相同 ( 除了不確定的次態(tài)和外部輸出以外 )，則稱狀態(tài) Si和 Sj是相容狀態(tài)， 記作 (Si, Sj)，或者稱狀態(tài) Si和 Sj是相容對。 有效的輸入序列 是指在原始狀態(tài)表中任取一個狀態(tài) Si，如果給定某個輸入序列所得到的 輸出響應(yīng)序列除了最后一個次態(tài)以外，其他次態(tài)都是確定的， 那么這個輸入序列對狀態(tài) Si來講是有效的輸入序列。 例如：“ 1111序列檢測器，對與 A狀態(tài)，外部輸入序列” 1111“是有效的 有效的輸入序列，則” 11111“，不是。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 對于不完全確定狀態(tài)表， 判斷兩個狀態(tài)是否相容 的依據(jù)是表中給出的次態(tài)和輸出。假定狀態(tài) Si和 Sj是不完全確定狀態(tài)表中的兩個現(xiàn)態(tài)，那么，狀態(tài) Si和 Sj相容的條件是在一位輸入的各種取值組合下滿足如下兩個條件： 第一， Si和 Sj的輸出完全相同。 如果 Si和 Sj中有輸出為不確定“ d”，則把“ d”進(jìn)行給定，使 Si和 Sj的輸出完全相同。 第二， Si和 Sj的次態(tài)屬于下列情況之一： 1) Si和 Sj的次態(tài)相同； 2) Si和 Sj的次態(tài)交錯，或者 Si和 Sj次態(tài)為各自的現(xiàn)態(tài)； 3) Si和 Sj的次態(tài)循環(huán)或者 Si和 Sj為相容對； 4) Si和 Sj的次態(tài)如果是不確定的次態(tài)“ d”，則把“ d”進(jìn)行給定次態(tài)，使 Si和 Sj的次態(tài)相同。 相容狀態(tài)不具有傳遞性 ，即不能由 S1和 S2相容、 S2和 S3相容，推出 S1和 S3相容。因?yàn)榕袛鄡蓚€狀態(tài)是否為相容對時，對于不確定的輸出和次態(tài)可以是隨意指定的。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 2) 相容類。相容類是由彼此相容的狀態(tài)構(gòu)成的集合。處于同一相容類中的所有狀態(tài)之間都是兩兩相容的。例如，若有相容對 ( S1， S2 )、 ( S2， S3 )、 ( S3， S4 )、 ( S1， S4 )、 ( S1，S3 )和 ( S2， S4 )，則可構(gòu)成相容類 { S1， S2， S3， S4 }。 3) 最大相容類。如果一個相容類不是任何其他相容類的子集，則該相容類稱為一個最大相容類。由于相容狀態(tài)不具有傳遞性，所以同一原始狀態(tài)表的各最大相容類之間可能存在相同狀態(tài)，也就是同一狀態(tài)可能出現(xiàn)在不同的最大相容類中。 不完全確定狀態(tài)表的化簡過程與完全確定狀態(tài)表的化簡過程相似，只是在某些環(huán)節(jié)的具體處理上有些不同。其步驟如下所述： 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) (1) 畫隱含表，找出全部的相容狀態(tài)對。 在順序比較完成后，進(jìn)行關(guān)聯(lián)比較。如果與之關(guān)聯(lián)的次態(tài)對都是相容的，則狀態(tài)對是相容的。只要某方格中填入的次態(tài)對中有一對不相容，則該方格所對應(yīng)的狀態(tài)對不是相容狀態(tài)，在方格中填入“”標(biāo)記。在隱含表中逐個進(jìn)行關(guān)聯(lián)比較，直到判斷出所有狀態(tài)對是相容狀態(tài)或者不相容狀態(tài)，這時可列出原始狀態(tài)表中的全部相容狀態(tài)對。 (2) 狀態(tài)合并圖。狀態(tài)合并圖是為了求出最大相容類。狀態(tài)合并圖是將不完全確定狀態(tài)表的狀態(tài)以點(diǎn)的形式均勻地分布在圓周上，然后把相容狀態(tài)對用線段連接起來的圖。 圖中圓周上的點(diǎn)表示狀態(tài)，點(diǎn)與點(diǎn)之間的連線表示兩狀態(tài)之間是相容狀態(tài)。所有點(diǎn)之間都有連線的多邊形構(gòu)成一個最大相容類。 不完全確定狀態(tài)表的化簡過程： 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 圖 437 a、 b和 c分別表示包含 3個、 4個和 5個狀態(tài)的最大相容類的狀態(tài)合并圖。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) (3) 閉合覆蓋表。閉合覆蓋表的作用是從最大相容類中選出一組相容類，用來構(gòu)成最小化狀態(tài)表。 在閉合覆蓋表中選出的一組相容類的集合必須滿足以下 3個條件： 1) 覆蓋性。所選出的一組相容類集合應(yīng)包含原始狀態(tài)表的全部狀態(tài)。 2) 最小性。所選出的一組相容類集合中相容類的個數(shù)應(yīng)最少。 3) 閉合性。所選出的一組相容類集合中的任一相容類狀態(tài)，在原始狀態(tài)表中任一輸入條件下產(chǎn)生的次態(tài)，應(yīng)該屬于該集合中的某一個相容類狀態(tài)。 具備覆蓋性、最小性和閉合性條件的最大相容類的集合，稱為最小閉合覆蓋。 最小閉合覆蓋是不完全確定狀態(tài)表化簡的結(jié)果。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) (4) 做出最小化狀態(tài)表。選出一組最小閉合覆蓋之后，將最小閉合覆蓋中的每個相容類用一個新的狀態(tài)符號表示，即可得到與原始狀態(tài)表功能相同的最小化狀態(tài)表。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 例 48 化簡表 423所示的原始狀態(tài)表。 (1) 畫隱含表，得相容狀態(tài)對。 相容狀態(tài)對：（ A,B） ,（ A,C） ,（ A,D） ,（ A,E） ,（ B,D） ,（ C,D）（ C,E） 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) (2) 畫狀態(tài)合并圖，找出最大相容類。 最大相容類為 : {A， B， D}， {A， C， D }， {A， C， E }。 相容狀態(tài)對：（ A,B），（ A,C），（ A,D） ,（ A,E） , （ B,D），（ C,D），（ C,E） 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) (3) 畫閉合覆蓋表，求最小閉合覆蓋。 最小閉合覆蓋可由最大相容類 {A， B， D }和 {A， C， E }組成。 1) 覆蓋性。所選出的一組相容類集合應(yīng) 包含原始狀態(tài)表的全部狀態(tài) 。 2) 最小性。所選出的一組相容類集合中 相容類的個數(shù)應(yīng)最少。 3) 閉合性。所選出的一組相容類集合中的任一相容類狀態(tài)，在原始狀態(tài)表中任一輸入條件下產(chǎn)生的次態(tài)，應(yīng)該屬于該集合中的某一個相容類狀態(tài)。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) (4) 做出最小化狀態(tài)表。假定最小閉合覆蓋中的相容類 {A，B， D }用狀態(tài) a表示，相容類 {A， C， E}用狀態(tài) b表示，代入到原始狀態(tài)表中 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì) 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計(jì)