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

1、有限狀態(tài)機的分析有限狀態(tài)機的分析狀態(tài)最簡化狀態(tài)最簡化最少的狀態(tài)需要最少的狀態(tài)位最少的狀態(tài)需要最少的狀態(tài)位最少的位需要最少的邏輯方程最少的位需要最少的邏輯方程狀態(tài)最簡化方法狀態(tài)最簡化方法行匹配法行匹配法蘊含表方法蘊含表方法狀態(tài)分配策略狀態(tài)分配策略順序編碼順序編碼隨機編碼隨機編碼單點編碼單點編碼面向輸出的編碼面向輸出的編碼啟發(fā)式編碼啟發(fā)式編碼有限狀態(tài)機的劃分有限狀態(tài)機的劃分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)機設計過程通用有限狀態(tài)機設計過程n(1) (1) 定義輸入和輸出定義輸入和輸出n(2) (2) 定義狀態(tài)機可能的狀態(tài)定義狀態(tài)機可能的狀態(tài)q狀態(tài)化簡狀態(tài)化簡n(3) (3) 用二進制對狀態(tài)和輸出進行編碼用二進制對狀態(tài)和輸出進行編碼q狀態(tài)分配或狀態(tài)編碼狀態(tài)分配或狀態(tài)編碼q輸出編碼輸出編碼q可能的輸入編碼可能的輸入編碼n(4) (4) 選擇適當的邏輯實現(xiàn)狀態(tài)和輸出選擇適當的邏輯實現(xiàn)狀態(tài)和輸出q組合邏輯的實現(xiàn)和優(yōu)化組合邏輯的實現(xiàn)和優(yōu)化q步驟步驟2 2和和3 3對最

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

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

5、期例：簡單的自動售貨機例：簡單的自動售貨機2 2、有限狀態(tài)機抽象表達、有限狀態(tài)機抽象表達列出最終能給出商品的輸入順序列出最終能給出商品的輸入順序: :3 3個個5 5美分：美分：N N，N N，N N2 2個個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個個1 1角：角：D D，D D畫狀態(tài)圖畫狀態(tài)圖: :輸入輸入: N, D, reset, clk: N, D, reset, clk輸出商品輸出商品: open: open假設假設: :假設信號假設信號N N和和D D從來不會同時為真從來不

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

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

8、行狀態(tài)分配 4 4個狀態(tài)，采用個狀態(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當前狀態(tài)當前狀態(tài)輸入輸入 次態(tài)次態(tài) 輸出輸出tQ1 Q0DND1 D0open 0000 000010101010011 0100 010011001011011 1000 100011101011011 11 111狀態(tài)分配后的狀態(tài)轉換表狀態(tài)分配

9、后的狀態(tài)轉換表簡單的自動售貨機簡單的自動售貨機(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例：簡單的自動售貨機例：簡單的自動售貨機邏輯電路邏輯電路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、實現(xiàn)、實現(xià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)簡化的等價狀態(tài)狀態(tài)簡化的等價狀態(tài)等價狀態(tài)等價狀態(tài): :設設S Si i、S Sj j為兩個原始狀態(tài)，當它們滿足以下條件時等效。為兩個原始狀態(tài)，當它們滿足以下條件時等效。對于所有的輸入組合對于所有的輸入組合 輸出

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)交錯或為各自的現(xiàn)態(tài)。次態(tài)交錯或為各自的現(xiàn)態(tài)。 交錯：交錯：S Si i的次態(tài)為的次態(tài)為S Sj j，S Sj j 的次態(tài)為的次態(tài)為S Si i 。 為各自的現(xiàn)態(tài)：或為各自的現(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)構成的集合。等效類中任意兩個狀態(tài)均等效。若存在關：由若干等效狀態(tài)構成的集合。等效類中任意兩個狀態(tài)均等效。若存在關系，系，(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 | |。最大等效類：最大等效類：一個等效類不是其他等效類的子集，則該等效類為最大等效類。一個等效類不是其他等效類的子集，則該等效類為最大等效類。VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello an

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

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

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

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

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

21、h Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz15行匹配法行匹配法檢查狀態(tài)轉換表中的每一行，尋找具有相同次態(tài)和輸出的狀態(tài)檢查狀態(tài)轉換表中的每一行，尋找具有相同次態(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ài)名合并成新狀態(tài)名S10S10nS7S7，S8S8，

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

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

24、的方格用狀態(tài)名稱標注。橫蘊含表為直角三角型網格，表中的方格用狀態(tài)名稱標注。橫向從左到右的狀態(tài)順序依次為第一個到倒數第二個狀態(tài)，縱向從向從左到右的狀態(tài)順序依次為第一個到倒數第二個狀態(tài)，縱向從上到下的狀態(tài)順序為第二到最后一個狀態(tài)，每個方格代表一個狀上到下的狀態(tài)順序為第二到最后一個狀態(tài)，每個方格代表一個狀態(tài)對態(tài)對 尋找等效對尋找等效對 進行兩輪比較，先進行順序比較，再進行關聯(lián)比較進行兩輪比較，先進行順序比較，再進行關聯(lián)比較VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz19

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

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

27、04, Gaetano Borriello and Randy H. Katz20蘊含表方法化簡實例蘊含表方法化簡實例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對表中狀態(tài)進行順序比較，根據等對表中狀態(tài)進行順序比較，根據等效狀態(tài)判別標準進行判別。效狀態(tài)判別標準進行判別

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

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

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

31、，E )E )、( B( B，E ) E ) 構成最大等效類構成最大等效類 A A，B B，E E 。 ( C( C，F(xiàn) ) F ) 不包含在其他等效類中，也是一個最大等效類。狀態(tài)不包含在其他等效類中，也是一個最大等效類。狀態(tài) D D、G G 不和其他狀態(tài)等效，故各自構成最大等效類。不和其他狀態(tài)等效，故各自構成最大等效類。原始狀態(tài)表中原始狀態(tài)表中 7 7 個狀態(tài)構成個狀態(tài)構成 4 4 個最大等效類，個最大等效類，分別為：分別為： 現(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個最大等效類分別用個最大等效類分別用 a a、b b、c c、d d 表示，表示，代入原始狀態(tài)表，可得化簡后的最小化狀態(tài)表。代入原始狀態(tài)表，可得化簡后的最小化狀態(tài)表。用蘊含表化簡用蘊含表化簡 由狀態(tài)轉由狀態(tài)轉移表構造移表構造初始蘊含初始蘊含表表VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz23 尋找等效尋找等效由造出的初始蘊含表可知，由造出的初始蘊含表可知，1 1 個等效對個等效對 ( D( D，E

33、)E ) 求出最大等效類求出最大等效類 (D(D，E)E)用用D D表示表示 作出最小化狀態(tài)作出最小化狀態(tài)表表蘊含表方法化簡實例蘊含表方法化簡實例VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz24輸入輸入 次態(tài)次態(tài) 輸出輸出序列序列當前狀態(tài)當前狀態(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、比特序列檢測器，當檢測到比特序列檢測器，當檢測到010010或或110110時輸出為時輸出為1 1根據要求列出初始狀態(tài)表根據要求列出初始狀態(tài)表 由狀由狀態(tài)轉移態(tài)轉移表構造表構造初始蘊初始蘊含表含表 尋找等效尋找等效蘊含表方法化簡實例蘊含表方法化簡實例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更復雜狀態(tài)圖的化簡更復雜狀態(tài)圖的化簡多輸入狀態(tài)圖和轉換表多輸入狀態(tài)圖和轉換表VIII - Working with Sequential Logic Copyright 2004, Gaetano Borriello and Randy H. Katz26符號狀態(tài)轉換表符號狀態(tài)轉換表 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)轉移表構由狀態(tài)轉移表構造初始蘊含表造初始蘊含表 尋找等效尋找等效更復雜狀態(tài)圖的化簡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)分配是選擇二進制位向量分配給每個符號狀態(tài)狀態(tài)分配是選擇二進制位向量分配給每個符號狀態(tài)如果如果m m個狀態(tài)用個狀態(tài)用n n位來對狀態(tài)進行編碼，則可能的分配方案有位來對狀態(tài)進行編碼，則可能的分配方案有2 2n n!/(2!/(2n n m)! m)! 簡單的按照二進制順序來進行

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

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

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

42、數小規(guī)模的邏輯函數每個狀態(tài)位對應方程中所含或項的數目和狀態(tài)圖中指向該狀態(tài)的所有弧對應項每個狀態(tài)位對應方程中所含或項的數目和狀態(tài)圖中指向該狀態(tài)的所有弧對應項的總數相同的總數相同適合于適合于FPGAFPGA實現(xiàn)實現(xiàn)大量的觸發(fā)器可用大量的觸發(fā)器可用對大的狀態(tài)機不實用對大的狀態(tài)機不實用太多的狀態(tài)需要太多的太多的狀態(tài)需要太多的flip-flopsflip-flops對大的有限狀態(tài)機劃分成小塊可用單點編碼對大的有限狀態(tài)機劃分成小塊可用單點編碼對單點編碼進行一些改變對單點編碼進行一些改變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個狀態(tài)，每個狀態(tài)的單點編碼只有在對應個狀態(tài)，每個狀態(tài)的單點編碼只有在對應的位上為的位上為1 1，在其它位上均為，在其它位上均為0 0隨機編碼隨機編碼這是更簡單的策略，隨機選擇可能的編碼進這是更簡單的策略，隨機選擇可能的編碼進行分配，它僅需要保證每個狀態(tài)對應唯一的行分配，它僅需要保證每個狀態(tài)對應唯一的編碼，以保證組合邏輯能夠區(qū)分各個狀態(tài)編碼，以保證組合邏輯能夠區(qū)分各個狀態(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對于摩爾型，輸出直接與狀態(tài)位有關，但如果設對于摩爾型，輸出直接與狀態(tài)位有關，但如果設計者直接實現(xiàn)摩爾型輸出計者直接實現(xiàn)摩爾型輸出( (即觸發(fā)器的輸出就是狀即觸發(fā)器的輸出就是狀態(tài)機的輸出），則可以使用輸出來區(qū)別狀態(tài)態(tài)機的輸出），則可以使用輸出來區(qū)別狀態(tài)n同步米利型輸出也是通過觸發(fā)

45、器的輸出直接實現(xiàn)，同步米利型輸出也是通過觸發(fā)器的輸出直接實現(xiàn)，因此也可以這樣用因此也可以這樣用n對于整個狀態(tài)機都使用面向輸出的編碼方式并不對于整個狀態(tài)機都使用面向輸出的編碼方式并不是很好的策略，明智的使用部分輸出作為編碼，是很好的策略，明智的使用部分輸出作為編碼，也許能減少狀態(tài)位的數量也許能減少狀態(tài)位的數量啟發(fā)式方法啟發(fā)式方法該方法試圖縮短相關狀態(tài)間的布爾空間的距離。如狀態(tài)該方法試圖縮短相關狀態(tài)間的布爾空間的距離。如狀態(tài)Y Y用狀用狀態(tài)態(tài)X X轉換而來，則它們的狀態(tài)編碼中的不同比特位應盡量少轉換而來，則它們的狀態(tài)編碼中的不同比特位應盡量少狀態(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)位的二進制值照狀態(tài)位的二進制值進行索引，給出該編進行索引，給出該編碼的狀態(tài)便放在圖中碼的狀態(tài)便放在圖中對應的的方格里（最對應的的方格里（最多能處理多能處理2 26 6個狀態(tài)）個狀態(tài)）最少位變化啟發(fā)式方法最少位變化啟發(fā)式方法目的是使所有狀態(tài)間的轉換中發(fā)生變化的位數最少目的是使所有狀態(tài)間的轉換中發(fā)生變化的位數最少第二種分配方案：第二

47、種分配方案： 分配分配S0S0，由于復位邏輯工作，通常將全，由于復位邏輯工作，通常將全0 0分配給起始狀態(tài)分配給起始狀態(tà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)先級：在給定的輸入轉換條件下，具有相同次態(tài)的狀態(tài)應最高優(yōu)先級：在給定的輸入轉換條件下，具有相同次態(tài)的狀態(tài)應該在狀態(tài)圖中放到鄰近的位置該在狀態(tài)圖中放到鄰近的位置中等優(yōu)先級：具有相同現(xiàn)態(tài)的次態(tài)應放在狀態(tài)圖中鄰近的位置中等優(yōu)先級：具有相同現(xiàn)態(tài)的次態(tài)應放在狀態(tài)圖中鄰近的位置最低優(yōu)先級：在給定輸入的情況下，具有相同輸出的狀態(tài)應該放最低優(yōu)先級：在給定輸入的情況下，具有相同輸出