清華大學數字邏輯電路課件四時序5電路設計狀態(tài)化簡

1、第四章 時序電路Sequential Circuits434 同步時序電路設計（2）狀態(tài)化簡（Reduction of State）(書263273) l 同一時序邏輯，不同狀態(tài)設立方案所得原始狀態(tài)圖中狀態(tài)數之所以不同是因為狀態(tài)數目較多的設計結果中存在著多余狀態(tài)。l 如消除多余態(tài)，則可得相同的設計結果。l 無法確保通過合適的狀態(tài)設立方法直接得到最少狀態(tài)數的原始狀態(tài)圖，但有某些規(guī)范方法將原始狀態(tài)圖中的多余狀態(tài)消除，此過程之為狀態(tài)化簡。l 隨著集成電路密度的提高和可編程器件的發(fā)展，以及出于設計中的特殊考慮，不一定將電路狀態(tài)化至最簡，但電路盡量簡化的原則還是應該遵循的。l 狀態(tài)化簡工作可由計算機完成

2、。l 所謂多余狀態(tài)就是狀態(tài)圖中存在著可被另一狀態(tài)所代替的狀態(tài)。l 可以相互代替的狀態(tài)稱之為狀態(tài)等價。l 如能找出原始狀態(tài)圖中所有相互等價態(tài)，則可只留不相互等價態(tài)，得到最簡狀態(tài)圖。狀態(tài)等價如果將同一時序電路的兩個狀態(tài)Si和Sj分別作為起始態(tài)，不論何種輸入序列，電路均產生相同的輸出序列，我們稱Si和Sj是等價狀態(tài)或等價對，記作SiSj。等價具有傳遞性。即如有SiSj，SjSK，則有SiSK。等價類：多個相互等價狀態(tài)之集合。如上述SiSjSk構成一等價類。最大等價類：在同一時序電路中，包含所有狀態(tài)的等價類的集合。不與其它任何狀態(tài)等價的單個狀態(tài)也須看成一個等價類。 等價的時序電路：滿足等價條件的兩個狀

3、態(tài)分別在兩個時序電路M1和M2中，兩個狀態(tài)也為等價態(tài)。兩個時序電路M1M2，它們各自的每個狀態(tài)都能在對方電路中至少找到一個等價態(tài)，則稱M1M2 是等價的時序電路，否則，是可區(qū)分的時序電路。等價態(tài)可以互相替代或合并：因從輸入和輸出的角度看，等價態(tài)的表現相同，無法區(qū)分。狀態(tài)化簡：找出時序電路原始狀態(tài)圖中的最大等價類，并從每個等價類選一狀態(tài)作為代表留用，消除其余態(tài)，得到最小化的狀態(tài)圖和表。完全確定的時序電路：在原始狀態(tài)圖、表中，對于各種輸入，每個狀態(tài)都有唯一確定的次態(tài)和輸出。包含有不確定次態(tài)、輸出時序電路為不完全確定時序電路。完全確定的時序電路狀態(tài)：化簡方法1：蘊含圖法。方法2：分隔法。(補充)蘊含

4、圖法化簡： 原理與步驟：1原始狀態(tài)集中尋找所有的狀態(tài)等價對；2組合出最大等價類；3狀態(tài)合并，構成最簡狀態(tài)集；4由最簡狀態(tài)集導出最小化狀態(tài)圖和表。關鍵步驟：1.列出原始狀態(tài)集中所有可能狀態(tài)對；2.對所有狀態(tài)對等價判定。組對易，判定難，利用推論。根據等價定義，等價的先決（必要）條件是在所有可能輸入情況下狀態(tài)對輸出必須相同，不相同肯定不等價；相同則可能等價，真等價否？取決于轉入次態(tài)等價對后，所有可能輸入作用下輸出的情況。由此可得狀態(tài)對等價判定推論：推論1：在所有可能的相同輸入條件下，狀態(tài)對輸出只要有不同，兩態(tài)一定不等價；推論2：在所有可能的相同輸入條件下，狀態(tài)對輸出均相同，且對應次態(tài)對等價，則兩態(tài)等

5、價；對應次態(tài)不等價，此兩態(tài)也不等價。如狀態(tài)對SiSj現對所有可能相同輸入情況其輸出均相同，則需考慮次態(tài)對情況才能對狀態(tài)對此SiSj進行等價判定。對應次態(tài)對可能出現下兩種情況：1、 原態(tài)（仍為SiSj）；交錯原態(tài)（即為SjSi）；同態(tài)（即同為Sk）2隱含態(tài)。（即對于所有可能相同輸入，新的次態(tài)對SmSn的輸出相同，則稱為狀態(tài)隱含。如次態(tài)對的次態(tài)對最終為原態(tài)對，則稱狀態(tài)互為隱含。）不難驗證，當次態(tài)對屬這兩種情況時，對所有相同的輸入序列狀態(tài)對都產生相同輸出序列，因此，欲判狀態(tài)對等價，由此得推論3：推論3：在所有可能的相同輸入條件下，狀態(tài)對的輸出相同，且對應次態(tài)對為原態(tài)、交錯原態(tài)、同態(tài)和互為隱含時，狀態(tài)

6、對等價。根據推論1、2、3，可對狀態(tài)對進行直觀地等價判定。如狀態(tài)對的等價判定出現需對次態(tài)的次態(tài)繼續(xù)進行等價判定，稱追蹤判定，經追蹤判定最終終可根據三推判定等價否。對于比較簡單的原始狀態(tài)圖表可用觀察法化簡。例：觀察法簡化三位一判101檢測器。觀察可得，狀態(tài)S3、S4和S6在所有同樣輸入情況下，輸出相同，且次態(tài)相同，因此相互等價，可合并為一個狀態(tài)，用狀態(tài)S3代表。得最小化的狀態(tài)圖。三位一判101 檢測器 簡化狀態(tài)圖三位一判101檢測器 原始狀態(tài)圖 例：觀察法化簡不重碼101檢測器原始狀態(tài)圖。 S0和S3輸出同態(tài)，相互等價，合并為一狀態(tài)S0，得簡化狀態(tài)圖。不重碼101檢測器不簡化狀態(tài)圖不重碼101檢

7、測器原始狀態(tài)圖 蘊含表法等價對判定適于比較復雜的原始狀態(tài)圖表，可防止遺漏，條理清晰。蘊含表狀態(tài)等價判定步驟： 設全部原始狀態(tài)按序排列為S0SN。 1 建立網格，“掐頭”“去尾”標注。網格羅列了所有的狀態(tài)對。2 根據原始狀態(tài)表逐格進行初始判定并填寫結果（等價，不等價，隱含）。3 對隱含狀態(tài)對進行追蹤判定，直至判定結果確定為等價或不等價。4完成追蹤判定后，隱含表中所有非打“×”方格對應的狀態(tài)對即是我們要找的全部等價對。例：對連續(xù)3個1檢測解1的原始狀態(tài)圖表表格法狀態(tài)化簡?，F態(tài)次態(tài)NS輸出Zx=0x=1x=0x=1SA:000SASB00SB:001SCSD00SC:010SESF00SD

8、:011SGSH01SE:100SASB00SF:101SCSD00SG:110SESF00SH:111SGSH01 1初始判定。（先審輸出，再看次態(tài)）2追蹤判定。如方格中有兩項隱含狀態(tài)對時，只要其中一項被判定不等價，則本方格對應狀態(tài)為不等價，不必再對另項進行追蹤判定。（先判不等價）3 列出所有等價狀態(tài)對。SASC，SASE，SASG，SBSF，SCSE，SCSG，SDSH，SESG。4 導出最大等價類集。注意不要忘記檢查完備性，即所有原始狀態(tài)都必須出現在最大等價類集中。所得最大等價類集為： SASCSESG，SBSF，SDSH。5 合并狀態(tài)，得最簡狀態(tài)集。用S0、S1、S2順序分別代表所得三

9、個最大等價類。6 列最小化狀態(tài)表，畫最小化狀態(tài)圖?，F態(tài)次態(tài)輸出x=0x=1x=0x=1S0S0S100S1S0S200S2S0S201 最小化狀態(tài)表最小化狀態(tài)圖 可以發(fā)現，與例解2的原始狀態(tài)圖與表完全相同。這說明，最簡狀態(tài)圖是唯一的。 例：化簡下示原始狀態(tài)表?，F態(tài)S(tj)次態(tài)S(tj+1)輸出z(tj)x=0x=1x=0x=1S1S7S100S2S7S100S3S1S501S4S2S601S5S7S301S6S7S201S7S1S700 1.全部等價狀態(tài)對為：S1S2,S1S7,S2S7,S3S5。2.最大等價類集為： S1S2S7，S3S5，S4，S6。3 千萬不要忘記，最簡狀態(tài)集。S1、

10、S3、S4、S6。4 最小化狀態(tài)表?，F態(tài)S(tj)次態(tài)S(tj+1)輸出z(tj)x=0x=1x=0x=1S1S1S100S3S1S301S4S1S601S6S1S101分割法化簡：蘊含表法化簡思路是在原始狀態(tài)集中尋找等價類集。與之對應，分割法是對原始狀態(tài)集逐步分割為互不等價類，最后得到最大等價類集。（負向思維）原理與步驟：1、 設原始狀態(tài)集為P0。2、 把P0分隔不同塊，即把各種輸入情況下輸出相同的狀態(tài)放入同塊，結果為P1；所分結果，不同塊的狀態(tài)之間肯定不等價。同塊中狀態(tài)可能等價，也可能不等價。（根據：在各輸入的作用下，輸出不同肯定不等價。）3、 對P1進行繼續(xù)分隔，即對每塊中狀態(tài)的次態(tài)進行

11、審察，把其次態(tài)都在P1中同塊的狀態(tài)仍放入同塊，否則分為新塊，結果為P2；所分結果，不同塊的狀態(tài)之間肯定不等價。同塊中狀態(tài)可能等價，也可能不等價。（根據：因在不同塊中的次態(tài)肯定不等價，所以在各輸入的作用下，次態(tài)在同塊中的狀態(tài)不等價，須分割。）4、 連續(xù)分進行步驟2，直至PK1PK，分割完畢。所分結果為最大等價類集。同塊中狀態(tài)等價，不同塊狀態(tài)不等價。（根據：各塊中，在各輸入的作用下，次態(tài)永同塊，輸出永相同，必等價。）例1：分割法化簡。（p306 8-11）P1=（ADFG）(BCEH)00 DDDG CCCB01 DBDG DDFD11 FAAA EEEE10 AFFA FAAAP2=（AFG）(

12、D)(BCEH)00 DDG CCCB 01 DDG DDFD11 FAA EEEE10 AFA FAAAP3=(AF)(G)(D)(BCH)(E)P4P3令：a=（AF）,b=(BCH),c=(D),d=(E),e=(G).例2：PS NS/ZX=0X=1AC/1B/0BC/1E/0CB/1E/0DD/0B/1EE/0A/1(ABCDE)輸出 11100輸出 00011 ABC輸出同DE輸出同分（ABC）（DE） (ABC) (DE)次態(tài) CCB DE次態(tài) BEE BA BC次態(tài)在x0、1時均同塊，A次態(tài)X1時與BC不同塊，分出。D、E次態(tài)均同塊，不分。分（A）（BC）（A）(BC) (DE)次態(tài) C CB DE次態(tài) B EE BAB、C次態(tài)均同塊，不分。DE次態(tài)X1時不同塊，分。分（D）（E）(A) (BC) (D) (E)次態(tài) C CB D E次態(tài) B EE B A(A) (BC) (D) (E) P0X=0 X=1 P1 X=0 X=1 P2 X=0 X=1 P3 X=0 X=1 P4=P3例3：分割法化簡前例。（連續(xù)2個以上1檢測）現態(tài)次態(tài)NS輸出Zx=0x=1x=0x=1SA:000SASB00SB:001SCSD