從記憶到決策
到這一階為止，你已經拿到了一整箱工具。正反器能在一個拍子之間記住一個位元；暫存器是一排正反器，記住一整個字組；時脈讓每個暫存器在同一瞬間擷取它的輸入；而組合邏輯——加法器、多工器、解碼器——在輸入穩定的那一刻就算出嶄新的輸出。我們還沒打造的，是把這些綁在一起的東西：一個不只是儲存或運算，而是會根據「自己目前在哪裡」來決定下一步該做什麼的電路。這就是 有限狀態機 的工作。
最貼近日常的畫面是紅綠燈。它永遠恰好處於一組數目有限的小小情境之一——綠、黃、紅——而那個情境，也就是 狀態，正是它對整段過去唯一需要記住的東西。當計時器響起，它就依一條固定規則跳到下一個狀態：綠變黃、黃變紅、紅又回到綠。它根本不需要一本記下每輛經過車輛的歷史書；當下的狀態已經捕捉了所有要緊的事。有限狀態機，正是把這個想法用閘打造出來：少數幾個命名的狀態，以及在它們之間跳躍的規則。
解剖：一個暫存器，兩塊邏輯
美妙之處在於——硬體裡的每一部有限狀態機都有同樣的三件式骨架，而這三件你都已經認識了。第一，狀態暫存器：一小束正反器，把目前狀態當成一個位元圖樣存著（用 k 個正反器，最多可命名 2^k 個狀態）。第二，一塊叫 次態邏輯 的組合邏輯，它看著目前狀態加上任何輸入，算出接下來該進入哪個狀態。第三，另一塊組合邏輯，輸出邏輯，把目前狀態（也許還加上輸入）變成這部機器的輸出。把次態邏輯的輸出接回暫存器的輸入，你就闔上了那個迴圈，讓機器記得自己在哪裡。
+-------------------+
inputs ------>| next-state logic |---- next state ---+
| +-->| (combinational) | |
| | +-------------------+ v
| | +------------------+
| | current state <---------------| state register |<-- clock
| | | | (flip-flops) |
| +----------+ +------------------+
| |
v v
+-------------------+
| output logic |----> outputs
| (combinational) |
+-------------------+
one clock tick: register latches the computed next state -> it becomes
the new current state -> logic recomputes outputs and the next next-state.注意這如何乾淨地沿著前幾篇畫下的那條線把世界一分為二。所有的決策與運算都發生在組合邏輯區塊裡，它們在拍子之間沉澱出一個穩定的答案；所有的記憶都發生在那一個暫存器裡，而它只在時脈邊緣改變。這是最純粹形式的同步設計：在一個週期之內，機器的狀態從來不會處於變動中，所以你永遠不必去推敲那些只做了一半的轉移。機器一步一步走，一格一格凍結的畫面，每個拍子走一個狀態。
Moore 與 Mealy：輸出住在哪裡
有限狀態機有兩種誠實的口味，差別正在於輸出從哪裡來。在 Moore 機 中，輸出只取決於目前狀態——紅綠燈顯示綠燈，純粹因為它處在綠燈狀態，就這樣。在 Mealy 機 中，輸出同時取決於目前狀態與目前輸入，所以輸出能在輸入到達的同一個週期內就做出反應。Mealy 機往往需要較少的狀態，因為每個狀態能做更多事，但當輸入在週期中途擺動時，它的輸出可能會出現毛刺；Moore 機稍微大一點，但輸出穩如磐石，因為它只在狀態改變時才改變。
用一個小例子把它具體化：一座投幣旋轉閘門，過一次要一枚代幣。它有兩個狀態——鎖住與解鎖——以及兩個輸入：投入代幣，或推一下。把它當成 Moore 機來追蹤。從鎖住開始；輸出「閘門電磁鎖」是關的，所以橫桿不動。投入一枚代幣，次態邏輯就把它送到解鎖，在那裡電磁鎖輸出開啟、橫桿放行。推過去之後，次態邏輯又把它送回鎖住。兩個狀態、幾條轉移規則，你就用一個一位元暫存器加一小片邏輯，捕捉了一台真實裝置的全部行為。
現在看看要把它變真只需多少。把鎖住編碼成位元 0、解鎖編碼成位元 1——一個正反器就夠了，因為只有兩個狀態。次態規則直接從描述讀出來：在鎖住時，代幣把你送到 1，推一下讓你停在 0；在解鎖時，推一下把你送回 0，代幣讓你停在 1。輸出（電磁鎖開或關）就只是狀態位元本身，這正是它之所以是 Moore 機的原因——輸出恰好在狀態為解鎖時開啟。一個一位元暫存器，加上一小撮算次態函數的布林代數，這台裝置就完成了。
動手做一部：從圖示到閘
有限狀態機之所以如此重要，是因為從「我要它做什麼」一路到一個能運作的電路，存在一套機械化的食譜。你不必靈光乍現；照著步驟走就好。這正是你日後在大得多的規模上設計真實控制器時，會走的同一條有紀律的路。
- 畫出狀態圖：每個狀態一個泡泡，每條轉移一個箭頭，箭頭標上引發它的輸入。確認每個狀態對每一種可能的輸入都有一條箭頭，這樣機器才不會卡住或落入未定義。
- 把狀態編碼成位元圖樣。有 S 個狀態時，你至少需要 ceil(log2 S) 個正反器；挑一種指派（0、1、10、11……）——而這個編碼的選擇，就決定了你狀態暫存器的大小。
- 填好狀態表：對每一組（目前狀態、輸入）的配對，寫下次態與輸出。這張表「就是」規格——沒有任何東西留給人去詮釋。
- 把表中的每一欄變成一張真值表，再用本階第一篇的布林代數與卡諾圖工具導出組合邏輯。次態位元與輸出位元，不過是目前狀態位元與輸入的布林函數而已。
- 接線：把次態邏輯送進狀態暫存器的輸入，給暫存器時脈，再把它的輸出回授給次態邏輯與輸出邏輯。完成——迴圈闔上了，機器每個拍子走一個狀態。
為什麼這是處理器的心臟
退一步看看你剛剛打造的東西，因為它比一座旋轉閘門大多了。回想基礎那一階的擷取—解碼—執行週期：處理器無止盡地擷取一條指令、解碼它、執行它，再前進到下一條。那個迴圈就是一部有限狀態機。它的狀態是週期的各個階段；它的輸入是目前指令的位元；它的輸出則是駕馭資料路徑的控制訊號——告訴 ALU 該做哪個運算、告訴暫存器何時載入、告訴多工器該選哪個來源。
這正是 CPU 的 控制單元。處理器的控制單元，本質上就是一部有限狀態機，它的輸出是控制訊號，它的任務是讓資料路徑為當前執行的任何指令，行進過正確順序的微步驟。當工程師把它做成一團從狀態表導出的閘——正如你剛學的那樣——他們稱之為 硬接線控制。（還有一種較柔軟的替代方案——把每一步的控制訊號存進一塊小記憶體，叫做微程式設計——但在底下，走過它的那個定序器仍是一部有限狀態機。）無論哪種方式，讓一整顆處理器活過來的那個控制器，都是本篇這個模式的放大版。
所以這個單一的概念，是整座階梯的拱心石。電晶體成了開關；開關成了閘；閘成了加法器與多工器這類組合區塊；正反器給了那些閘記憶；時脈把那記憶馴服成時序邏輯；而如今，有限狀態機把記憶與邏輯組織成一個會決策、會定序的東西。再往上爬一階，你就會把這些組裝成一個真正的資料路徑，看著正是這個控制器去驅動一套能運作的指令集——但那控制器跳動的心臟，仍會是你現在已能徒手打造的、謙遜的有限狀態機。