狀態機

狀態機

狀態機由狀態暫存器和組合邏輯電路構成，能夠根據控制信號按照預先設定的狀態進行狀態轉移，是協調相關信號動作、完成特定操作的控制中心。有限狀態機簡寫為FSM（Finite State Machine），主要分為2大類：

第一類，若輸出只和狀態有關而與輸入無關，則稱為Moore狀態機

第二類，輸出不僅和狀態有關而且和輸入有關係，則稱為Mealy狀態機

基本介紹

  • 中文名：狀態機
  • 外文名：Finite State Machine
  • 縮寫：FSM
  • 又名：狀態轉移圖
基本信息,狀態機綜述,兩種寫法,有限狀態機FSM,豎著寫C代碼片段,其它,Moore狀態機,範例,Mealy狀態機,

基本信息

狀態機由狀態暫存器和組合邏輯電路構成，能夠根據控制信號按照預先設定的狀態進行狀態轉移，是協調相關信號動作,完成特定操作的控制中心。狀態機分為摩爾（Moore）型狀態機和米莉（Mealy）型狀態機。
就是狀態轉移圖。舉個最簡單的例子。人有三個狀態健康，感冒，康復中。觸發的條件有淋雨（t1），吃藥（t2），打針（t3），休息（t4）。所以狀態機就是健康-（t4）->健康；健康-（t1）->感冒；感冒-（t3）->健康；感冒-（t2）->康復中；康復中-（t4）->健康，等等。就是這樣狀態在不同的條件下跳轉到自己或不同狀態的圖。

狀態機綜述

關於狀態機的一個極度確切的描述是它是一個有向圖形，由一組節點和一組相應的轉移函式組成。狀態機通過回響一系列事件而“運行”。每個事件都在屬於“當前” 節點的轉移函式的控制範圍內，其中函式的範圍是節點的一個子集。函式返回“下一個”（也許是同一個）節點。這些節點中至少有一個必須是終態。當到達終態， 狀態機停止。
包含一組狀態集（states）、一個起始狀態（start state）、一組輸入符號集（alphabet）、一個映射輸入符號和當前狀態到下一狀態的轉換函式（transition function）的計算模型。當輸入符號串，模型隨即進入起始狀態。它要改變到新的狀態，依賴於轉換函式。在有限狀態機中，會有有許多變數，例如，狀態 機有很多與動作（actions）轉換(Mealy機)或狀態（摩爾機）關聯的動作，多重起始狀態，基於沒有輸入符號的轉換，或者指定符號和狀態（非定有 限狀態機）的多個轉換，指派給接收狀態（識別者）的一個或多個狀態，等等。
傳統應用程式的控制流程基本是順序的：遵循事先設定的邏輯，從頭到尾地執行。很少有事件能改變標準執行流程；而且這些事件主要涉及異常情況。“命令行實用程式”是這種傳統應用程式的典型例子。
另一類應用程式由外部發生的事件來驅動——換言之，事件在應用程式之外生成，無法由應用程式或程式設計師來控制。具體需要執行的代碼取決於接收到的事件，或者它 相對於其他事件的抵達時間。所以，控制流程既不能是順序的，也不能是事先設定好的，因為它要依賴於外部事件。事件驅動的GUI應用程式是這種應用程式的典 型例子，它們由命令和選擇（也就是用戶造成的事件）來驅動。
Web應用程式由提交的表單和用戶請求的網頁來驅動，它們也可劃歸到上述類別。但是，GUI應用程式對於接收到的事件仍有一定程度的控制，因為這些事件要依賴於向用戶顯示的視窗和控制項，而視窗和控制項是由程式設計師控制的。Web套用 程式則不然，因為一旦用戶採取不在預料之中的操作（比如使用瀏覽器的歷史記錄、手工輸入連結以及模擬一次表單提交等等），就很容易打亂設計好的應用程式邏輯。
顯然，必須採取不同的技術來處理這些情況。它能處理任何順序的事件，並能提供有意義的回響——即使這些事件發生的順序和預計的不同。有限狀態機正是為了滿足這方面的要求而設計的。
有限狀態機是一種概念性機器，它能採取某種操作來回響一個外部事件。具體採取的操作不僅能取決於接收到的事件，還能取決於各個事件的相對發生順序。之所以能 做到這一點，是因為機器能跟蹤一個內部狀態，它會在收到事件後進行更新。為一個事件而回響的行動不僅取決於事件本身，還取決於機器的內部狀態。另外，採取 的行動還會決定並更新機器的狀態。這樣一來，任何邏輯都可建模成一系列事件/狀態組合。
狀態機可歸納為4個要素，即現態、條件、動作、次態。這樣的歸納，主要是出於對狀態機的內在因果關係的考慮。“現態”和“條件”是因，“動作”和“次態”是果。詳解如下：
①現態：是指當前所處的狀態。
②條件：又稱為“事件”，當一個條件被滿足，將會觸發一個動作，或者執行一次狀態的遷移。
③動作：條件滿足後執行的動作。動作執行完畢後，可以遷移到新的狀態，也可以仍舊保持原狀態。動作不是必需的，當條件滿足後，也可以不執行任何動作，直接遷移到新狀態。
④次態：條件滿足後要遷往的新狀態。“次態”是相對於“現態”而言的，“次態”一旦被激活，就轉變成新的“現態”了。

兩種寫法

有限狀態機FSM

思想廣泛套用於硬體控制電路設計，也是軟體上常用的一種處理方法(軟 件上稱為FMM--有限訊息機)。它把複雜的控制邏輯分解成有限個穩定狀態，在每個狀態上判斷事件，變連續處理為離散數字處理，符合計算機的工作特點。同時，因為有限狀態機具有有限個狀態，所以可以在實際的工程上實現。但這並不意味著其只能進行有限次的處理，相反，有限狀態機是閉環系統，有限無窮，可以用有限的狀態，處理無窮的事務。
有限狀態機的工作原理如圖1所示，發生事件(event)後，根據當前狀態(cur_state) ，決定執行的動作(action)，並設定下一個狀態號(nxt_state)。
狀態機
狀態機
狀態機
表1 圖2狀態機實例的二維表格表示(動作/下一狀態)
圖2為一個狀態機實例的狀態轉移圖，它的含義是：
在s0狀態，如果發生e0事件，那么就執行a0動作，並保持狀態不變；
如果發生e1事件，那么就執行a1動作，並將狀態轉移到s1態；
如果發生e2事件，那么就執行a2動作，並將狀態轉移到s2態；
在s1狀態，如果發生e2事件，那么就執行a2動作，並將狀態轉移到s2態；
在s2狀態，如果發生e0事件，那么就執行a0動作，並將狀態轉移到s0態；
有限狀態機不僅能夠用狀態轉移圖表示，還可以用二維的表格代表。一般將當前狀 態號寫在橫行上，將事件寫在縱列上，如表1所示。其中“--”表示空(不執行動作，也 不進行狀態轉移)，“an/sn”表示執行動作an,同時將下一狀態設定為sn。表1和圖2表示 的含義是完全相同的。
觀察表1可知，狀態機可以用兩種方法實現：豎著寫(在狀態中判斷事件)和橫著寫( 在事件中判斷狀態)。這兩種實現在本質上是完全等效的，但在實際操作中，效果卻截然 不同。

豎著寫C代碼片段

cur_state = nxt_state;
switch(cur_state){ //在當前狀態中判斷事件
case s0: //在s0狀態
if(e0_event){ //如果發生e0事件，那么就執行a0動作，
並保持狀態不變；
執行a0動作;
//nxt_state = s0; //因為狀態號是自身，所以可以刪除此句
，以提高運行速度。
}
else if(e1_event){ //如果發生e1事件，那么就執行a1動作，
並將狀態轉移到s1態；
執行a1動作;
nxt_state = s1;
}
else if(e2_event){ //如果發生e2事件，那么就執行a2動作，
並將狀態轉移到s2態；
執行a2動作;
nxt_state = s2;
}
break;
case s1: //在s1狀態
if(e2_event){ //如果發生e2事件，那么就執行a2動作，
並將狀態轉移到s2態；
執行a2動作;
nxt_state = s2;
}
break;
case s2: //在s2狀態
if(e0_event){ //如果發生e0事件，那么就執行a0動作，
並將狀態轉移到s0態；
執行a0動作;
nxt_state = s0;
}
}
橫著寫(在事件中判斷狀態)C代碼片段
//e0事件發生時，執行的函式
void e0_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //觀察表1，在e0事件發生時，s1處為空
case s2:
執行a0動作;
*nxt_state = s0;
}
}
//e1事件發生時，執行的函式
void e1_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //觀察表1，在e1事件發生時，s1和s2處為
空
執行a1動作;
*nxt_state = s1;
}
}
//e2事件發生時，執行的函式
void e2_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //觀察表1，在e2事件發生時，s2處為空
case s1:
執行a2動作;
*nxt_state = s2;
}
}

其它

Moore狀態機

其Moore狀態圖如圖1所示。
S0/0S1/1S3/0S2/100110011
其中S0/0所代表的意思為現在是狀態S0且輸出為0，狀態圖最主要是將每個狀態都給予一個編號，詳細描述如下：
1） 在某狀態時，列出所有的輸出條件。
2） 在某狀態時，當輸入信號是什麼則會跳至哪一個狀態。
3） 在某狀態時，當輸入信號是什麼則會維持原狀態不變。
可以將圖1的Moore狀態機寫成狀態表如表1.
表1 Moore狀態表
現態
次態
輸出
輸入
X=0
X=1
X=0
X=1
S0
S0
S1
0
0
S1
S1
S2
1
1
S2
S3
S0
0
0
S3
S0
S3
0
0
狀態表主要描述它與狀態圖的關係，再設計狀態機電路是，需要先定義狀態機的變數，定義狀態機的變數時使用枚舉類型來定義，如下範例所示：
Type State is (S0,S1,S2,S3)
接下來，狀態會被加以編碼。其狀態編碼方式如下：
（1） 時序編碼（Sequential）
將每個狀態以二進制來做編碼。
（2）格雷碼(Gray)
也是將四個State以二進制來編碼，不過不同的是每次編碼只會差一個位，其主要缺點是狀態改變是要依序改變才可以，若狀態不是依序是，則Gray編碼不適用。
（3） 獨熱碼（One hot）
獨熱碼狀態編碼的特色為每一個狀態均有自己的觸發器，所以若有N個狀態就也存在有N個觸發器，在任一時刻只會有一組狀態編碼，缺點是會產生較大的電路，但是相對的使用獨熱碼狀態編碼對幀錯相當有幫助。
三種格式之狀態編碼如表2所示。
狀態
時序編碼
Gray編碼
One hot編碼
S0
00
00
0001
S1
01
01
0010
S2
10
11
0100
S3
11
10
1000
從狀態編碼表可以看出時序編碼和Gray編碼均是用二個位來做編碼，而以獨熱碼作為編碼方式則編碼位增加至四個位，所以電路比其他兩種編碼方式都大一些。
所以可以使用屬性來定義編碼方式，若要編碼成獨熱碼編碼，則可加上：
Type State is (S0,S1,S2,S3);
Attribute encoding of state;
Type is “0001 0010 0100 1000”;
在設計狀態機時，通常使用進程語句來描述狀態機，其中進程語句又可以分為三種方式：
n 一個進程
利用一個進程來描述狀態的轉換及輸出信號的定義。
n 兩個進程
一個為時序電路主要負責狀態變數的更新，此進程為同步電路，而另一個進程語句主要是描述下次態變數和輸出的更新。
n 三個進程
第一個進程主要負責狀態變數的更新，第二個進程語句負責描述次態變數，而最後一個則是負責輸出信號的更新。
有了以上的初步觀念，可以設計圖1四個狀態的Moore狀態機。

範例

首先根據之前的狀態表編寫VHDL程式如下所示：
Library ieee;
Use ieee.std_logic_1164.all;
Use ieee.numeric_std.all;
Entity moore_fsm is
Port(
clk : in std_logic;
rstn : in std_logic;
x : in std_logic;
output : out std_logic
);
End moore_fsm;
Architecture rtl of moore_fsm is
Type state is (s0,s1,s2,s3); ---狀態定義
Signal current_state : state; ---現態
Signal next_state : state; ---次態
Begin
Statefsm: process(rstn, x, current_state)
Begin
If rstn = ‘0’ then --異步reset
next_state <= s0;
output <= ‘0’;
else
case current_state is
when s0 =>
if x =’0’ then
next_state <= s0;
else
next_state <= s1;
end if;
output <= ‘0’;
when s1 =>
if x =’0’ then
next_state <= s1;
else
next_state <= s2;
end if;
output <= ‘1’;
when s2 =>
if x =’0’ then
next_state <= s3;
else
next_state <= s0;
end if;
output <= ‘0’;
when s3 =>
if x =’0’ then
next_state <= s0;
else
next_state <= s3;
end if;
output <= ‘0’;
end case;
end if;
end process statefsm;
stat: process(clk) --current_stateànext_state
begin
if rising_edge (clk) then
current_state <=next_state;
end if;
end process stat;
end rtl;
1) 編碼方式預設為時序編碼
2) 使用兩個進程語句來設計狀態機
其綜合電路如圖2 所示。
其狀態圖如圖3 所示。
Moore FSM 模擬波形如圖4 所示。
模擬結果說明：
（1） 由於reset 為異步reset ，所以當reset在150ns~200ns為0時，則狀態圖會從s1回到s0.
（2） 在50 ns時輸入x為0且現態為1，在70 ns 時clk上升沿觸發且x為1，則current_state會變成next_state s2;

Mealy狀態機

接下來我們要介紹Mealy狀態機，它和輸入、輸出、狀態皆有關。它的狀態圖、狀態表與Moore狀態機都有所不同，輸出會隨輸入變化而變化。如圖5 所示。
0/0
圖5：
S0S1S3S20/11/10/10/01/11/0 1/0
若現態為s0輸入為0時，則次態為s0且輸出為0；若現態為s0輸入為1時，則次態為s1且輸出為1。
根據這個規則，列出Mealy狀態機的狀態表如表3。
現態
次態
　輸出
輸入
X=0
X=1
X=0
X=1
S0
S0
S1
0
1
S1
S2
S1
1
0
S2
S3
S0
0
1
S3
S0
S3
1
0
其Mealy狀態機的VHDL如下所示：
Library ieee;
Use ieee.std_logic_1164.all;
Use ieee.numeric_std.all;
Entity melay_fsm is
Port(
clk: : in std_logic;
rstn : in std_logic;
x : in std_logic;
output : out std_logic
);
End moore_fsm;
Architecture rtl of moore_fsm is
Type state is (s0,s1,s2,s3); ---狀態定義
Signal current_state : state; ---現態
Signal next_state : state; ---次態
Begin
Statefsm: process(rstn, x, current_state)
Begin
If rstn = ‘0’ then --異步reset
next_state <= s0;
output <= ‘0’;
else
case current_state is
when s0 =>
if x =’0’ then
next_state <= s0;
else
next_state <= s1;
end if;
if x= ‘0’ then
output <= ‘0’;
else
output <= ‘1’;
end if;
when s1 =>
if x =’0’ then
next_state <= s2;
else
next_state <= s1;
end if;
if x= ‘0’ then
output <= ‘1’;
else
output <= ‘0’;
end if;
when s2 =>
if x =’0’ then
next_state <= s3;
else
next_state <= s0;
end if;
if x= ‘0’ then
output <= ‘0’;
else
output <= ‘1’;
end if;
when s3 =>
if x =’0’ then
next_state <= s0;
else
next_state <= s3;
end if;
if x= ‘0’ then
output <= ‘1’;
else
output <= ‘0’;
end if;
end case;
end if;
end process statefsm;
stat: process(clk) --current_stateànext_state
begin
if prsing_edge (clk) then
current_state <=next_state;
end if;
end process stat;
end rtl;
Mealy狀態機綜合電路如圖6 所示。

相關詞條

熱門詞條

聯絡我們