狀態機

狀態機由狀態寄存器和組合邏輯電路構成，能夠根據控制信號按照預先設定的狀態進行狀態轉移，是協調相關信號動作，完成特定操作的控制中心。狀態機分為摩爾（Moore）型狀態機和米莉（Mealy）型狀態機。

就是狀態轉移圖。舉個最簡單的例子。人有三個狀態健康，感冒，康復中。觸發的條件有淋雨（t1），吃藥（t2），打針（t3），休息（t4）。所以狀態機就是健康-（t4）->健康；健康-（t1）->感冒；感冒-（t3）->健康；感冒-（t2）->康復中；康復中-（t4）->健康，等等。就是這樣狀態在不同的條件下跳轉到自己或不同狀態的圖。

關於狀態機的一個極度確切的描述是它是一個有向圖形，由一組節點和一組相應的轉移函數組成。狀態機通過響應一系列事件而“運行”。每個事件都在屬於“當前”節點的轉移函數的控制範圍內，其中函數的範圍是節點的一個子集。函數返回“下一個”（也許是同一個）節點。這些節點中至少有一個必須是終態。當到達終態，狀態機停止。

包含一組狀態集（states）、一個起始狀態（start state）、一組輸入符號集（alphabet）、一個映射輸入符號和當前狀態到下一狀態的轉換函數（transition function）的計算模型。當輸入符號串，模型隨即進入起始狀態。它要改變到新的狀態，依賴於轉換函數。在有限狀態機中，會有有許多變數，例如，狀態 機有很多與動作（actions）轉換(Mealy機)或狀態（摩爾機）關聯的動作，多重起始狀態，基於沒有輸入符號的轉換，或者指定符號和狀態（非定有 限狀態機）的多個轉換，指派給接收狀態（識別者）的一個或多個狀態，等等。

傳統應用程序的控制流程基本是順序的：遵循事先設定的邏輯，從頭到尾地執行。很少有事件能改變標準執行流程；而且這些事件主要涉及異常情況。“命令行實用程序”是這種傳統應用程序的典型例子。

另一類應用程序由外部發生的事件來驅動——換言之，事件在應用程序之外生成，無法由應用程序或程序員來控制。具體需要執行的代碼取決於接收到的事件，或者它 相對於其他事件的抵達時間。所以，控制流程既不能是順序的，也不能是事先設定好的，因為它要依賴於外部事件。事件驅動的GUI應用程序是這種應用程序的典 型例子，它們由命令和選擇（也就是用戶造成的事件）來驅動。

Web應用程序由提交的表單和用戶請求的網頁來驅動，它們也可劃歸到上述類別。但是，GUI應用程序對於接收到的事件仍有一定程度的控制，因為這些事件要依賴於向用戶顯示的窗口和控制項，而窗口和控制項是由程序員控制的。Web應用 程序則不然，因為一旦用戶採取不在預料之中的操作（比如使用瀏覽器的歷史記錄、手工輸入鏈接以及模擬一次表單提交等等），就很容易打亂設計好的應用程序邏輯。

顯然，必須採取不同的技術來處理這些情況。它能處理任何順序的事件，並能提供有意義的響應——即使這些事件發生的順序和預計的不同。有限狀態機正是為了滿足這方面的要求而設計的。

有限狀態機是一種概念性機器，它能採取某種操作來響應一個外部事件。具體採取的操作不僅能取決於接收到的事件，還能取決於各個事件的相對發生順序。之所以能 做到這一點，是因為機器能跟蹤一個內部狀態，它會在收到事件後進行更新。為一個事件而響應的行動不僅取決於事件本身，還取決於機器的內部狀態。另外，採取 的行動還會決定並更新機器的狀態。這樣一來，任何邏輯都可建模成一系列事件/狀態組合。

狀態機可歸納為4個要素，即現態、條件、動作、次態。這樣的歸納，主要是出於對狀態機的內在因果關係的考慮。“現態”和“條件”是因，“動作”和“次態”是果。詳解如下：

①現態：是指當前所處的狀態。

②條件：又稱為“事件”，當一個條件被滿足，將會觸發一個動作，或者執行一次狀態的遷移。

③動作：條件滿足后執行的動作。動作執行完畢后，可以遷移到新的狀態，也可以仍舊保持原狀態。動作不是必需的，當條件滿足后，也可以不執行任何動作，直接遷移到新狀態。

④次態：條件滿足后要遷往的新狀態。“次態”是相對於“現態”而言的，“次態”一旦被激活，就轉變成新的“現態”了。

思想廣泛應用於硬體控制電路設計，也是軟體上常用的一種處理方法(軟 件上稱為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可知，狀態機可以用兩種方法實現：豎著寫(在狀態中判斷事件)和橫著寫( 在事件中判斷狀態)。這兩種實現在本質上是完全等效的，但在實際操作中，效果卻截然 不同。

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狀態圖如圖1所示。

S0/0S1/1S3/0S2/100110011

其中S0/0所代表的意思為現在是狀態S0且輸出為0，狀態圖最主要是將每個狀態都給予一個編號，詳細描述如下：

1）在某狀態時，列出所有的輸出條件。

2）在某狀態時，當輸入信號是什麼則會跳至哪一個狀態。

3）在某狀態時，當輸入信號是什麼則會維持原狀態不變。

可以將圖1的Moore狀態機寫成狀態表如表1.

表1 Moore狀態表

狀態表主要描述它與狀態圖的關係，再設計狀態機電路是，需要先定義狀態機的變數，定義狀態機的變數時使用枚舉類型來定義，如下範例所示：

Type State is (S0,S1,S2,S3)

接下來，狀態會被加以編碼。其狀態編碼方式如下：

（1）時序編碼（Sequential）

將每個狀態以二進位來做編碼。

（2）格雷碼(Gray)

也是將四個State以二進位來編碼，不過不同的是每次編碼只會差一個位，其主要缺點是狀態改變是要依序改變才可以，若狀態不是依序是，則Gray編碼不適用。

（3）獨熱碼（One hot）

獨熱碼狀態編碼的特色為每一個狀態均有自己的觸發器，所以若有N個狀態就也存在有N個觸發器，在任一時刻只會有一組狀態編碼，缺點是會產生較大的電路，但是相對的使用獨熱碼狀態編碼對幀錯相當有幫助。

三種格式之狀態編碼如表2所示。

從狀態編碼表可以看出時序編碼和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狀態機，它和輸入、輸出、狀態皆有關。它的狀態圖、狀態表與Moore狀態機都有所不同，輸出會隨輸入變化而變化。如圖5 所示。

圖5：

S0S1S3S20/11/10/10/01/11/0 1/0

若現態為s0輸入為0時，則次態為s0且輸出為0；若現態為s0輸入為1時，則次態為s1且輸出為1。

根據這個規則，列出Mealy狀態機的狀態表如表3。

其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 所示。