狀態機由狀態寄存器和組合邏輯電路構成,能夠根據控制信號按照預先設定的狀態進行狀態轉移,是協調相關信號動作、完成特定操作的控制中心。有限狀態機簡寫為FSM(Finite?State?Machine),主要分為2大類:第一類,若輸出只和狀態有關而與輸入無關,則稱為Moore狀態機。第二類,輸出不僅和狀態有關而且和輸入有關系,則稱為Mealy狀態機。狀態機就是狀態轉移圖。舉個最簡單的例子,人有三個狀態:健康,感冒,康復中。觸發的條件有淋雨(t1),吃藥(t2),打針(t3),休息(t4)。所以狀態機就是健康-(t4)->健康;健康-(t1)->感冒;感冒-(t3)->健康;感冒-(t2)->康復中;康復中-(t4)->健康,等等。就是這樣狀態在不同的條件下跳轉到自己或不同狀態的圖。

中文名

狀態機

外文名

Finite?State?Machine

別名

狀態轉移圖

縮寫

FSM

類別

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個要素,即現態、條件、動作、次態。這樣的歸納,主要是出于對狀態機的內在因果關系的考慮?!艾F態”和“條件”是因,“動作”和“次態”是果。詳解如下:

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

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

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

④次態:條件滿足后要遷往的新狀態?!按螒B”是相對于“現態”而言的,“次態”一旦被激活,就轉變成新的“現態”了。

兩種寫法

思想廣泛應用于硬件控制電路設計,也是軟件上常用的一種處理方法(軟?件上稱為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)?使用兩個進程語句來設計狀態機

Moore?FSM?模擬波形。

模擬結果說明:

(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狀態機都有所不同,輸出會隨輸入變化而變化。

0/0

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狀態機綜合電路。