狀態機

狀態機

狀態機由狀態暫存器和組合邏輯電路構成,能夠根據控制信號按照預先設定的狀態進行狀態轉移,是協調相關信號動作、完成特定操作的控制中心。有限狀態機簡寫為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 所示。

相關詞條

熱門詞條

聯絡我們