状态之舞

有限状态机的形式定义 M=(S, I, O, δ, λ)：S 为有限状态集，I/O 为输入/输出字母表，δ:S×I→S 为转移函数，λ 为输出函数。状态转移图（STD）的绘制规范：圆圈表状态、有向边表转移、边上标注"输入/输出"，且必须有且仅有一个初始状态。合法性的核心是确定性——每个状态对每种输入组合必须恰好有一条出边；随手画的图往往缺边（某输入下无去处）或重边（同输入两个去处），这正是"不合法"的根源。图形会骗人，五元组不会。（Harris Ch3 / Mano Ch5）

Moore 机的输出函数 λ:S→O 只挂在状态上：时钟沿更新状态之后输出才变化，因此输出天然与输入噪声隔离、无毛刺，时序分析也最干净。代价是响应慢一个时钟周期——输入要先改变状态，状态再改变输出。工程上凡是对"输出必须严格同步、不得随输入抖动"有要求的场合（控制信号、流水线标志位、片选使能），首选 Moore。检测"101"时，灯在第三个时钟沿之后才亮，正是这慢一拍的直观体现。（Harris Ch3）

Mealy 机的输出函数 λ:S×I→O 挂在转移边上：输入变化的瞬间输出立即变化，比 Moore 少一拍延迟，且因为输出可以"因边而异"，通常还能用更少的状态表达同一行为。但它是异步透明的——输入毛刺在一个时钟周期内会直接穿透到输出，刚才那个"假的 101"让灯误亮一拍就是铁证。工程惯例：对已在时钟域内同步过的内部信号可用 Mealy 省状态省延迟；对外输出常再寄存一拍，把毛刺关进寄存器里。（Harris Ch3）

Moore→Mealy：把每个状态标注的输出值搬到它的所有入边上即可，状态数不增，但输出从此随输入异步变化。Mealy→Moore：若某状态的多条入边标注着不同输出值，就必须按输出值把该状态拆成若干副本（本章演示 4→6），每个副本固定输出一种值——状态数的上界是"原状态数 × 输出种数"。两个方向的算法都能从五元组定义直接推导：等价的是输入-输出行为，改变的是状态数与毛刺特性的分布。这就是"推导"层次的知识——不是背结论，而是会造桥。（Harris Ch3）

STT 的建立规则：行 = 现态，列 = 输入组合，格 = 次态/输出（Moore 机输出单列一列）。n 个状态、k 位输入 ⇒ 规模 n×2^k——输入每加一位，列数严格翻倍，这是"状态爆炸"在表格层面的第一次显形。STD 与 STT 各司其职：STD 适合人读（结构直觉），STT 适合机器综合（枚举完备）。所有 CAD 综合工具一律从 STT 出发生成次态布尔方程；STD 漏一条边人眼难察，STT 空一格立刻现形。把图落成表，是从"画图"走向"工程"的第一步。（Mano Ch5）

n 个状态的编码三角权衡：二进制用 ⌈log₂n⌉ 个触发器最省面积，但次态译码逻辑最深、多位同时翻转毛刺风险高；独热（One-hot）用 n 个触发器换来极简次态逻辑（每个新状态只需 OR 汇集入边），是寄存器富余、布线稀缺 FPGA 的默认选择；格雷码让相邻状态只差 1 bit，转移时单位翻转，毛刺与动态功耗最低，计数器和跨时钟域指针（如 FIFO 的 Gray 指针）非它莫属。编码不改变状态机的行为，只改变代价在"触发器数 / 逻辑深度 / 毛刺风险"三者间的分布。（Harris Ch3）

等价状态：若两个状态对任意输入序列产生完全相同的输出序列，则它们可安全合并（本章 6→4 正是 {0,4} 与 {1,5} 两对等价对的合并）。隐含表法是系统化判定流程：C(n,2) 个格子逐对审查——输出不同立即标 ✗；输出相同但次态不同，则把等价性"挂起"为条件项，迭代传播直至不动点：条件全部满足的标 ✓，链条断裂的标 ✗。6 状态 15 格尚可手工，12 状态 66 格已是极限，更大规模交给状态最小化算法。但请记住撞墙的结论：化简只能去除冗余，剩余状态两两不等价时，那就是问题本身的内在复杂度。（Mano Ch5）

三段式电路：次态组合逻辑（由 STT 综合出 δ 的布尔方程）→ 状态寄存器（一列 D 触发器，位数随编码方案取 ⌈log₂n⌉ 或 n）→ 输出组合逻辑（λ）。这个骨架在所有同步时序电路中反复出现，认出它就读懂了任何控制器。计数器是输入恒定为"计数使能"的退化 FSM：3 位二进制计数器 = 8 状态单向环，转移不依赖外部输入，分析它只需把状态图展开——这也是"FSM 是时序电路的通用语言"的最佳例证。幽灵状态来自编码空间大于状态数：2 位编码提供 4 个编码、只用 3 态，"11" 就是幽灵——上电时触发器初值随机，可能正好落进去。（Harris Ch3 / Mano Ch5）

序列检测器是 FSM 设计的范式全集：把"已匹配的目标前缀长度"定义为状态（检测 1011 需 4 态），关键决策在重叠——匹配失败后不清零，而是回退到"输入后缀与目标前缀的最长公共部分"对应的状态继续。允许重叠才能检出 1011011 中背靠背的两次命中。自启动（自恢复）：给每个幽灵状态显式补一条"无条件回归主循环"的出边，或综合后用次态方程验证所有非法编码都能在有限拍内收敛——上电初值随机，落在任何编码都必须能归位，否则电路可能永远锁死在真空地带。（Harris Ch3 / Mano Ch5）

握手协议四拍：REQ↑ → ACK↑ → REQ↓ → ACK↓，两个信号严格交错，每一拍都要状态记忆——协议状态机因此天然比数据通路状态机"密"。状态爆炸：每新增一个独立控制信号，可达状态数至多翻倍（本章 4→8→16→32）；多台 FSM 并发组合时总状态数更是相乘关系——这正是形式验证中模型检验动辄面对 10^N 状态空间的原因。工程对策不是"画更大的图"，而是层次化分解：把数据通路从控制 FSM 中剥离、把大机拆成通信的小机组。承认维度在膨胀，然后在更高的抽象层作战。（Harris Ch3）

回头看这条链：五元组是本体（K04-01），STD/STT 是它的两张面孔（K04-05/06）；Moore 与 Mealy 是输出的两种挂法（K04-02/03），转换与化简是等价类内的旅行（K04-04/08/09）；编码与三段式把抽象钉进硅片（K04-07/10）；检测器、计数器、自启动、握手是四大设计范式（K04-11~14）；而状态爆炸（K04-15）是永远的对立面——它不来自错误，来自维度本身。下一章 ch05 将登上更高的抽象层：算法观澜——用渐近之尺量度万法生长，直到撞上 P/NP 与停机问题的绝壁。