每一個有限狀態機 (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 設計流程
- 畫 State diagram
- 建立兩個真值表 (truth table),一個是 next state 和 present state 及 input 的關係,另一個是 output 和 present state 及 input (Mealy machine only) 的關係
- 運用 Karnaugh map 進行邏輯化簡,得到 next state 和 output 的布林函數
- 使用 combinational circuit 實現布林函數,用 DFF 存放 FSM 狀態
- 決定是否要在 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 有關
而在 recursive machine 中,由於輸出函數與先前的 output 有關,因此需要額外的 memory 用來儲存先前的 output。
FSM 結合/分解 (Association/Decomposition)
當我們要實現一個較複雜的功能時,可以先實現多個較簡單的 FSMs,並且將這些 FSMs 結合起來。也可以看做是將一個複雜 FSM,拆解成多個簡單的 FSMs。FSM 結合的方法有以下三種:
- 序列結合式 (Serial association)
- 平行結合式 (Parallel association)
- 內部結合式 (Internal association)
Datapath 控制單元 (Control Unit)
無論是簡單的算數邏輯運算,或是較複雜的演算法,其實都是一個資料流動的過程,資料從一個輸入端進入,在資料路徑中傳遞,經過不同的功能單元 (functional unit),直到從輸出離開為止,也有可能這個資料路徑是有回饋的、或者是一個封閉的迴圈。而為了實現複雜的運算功能,我們可以利用 FSM 來進行資料路徑的控制。在資料路徑中,常見的功能單元有:
- 暫存器 (Register):由 DFFs 所組成。
- 記憶體 (Memory):由 SRAM 儲存單元組成,儲存運算當中所產生的資料。
- 多工器 (Multiplexer):藉由一個選擇訊號來從多工器的多個輸入路徑中選擇一條作為輸出。
- 算術邏輯單元 (Arithmetic logic unit; ALU):進行加、減、乘、除等算術運算,或者是 and、or、not 等邏輯運算。
- 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.