有限狀態機（Finite State Machine）

簡介

有限狀態機（Finite State Machine，簡稱FSM）是指狀態節點數和輸入、輸出范圍皆有限的狀態機。

狀態機的組成六要素

(1) 狀態集合

狀態集合是組成狀態機的必備要素，該集合里包含了狀態機所能達到的所有狀態：

{起床, 找小明, 找小強, 踢足球, 喝冷飲, 看電影, 吃火鍋, 打游戲, 睡覺}

Summary: 狀態集合定義了狀態機可以存在的所有狀態。

(2) 初態

初態是狀態機的第二個必備要素，它是整個狀態機開始工作的起點。

Summary: 初態決定了狀態機的起始狀態。

(3) 終態

終態是狀態機的結束狀態，即若狀態機到達終態，它的使命也將完成，從此不再工作。事實上，大部分運行在FPGA上的狀態機是沒有終態的，因為它們都需要用有限的狀態來處理無限的事件。

Summary: 終態表示狀態機的任務完成狀態，但在FPGA中很少存在真正的終態。

(4) 輸入符號集

輸入符號集是驅動狀態機進行狀態轉換的主要因素，不過狀態機的狀態轉換不一定需要外界的事件觸發，因此輸入符號集也不是組成狀態機的必備要素。但是大部分運行在FPGA上的狀態機還是需要輸入符號集的，至少大多數情況下，它們都需要一個復位信號來讓狀態機進入初態。

Summary: 輸入符號集用于驅動狀態轉換，但在某些情況下可以沒有輸入符號集。

(5) 輸出符號集

輸出符號集是狀態機輸出結果的集合。狀態機的輸出是由現態或現態和輸入共同決定的。

Summary: 輸出符號集定義了狀態機可能產生的所有輸出。

(6) 狀態轉移函數

狀態轉移函數定義了狀態機如何從一個狀態轉移到另一個狀態。它決定了在給定輸入的情況下，狀態機會轉移到哪個下一個狀態。

Summary: 狀態轉移函數決定了狀態機的狀態轉換規則。

狀態機的工作四要素

狀態機在工作時，將狀態機的工作狀態劃分為四個要素——現態、輸入、輸出、次態。其中，“現態”和“輸入”是因，“輸出”和“次態”是果，分別介紹如下。

(1) 現態

現態指狀態機當前所處的狀態。

Summary: 現態是狀態機在某一時刻的具體狀態。

(2) 輸入

輸入一般指外部事件，當一個外部事件發生后，狀態機便會根據狀態轉移函數發生相應的狀態跳轉，或者狀態機將會更新自己的輸出情況。在FPGA中，根據輸入信號是異步的還是同步的又可將狀態機分為異步狀態機和同步狀態機。鑒于穩定性的考慮，以后提到和FPGA相關的狀態機全部為同步狀態機。對于異步輸入信號，可以參考【本篇→編程思路→時鐘及時鐘域→跨時鐘域問題】中的相關處理方法，同步化后再送至狀態機。

Summary: 輸入是觸發狀態機狀態轉換的條件。

(3) 輸出

輸出是由現態或者現態和輸入共同決定的，如果這兩者都沒有變化，那么輸出也不應該有變化。輸出符號集是必需的，但具體到某一狀態或者某一輸入觸發事件，輸出并不是必需的，有時候帶來的僅僅是狀態遷移而已。

Summary: 輸出是狀態機在某一狀態下可能產生的結果。

(4) 次態

次態是根據現態、輸入及狀態轉移函數所得出的狀態機將要跳轉至的新狀態。次態是相對于現態而言的，一旦狀態遷移完成，次態便成為了新的現態。

Summary: 次態是狀態機即將進入的新狀態。

FPGA中的狀態機模型

按照狀態機的輸出與其現態、輸入之間的關系，可將FPGA中的狀態機抽象為三種基本模型——Moore、Mealy和Mix，即摩爾型、米利型和混合型，分別介紹如下。

1. Moore型狀態機

如果一個狀態機的輸出僅由現態決定，那么它就是一個Moore型的狀態機。而按照驅動輸出的數字電路特性，又將Moore型狀態機細分為Moore l型、Moore 2型、Moore 3型，詳細介紹如下。

(1) Moore l型

Moore 1型狀態機的原理結構框圖如下所示：

從圖中可以看出，Moore 1型狀態機的結構可以劃分為兩大部分——狀態轉移部分和輸出生成部分。

• 狀態轉移部分：輸入和現態（現態寄存器的輸出）通過組合邏輯共同作用產生次態，當下一次時鐘有效邊沿到來的時候，現態寄存器發生更新，剛才產生的次態即成為了新的現態，而新的現態將和新的輸入共同作用產生新的次態，如此往復。
• 輸出生成部分：現態（現態寄存器的輸出）直接通過組合邏輯產生當前的輸出（這點也是Moore狀態機區別于Mealy狀態機最顯著的特點）。有時候，我們不希望將這部分的組合邏輯的延遲影響到后續模塊的處理，那么可以仿照圖通過添加輸出寄存器來解決這個問題，但是需要特別注意的一點是，由于輸出寄存器的更新需要等到下次時鐘的有效邊沿，因此經過輸出寄存器寄存后的輸出其實對應的是狀態機上一個狀態。

Summary: Moore 1型狀態機的輸出僅由現態決定，存在輸出延遲的問題。

(2) Moore 2型

Moore 2型狀態機的原理結構框圖如下所示：

從圖中可以看出，Moore 2型狀態機的結構仍劃分為狀態轉移和輸出生成兩大部分。與Moore 1型狀態機相比，輸出生成部分的輸入端由之前的現態（現態寄存器的輸出）變為了次態（由輸入和現態通過組合邏輯產生）。這樣一來，由于次態和次態決定的輸出在同一個時鐘周期內變得有效，那么在下一次時鐘有效邊沿到來時，現態寄存器和輸出寄存器將會同時進行更新，至此，次態變成新的現態，次態決定的輸出變成新的輸出。因此，Moore 2型狀態機中經過寄存后的輸出是對應于當前狀態的。

Summary: Moore 2型狀態機通過改變輸出生成部分的輸入端，解決了輸出延遲的問題。

(3) Moore 3型

Moore 3型狀態機的原理結構框圖如下所示：

通過上圖可以看出，Moore 3型狀態機就是將那些適合使用組合邏輯的輸出采用Moore 1型的方式來處理，而將那些適合使用寄存器的輸出采用Moore 2型的方式來處理，因此Moore 3型也叫混合型Moore狀態機。

Summary: Moore 3型狀態機結合了Moore 1型和Moore 2型的優點，適用于不同的輸出需求。

2. Mealy型狀態機

如果一個狀態機的輸出是由現態和輸入共同決定的，那么它就是一個Mealy型的狀態機。而按照驅動輸出的數字電路特性，又將Mealy型狀態機細分為Mealy l型、Mealy 2型、Mealy 3型，詳細介紹如下。

(1) Mealy l型

Mealy 1型狀態機的原理結構框圖如下所示：

從圖中可以看出，對于Mealy 1型狀態機來說，由于次態和輸出均由現態和輸入通過組合邏輯共同決定，因此可以將狀態轉移部分和輸出生成部分合并成一個部分，兼并產生狀態機的次態和輸出。當下一次時鐘有效邊沿到來后，現態寄存器完成刷新，次態成為了新的現態，而新的現態和新的輸入共同作用產生新的次態和新的輸出，如此往復。

Summary: Mealy 1型狀態機的輸出由現態和輸入共同決定，可能產生輸出延遲的問題。

(2) Mealy 2型

Mealy 2型狀態機的原理結構框圖如下所示：

從圖中可以看出，Mealy 2型狀態機重新將狀態轉移部分和輸出生成部分分開，并做成級聯的形態。輸出生成部分由次態和輸入共同作用產生次態對應的輸出。這樣，由于次態和次態決定的輸出在同一個時鐘周期內變得有效，那么在下一次時鐘有效邊沿到來時，現態寄存器和輸出寄存器將會同時進行更新，至此，次態變成新的現態，次態決定的輸出變成新的輸出。因此，Mealy 2型狀態機中經過寄存后的輸出是對應于當前狀態的。

Summary: Mealy 2型狀態機通過將狀態轉移部分和輸出生成部分分開，解決了輸出延遲的問題。

(3) Mealy 3型

Mealy 3型狀態機的原理結構框圖如下所示：

與Moore型狀態機類似，Mealy l型和Mealy 2型狀態機也各有其優缺點。它們的本質區別仍在于“由狀態產生輸出”這部分的組合邏輯所處的位置。如果像Mealy l型那樣，將該部分邏輯和次態產生邏輯并聯，那么該組合邏輯的時間延遲將會影響到后續電路的工作；反之，如果像Mealy 2型那樣，將該部分邏輯和次態產生邏輯串聯，那么該組合邏輯的時間延遲將會影響到狀態機自身的工作。因此，為了將Mealy l型和Mealy 2型狀態機的缺點最小化、優點最大化，便有了Mealy 3型狀態機。

Summary: Mealy 3型狀態機結合了Mealy 1型和Mealy 2型的優點，適用于不同的輸出需求。

3. Mix型狀態機

如果一個狀態機有多個輸出，且其中一些僅由現態決定，而另一些是由現態和輸入共同決定的，那么它就是一個Mix型的狀態機。其實，Mix型狀態機就是一個Moore型狀態機和Mealy型狀態機的組合體，而每一個Moore型狀態機可以有Moore 1型、Moore 2型、Moore 3型三種選擇，每一個Mealy型狀態機也可以有Mealy l型、Mealy 2型、Mealy 3型三種選擇，因此Mix型狀態機可以細分為9種類型。

Summary: Mix型狀態機結合了Moore型和Mealy型狀態機的優勢，適用于復雜的輸出需求。