有限狀態機

控制與資料通路

打開幾乎任何一個數位模組，你都會看到兩類邏輯並肩共存。資料通路是數字真正流動的地方——暫存器、多工器、加法器，以及那一整套轉換資料的組合電路。控制則是站在它之上、拉動各種操縱桿的小單元：*現在載入這個暫存器、選擇那個多工器的輸入、這一拍啟動乘法。*資料通路是廚房，控制則是那位喊出操作順序的大廚。

為什麼要在腦子裡把它們分開？因為它們出錯的方式不同，設計它們的方式也不同。資料通路的 bug 看起來是數字算錯了；控制的 bug 看起來是數字算對了、卻出現在錯誤的時刻——或者一台機器永遠卡死，等著一個永遠不會發生的步驟。當一段行為主要是*「按這個順序做這些事，並視情況而定」*時，這種排序就是控制，而控制正是狀態機的用武之地。

狀態機到底是什麼

一台有限狀態機說穿了就是這樣：一小組有名字的狀態，任何時刻恰好有一個是「當前」的，再加上一組轉移規則，根據輸入說明下一個該進入哪個狀態。想想紅綠燈。它有三個狀態——綠、黃、紅——它任何時候都只處在其中一個，而時脈（或計時器）的一次滴答就把它推向下一個。它永遠不可能「有點兒綠」。這種*恰好 N 選一*的紀律，正是它的全部要義。

從機理上看，一台狀態機是由兩塊你已經熟悉的硬體搭起來的。一個狀態暫存器——一組正反器——保存當前狀態，並且只在時脈邊緣改變；這是時序部分，也就是記憶。圍繞它的是次態邏輯——純組合閘電路，它看著當前狀態加上輸入，算出*下一步該去哪兒*。每一次時脈滴答，暫存器就鎖存那個次態，循環往復。

摩爾型與米利型

狀態機有兩種風味，唯一的區別是輸出從哪裡來。在摩爾型機器裡，輸出只取決於當前狀態——綠燈亮著，是*因為*你正處在「綠」狀態，就這麼簡單。在米利型機器裡，輸出取決於狀態與當前輸入兩者的組合，因此一個輸入可以*在同一拍內*改變輸出，甚至在狀態還沒動之前。

這個取捨是實打實的。摩爾型的輸出無毛刺、像暫存過一樣乾淨——它們只在時脈邊緣之後才改變——但米利型機器往往需要更少的狀態，並且能早一拍做出反應，因為它不必等著跳進一個專門的輸出狀態。代價是：米利型的輸出是輸入的組合函數，所以它們可能產生毛刺，而且會把你的時序綁死在那些驅動這些輸入的源頭上。

畫狀態圖

在寫下一行 Verilog 之前，先把這台機器畫出來。這套記號很小：每個狀態是一個圓圈，每個轉移是一根箭頭，箭頭上標著觸發它的輸入條件，還有一根憑空而來的箭頭標出重置狀態。對摩爾型機器，把每個輸出寫*在圓圈裡*；對米利型，把它寫*在箭頭上*。這張圖就是規格——在紙上把它做對，程式碼幾乎就自己寫出來了。

我們拿一個自動販賣機控制器把它講具體：它在 15 美分時出貨，只收 5 美分（nickel）和 10 美分（dime）的硬幣。狀態就是它已經看到了多少錢：S0（0 美分）、S5（5 美分）、S10（10 美分）、S15（出貨，然後回到 S0）。從 S0，投一枚 5 美分到 S5，投一枚 10 美分到 S10；從 S5，投 5 美分到 S10，投 10 美分就達到 15；從 S10，無論哪種硬幣都達到 15 或以上，觸發出貨輸出。四個圓圈、幾根箭頭——這就是整個大腦。

列出狀態：把這個模組可能處於的每一種不同情形都寫下來（這裡是：已經投了多少錢），並給每一個起一個清晰的名字。
選定重置狀態——機器上電後進入的那個狀態。給它畫上那根獨一無二的入箭頭（這裡是 S0，沒有錢）。
對每個狀態，問一句「對於每一種可能的輸入，我該去哪兒？」，並為每種情況畫一根帶標註的箭頭。漏掉一種情況，就是一個無聲無息的 bug。
放置輸出：摩爾型放在圓圈裡（出貨住在 S15 裡），米利型放在箭頭上。到這裡，這張圖就是一份完整的、可以照著寫程式碼的規格了。

用 Verilog 寫一台狀態機

我們推崇的寫法是兩段式狀態機，它和第 2 節裡的硬體一一對應。一個時脈驅動的區塊是狀態暫存器——它什麼都不做，只是在每個時脈邊緣把 *next_state* 拷進 *state*（並在重置時跳回起點）。一個組合區塊是次態邏輯——一條乾淨的 case 語句，針對當前狀態決定該往哪兒走。把這兩者分開，是寫出可讀、可合成狀態機的頭號好習慣。

// Block 1: the state register (sequential)
always @(posedge clk or posedge rst)
  if (rst) state <= S0;          // reset to the start state
  else     state <= next_state;  // latch next state each clock edge

狀態暫存器——一組正反器。這是狀態機裡唯一的記憶，每個時脈邊緣改變一次。（這裡用的是非同步重置；若要同步重置，就把 rst 從敏感列表裡去掉。）

// Block 2: next-state logic (combinational)
always @(*) begin
  next_state = state;            // DEFAULT: stay put — no latches
  case (state)
    S0:  if (nickel) next_state = S5;
         else if (dime) next_state = S10;
    S5:  if (nickel) next_state = S10;
         else if (dime) next_state = S15;
    S10: if (nickel || dime) next_state = S15;
    S15: next_state = S0;        // dispensed; back to start
    default: next_state = S0;    // covers unused encodings
  endcase
end

次態邏輯：純組合閘電路。預設賦值加上 default 分支，正是讓它安全無虞的關鍵。

輸出就掛在這同一副骨架上。對摩爾型機器，只用 *state* 來驅動它們（assign dispense = (state == S15);）。對米利型，再把輸入也揉進去。有些團隊會專門加一個第三段來寫輸出——這沒問題，只要狀態暫存器、次態邏輯和輸出邏輯在視覺上依然分得清清楚楚。

狀態編碼（二進位與獨熱）

你的狀態有 S0、S10 這樣的名字，可正反器只認得位元——所以每個狀態都需要一個二進位位型，而你如何分配這些位型，就叫*編碼*。兩個經典選擇是二進位和獨熱，它們的區別正是一道教科書式的「正反器換邏輯」的取捨題。

二進位編碼把 N 個狀態壓進大約 ceil(log2(N)) 個正反器——4 個狀態用 2 位元就放得下（00、01、10、11）。暫存器很少，但次態邏輯必須*解碼*這些位元，於是你在組合閘上付出代價。獨熱編碼給每個狀態各自一個正反器——任何時刻恰好有一位是熱的（0001、0010、0100、1000）。這要燒掉更多正反器，但每個轉移判斷都變成一次單位元檢查，於是邏輯既淺又快。