什麼是有限狀態機？

有限狀態機(Finite State Machine)簡稱FSM。

首先什麼是有限狀態機？我們可以用自己的話來理解，可以先拋開官方解釋可能會更好理解一些。

有限顧名思義就是可以數得來的，也就是說，這個狀態機所有的狀態都是有限的，比如3個、4個、5個等等。反正不管它有多少個狀態，肯定是有限的。所以就叫做有限狀態機。

與之對應的當然就有個無限狀態機(ISM)的東東，具體是什麼東西，就先不講了，有機會再講，可能很多人對於自然語言處理裡面的下推自動機(Pushdown Automaton,PDA)比較熟悉，其實PDA就是一種特殊的無限狀態自動機(Infinite State Machine,ISM)

要是把有限狀態機(FSM)的所有狀態看作一個集合，那麼其在任意時刻都處於有限狀態集合中的某一狀態。當其獲得一個輸入字符時，將從當前狀態轉換到另一個狀態，或者仍然保持在當前狀態。

作為一個有限狀態機，完整的FSM組成是由：一組狀態，一些輸入，一些輸出以及一組狀態到狀態的轉換規則組成。

而在數字系統中，特別是FPGA中有限狀態機也是一個非常常見的數字系統的主要組成部分，可以用在數字系統的核心部件設計中，可實現高效並且可靠的邏輯控制。

一個設計良好的狀態機可以很容易地通過FPGA硬件描述語言(例如Verilog或VHDL)來編程實現，然後就可以在數字IC(集成電路)上綜合實現。

一般狀態機的狀態轉換圖

分析上面的狀態機狀態轉換圖，可以看出該轉換圖中有兩個特殊的狀態節點，狀態1稱為起始狀態，這個是每一個狀態機必須有的一個狀態，還有一個狀態6，是結束狀態。

狀態機工作過程：在啟動一個FSM時，首先必須將FSM置於“起始狀態”，也就是狀態轉換圖的狀態1，然後會根據輸入情況進入其它狀態，比如轉換圖中的當輸入為A時會從狀態1轉換為狀態2，當輸入為D時，會從狀態1轉換到狀態5。

最終FSM會到達“結束狀態”，或者消亡狀態。

數字系統FSM結構圖

上圖所示的狀態機為最常見的數字系統FSM，可以看出主要分為時序部分、邏輯部分與輸出部分組成，組合邏輯部分決定下一個狀態是什麼，時序邏輯決定當前狀態。

並且還需要時鐘同步整個過程以及Reset來恢復到初試狀態。

而在數字系統中，將FSM(有限狀態機)分為Moore狀態機與Mealy狀態機，其中Moore也可以翻譯為摩爾，Mealy也可以翻譯為米立，當然你要是願意，叫米粒也是可以的。

下面就著重講下：什麼是Moore與Mealy狀態機以及兩者的不同之處。

Moore狀態機介紹

首先講下Moore狀態機，摩爾狀態機也是FSM種的一種，主要是指輸出只取決於當前狀態的狀態機，也就是說，狀態機的輸出只與狀態機所處的當前狀態有關。

下圖所示為一般Moore狀態機的狀態轉換圖，可以看出該狀態機有四個狀態S0--S3，還可以看出輸出Dout是與狀態在一起，“

Moore狀態機狀態轉換圖

Mealy狀態機介紹

Mealy狀態機主要是指輸出不光取決於當前狀態，還與輸入有關係的狀態機。

下圖所示為一般的Mealy狀態機狀態轉換圖，可以看出，與上圖的Moore狀態機相比較，輸出不是與狀態一起，而是移出到了“圈圈外面”，是跟輸入Din在一起的，說明輸出不光與當前有關，還與輸入有關。

Mealy狀態機轉換圖

所以說，具體識別狀態機屬於哪種狀態機，只需要看他們的狀態轉換圖就可以，輸出在“圈圈外面”且與輸入Din在一起的就屬於Mealy米粒狀態機。

輸出與狀態在一起在“圈圈裡面”的就屬於Moore狀態機，是不是特別簡單，以後再也不用愁區分不開一個狀態機屬於哪種狀態機了吧。

下面將這兩種狀態機進行一個比較。

Moore與Mealy狀態機對比

Moore與Mealy狀態機主要有以下幾點不同點與共同點。

1. 兩者在形式上都是按時序邏輯、組合邏輯、狀態轉換、控制輸出等部分劃分的；
2. 本質上來說，Moore狀態機輸出信號由當前狀態決定，Mealy狀態機輸出信號由當前狀態與輸入信號共同決定；
3. 輸出時序上，Moore狀態機同步輸出，Mealy狀態機異步輸出；
4. 輸出變化上，Mealy狀態機比Moore狀態機領先一個時鐘週期；

針對以上特點的具體解釋，請看下一篇關於FPGA學習的文章。下一篇文章主要通過使用FPGA硬件描述語言來實現這兩種狀態機，並且也會將大家容易混淆的一段式、兩段式、三段式狀態機編程實現方式進行詳細的講解。

結尾：

通過本篇文章，你應該對狀態機有了一個特別詳細的瞭解了，相信已經講解的足夠清楚了，要是還有不清楚的地方或者講錯的地方都可以留言或者關注我一起交流，一起學習。

更多學習相關內容都可以關注我哦，感謝您的閱讀。

閱讀更多 學習以後 的文章

關鍵字: 狀態 設計 自然語言處理