有限狀態機

每一個有限狀態機 (Finite State Machine, FSM) 通常包含了以下幾個組成要件：輸入字母表、狀態集合、轉移函數、輸出子母表、輸出函數，而根據輸出的產生方式不同，FSM 又可以分為以下兩種模型。

Mealy Machine

Mealy Machine [1] 的輸出和目前的狀態以及輸入有關。

數學模型 (S, S0, Σ, Λ, T, G)
S：狀態集合
S0：初始狀態
Σ：輸入子母表
Λ：輸出子母表
T：轉移函數 (T: S×Σ → S)
G：輸出函數 (G: S×Σ → Λ)

Moore Machine

Moore Machine [2] 的輸出只和目前的狀態有關。

數學模型 (S, S0, Σ, Λ, T, G)
S：狀態集合
S0：初始狀態
Σ：輸入子母表
Λ：輸出子母表
T：轉移函數 (T: S×Σ → S)
G：輸出函數 (G: S → Λ)

從輸出函數 G 的差異可以看出，Moore Machine 的輸出只和目前的狀態有關，而Mealy Machine 的輸出和目前的狀態以及輸入都有關。

FSM 設計流程

1. 畫 State diagram
2. 建立兩個真值表 (truth table)，一個是 next state 和 present state 及 input 的關係，另一個是 output 和 present state 及 input (Mealy machine only) 的關係
3. 運用 Karnaugh map 進行邏輯化簡，得到 next state 和 output 的布林函數
4. 使用 combinational circuit 實現布林函數，用 DFF 存放 FSM 狀態
5. 決定是否要在 output 之後加上一個額外的 DFF，以消除 glitch 或實現 pipelining

其他在設計上需注意之重點：

• Mealy machine 和 Moore machine 可以互相轉換，並且 Mealy machine 的狀態數量會小於或等於 Moore machine
• 需檢查是否存在 under- or overspecified state transition diagram
• Transition 種類：{conditional, timed, conditional-timed, unconditional}
• FSM 種類：{regular machine, timed machine, recursive machine}

FSM 種類

• Regular machine：State machine 的轉移函數與時間無關，且輸出函數與先前的 output 無關
• Timed machine：State machine 的轉移函數與時間有關，但輸出函數與先前的 output 無關
• Recursive machine：State machine 的轉移函數與時間有關，且輸出函數與先前的 output 有關

在 timed machine 中，由於轉移函數與時間有關，所以在硬體上需要一個 counter，在每一次狀態轉換的時候，counter 會歸零，並且當處在轉移函數與時間有關的狀態中時，counter 會在每一個 clock cycle 遞增。

而在 recursive machine 中，由於輸出函數與先前的 output 有關，因此需要額外的 memory 用來儲存先前的 output。

FSM 結合/分解 (Association/Decomposition)

當我們要實現一個較複雜的功能時，可以先實現多個較簡單的 FSMs，並且將這些 FSMs 結合起來。也可以看做是將一個複雜 FSM，拆解成多個簡單的 FSMs。

FSM 結合的方法有以下三種：

1. 序列結合式 (Serial association)
2. 平行結合式 (Parallel association)
3. 內部結合式 (Internal association)

Datapath 控制單元 (Control Unit)

無論是簡單的算數邏輯運算，或是較複雜的演算法，其實都是一個資料流動的過程，資料從一個輸入端進入，在資料路徑中傳遞，經過不同的功能單元 (functional unit)，直到從輸出離開為止，也有可能這個資料路徑是有回饋的、或者是一個封閉的迴圈。而為了實現複雜的運算功能，我們可以利用 FSM 來進行資料路徑的控制。

在資料路徑中，常見的功能單元有：

• 暫存器 (Register)：由 DFFs 所組成。
• 記憶體 (Memory)：由 SRAM 儲存單元組成，儲存運算當中所產生的資料。
• 多工器 (Multiplexer)：藉由一個選擇訊號來從多工器的多個輸入路徑中選擇一條作為輸出。
• 算術邏輯單元 (Arithmetic logic unit; ALU)：進行加、減、乘、除等算術運算，或者是 and、or、not 等邏輯運算。

在 FSM 的設計中，則需要注意以下幾個重點：

• FSM 通常只負責產生控制訊號，而不會直接存取資料。
• 需注意資料間相互依賴關係 (data dependency)。

Reference [3] 是很好的教材，推薦給大家。


Reference
[1] Mealy, G. H. (1955). A method for synthesizing sequential circuits. The Bell System Technical Journal, 34(5), 1045-1079.
[2] Moore, E. F. (1956). Gedanken-experiments on sequential machines. Automata studies, 34, 129-153.
[3] Pedroni, V. A. (2013). Finite state machines in hardware: theory and design (with VHDL and SystemVerilog). MIT press.