【正文】 個狀態(tài)均等效。最大等效類的數(shù)量就是簡化后的狀態(tài)數(shù)。 一般講，對復雜的原始狀態(tài)表，需要將觀察法與隱含表法結合起來用，先用前者消去明顯多余的狀態(tài)，再用后者作進一步化簡。而 √ 故 B、 E等效， A、 E也等效。 76 它化簡的步驟與前面介紹的完全確定狀態(tài)表的類似，但是因為其中的部分狀態(tài)和輸出值不確定（任意項），所以不能用狀態(tài)等效的概念，只能用 狀態(tài)相容 的概念來進行化簡。 ，次態(tài)滿足下列條件之一： d （ 2）相容類 若干個相容狀態(tài)的集合稱為相容類。 （ 3）最大相容類 是指不包含在任何其他相容類中的相容類。 以下分別為 5個狀態(tài)的最大相容類合并圖。 ，確定最大相容類。 作最小化狀態(tài)表即 選擇一個相容類（包括最大相容類）集合，將每個相容類的狀態(tài)用一個新的狀態(tài)來 代替，以得到一個新的狀態(tài)表。 覆蓋： 是指所選的相容類（包括最大相容類）集合中，包含了原狀態(tài)表中的全部狀態(tài)，即：原狀態(tài)表中任何一個狀態(tài)至少包含在一個所選的相容類中。 81 下面舉例說明。 從狀態(tài)合并圖中可確定出最大相容類為： (A,B,C)， (A,C,D)， (A,D,E) 次態(tài) / 輸出 X=0 X=1 A D/d A/d B E/0 A/d C D/0 B/d D C/d C/d E C/1 B/D 現(xiàn)態(tài) 83 滿足覆蓋的相容類集合可有下列幾種組合： (A,B,C)， (A,C,D)， (A,D,E) (1) 閉合 (A,B,C)， (D,E) (2) 閉合 (B,C)， (A,D,E) (3) 不閉合 若選（ 1），則用 閉合表一 來檢驗其閉合情況，顯然滿足閉合條件，再選（ 2），則用 閉合表二 來檢驗其閉合情況，也滿足閉合條件。 注：不完全確定狀態(tài)表的最小化狀態(tài)表不是唯一的。 ，即哪個狀態(tài)分配哪個代 碼。即 故已知電路的狀態(tài)數(shù)便可由上式求出狀態(tài)需分配的二進制代碼的位數(shù)。如用 2位代碼對四個狀態(tài)進行編碼，則方案可達 24種（ 4的全排列為 4！＝ 24）。 注： 對于某些狀態(tài)表，滿足前面所給定的分配規(guī)則的 分配方案不一定是唯一的 ，設計者可以任選一種。 根據(jù)規(guī)則 1，狀態(tài) A與 C， B與 D， A與 D均應分配相鄰的二進制代碼；根據(jù)規(guī)則 2，狀態(tài) E與 B， A與 D， E與 A， A與 B， D與 C均應分配相鄰的二進制代碼；根據(jù)規(guī)則 3，狀態(tài) A與 C， A與 E， C與 E均應分配相鄰的二進制代碼；根據(jù)規(guī)則 4 ，狀態(tài) A應分配邏輯 0。下面先介紹各種 觸發(fā)器的激勵表 。參見第 5章 47頁始的 PPT。 94 下面舉例來具體說明如何由二進制狀態(tài)表與觸發(fā)器激勵表來確定 激勵函數(shù) 及 輸出函數(shù) 的表達式。 輸出函數(shù)式則可直接由二進制狀態(tài)表的 z值作出輸出函數(shù)卡諾圖便得到簡化后的輸出函數(shù)。 然后，根據(jù)激勵函數(shù)及輸出函數(shù)表達式畫出組合部分的 邏輯圖。 解： 據(jù)題意，電路有一個輸入端 x，用以接收二進制信號序列，還有一個輸出端 z，用來指示對 “ 111”序列的識別，且輸入與輸出之間的關系見下面典型序列所示： x： 1 1 0 1 1 1 1 0 z： 0 0 0 0 0 1 1 0 同步時序邏輯電路設計舉例 101 據(jù)題意，電路在連續(xù)收到 3個 1（或者 3個以上 1）時，輸出為 1，其它情況輸出則為 0，因此，要求電路能記憶收到 1個 1，連續(xù)兩個 1，連續(xù) 3個 1的情況。將等效對（ S2， S3）合并為一個狀態(tài)，記為 S2，則可作出最小化狀態(tài)表如下： 次態(tài) /輸出 X=0 X=1 S0 S0/0 S1/0 S1 S0/0 S2/0 S2 S0/0 S2/1 現(xiàn)態(tài) X=0 X=1 00 00/0 01/0 01 00/0 11/0 11 00/0 11/1 zyy nn )1(1)1(2 ??12 yy103 因為最小化狀態(tài)表中只有三個狀態(tài)，所以只需要 2位二進制 代碼來表示各個狀態(tài)。 由規(guī)則 3知， S0 與 S1應分配相鄰的二進制代碼。 105 將上表中的激勵函數(shù)值及狀態(tài)表中的輸出值填入相應的卡諾圖，如下所示： 0 1 00 0 0 01 0 1 11 d d 10 d d 0 1 00 d d 01 d d 11 1 0 10 d d 0 1 00 0 1 01 d d 11 d d 10 d d 0 1 00 d d 01 1 0 11 1 0 10 d d 0 1 00 0 0 01 0 0 11 0 1 10 d d 12yy 12yy 12yy 12yy 12yyx x x x xJ2 K2 J1 K1 。 由以上分析得到的狀態(tài)分配圖及編碼如下： y2 0 1 y2 y1 y1 0 S0 S0 0 0 1 S1 S2 S1 0 1 S2 1 1 將以上分配的狀態(tài)編碼代入最小化狀態(tài)表中，便可得到二進制狀態(tài)表。 由規(guī)則 1知， S1 與 S2， S0與 S2， S0與 S1均應分配相鄰的二 進制代碼。 102 由于獲得的是完全確定的狀態(tài)表，故用觀察法化簡便可以得等效狀態(tài)對為（ S2， S3）。 例如：前面剛講的那個例子，其激勵函數(shù)和輸出函數(shù) 表達式為： 112 xyyyz ??xKyxJ??2121111??KJ99 根據(jù)以上各表達式，再按剛才介紹的方法， 先畫觸發(fā)器 ，再畫組合部分 ， 從而作出邏輯電路圖如下 ： 100 例 1. 設計一個序列檢測器，用來檢測二進制序列。 根據(jù)激勵函數(shù)和輸出函數(shù)的邏輯表達式，就可以畫出電 路圖。 現(xiàn)態(tài)y2y1 X=0 X=1 00 11/0 01/0 01 00/0 00/1 11 00/1 10/1 10 01/0 11/0 xy2 y1 激勵函數(shù) J2 K2 J1 K1 000 1 d 1 d 001 0 d d 1 010 d 1 1 d 011 d 1 d 1 100 0 d 1 d 101 0 d d 1 110 d 0 1 d 111 d 0 d 1 zyy nn )1(1)1(2 ??二進制狀態(tài)表 激勵函數(shù)真值表 95 解： 根據(jù)給定的二進制狀態(tài)表和 JK觸發(fā)器的激勵表可列出 激勵函數(shù)真值表 （如狀態(tài)表右側所示）。 在選定觸發(fā)器后，就可以根據(jù)二進制狀態(tài)表和選定的觸發(fā)器的激勵表求出 激勵函數(shù) 和 輸出函數(shù) 。 也即， 觸發(fā)器的激勵表說明了從現(xiàn)態(tài)轉移到某種次態(tài)時，對輸入條件的要求。 91 采用不同類型的觸發(fā)器作為存儲電路，將影響所設計電路的繁簡程度?，F(xiàn)在在工程上采用的方法雖不能說是最佳，也接近最佳，有一定的實用價值。目前，還不能準確的估計采用那種狀態(tài)分配方案更有利于獲得最簡單的電路結構。 以上解決了第一個問題，如何解決第二個問題呢？ mr ?2 mr2lo g?38lo g 2 ??r 二進制代碼的位數(shù)確定后，可以有許多種的狀態(tài)分配方案。 r個觸發(fā)器能表示的狀態(tài)數(shù)為 個， 故各狀態(tài)的二進制代碼 的位數(shù)就等于觸發(fā)器的位數(shù) （個數(shù)）。 狀態(tài)分配 則是根據(jù)最小化狀態(tài)表的狀態(tài)數(shù)，確定觸發(fā)器 的個數(shù)，指定每個狀態(tài)的二進制編碼。 若將狀態(tài) A、 B、 C用 a表示，狀態(tài) D、 E用 b表示，則可得 簡化表 （見原狀態(tài)表右側）。 次態(tài) / 輸出 X=0 X=1 A D/d A/d B E/0 A/d C D/0 B/d D C/d C/d E C/1 B/D 次態(tài) / 輸出 X=0 X=1 a b/0 a/d b a/1 a/d 現(xiàn)態(tài) 現(xiàn)態(tài) 最小化狀態(tài)表 82 解： ，并找出相容狀態(tài)對。 最?。?指滿足覆蓋的相容類（包括最大相容類）的數(shù)目最少。它與原先的狀態(tài)表所表示的邏輯功能應相同。 且每種方法的步驟也與完全確定狀態(tài)表的簡化一樣。 S2 S3 S2 S4 S2 S3 S1 S1 S1 圖 a S3 S4 S5 圖 b 圖 c （ 4）狀態(tài)合并圖 它 是用來從相容對中快速尋找最大相容類的工具圖。 78 將原始狀態(tài)表中的所有狀態(tài)以點的形式均勻地標在一個圓周上，然后將所有相容的狀態(tài)用線段連接起來。如相容類（ S1， S2， S3）中， S1與S2相容， S2與 S3相容， S1與 S3也相容。不完全確定狀態(tài)表的簡化就是根據(jù)這一原則進行的。 因此得等效狀態(tài)對是： (A,B)， (A,E)， (B,E)， (C,F) （ 2）再確定最大等效類 根據(jù)等效關系的傳遞性，等效對 (A,B)， (A,E)， (B,E)可構成等效類為 (A,B,E)。 A與 B等效取決于 C與 F是否等效， …… 。 72 注： 最大等效類的集合必須覆蓋原始狀態(tài)表中的全部狀態(tài)，這樣得到的最小化狀態(tài)表才與原始狀態(tài)表等效。 即最大等效類集合中，各最大等效類沒有公共狀態(tài)。 若 次態(tài)對不等效 （只要有一對不等效），則原狀態(tài)對不等效，并 在小方格內添加 / 表示。 （ 1）作隱含表，尋找等效狀態(tài)對 隱含表是一個正直角三角形表格：兩直角邊的小方格數(shù)分 別等于原始狀態(tài)表中的狀態(tài)數(shù)減 1，且左垂直方向從上到下，按 原始狀態(tài)表中的狀態(tài)順序標注，但 “ 缺頭 ” ；水平方向從左到右 也是按表的狀態(tài)順序標注，但 “ 缺尾 ” 。 由于以上等效類不包含在任何其它等效類中，因此，等效類 (S1,S2)， (S3,S5)， (S4)， (S6)即為最大等效類。由于它們在 x=0和 x=1時的輸出均相同，并且次態(tài)也相同，故 S3與 S5等效。一直 到剩下的狀態(tài)不能再合并而得到一個最小化的狀態(tài)表為止。 其 具體過程 為： 先觀察狀態(tài)表中的輸出部分，找出輸出 完全相同的那些現(xiàn)態(tài)，再進一步觀察其次態(tài)是否相同、交錯、 循環(huán)或者次態(tài)對等效。 利用上述判別狀態(tài)等效的條件及狀態(tài)等效的性質，便可 簡化原始狀態(tài)表。即若干個狀態(tài)集合中，任何兩個狀態(tài)都相互等效，則將這 些個狀態(tài)組成一個等效類。 次態(tài)循環(huán) 是指在次態(tài)之間的關系構成閉環(huán)。 記做（ S1， S2），此時 S1與 S2可以合并為一個狀態(tài)，完全確定狀態(tài)表的簡化是根據(jù)這一原則進行的。最小化狀態(tài)表包 含的狀態(tài)數(shù)目最少，它與原始的狀態(tài)表相比，雖代表的內部結 構不同的電路，但均具有相同的邏輯特性，也即：對于任意的 輸入，他們對應的輸出總是一樣的。 一般狀態(tài)圖中不一定要求標 d項，對不可能出現(xiàn)的情況是隱含的。 x CP z CP x 0 1 1 1 1 z 圖 a 圖 b 引爆電路 59 解： 根據(jù)題意，設電路的初態(tài)為 S0，因電路需記憶住 4個連續(xù)的 1信號，故需增設狀態(tài) S1,S2和 S3，用其分別表示電路收到的 1個 1， 2個 1和 3個 1的狀態(tài)。當 x=1時，在四個時鐘脈沖的作用下，使電路的輸出為z=1。（因為它可能是又一個 101序列的開始） 當電路處于 S2時，若輸入為 0，則輸出為 0，且狀態(tài)轉移至 S0，以便重新開始檢測。 若第一個輸入為 1，則可能是檢測序列 101的第一個數(shù)碼，輸出為 0，狀態(tài)從 S0轉移到 S1，表示電路已收到檢測序列的第一個數(shù)碼；若第二個輸入為 0，則輸出為 0，狀態(tài)從 S1轉到 S2，表示已收到 10序列；如果第三個輸入為 1，則輸出應為 1（因為此時電路已經(jīng)收到 101序列，狀態(tài)從 S2轉至 S3，如上圖 b ： 55 S3 S2 S1 S0 0/0 0/0 1/1 0/0 0/0 1/0 1/0 1/0 3. 進一步完善原始狀態(tài)圖