有限狀態(tài)機(jī)的分析

1、有限狀態(tài)機(jī)的分析有限狀態(tài)機(jī)的分析狀態(tài)最簡(jiǎn)化狀態(tài)最簡(jiǎn)化最少的狀態(tài)需要最少的狀態(tài)位最少的狀態(tài)需要最少的狀態(tài)位最少的位需要最少的邏輯方程最少的位需要最少的邏輯方程狀態(tài)最簡(jiǎn)化方法狀態(tài)最簡(jiǎn)化方法行匹配法行匹配法蘊(yùn)含表方法蘊(yùn)含表方法狀態(tài)分配策略狀態(tài)分配策略順序編碼順序編碼隨機(jī)編碼隨機(jī)編碼單點(diǎn)編碼單點(diǎn)編碼面向輸出的編碼面向輸出的編碼啟發(fā)式編碼啟發(fā)式編碼有限狀態(tài)機(jī)的劃分有限狀態(tài)機(jī)的劃分VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz1VIII - Working with Seque

2、ntial Logic Copyright 2004, Gaetano Borriello and Randy H. Katz2通用有限狀態(tài)機(jī)設(shè)計(jì)過(guò)程通用有限狀態(tài)機(jī)設(shè)計(jì)過(guò)程n(1) (1) 定義輸入和輸出定義輸入和輸出n(2) (2) 定義狀態(tài)機(jī)可能的狀態(tài)定義狀態(tài)機(jī)可能的狀態(tài)q狀態(tài)化簡(jiǎn)狀態(tài)化簡(jiǎn)n(3) (3) 用二進(jìn)制對(duì)狀態(tài)和輸出進(jìn)行編碼用二進(jìn)制對(duì)狀態(tài)和輸出進(jìn)行編碼q狀態(tài)分配或狀態(tài)編碼狀態(tài)分配或狀態(tài)編碼q輸出編碼輸出編碼q可能的輸入編碼可能的輸入編碼n(4) (4) 選擇適當(dāng)?shù)倪壿媽?shí)現(xiàn)狀態(tài)和輸出選擇適當(dāng)?shù)倪壿媽?shí)現(xiàn)狀態(tài)和輸出q組合邏輯的實(shí)現(xiàn)和優(yōu)化組合邏輯的實(shí)現(xiàn)和優(yōu)化q步驟步驟2 2和和3 3對(duì)最

3、終的邏輯將產(chǎn)生很大的影響對(duì)最終的邏輯將產(chǎn)生很大的影響例：簡(jiǎn)單的自動(dòng)售貨機(jī)例：簡(jiǎn)單的自動(dòng)售貨機(jī)自動(dòng)售貨機(jī)在收到自動(dòng)售貨機(jī)在收到1515美分之后就會(huì)給出一件商品，這臺(tái)機(jī)器具有美分之后就會(huì)給出一件商品，這臺(tái)機(jī)器具有能夠接收能夠接收5 5美分和美分和1 1角硬幣的單個(gè)投幣口，每次投入一枚硬幣，其角硬幣的單個(gè)投幣口，每次投入一枚硬幣，其中機(jī)械傳感器用來(lái)指示插入投幣口是中機(jī)械傳感器用來(lái)指示插入投幣口是5 5美分還是美分還是1 1角，控制器的輸角，控制器的輸出導(dǎo)致一件商品交到顧客手中出導(dǎo)致一件商品交到顧客手中兩個(gè)假設(shè)簡(jiǎn)化設(shè)計(jì)：兩個(gè)假設(shè)簡(jiǎn)化設(shè)計(jì)：不找零不找零在每次使用前，機(jī)器都會(huì)復(fù)位在每次使用前，機(jī)器都會(huì)復(fù)位

4、VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz3自動(dòng)售貨機(jī)自動(dòng)售貨機(jī)FSMNDResetClockOpen硬幣傳感器硬幣傳感器商品釋放機(jī)制商品釋放機(jī)制1 1、理解問(wèn)題、理解問(wèn)題假設(shè)：投入假設(shè)：投入5 5美分，在美分，在單個(gè)周期內(nèi)單個(gè)周期內(nèi)N N為真；投為真；投入入1 1角，在單個(gè)周期內(nèi)角，在單個(gè)周期內(nèi)D D為真；在上一次復(fù)位之為真；在上一次復(fù)位之后，若收到后，若收到1515美分或更美分或更多，則狀態(tài)機(jī)多，則狀態(tài)機(jī)OpenOpen為真，為真，并保持一個(gè)周期并保持一個(gè)周

5、期例：簡(jiǎn)單的自動(dòng)售貨機(jī)例：簡(jiǎn)單的自動(dòng)售貨機(jī)2 2、有限狀態(tài)機(jī)抽象表達(dá)、有限狀態(tài)機(jī)抽象表達(dá)列出最終能給出商品的輸入順序列出最終能給出商品的輸入順序: :3 3個(gè)個(gè)5 5美分：美分：N N，N N，N N2 2個(gè)個(gè)5 5美分，再美分，再1 1角：角：N N，N N，D D1 1角，角，5 5分：分：D D，N N5 5分，分，1 1角：角：N N，D D2 2個(gè)個(gè)1 1角：角：D D，D D畫狀態(tài)圖畫狀態(tài)圖: :輸入輸入: N, D, reset, clk: N, D, reset, clk輸出商品輸出商品: open: open假設(shè)假設(shè): :假設(shè)信號(hào)假設(shè)信號(hào)N N和和D D從來(lái)不會(huì)同時(shí)為真從來(lái)不

6、會(huì)同時(shí)為真省略了自環(huán)省略了自環(huán) N=D=0 (no coin)N=D=0 (no coin)只將只將openopen信號(hào)為真時(shí)列出信號(hào)為真時(shí)列出VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz4S0ResetS2DS6openDS4openDS1NS3NS5openNS8openDS7openN例：簡(jiǎn)單的自動(dòng)售貨機(jī)例：簡(jiǎn)單的自動(dòng)售貨機(jī)3 3、狀態(tài)最簡(jiǎn)化：、狀態(tài)最簡(jiǎn)化：狀態(tài)狀態(tài)S4S4S8S8具有等價(jià)，可合并成一個(gè)狀態(tài)具有等價(jià)，可合并成一個(gè)狀態(tài)每個(gè)狀態(tài)表示接受到錢的數(shù)量

7、每個(gè)狀態(tài)表示接受到錢的數(shù)量VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz5最簡(jiǎn)化的符號(hào)狀態(tài)轉(zhuǎn)換表最簡(jiǎn)化的符號(hào)狀態(tài)轉(zhuǎn)換表presentinputsnextoutputstateDNstateopen 000 0001 501010011 500 5001100101501110001000115010150111515100Reset50NNN + D100D15openD狀態(tài)圖狀態(tài)圖狀態(tài)轉(zhuǎn)換表狀態(tài)轉(zhuǎn)換表例：簡(jiǎn)單的自動(dòng)售貨機(jī)例：簡(jiǎn)單的自動(dòng)售貨機(jī)4 4、進(jìn)行狀態(tài)分配、進(jìn)

8、行狀態(tài)分配 4 4個(gè)狀態(tài)，采用個(gè)狀態(tài)，采用2 2位狀態(tài)編碼：位狀態(tài)編碼： 0 0（0000）、）、 5 5（0101）、）、 1010（1010）、）、 1515（1111）VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz6當(dāng)前狀態(tài)當(dāng)前狀態(tài)輸入輸入 次態(tài)次態(tài) 輸出輸出tQ1 Q0DND1 D0open 0000 000010101010011 0100 010011001011011 1000 100011101011011 11 111狀態(tài)分配后的狀態(tài)轉(zhuǎn)換表狀態(tài)分配

9、后的狀態(tài)轉(zhuǎn)換表簡(jiǎn)單的自動(dòng)售貨機(jī)簡(jiǎn)單的自動(dòng)售貨機(jī)(VERILOG)module autosell (clk, reset, D, N,open); input clk, reset, D,N; output open; parameter cell0= 2b00，cell5 = 2b01, cell10= 2b10, cell15 = 2b11;reg 2:1 state;reg 2:1 next_state;always (posedge clk) if (reset) state = cell0; else state = next_state;always (N or D or state

10、) case (state) cell0: begin if (N) next_state = cell5;else if (D) next_state = cell10; else state = cell0; endVIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz7cell5: begin if (N) next_state = cell10;else if (D) next_state = cell15; else state = cell10; endcell

11、10: begin if (N) next_state = cell15;else if (D) next_state = cell15; else state = cell10; endcell15:next_state = cell15; endcaseassign open=(state= cell15); endmodule例：簡(jiǎn)單的自動(dòng)售貨機(jī)例：簡(jiǎn)單的自動(dòng)售貨機(jī)邏輯電路邏輯電路VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz8D1 = Q1 + D + Q0

12、 ND0 = Q0 N + Q0 N + Q1 N + Q1 DOPEN = Q1 Q000110111XX1X1111Q1D1Q0ND01101011XX1X0111Q1D0Q0ND00100010XX1X0010Q1OpenQ0ND5 5、實(shí)現(xiàn)、實(shí)現(xiàn)例：簡(jiǎn)單的自動(dòng)售貨機(jī)例：簡(jiǎn)單的自動(dòng)售貨機(jī)單點(diǎn)編碼單點(diǎn)編碼VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz9present state inputsnext stateoutputQ3Q2 Q1Q0DND3D2 D1D0

13、open0 00100000100100100100100011-0 01000001000101000101000011-0 10000010000110000101000011-1 000-10001D0 = Q0 D ND1 = Q0 N + Q1 D ND2 = Q0 D + Q1 N + Q2 D ND3 = Q1 D + Q2 D + Q2 N + Q3OPEN = Q3狀態(tài)簡(jiǎn)化的等價(jià)狀態(tài)狀態(tài)簡(jiǎn)化的等價(jià)狀態(tài)等價(jià)狀態(tài)等價(jià)狀態(tài): :設(shè)設(shè)S Si i、S Sj j為兩個(gè)原始狀態(tài)，當(dāng)它們滿足以下條件時(shí)等效。為兩個(gè)原始狀態(tài)，當(dāng)它們滿足以下條件時(shí)等效。對(duì)于所有的輸入組合對(duì)于所有的輸入組合 輸出

14、相同輸出相同 它們的次態(tài)屬于下列情況之一它們的次態(tài)屬于下列情況之一 A A次態(tài)相同。次態(tài)相同。S Si i、S Sj j的次態(tài)均為的次態(tài)均為S Sk k B B次態(tài)交錯(cuò)或?yàn)楦髯缘默F(xiàn)態(tài)。次態(tài)交錯(cuò)或?yàn)楦髯缘默F(xiàn)態(tài)。 交錯(cuò)：交錯(cuò)：S Si i的次態(tài)為的次態(tài)為S Sj j，S Sj j 的次態(tài)為的次態(tài)為S Si i 。 為各自的現(xiàn)態(tài)：或?yàn)楦髯缘默F(xiàn)態(tài)：或S Si i的次態(tài)為的次態(tài)為S Si i，S Sj j的次態(tài)為的次態(tài)為S Sj j 。等效類等效類：由若干等效狀態(tài)構(gòu)成的集合。等效類中任意兩個(gè)狀態(tài)均等效。若存在關(guān)：由若干等效狀態(tài)構(gòu)成的集合。等效類中任意兩個(gè)狀態(tài)均等效。若存在關(guān)系，系，(S(S1 1，S S

15、2 2 ) )，(S(S2 2，S S3 3 ) (S) (S1 1，S S3 3 ) )，則，則 S S1 1、S S2 2、S S3 3 屬于同一等效類。屬于同一等效類。 記記作作 (S(S1 1，S S2 2 ) )，(S(S2 2，S S3 3 ) | S) | S1 1、S S2 2、S S3 3 | |。最大等效類：最大等效類：一個(gè)等效類不是其他等效類的子集，則該等效類為最大等效類。一個(gè)等效類不是其他等效類的子集，則該等效類為最大等效類。VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello an

16、d Randy H. Katz10狀態(tài)簡(jiǎn)化：對(duì)原始狀態(tài)表進(jìn)行簡(jiǎn)化，消去多余狀態(tài)，求得最小化狀態(tài)表。狀態(tài)簡(jiǎn)化：對(duì)原始狀態(tài)表進(jìn)行簡(jiǎn)化，消去多余狀態(tài)，求得最小化狀態(tài)表。狀態(tài)簡(jiǎn)化目標(biāo)狀態(tài)簡(jiǎn)化目標(biāo) 識(shí)別和結(jié)合有等價(jià)行為的狀態(tài)識(shí)別和結(jié)合有等價(jià)行為的狀態(tài)狀態(tài)化簡(jiǎn)方法狀態(tài)化簡(jiǎn)方法行匹配法：一種良好的人工推導(dǎo)方法，但行匹配法：一種良好的人工推導(dǎo)方法，但并不是總能得到最簡(jiǎn)狀態(tài)表并不是總能得到最簡(jiǎn)狀態(tài)表蘊(yùn)含表法：容易用軟件實(shí)現(xiàn)，并確實(shí)能找蘊(yùn)含表法：容易用軟件實(shí)現(xiàn)，并確實(shí)能找到可能的最優(yōu)解到可能的最優(yōu)解可同時(shí)應(yīng)用這兩種方法：可同時(shí)應(yīng)用這兩種方法： 行匹配法能快速化簡(jiǎn)，減少狀態(tài)數(shù)目。行匹配法能快速化簡(jiǎn)，減少狀態(tài)數(shù)目。接

17、下來(lái)用蘊(yùn)含表法，由于只針對(duì)更少的狀接下來(lái)用蘊(yùn)含表法，由于只針對(duì)更少的狀態(tài)，因此能迅速找到行匹配法遺漏的等價(jià)態(tài)，因此能迅速找到行匹配法遺漏的等價(jià)狀態(tài)狀態(tài)VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz11行匹配算法概述行匹配算法概述算法概述算法概述（由狀態(tài)轉(zhuǎn)換表開(kāi)始對(duì)狀態(tài)進(jìn)行化簡(jiǎn)）（由狀態(tài)轉(zhuǎn)換表開(kāi)始對(duì)狀態(tài)進(jìn)行化簡(jiǎn)）1. 1. 對(duì)狀態(tài)進(jìn)行分組，每組中的狀態(tài)具有相同的對(duì)狀態(tài)進(jìn)行分組，每組中的狀態(tài)具有相同的輸出輸出2. 2. 檢查轉(zhuǎn)換表，查看各組中的狀態(tài)是否對(duì)于所檢查轉(zhuǎn)換表，

18、查看各組中的狀態(tài)是否對(duì)于所有的輸入組合都進(jìn)入等價(jià)的次態(tài)，若等價(jià)可將它有的輸入組合都進(jìn)入等價(jià)的次態(tài)，若等價(jià)可將它們合并成一個(gè)狀態(tài)，并重新命名。們合并成一個(gè)狀態(tài)，并重新命名。3.3.然后將所有的狀態(tài)轉(zhuǎn)換過(guò)程都指向這些新?tīng)顟B(tài)然后將所有的狀態(tài)轉(zhuǎn)換過(guò)程都指向這些新?tīng)顟B(tài)4.4.重復(fù)以上過(guò)程，直到再也沒(méi)有狀態(tài)可以合并重復(fù)以上過(guò)程，直到再也沒(méi)有狀態(tài)可以合并VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz12行匹配法例子行匹配法例子僅通過(guò)觀察狀態(tài)表就能判斷狀態(tài)等效僅通過(guò)觀察狀態(tài)表就能判

19、斷狀態(tài)等效VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz13化簡(jiǎn)后的狀態(tài)表化簡(jiǎn)后的狀態(tài)表行匹配法化簡(jiǎn)例子行匹配法化簡(jiǎn)例子4 4比特序列檢查器比特序列檢查器初始狀態(tài)圖初始狀態(tài)圖該狀態(tài)機(jī)具有單一輸入該狀態(tài)機(jī)具有單一輸入X X和輸出和輸出Z Z，如果每次接收的，如果每次接收的4 4比特輸入為比特輸入為01100110或或10101010中的中的一個(gè)，則輸出為一個(gè)，則輸出為1 1。狀態(tài)機(jī)每次接收比特輸入后回到復(fù)位狀態(tài)。狀態(tài)機(jī)每次接收比特輸入后回到復(fù)位狀態(tài)。假設(shè)用米利型機(jī)實(shí)現(xiàn)

20、：假設(shè)用米利型機(jī)實(shí)現(xiàn)：只有在之前的比特輸入匹配指定串中的任意一個(gè)，輸出才為只有在之前的比特輸入匹配指定串中的任意一個(gè)，輸出才為狀態(tài)機(jī)只在每位比特一組輸入后才決定是否輸出狀態(tài)機(jī)只在每位比特一組輸入后才決定是否輸出VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz14q原始狀態(tài)圖原始狀態(tài)圖狀態(tài)表和行匹配法狀態(tài)表和行匹配法狀態(tài)表：每個(gè)狀態(tài)對(duì)應(yīng)一行，每列對(duì)應(yīng)不同的輸入組合的次態(tài)和狀態(tài)表：每個(gè)狀態(tài)對(duì)應(yīng)一行，每列對(duì)應(yīng)不同的輸入組合的次態(tài)和輸出輸出VIII - Working wit

21、h Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz15行匹配法行匹配法檢查狀態(tài)轉(zhuǎn)換表中的每一行，尋找具有相同次態(tài)和輸出的狀態(tài)檢查狀態(tài)轉(zhuǎn)換表中的每一行，尋找具有相同次態(tài)和輸出的狀態(tài)VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz16nS10S10和和S12S12具有相同次具有相同次態(tài)和輸出的狀態(tài)，可以態(tài)和輸出的狀態(tài)，可以合并成新?tīng)顟B(tài)名合并成新?tīng)顟B(tài)名S10S10nS7S7，S8S8，

22、S9S9， S11S11，S13S13，S14 S14 均具有相同均具有相同的次態(tài)和輸出，可能合的次態(tài)和輸出，可能合并成新?tīng)顟B(tài)并成新?tīng)顟B(tài)S7S7行匹配法迭代行匹配法迭代合并后的新?tīng)顟B(tài)表合并后的新?tīng)顟B(tài)表 再對(duì)再對(duì)S3S3，S6S6進(jìn)行合并，用進(jìn)行合并，用S3S3表示表示 對(duì)對(duì)S4S4，S5S5進(jìn)行合并，用進(jìn)行合并，用S4S4表示表示VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz17n合并后的新?tīng)顟B(tài)合并后的新?tīng)顟B(tài)表，不能再用行匹表，不能再用行匹配法進(jìn)行合并配法進(jìn)行合并n

23、將將1515個(gè)狀態(tài)化簡(jiǎn)個(gè)狀態(tài)化簡(jiǎn)為僅為僅7 7個(gè)狀態(tài)個(gè)狀態(tài)行匹配法化簡(jiǎn)得到的狀態(tài)圖行匹配法化簡(jiǎn)得到的狀態(tài)圖行匹配法的局限性行匹配法的局限性 并不是總能得到最簡(jiǎn)化并不是總能得到最簡(jiǎn)化的狀態(tài)的狀態(tài)VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz18蘊(yùn)含表方法蘊(yùn)含表方法蘊(yùn)含表化簡(jiǎn)的步驟為：蘊(yùn)含表化簡(jiǎn)的步驟為：作隱含表、尋找等效對(duì)、作隱含表、尋找等效對(duì)、求出最大等效類、作出最小化狀態(tài)表。求出最大等效類、作出最小化狀態(tài)表。 作初始蘊(yùn)含表作初始蘊(yùn)含表 蘊(yùn)含表為直角三角型網(wǎng)格，表中

24、的方格用狀態(tài)名稱標(biāo)注。橫蘊(yùn)含表為直角三角型網(wǎng)格，表中的方格用狀態(tài)名稱標(biāo)注。橫向從左到右的狀態(tài)順序依次為第一個(gè)到倒數(shù)第二個(gè)狀態(tài)，縱向從向從左到右的狀態(tài)順序依次為第一個(gè)到倒數(shù)第二個(gè)狀態(tài)，縱向從上到下的狀態(tài)順序?yàn)榈诙阶詈笠粋€(gè)狀態(tài)，每個(gè)方格代表一個(gè)狀上到下的狀態(tài)順序?yàn)榈诙阶詈笠粋€(gè)狀態(tài)，每個(gè)方格代表一個(gè)狀態(tài)對(duì)態(tài)對(duì) 尋找等效對(duì)尋找等效對(duì) 進(jìn)行兩輪比較，先進(jìn)行順序比較，再進(jìn)行關(guān)聯(lián)比較進(jìn)行兩輪比較，先進(jìn)行順序比較，再進(jìn)行關(guān)聯(lián)比較VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz19

25、蘊(yùn)含表化簡(jiǎn)蘊(yùn)含表化簡(jiǎn)是一種更系統(tǒng)的方法，它尋找能夠合并成單一狀態(tài)的是一種更系統(tǒng)的方法，它尋找能夠合并成單一狀態(tài)的所有狀態(tài)所有狀態(tài)蘊(yùn)含表方法蘊(yùn)含表方法 順序比較：對(duì)照原始狀態(tài)表，對(duì)所有狀態(tài)進(jìn)行檢查比較。若狀態(tài)對(duì)等順序比較：對(duì)照原始狀態(tài)表，對(duì)所有狀態(tài)進(jìn)行檢查比較。若狀態(tài)對(duì)等效，在方格中打效，在方格中打 “ ”；若不等效，在方格中打；若不等效，在方格中打 “ ”；與其他狀；與其他狀態(tài)對(duì)相關(guān)，有待進(jìn)一步檢查，在方格中填上待檢查狀態(tài)對(duì)。態(tài)對(duì)相關(guān)，有待進(jìn)一步檢查，在方格中填上待檢查狀態(tài)對(duì)。 關(guān)聯(lián)比較：確定待檢查狀態(tài)對(duì)是否等效，由此確定原狀態(tài)對(duì)是否等效。關(guān)聯(lián)比較：確定待檢查狀態(tài)對(duì)是否等效，由此確定原狀態(tài)對(duì)是

26、否等效。若方格內(nèi)有一狀態(tài)對(duì)不等效，則用若方格內(nèi)有一狀態(tài)對(duì)不等效，則用 “”標(biāo)志。標(biāo)志。 求出最大等效類求出最大等效類 利用等效狀態(tài)的傳遞性，通過(guò)合并求出最大等效類。原始狀態(tài)表中的利用等效狀態(tài)的傳遞性，通過(guò)合并求出最大等效類。原始狀態(tài)表中的每個(gè)狀態(tài)都應(yīng)該屬于一個(gè)最大等效對(duì)。每個(gè)狀態(tài)都應(yīng)該屬于一個(gè)最大等效對(duì)。 作出最小化狀態(tài)表作出最小化狀態(tài)表 將每個(gè)最大等效類中的全部狀態(tài)合并為一個(gè)狀態(tài)，可得與原始狀態(tài)表將每個(gè)最大等效類中的全部狀態(tài)合并為一個(gè)狀態(tài)，可得與原始狀態(tài)表等價(jià)的最小化狀態(tài)表。等價(jià)的最小化狀態(tài)表。VIII - Working with Sequential Logic Copyright 20

27、04, Gaetano Borriello and Randy H. Katz20蘊(yùn)含表方法化簡(jiǎn)實(shí)例蘊(yùn)含表方法化簡(jiǎn)實(shí)例VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz21現(xiàn)態(tài)次態(tài) / 輸出x = 0 x = 1 ABCDEFGC / 0F / 0F / 0D / 0C / 0C / 0C / 1B / 1A / 1G / 0E / 0E / 1G / 0D / 0對(duì)表中狀態(tài)進(jìn)行順序比較，根據(jù)等對(duì)表中狀態(tài)進(jìn)行順序比較，根據(jù)等效狀態(tài)判別標(biāo)準(zhǔn)進(jìn)行判別。效狀態(tài)判別標(biāo)準(zhǔn)進(jìn)行判別

28、。狀態(tài)狀態(tài)C C、F F輸出相同，輸出相同，x=0 x=0時(shí)次態(tài)交錯(cuò)，時(shí)次態(tài)交錯(cuò)， x =1x =1時(shí)次態(tài)相同，故時(shí)次態(tài)相同，故C C、F F為等效對(duì)，在為等效對(duì)，在相應(yīng)方格中打相應(yīng)方格中打 “ ” 狀態(tài)狀態(tài) A A、F F不滿足等效條件，不滿足等效條件，在相應(yīng)方格中打在相應(yīng)方格中打“”。狀態(tài)。狀態(tài)A A、E E滿足輸出相同條件，當(dāng)滿足輸出相同條件，當(dāng)x=0 x=0時(shí)時(shí)次態(tài)相同，但當(dāng)次態(tài)相同，但當(dāng)x=1x=1時(shí)次態(tài)分別時(shí)次態(tài)分別為為B B、E E，當(dāng)前無(wú)法判定，當(dāng)前無(wú)法判定B B、E E 是是否等效，因此在方格中填入否等效，因此在方格中填入BEBE。 經(jīng)比較后，還有經(jīng)比較后，還有A A、B B

29、；A A、E E；B B、E E；D D、G G共共4 4個(gè)狀態(tài)對(duì)尚未確個(gè)狀態(tài)對(duì)尚未確定是否等效，因此應(yīng)進(jìn)行關(guān)聯(lián)定是否等效，因此應(yīng)進(jìn)行關(guān)聯(lián)比較。比較。 狀態(tài)狀態(tài)A A、B B對(duì)應(yīng)的方格中次態(tài)對(duì)應(yīng)的方格中次態(tài)對(duì)為對(duì)為C C、F F，由順序比較已知，由順序比較已知C C、F F等效，故等效，故A A、B B等效，在對(duì)應(yīng)的等效，在對(duì)應(yīng)的方格中打方格中打“ ”。檢查。檢查A A、E E狀態(tài)對(duì)，出現(xiàn)循環(huán)關(guān)系：狀態(tài)對(duì)，出現(xiàn)循環(huán)關(guān)系：AEBECFAEBECF。已知。已知C C、F F等效，等效，故故B B、E E等效。等效。BEBE又與又與AEAE構(gòu)成循構(gòu)成循環(huán)，故環(huán)，故A A、E E等效，在對(duì)應(yīng)的方等效，

30、在對(duì)應(yīng)的方格中打格中打 “ ”。 構(gòu)造初始蘊(yùn)含表構(gòu)造初始蘊(yùn)含表 尋找等效對(duì)尋找等效對(duì)VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz22由造出的初始蘊(yùn)含表可知，由造出的初始蘊(yùn)含表可知，7 7 個(gè)狀態(tài)共有個(gè)狀態(tài)共有 4 4 個(gè)等效對(duì)個(gè)等效對(duì) ( A( A，B )B )、( A( A，E )E )、( B( B，E )E )、( C( C，F(xiàn) )F )。 求出最大等效類求出最大等效類由所得由所得 4 4 個(gè)等效對(duì)可知，個(gè)等效對(duì)可知，( A( A，B )B )、( A( A

31、，E )E )、( B( B，E ) E ) 構(gòu)成最大等效類構(gòu)成最大等效類 A A，B B，E E 。 ( C( C，F(xiàn) ) F ) 不包含在其他等效類中，也是一個(gè)最大等效類。狀態(tài)不包含在其他等效類中，也是一個(gè)最大等效類。狀態(tài) D D、G G 不和其他狀態(tài)等效，故各自構(gòu)成最大等效類。不和其他狀態(tài)等效，故各自構(gòu)成最大等效類。原始狀態(tài)表中原始狀態(tài)表中 7 7 個(gè)狀態(tài)構(gòu)成個(gè)狀態(tài)構(gòu)成 4 4 個(gè)最大等效類，個(gè)最大等效類，分別為：分別為： 現(xiàn)態(tài)次態(tài) / 輸出 x = 0 x = 1 abcdb / 0b / 0c / 0b / 1a / 1d / 0a / 0c / 0 A，B，E 、 C，F(xiàn) 、 D

32、、 G a b c d 作出最小化狀態(tài)表作出最小化狀態(tài)表將將4 4個(gè)最大等效類分別用個(gè)最大等效類分別用 a a、b b、c c、d d 表示，表示，代入原始狀態(tài)表，可得化簡(jiǎn)后的最小化狀態(tài)表。代入原始狀態(tài)表，可得化簡(jiǎn)后的最小化狀態(tài)表。用蘊(yùn)含表化簡(jiǎn)用蘊(yùn)含表化簡(jiǎn) 由狀態(tài)轉(zhuǎn)由狀態(tài)轉(zhuǎn)移表構(gòu)造移表構(gòu)造初始蘊(yùn)含初始蘊(yùn)含表表VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz23 尋找等效尋找等效由造出的初始蘊(yùn)含表可知，由造出的初始蘊(yùn)含表可知，1 1 個(gè)等效對(duì)個(gè)等效對(duì) ( D( D，E

33、)E ) 求出最大等效類求出最大等效類 (D(D，E)E)用用D D表示表示 作出最小化狀態(tài)作出最小化狀態(tài)表表蘊(yùn)含表方法化簡(jiǎn)實(shí)例蘊(yùn)含表方法化簡(jiǎn)實(shí)例VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz24輸入輸入 次態(tài)次態(tài) 輸出輸出序列序列當(dāng)前狀態(tài)當(dāng)前狀態(tài) X=0 X=1 X=0 X=1ResetS0S1 S2 0 00S1S3 S4 0 01S2S5 S6 0 000S3S0 S0 0 001S4S0 S0 1 010S5S0 S0 0 011S6S0 S0 1 03 3

34、比特序列檢測(cè)器，當(dāng)檢測(cè)到比特序列檢測(cè)器，當(dāng)檢測(cè)到010010或或110110時(shí)輸出為時(shí)輸出為1 1根據(jù)要求列出初始狀態(tài)表根據(jù)要求列出初始狀態(tài)表 由狀由狀態(tài)轉(zhuǎn)移態(tài)轉(zhuǎn)移表構(gòu)造表構(gòu)造初始蘊(yùn)初始蘊(yùn)含表含表 尋找等效尋找等效蘊(yùn)含表方法化簡(jiǎn)實(shí)例蘊(yùn)含表方法化簡(jiǎn)實(shí)例VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz25 求出最大等效類求出最大等效類 (S1，S2)用用S1表示表示(S3，S5)用用S3表示表示(S4，S6)用用S4表示表示 作出最小化狀態(tài)作出最小化狀態(tài)表表Input N

35、ext State OutputSequencePresent StateX=0X=1X=0X=1ResetS0S1S1000 + 1S1S3S400X0S3S0S000X1S4S0S010S0S1S3S4X/01/01/00/10/0X/0更復(fù)雜狀態(tài)圖的化簡(jiǎn)更復(fù)雜狀態(tài)圖的化簡(jiǎn)多輸入狀態(tài)圖和轉(zhuǎn)換表多輸入狀態(tài)圖和轉(zhuǎn)換表VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz26符號(hào)狀態(tài)轉(zhuǎn)換表符號(hào)狀態(tài)轉(zhuǎn)換表 present next state output state00011

36、011 S0S0S1S2S31 S1S0S3S1S40 S2S1S3S2S41 S3S1S0S4S50 S4S0S1S2S51 S5S1S4S0S50inputs here1001110000011110100111001000110011100110110100S01S21S41S10S30S5001S0-S1 S1-S3 S2-S2 S3-S4 S0-S0 S1-S1 S2-S2 S3-S5 S0-S1 S3-S0 S1-S4 S4-S5 S0-S1 S3-S4 S1-S0 S4-S5 S1-S0 S3-S1 S2-S2S4-S5 S4-S0S5-S5 S1-S1 S0-S4 S1 S2

37、S3 S4 S5S0S1S2S3S4 由狀態(tài)轉(zhuǎn)移表構(gòu)由狀態(tài)轉(zhuǎn)移表構(gòu)造初始蘊(yùn)含表造初始蘊(yùn)含表 尋找等效尋找等效更復(fù)雜狀態(tài)圖的化簡(jiǎn)VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz27minimized state table(S0=S4) (S3=S5)present next state output state00011011 S0S0 S1S2S31 S1S0 S3S1S30 S2S1S3S2S01 S3S1S0S0 S30 求出最大等效類求出最大等效類 (S0，S

38、4)用用S0表示表示(S3，S5)用用S3表示表示present next state output state00011011 S0S0S1S2S31 S1S0S3S1S40 S2S1S3S2S41 S3S1S0S4S50 S4S0S1S2S51 S5S1S4S0S50 作出最小化狀態(tài)表作出最小化狀態(tài)表狀態(tài)分配狀態(tài)分配狀態(tài)分配是選擇二進(jìn)制位向量分配給每個(gè)符號(hào)狀態(tài)狀態(tài)分配是選擇二進(jìn)制位向量分配給每個(gè)符號(hào)狀態(tài)如果如果m m個(gè)狀態(tài)用個(gè)狀態(tài)用n n位來(lái)對(duì)狀態(tài)進(jìn)行編碼，則可能的分配方案有位來(lái)對(duì)狀態(tài)進(jìn)行編碼，則可能的分配方案有2 2n n!/(2!/(2n n m)! m)! 簡(jiǎn)單的按照二進(jìn)制順序來(lái)進(jìn)行

39、狀態(tài)分配，設(shè)計(jì)者僅需要保證每簡(jiǎn)單的按照二進(jìn)制順序來(lái)進(jìn)行狀態(tài)分配，設(shè)計(jì)者僅需要保證每個(gè)狀態(tài)對(duì)應(yīng)唯一的編碼，以保證組合邏輯能區(qū)分各個(gè)狀態(tài)個(gè)狀態(tài)對(duì)應(yīng)唯一的編碼，以保證組合邏輯能區(qū)分各個(gè)狀態(tài)單點(diǎn)編碼是用單點(diǎn)編碼是用m m位狀態(tài)位編碼位狀態(tài)位編碼m m個(gè)狀態(tài)，每個(gè)狀態(tài)的單點(diǎn)編碼只個(gè)狀態(tài)，每個(gè)狀態(tài)的單點(diǎn)編碼只有在對(duì)應(yīng)的位上為有在對(duì)應(yīng)的位上為1 1，在其它位上均為，在其它位上均為0 0啟發(fā)式編碼能實(shí)現(xiàn)良好的狀態(tài)分配，但不能保證是好的電路實(shí)啟發(fā)式編碼能實(shí)現(xiàn)良好的狀態(tài)分配，但不能保證是好的電路實(shí)現(xiàn)現(xiàn)VIII - Working with Sequential Logic Copyright 2004, Gaet

40、ano Borriello and Randy H. Katz28 實(shí)現(xiàn)時(shí)序邏輯網(wǎng)絡(luò)所需門的數(shù)量嚴(yán)重依賴于如何將編碼后實(shí)現(xiàn)時(shí)序邏輯網(wǎng)絡(luò)所需門的數(shù)量嚴(yán)重依賴于如何將編碼后的邏輯值分配給符號(hào)狀態(tài)，最優(yōu)的分配方案的唯一途徑是嘗試的邏輯值分配給符號(hào)狀態(tài)，最優(yōu)的分配方案的唯一途徑是嘗試所有的分配方案所有的分配方案狀態(tài)分配策略狀態(tài)分配策略可能的策略可能的策略順序編碼順序編碼隨機(jī)編碼隨機(jī)編碼單點(diǎn)編碼單點(diǎn)編碼面向輸出的編碼面向輸出的編碼啟發(fā)式編碼啟發(fā)式編碼不能保證結(jié)果是最優(yōu)的不能保證結(jié)果是最優(yōu)的 另一個(gè)復(fù)雜的問(wèn)題另一個(gè)復(fù)雜的問(wèn)題VIII - Working with Sequential Logic Copy

41、right 2004, Gaetano Borriello and Randy H. Katz29順序編碼順序編碼簡(jiǎn)單的將符號(hào)狀態(tài)名字替換成為規(guī)則的編碼，簡(jiǎn)單的將符號(hào)狀態(tài)名字替換成為規(guī)則的編碼，設(shè)計(jì)者僅需要保證每個(gè)狀態(tài)對(duì)應(yīng)唯一的編碼，設(shè)計(jì)者僅需要保證每個(gè)狀態(tài)對(duì)應(yīng)唯一的編碼，以保證組合邏輯能夠區(qū)分各個(gè)狀態(tài)以保證組合邏輯能夠區(qū)分各個(gè)狀態(tài)VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz30單點(diǎn)編碼單點(diǎn)編碼簡(jiǎn)單簡(jiǎn)單容易編碼、容易診斷和修改容易編碼、容易診斷和修改小規(guī)模的邏輯函

42、數(shù)小規(guī)模的邏輯函數(shù)每個(gè)狀態(tài)位對(duì)應(yīng)方程中所含或項(xiàng)的數(shù)目和狀態(tài)圖中指向該狀態(tài)的所有弧對(duì)應(yīng)項(xiàng)每個(gè)狀態(tài)位對(duì)應(yīng)方程中所含或項(xiàng)的數(shù)目和狀態(tài)圖中指向該狀態(tài)的所有弧對(duì)應(yīng)項(xiàng)的總數(shù)相同的總數(shù)相同適合于適合于FPGAFPGA實(shí)現(xiàn)實(shí)現(xiàn)大量的觸發(fā)器可用大量的觸發(fā)器可用對(duì)大的狀態(tài)機(jī)不實(shí)用對(duì)大的狀態(tài)機(jī)不實(shí)用太多的狀態(tài)需要太多的太多的狀態(tài)需要太多的flip-flopsflip-flops對(duì)大的有限狀態(tài)機(jī)劃分成小塊可用單點(diǎn)編碼對(duì)大的有限狀態(tài)機(jī)劃分成小塊可用單點(diǎn)編碼對(duì)單點(diǎn)編碼進(jìn)行一些改變對(duì)單點(diǎn)編碼進(jìn)行一些改變one-hot + all-0one-hot + all-0VIII - Working with Sequential

43、Logic Copyright 2004, Gaetano Borriello and Randy H. Katz31 用用m m位狀態(tài)位編碼位狀態(tài)位編碼m m個(gè)狀態(tài)，每個(gè)狀態(tài)的單點(diǎn)編碼只有在對(duì)應(yīng)個(gè)狀態(tài)，每個(gè)狀態(tài)的單點(diǎn)編碼只有在對(duì)應(yīng)的位上為的位上為1 1，在其它位上均為，在其它位上均為0 0隨機(jī)編碼隨機(jī)編碼這是更簡(jiǎn)單的策略，隨機(jī)選擇可能的編碼進(jìn)這是更簡(jiǎn)單的策略，隨機(jī)選擇可能的編碼進(jìn)行分配，它僅需要保證每個(gè)狀態(tài)對(duì)應(yīng)唯一的行分配，它僅需要保證每個(gè)狀態(tài)對(duì)應(yīng)唯一的編碼，以保證組合邏輯能夠區(qū)分各個(gè)狀態(tài)編碼，以保證組合邏輯能夠區(qū)分各個(gè)狀態(tài)VIII - Working with Sequential Log

44、ic Copyright 2004, Gaetano Borriello and Randy H. Katz32VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz33面向輸出的編碼面向輸出的編碼n對(duì)于摩爾型，輸出直接與狀態(tài)位有關(guān)，但如果設(shè)對(duì)于摩爾型，輸出直接與狀態(tài)位有關(guān)，但如果設(shè)計(jì)者直接實(shí)現(xiàn)摩爾型輸出計(jì)者直接實(shí)現(xiàn)摩爾型輸出( (即觸發(fā)器的輸出就是狀即觸發(fā)器的輸出就是狀態(tài)機(jī)的輸出），則可以使用輸出來(lái)區(qū)別狀態(tài)態(tài)機(jī)的輸出），則可以使用輸出來(lái)區(qū)別狀態(tài)n同步米利型輸出也是通過(guò)觸發(fā)

45、器的輸出直接實(shí)現(xiàn)，同步米利型輸出也是通過(guò)觸發(fā)器的輸出直接實(shí)現(xiàn)，因此也可以這樣用因此也可以這樣用n對(duì)于整個(gè)狀態(tài)機(jī)都使用面向輸出的編碼方式并不對(duì)于整個(gè)狀態(tài)機(jī)都使用面向輸出的編碼方式并不是很好的策略，明智的使用部分輸出作為編碼，是很好的策略，明智的使用部分輸出作為編碼，也許能減少狀態(tài)位的數(shù)量也許能減少狀態(tài)位的數(shù)量啟發(fā)式方法啟發(fā)式方法該方法試圖縮短相關(guān)狀態(tài)間的布爾空間的距離。如狀態(tài)該方法試圖縮短相關(guān)狀態(tài)間的布爾空間的距離。如狀態(tài)Y Y用狀用狀態(tài)態(tài)X X轉(zhuǎn)換而來(lái)，則它們的狀態(tài)編碼中的不同比特位應(yīng)盡量少轉(zhuǎn)換而來(lái)，則它們的狀態(tài)編碼中的不同比特位應(yīng)盡量少狀態(tài)圖：類似于卡諾圖，提供觀察狀態(tài)分配的相鄰性的方法狀態(tài)

46、圖：類似于卡諾圖，提供觀察狀態(tài)分配的相鄰性的方法。VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz34 狀態(tài)圖中的方格按狀態(tài)圖中的方格按照狀態(tài)位的二進(jìn)制值照狀態(tài)位的二進(jìn)制值進(jìn)行索引，給出該編進(jìn)行索引，給出該編碼的狀態(tài)便放在圖中碼的狀態(tài)便放在圖中對(duì)應(yīng)的的方格里（最對(duì)應(yīng)的的方格里（最多能處理多能處理2 26 6個(gè)狀態(tài)）個(gè)狀態(tài)）最少位變化啟發(fā)式方法最少位變化啟發(fā)式方法目的是使所有狀態(tài)間的轉(zhuǎn)換中發(fā)生變化的位數(shù)最少目的是使所有狀態(tài)間的轉(zhuǎn)換中發(fā)生變化的位數(shù)最少第二種分配方案：第二

47、種分配方案： 分配分配S0S0，由于復(fù)位邏輯工作，通常將全，由于復(fù)位邏輯工作，通常將全0 0分配給起始狀態(tài)分配給起始狀態(tài) 接下來(lái)分配接下來(lái)分配S1S1、S2S2，將它們放在，將它們放在S0S0鄰近位置鄰近位置 然后將然后將S3S3放在放在S1S1、S2S2之間之間 最后將最后將S4S4放在放在S3S3附近附近VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz35基于次態(tài)和輸入基于次態(tài)和輸入/輸出的啟發(fā)式方法輸出的啟發(fā)式方法最高優(yōu)先級(jí)：在給定的輸入轉(zhuǎn)換條件下，具有相同次態(tài)的狀態(tài)應(yīng)最高優(yōu)先級(jí)：在給定的輸入轉(zhuǎn)換條件下，具有相同次態(tài)的狀態(tài)應(yīng)該在狀態(tài)圖中放到鄰近的位置該在狀態(tài)圖中放到鄰近的位置中等優(yōu)先級(jí)：具有相同現(xiàn)態(tài)的次態(tài)應(yīng)放在狀態(tài)圖中鄰近的位置中等優(yōu)先級(jí)：具有相同現(xiàn)態(tài)的次態(tài)應(yīng)放在狀態(tài)圖中鄰近的位置最低優(yōu)先級(jí)：在給定輸入的情況下，具有相同輸出的狀態(tài)應(yīng)該放最低優(yōu)先級(jí)：在給定輸入的情況下，具有相同輸出