Learning Objectives
- 用狀態、轉移、輸出描述一個會記得過去的系統
- 說出 Moore 與 Mealy 的差別，並各設計一個序列偵測器
- 把狀態表經過狀態編碼變成次態邏輯與輸出邏輯，用正反器與閘接出來
- 比較二進位與 one-hot 編碼的代價，處理沒定義的狀態與重設
紅綠燈要記得現在輪到誰
站在路口看紅綠燈，同樣是「計時到了」這個訊號，有時候要從綠燈換黃燈，有時候要從黃燈換另一邊的綠燈。同樣的輸入，不同的反應，差別在它記得現在進行到哪裡。
前面的組合電路做不到這件事：輸入一樣，輸出就一樣。暫存器能記住一個數字，但還需要有東西決定「下一步存什麼」。把這兩件事合起來，就是有限狀態機（finite state machine，FSM）。它由三樣東西組成：
| 名稱 | 意思 | 紅綠燈的例子 |
|---|---|---|
| 狀態（state） | 目前進行到哪裡，種類是有限的 | 南北綠、南北黃、東西綠、東西黃 |
| 轉移（transition） | 收到某個輸入之後，下一個狀態是什麼 | 南北綠收到「計時到了」就換南北黃 |
| 輸出（output） | 每個狀態要做什麼 | 南北綠時，南北亮綠燈、東西亮紅燈 |
自動販賣機、電梯、網路協定、CPU 的控制單元都是有限狀態機。工程師寫狀態表的好處是：所有情況都列得出來，可以一格一格檢查，也可以用程式窮舉。
下面的實驗台裡有一個同學寫的紅綠燈。他想讓尖峰時段車流快一點，多加了一個狀態 FAST。這裡的 T 是簡化的計時訊號：輸入 1 代表計時到了，輸入 0 代表還沒到。
輸出寫在哪裡：Moore 與 Mealy
有限狀態機有兩種標準的寫法，差別在輸出看什麼：
| Moore | Mealy | |
|---|---|---|
| 輸出看什麼 | 只看目前狀態 | 目前狀態＋這一拍的輸入 |
| 輸出寫在哪裡 | 狀態圖的圓圈裡 | 狀態圖的箭頭上 |
| 輸入 n 個符號 | n＋1 個輸出（一開始就有一個） | n 個輸出 |
| 反應時間 | 下一拍才看得到 | 這一拍就看得到 |
| 狀態數量 | 通常比較多 | 通常比較少 |
| 輸入有雜訊時 | 輸出穩定，只在時脈後改變 | 雜訊可能直接傳到輸出 |
這兩個名字來自兩篇早期論文：George H. Mealy 1955 年發表於 Bell System Technical Journal、Edward F. Moore 1956 年收錄於 Automata Studies。
來做一個常見的題目：序列偵測器。電路一次收到一個位元，每當最近收到的位元是 101 就輸出 1。先想清楚要記得什麼：不是記得全部的歷史，而是「目前已經對到前幾個字」。10101 裡面有兩個 101，中間的 1 是共用的，所以對到之後不可以從頭開始。
狀態表就是一張查詢表
一個有限狀態機寫成程式只有幾行：查表、換狀態、記下輸出。寫成程式之後就能窮舉：把長度 4 的 16 種輸入全部跑一次，和「結尾是不是 101」直接比對。
用窮舉確認「兩邊都綠」不會發生
剛才實驗台的「走不到」與 GG 檢查就是這樣算的：從開始狀態出發，把走得到的狀態全部找出來。這裡用修好之後的紅綠燈，FAST 還留在表裡。
從狀態表到電路
每個有限狀態機的電路都長得一樣，分成三塊：
| 區塊 | 電路種類 | 做什麼 |
|---|---|---|
| 次態邏輯 | 組合電路 | 用輸入與目前的狀態，算出下一個狀態 |
| 狀態暫存器 | 正反器 | 時脈上升緣把次態存起來；它的輸出就是目前的狀態，再接回次態邏輯 |
| 輸出邏輯 | 組合電路 | 用目前的狀態算出輸出（Mealy 要再加上輸入） |
步驟也是固定的：
- 狀態編碼：幫每個狀態指定一組位元。
- 次態邏輯：列出「現態位元＋輸入 → 次態位元」的真值表，化簡成閘。
- 輸出邏輯：列出「現態位元 → 輸出」的真值表，化簡成閘（Mealy 要加上輸入）。
紅綠燈用格雷碼排列，依序走 00 → 01 → 11 → 10 → 00，每次只變一個位元。先看 T＝1（一定換狀態）的情況，把現態 Q1 Q0 對到次態：
| Q1 Q0 | 次態 Q1 Q0 | 狀態 |
|---|---|---|
| 0 0 | 0 1 | 南北綠 |
| 0 1 | 1 1 | 南北黃 |
| 1 1 | 1 0 | 東西綠 |
| 1 0 | 0 0 | 東西黃 |
看每一欄就能寫出式子：次態 Q0 剛好是 Q1′，次態 Q1 剛好是 Q0。T＝0 時要維持原狀，所以再各接一個 2 選 1 多工器，T 當選擇線：T＝0 選自己，T＝1 選算出來的次態。
輸出也只要兩個閘：南北綠是 00，也就是 (Q1 + Q0)′；東西綠是 11，也就是 Q1·Q0。
二進位還是 one-hot？ 剛才的編碼表已經算給你看了：N 個狀態，二進位大約需要 log₂N 個正反器，one-hot 需要 N 個。one-hot 多花正反器，但每個狀態只看一條線，次態與輸出邏輯常常比較簡單；正反器多的晶片（例如 FPGA）常選 one-hot，狀態少或正反器貴的時候常選二進位。
沒定義的狀態與重設
用 2 個位元編 3 個狀態，會多出一組用不到的編碼。剛才的編碼表把它標成 d（隨意項）：設計時可以任選，電路比較簡單。但選定之後，電路落進那組編碼時就真的會照那樣走。開機狀態不確定、電源不穩、干擾造成位元翻轉，都可能讓它落進去。
所以設計時要回答三個問題：
- 怎麼開始？ 接上重設，保證從已知的狀態出發。模擬器裡正反器開機是未知（x），就是在提醒這件事。
- 落進沒定義的編碼會怎樣？ 想清楚次態邏輯會帶它去哪裡。如果會卡在裡面出不來，就把這些編碼的次態明確指回安全的狀態，放棄一點隨意項的好處。
- 什麼事情絕對不可以發生？ 紅綠燈的兩邊都綠就是。窮舉可達狀態能檢查設計，但檢查的前提是硬體照設計運作。
真實的號誌系統不會只靠控制器自己保證：例如美國 NEMA TS 標準的號誌箱裡有獨立的衝突監視器（conflict monitor，新規格叫 malfunction management unit），它只看輸出的燈號，看到衝突的綠燈就把路口切成閃燈。這是常見的安全設計想法：負責檢查的電路和負責控制的電路分開，控制器壞了，檢查的電路還在。
確認一下
同一個偵測器做成 Moore 與 Mealy。輸入有一瞬間的雜訊（在時脈來之前又恢復），哪一個的輸出可能跟著抖一下？
一個有 16 個狀態的有限狀態機，二進位與 one-hot 各需要幾個正反器？
3 個狀態用 2 位元編碼，用不到的編碼 11 在次態表上全部填隨意項。電路真的落進 11 時會怎樣？
有人把紅綠燈的 FAST 狀態改成走不到，窮舉檢查通過，但 FAST 的輸出還是 GG。下列哪個說法正確？
偵測 101 的 Moore 狀態機只用了 3 個狀態 S0、S1、S2，輸出全部寫在狀態上。這樣為什麼做不到？
重點整理
- 有限狀態機＝狀態＋轉移＋輸出。狀態記的是「後面會用到的歷史」，不是全部的歷史。
- Moore 的輸出只看狀態，穩定但晚一拍、狀態通常多；Mealy 的輸出也看輸入，快但輸入的雜訊會傳過去。
- 電路分三塊：次態邏輯、狀態暫存器、輸出邏輯。步驟是狀態編碼、列真值表、化簡。
- 二進位省正反器，one-hot 省次態與輸出邏輯；用不到的編碼要想好落進去會怎樣。
- 開機狀態未知，一定要有重設。絕對不可以發生的事，用窮舉檢查設計，真實系統還會加上獨立的監視電路。
下一課學怎麼存很多資料：一個正反器存一個位元太貴，記憶體用另一種做法。