第4章 時序電路與狀態機#

組合電路沒有記憶，真實晶片卻需要「記住過去」：暫存器、計數器、通訊協定控制器都屬於時序電路。本章以有限狀態機（FSM）為統一模型，介紹狀態最小化（等價狀態合併）、狀態編碼（二進位/Gray/One-hot 的取捨演算法）、以及時序分析（setup/hold 約束與最長路徑計算）。這三件事分別對應「功能正確、面積合理、時序收斂」三個工程目標。本章的演算法也各具代表性：狀態最小化是「不動點迭代」的典範（同一範式在第 5 章模型檢查中再次出現）；狀態編碼是 NP-hard 問題上以啟發式換取工程可行性的實例；靜態時序分析則展示了「在 DAG 上做線性時間最長路徑」如何讓億級電晶體的晶片也能被完整驗證。理解本章後，你將能把第 2~3 章的組合邏輯基礎延伸到真正的時序系統。