【正文】 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 (4) 做出最小化狀態(tài)表。 3) 閉合性。 2) 最小性。 1) 覆蓋性。 相容狀態(tài)對：（ A,B），（ A,C），（ A,D） ,（ A,E） , （ B,D），（ C,D），（ C,E） 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 (3) 畫閉合覆蓋表，求最小閉合覆蓋。 相容狀態(tài)對：（ A,B） ,（ A,C） ,（ A,D） ,（ A,E） ,（ B,D） ,（ C,D）（ C,E） 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 (2) 畫狀態(tài)合并圖，找出最大相容類。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 例 48 化簡表 423所示的原始狀態(tài)表。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 (4) 做出最小化狀態(tài)表。 具備覆蓋性、最小性和閉合性條件的最大相容類的集合，稱為最小閉合覆蓋。 3) 閉合性。 2) 最小性。 在閉合覆蓋表中選出的一組相容類的集合必須滿足以下 3個條件： 1) 覆蓋性。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 (3) 閉合覆蓋表。所有點之間都有連線的多邊形構(gòu)成一個最大相容類。狀態(tài)合并圖是將不完全確定狀態(tài)表的狀態(tài)以點的形式均勻地分布在圓周上，然后把相容狀態(tài)對用線段連接起來的圖。 (2) 狀態(tài)合并圖。只要某方格中填入的次態(tài)對中有一對不相容，則該方格所對應(yīng)的狀態(tài)對不是相容狀態(tài)，在方格中填入“”標(biāo)記。 在順序比較完成后，進行關(guān)聯(lián)比較。 不完全確定狀態(tài)表的化簡過程與完全確定狀態(tài)表的化簡過程相似，只是在某些環(huán)節(jié)的具體處理上有些不同。如果一個相容類不是任何其他相容類的子集，則該相容類稱為一個最大相容類。例如，若有相容對 ( S1， S2 )、 ( S2， S3 )、 ( S3， S4 )、 ( S1， S4 )、 ( S1，S3 )和 ( S2， S4 )，則可構(gòu)成相容類 { S1， S2， S3， S4 }。相容類是由彼此相容的狀態(tài)構(gòu)成的集合。因為判斷兩個狀態(tài)是否為相容對時，對于不確定的輸出和次態(tài)可以是隨意指定的。 第二， 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”進行給定次態(tài)，使 Si和 Sj的次態(tài)相同。假定狀態(tài) Si和 Sj是不完全確定狀態(tài)表中的兩個現(xiàn)態(tài)，那么，狀態(tài) Si和 Sj相容的條件是在一位輸入的各種取值組合下滿足如下兩個條件： 第一， Si和 Sj的輸出完全相同。 例如：“ 1111序列檢測器，對與 A狀態(tài)，外部輸入序列” 1111“是有效的 有效的輸入序列，則” 11111“，不是。 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是相容對。最大等效類 {A， B， E}， {C， F}， {D}， {G}分別用字母 a、 b、 c、 d表示，可得到化簡后的最小化狀態(tài)表。因此，這 4個等效類是最大等效類。狀態(tài) D和 G不與任何其他狀態(tài)等效，它們各自是等效類。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 2）進行關(guān)聯(lián)比較， 等效狀態(tài)對：（ A， B)， (A， E)， (B， E)， (C， F)， D， G 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 等效狀態(tài)對：（ A， B)， (A， E)， (B， E)， (C， F)， D， G 等效類；由所得到的 3個等效對 (A， B)， (A， E)， (B，E)構(gòu)成一個等效類 {A， B， E}。 解：表 421是有 7個狀態(tài)的原始狀態(tài)表。 將每個最大等效類分別命名作為一個狀現(xiàn)狀命名，構(gòu)成最小化狀態(tài)表。 做出最小化狀態(tài)表。在找出原始狀態(tài)表中的所有等效對以后，使用等效狀態(tài)的傳遞性，確定等效類。在關(guān)聯(lián)比較時，首先要確定隱含表中的哪些次態(tài)需要進一步比較，以確定是否等效，并由此確定原狀態(tài)對是否等效。每個狀態(tài)對的比較結(jié)果有 3種情況：一、 是等效的，在相應(yīng)方格內(nèi)填上“ √”標(biāo)記； 二、 是不等效的，在相應(yīng)方格內(nèi)填上“”標(biāo)記； 三、 是有待于進一步比較的狀態(tài)對，對于這種情況，在隱含表相應(yīng)方格內(nèi)填上相比較的兩個狀態(tài)的次態(tài)。 使用隱含表采用： 1）順序比較， 2）關(guān)聯(lián)比較，找出原始狀態(tài)表中的全部等效狀態(tài)。 (1) 畫隱含表找出全部的隱含狀態(tài)對。即找出原始狀態(tài)表中 所有的等效狀態(tài)對， 然后根據(jù) 等效類 和 最大等效類的概念找出最大等效類。然后將每個最大等效類中的所有狀態(tài)合并為一個新的狀態(tài)，構(gòu)成最小化狀態(tài)表。 完成對原始狀態(tài)表的化簡。如果一個 等效類不是任何其它等效類的子集，則該等效類稱為最大等效類 。它是等效類的一個特例， 也就是任何狀態(tài)與它的自身是等效狀態(tài)。 在等效類關(guān)系中，等效對是對兩個狀態(tài)而言的，而等效類是兩個狀態(tài)或多個狀態(tài)組成的一個狀態(tài)集合。 例如， (S1， S2)和 (S2， S3)是等效狀態(tài)，根據(jù)等效狀態(tài)的傳遞性，可以得到 S1， S3是等效狀態(tài)。 等效類是指由彼此等效的若干狀態(tài)構(gòu)成的集合。 狀態(tài)化簡首先是： 找出原始狀態(tài)表中 所有的等效狀態(tài) ，然后使用下面的概念繼續(xù)對等效狀態(tài)進行處理。如果 S1和 S2等效， S2和 S3等效，那么 S1和 S3等效。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 次態(tài)為 等效對，例如， S1的次態(tài)是 S3， S2的次態(tài)是 S4，盡管 S3和 S4既不相同，也不交錯或循環(huán)，但是若以 S3和 S4作為現(xiàn)態(tài)，在一位輸入的各種取值下，其輸出相同而且次態(tài)相同或者交錯或者循環(huán)，即 S3和 S4等效，那么， S1和 S2也是等效狀態(tài)。 在 3）中， 所謂 次態(tài)循環(huán) 是指在某種輸入取值時，原始狀態(tài)表中的兩個狀態(tài)，次態(tài)之間構(gòu)成了循環(huán)。 在 2) 中，所謂 次態(tài)交錯 ， 是指在某種輸入取值時， Si的次態(tài)為 Sj， Sj的次態(tài)為 Si。 下面介紹： 判斷兩個狀態(tài)是否是等效狀態(tài)？ 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 假定 Si和 Sj是完全確定的原始狀態(tài)表中的兩個現(xiàn)態(tài)，則 Si和Sj是否等效，可歸納為在一位輸入的各種取值組合下滿足以下兩個條件：第一， Si和 Sj的輸出相同。 實際上在做原始狀態(tài)表中，對 每個狀態(tài)已經(jīng)考慮了在一位輸入各種取值下的次態(tài)和輸出。 這里所說的 所有可能的輸入序列，是指輸入序列的長度有 無窮位 ，輸入序列的結(jié)構(gòu)是 任意的組合 。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 (1) 等效狀態(tài)。 假設(shè) Si和 Sj是完全確定狀態(tài)表中的兩個狀態(tài)，如果對于所有可能的輸入序列，分別從 Si和 Sj出發(fā)，所得到的輸出響應(yīng)完全相同，則稱狀態(tài) Si和Sj是等效狀態(tài)， 記作 (Si, Sj)。為此，在討論化簡方法之前，先介紹狀態(tài)化簡中的幾個概念。對于完全確定原始狀態(tài)表和不完全確定原始狀態(tài)表使用不同的概念作為狀態(tài)化簡的原理，在處理過程上也有所不同。 通常沒有多余狀態(tài)的狀態(tài)表稱為最小化狀態(tài)表。為了降低時序邏輯電路的成本和復(fù)雜性，應(yīng)當(dāng)盡可能地使原始狀態(tài)表中包含的狀態(tài)數(shù)目達到最少。在構(gòu)造的原始狀態(tài)圖和原始狀態(tài)表中往往存在多余的狀態(tài)。它的 次態(tài)、輸出都是確定的 。而狀態(tài) B、 C、 D由于 x輸入不會為“ 0”，不可能發(fā)生輸出和次態(tài)。在狀態(tài) D、 x輸入為“ 1”時，輸出為“ 1”是確定的用于引爆，次態(tài)沒有了，即次態(tài)是不確定的。 在狀態(tài)B、 x輸入為“ 1”時，輸出為“ 0”， 次態(tài)為狀態(tài) C。狀態(tài) B表示收到了第一個“ 1”輸入，狀態(tài) C表示收到了連續(xù)兩個“ 11‘輸入，狀態(tài) D表示收到了連續(xù)三個” 111“輸入。它與一般序列檢測器有兩點不同： 一是 外部輸入 x不輸入“ 1”時， 始終為輸入“ 0” ，一旦輸入一個“ 1”，則一定是不被“ 0”間斷； 二是 在收到 4個“ 1”以后，產(chǎn)生引爆，同步時序邏輯電路就不存在了，因此不再有次態(tài)轉(zhuǎn)移產(chǎn)生。試建立該電路的 Mealy型原始狀態(tài)圖和狀態(tài)表。一旦 需要引爆時 ，則從 x連續(xù)輸入 4個“ 1” (不被“ 0”間斷 )。該電路有一個外部輸入端 x和一個外部輸出端 Z。根據(jù)這種原始狀態(tài)圖和狀態(tài)表設(shè)計的時序邏輯電路稱為 不完全確定時序邏輯電路 。 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 Mealy型原始狀態(tài)表 Moore型原始狀態(tài)表 第 4章 同步時序邏輯電路 同步時序邏輯電路的設(shè)計 不完全確定時序邏輯電路 原始狀態(tài)圖的建立 在實際應(yīng)用中，根據(jù)設(shè)計要求建立的原始狀態(tài)圖和原始狀態(tài)表中有時會出現(xiàn)次態(tài)和輸出 不可能