清華大學(xué)數(shù)字邏輯電路課件四時(shí)序5電路設(shè)計(jì)狀態(tài)化簡(jiǎn)

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

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

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

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

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

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

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

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

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

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

11、審察，把其次態(tài)都在P1中同塊的狀態(tài)仍放入同塊，否則分為新塊，結(jié)果為P2；所分結(jié)果，不同塊的狀態(tài)之間肯定不等價(jià)。同塊中狀態(tài)可能等價(jià)，也可能不等價(jià)。（根據(jù)：因在不同塊中的次態(tài)肯定不等價(jià)，所以在各輸入的作用下，次態(tài)在同塊中的狀態(tài)不等價(jià)，須分割。）4、 連續(xù)分進(jìn)行步驟2，直至PK1PK，分割完畢。所分結(jié)果為最大等價(jià)類集。同塊中狀態(tài)等價(jià)，不同塊狀態(tài)不等價(jià)。（根據(jù)：各塊中，在各輸入的作用下，次態(tài)永同塊，輸出永相同，必等價(jià)。）例1：分割法化簡(jiǎn)。（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時(shí)均同塊，A次態(tài)X1時(shí)與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時(shí)不同塊，分。分（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：分割法化簡(jiǎn)前例。（連續(xù)2個(gè)以上1檢測(cè)）現(xiàn)態(tài)次態(tài)NS輸出Zx=0x=1x=0x=1SA:000SASB00SB:001SCSD