极客工场

Appearance

共 6,191 字预计阅读约 21 分钟

有限状态机入门：状态图与 Moore/Mealy ​

更新时间：2026-09-10。本文是「芯片设计 · 入门层」数字逻辑基础第八篇。上承 锁存器与触发器，具体 Verilog 写法见进阶 状态机设计。

本文要回答的问题 ​

  • 什么是状态？为什么"过去"能被压缩成有限个状态？
  • 怎么从一句自然语言需求（如"收到请求→等应答→回空闲"）画出状态图？
  • Moore 和 Mealy 的输出区别，在时序波形和毛刺风险上有什么不同？
  • 状态表怎么列？状态数会不会数多/数漏？
  • 二进制编码和独热（one-hot）编码各适合什么器件（ASIC/FPGA）？

一、FSM 三要素：状态寄存器 + 次态逻辑 + 输出逻辑 ​

很多控制行为需要"记住过去发生了什么"才能决定现在做什么——总线主设备要知道自己处于"空闲/已发请求/等应答/传数据"哪个阶段。与其记住完整历史，不如观察到：对未来行为有影响的历史信息是有限的，可以归并成有限个"状态（state）"。这就是有限状态机（Finite State Machine, FSM）。任何同步 FSM 在硬件上都由三块拼成：

  1. 状态寄存器（时序逻辑）：一组触发器保存"当前状态"，每个时钟沿更新为次态；
  2. 次态逻辑（组合逻辑）：根据"当前状态 + 当前输入"算出"下一状态"；
  3. 输出逻辑（组合逻辑）：根据状态（和输入）算出对外控制信号（使能、选择、握手等）。

这恰好是上一节寄存器加组合逻辑的直接组合，没有任何新元件——计数器其实就是一种特殊的、线性流转的 FSM。

二、从需求到状态图 ​

建模四步：① 列举系统必须"记住"的处境，每个处境画成一个状态节点；② 指定复位后落在哪个状态；③ 对每个状态，针对各输入画出带条件的转移箭头到次态；④ 标出每个状态/转移下的输出。

以最常见的"请求—应答（req/ack）握手控制器"为例（输出 busy 在处理期间拉高）：

bash
                 req=0（停留）
              ┌──────────┐   req=1
              ▼          │ ────────┐
        ┌──────────┐     │         ▼
  复位→ │  IDLE    │──────────►┌──────────┐
        │ busy=0   │           │  WAIT    │
        └──────────┘           │ busy=1   │
             ▲                └────┬─────┘
             │                     │ ack=1
             └─────────────────────┘ （收到应答回 IDLE；ack=0 则停留）

要点：每个状态在每种可能输入下都必须有明确去向（哪怕是指向自己的"停留"），并安排好异常/超时转移，避免上电或异常输入后进入没有出口的状态（死锁）。状态数要恰好覆盖"会影响未来行为"的处境——两个处境若对所有输入的次态和输出都相同，就该合并为一个状态（状态过多浪费逻辑），反之漏掉必要处境则行为错误。先画状态图/列状态表、再写 RTL，是控制逻辑不出乱的关键习惯。

三、Moore 与 Mealy：输出取决于什么 ​

FSM 按输出依赖关系分两类：

Moore 型Mealy 型
输出取决于仅当前状态当前状态 + 当前输入
输出与输入的关系输入变化后，要等时钟沿进入新状态，输出才变输入一变，输出（经组合逻辑）立刻可变
输出时序与时钟沿对齐、稳定整一拍可在周期中途变化
毛刺风险小（仅随状态寄存器变）较大（输入组合路径上可能有毛刺）
状态数常需更多状态可用更少状态表达
典型控制输出、LED/时序节拍直接随数据/握手输入反应的输出

工程上输出（尤其要当使能/时钟相关信号时）优先做成 Moore 型并打一拍寄存，以获得与时钟对齐、无毛刺的干净信号；Mealy 型省状态、反应快，但要警惕其组合输出上的毛刺，必要时也对输出加一级寄存器（变成同步 Mealy，代价是晚一拍）。很多实际 FSM 是混合型：状态流转用 Mealy 思想，关键控制输出用 Moore/寄存输出。波形分析与握手实例见 valid/ready 握手。

四、状态表与完整性检查 ​

把状态图改写成状态转移表：行=当前状态，列=输入组合，格内填"次态/输出"。它的作用是机械地检查完备性——每个（状态 × 输入）格子都要有值。写 RTL 时这对应"case(状态) 里每个状态分支都覆盖所有输入条件，且 case 带 default"，否则组合的次态逻辑会因漏分支综合出锁存器（见 组合与时序逻辑、可综合 RTL 编码规范）。

五、状态编码：二进制、格雷、独热 ​

状态需要用触发器编码，常见三种方案，各有面积/时序取舍：

  • 二进制（binary，顺序编码）：n 个状态用 ⌈log₂n⌉ 个触发器，触发器省，但次态要靠较复杂的组合译码（加法/比较式逻辑）。
  • 格雷码（Gray）：相邻状态只差 1 位，降低多位同时翻转带来的功耗/毛刺风险；在跨时钟域计数器里不可或缺（见 异步 FIFO 与 Gray 码）。
  • 独热（one-hot）：每个状态用 1 个触发器，任意时刻只有 1 位为 1（如 IDLE=001、WAIT=010、DONE=100）。触发器用得多，但状态判断就是"某根线为 1"，几乎不需要译码组合逻辑，次态逻辑简单、速度快、毛刺少。

选择与器件强相关：FPGA 触发器资源丰富、组合逻辑（LUT）相对宝贵，默认用独热码；ASIC 中状态很多时二进制/格雷更省面积，综合器也常自动重编码。Verilog 里用 localparam 给状态命名，避免"魔数"：

verilog
localparam [1:0] IDLE = 2'b00, WAIT = 2'b01, DONE = 2'b10;
reg [1:0] state, next;

六、复位态与自启动 ​

务必指定复位后进入确定状态（通常 IDLE）。还要考虑未使用编码：二进制编码时若状态数不是 2 的幂，会存在编码空间里没用到的"野状态"。稳健设计应保证：一旦因干扰进入野状态，下一拍能自动跳回有效环路（自启动 / self-starting），而不是永远卡死——用 default 把所有未列状态导向 IDLE/安全态即可。独热码也有多位同时有效的非法情形，可加检测。完整的"一段式/两段式/三段式"RTL 模板（推荐三段式：状态寄存器、次态组合逻辑、输出逻辑分开）在进阶 状态机设计 中展开。

chip-design/beginner/17-fsm-intro.md D2 示意图

七、RTL 三段式骨架：状态图怎么落成代码 ​

状态图画好后，推荐用三段式把三块硬件分开写（完整规范与一段式/两段式对比见进阶 状态机设计，这里先建立骨架）：

verilog
// 第①段：状态寄存器（时序），只负责沿上 state <= next
always @(posedge clk or negedge rst_n)
  if (!rst_n) state <= IDLE;
  else        state <= next;

// 第②段：次态逻辑（组合），每个状态 × 每种输入都给出去向
always_comb begin
  next = state;                 // 默认保持：杜绝 latch、杜绝漏分支
  unique case (state)
    IDLE: if (req) next = WAIT;
    WAIT: if (ack) next = IDLE;
    default: next = IDLE;       // 野状态一律回家
  endcase
end

// 第③段：输出逻辑，Moore 只看 state；关键输出寄存一拍
assign busy = (state != IDLE);

三段式的好处不是"好看"，而是把三类 bug 隔离：时序段永远只写 state<=next，不会混入数据通路；组合段开头一句 next=state 默认保持，即使忘了某个分支也保持而非长出 latch；输出段纯组合或纯寄存，Moore/Mealy 一眼可辨。review 时逐段对照状态表：时序段查复位态、组合段查完备性、输出段查毛刺风险。

八、状态数会不会数错：化简与完备性 ​

数多了（冗余状态）浪费触发器和译码逻辑；数漏了则行为错误。判据回到"对未来行为是否有区别"：两个状态若对每一种可能的输入序列都产生相同输出序列、且走向等价的后续，它们就是等价状态，应当合并。手工化简用"蕴含表/分区法"逐轮合并不可区分状态（和卡诺图合并相邻格是同一种"区分等价类"的思想，见 布尔化简），状态机编译器（如 Kiss 格式工具）也能自动做。实际工程里状态数通常不多，更常见的问题反而是：

  • 把数据当状态：状态里编码了一个 8 位计数值（状态数爆炸）→ 计数值应放独立计数器，状态机只保留"正在计数/计数到"两三个处境。
  • 漏掉超时/异常出口：WAIT 状态只画了 ack 回来的箭头，没画对端永远不应答怎么办 → 每个等待状态都要有 timeout 转移，用 看门狗计数器 兜底。
  • 复位后状态不明：没指定初始态，上电落入野状态。
  • 输入组合没覆盖全：状态表有空格 → RTL 里靠 next=state 默认值 + default 双保险。

完备性检查可以用一张"状态 × 关键输入"表格，每个格子填次态；空一格就是一个潜在死锁或锁存器。

九、FSM 的高频陷阱清单 ​

  1. 组合次态逻辑漏 default：综合出锁存器，行为随电平漂移（见 组合与时序）。
  2. Mealy 组合输出直接当使能/中断：输入毛刺经输出传播，造成误动作 → 关键输出寄存一拍。
  3. 独热态出现多位为 1（单粒子翻转或复位不完全）→ 安全设计加 one-hot 合法性检测或让 default 兜底。
  4. 状态机 + 数据通路脱节：状态跳转了但数据没准备好，或数据 valid 与状态不同拍 → 状态转移条件里显式包含数据有效握手（见 valid/ready）。
  5. 在状态机里做复杂算术：次态逻辑里放乘除法，关键路径暴长 → 算术放数据通路、状态机只看标志位（零/进位/比较结果）。
  6. 两个状态机互相组合依赖：A 的次态直接看 B 的组合输出、B 又看 A → 形成组合环 → 双方都只看对方的寄存输出。
  7. 复位只复位状态不复位数据寄存器：回到 IDLE 但旧数据残留在通路 → 明确哪些数据需要随状态机一起初始化。

十、完整走查："1101" 序列检测器 ​

需求：串行输入 din，每拍 1 bit，检测到连续模式 1101 时输出 match 一个周期。先画状态——记住的是"已经匹配了多长前缀"：S0（没匹配）、S1（末尾是 1）、S2（末尾是 11）、S3（末尾是 110）。逐状态对 din=0/1 各画一条箭头：

  • S0：din=1→S1，din=0→S0；
  • S1：din=1→S2（前缀 11），din=0→S0；
  • S2：din=0→S3（前缀 110），din=1→S2（新末尾仍是 11，重叠保留！）；
  • S3：din=1→S1 且输出 match（1101 成立；落 S1 是因为最后这个 1 又可作下一次匹配的前缀，支持重叠检测），din=0→S0。

这个小例子浓缩了三个要点：① 每个状态对两种输入都有去向（完备）；② S2 收到 1 留在 S2、S3 成功后落 S1 而不是 S0，体现"重叠匹配"——若简单地匹配成功就回 S0 会漏掉 1101101 中间那次；③ match 若定义为"进入某状态时输出"是 Moore 型（match 对齐时钟沿、干净但晚一拍），若定义为"S3 且 din=1"则是 Mealy 型（省一个状态、当拍反应但输出直接含 din，din 有毛刺会漏到 match）。驱动中断/写使能时选 Moore 或对 Mealy 输出再打一拍。真实协议解析（UART 帧头、I2C 起始/停止条件、包头检测）全是这个模式的放大版。

十一、FSM 在芯片里的位置：控制器的通用语言 ​

FSM 从不单独出现，它总是"控制器 + 数据通路（control path + datapath）"这对分工里的控制器半边：数据通路（寄存器、ALU/加法器、MUX、存储器）负责算，FSM 负责按步骤拉起 MUX 选择线、寄存器使能、读写使能，并依据数据通路回来的标志位（零标志、比较结果、fifo 满空）决定下一步。CPU 控制器本质就是一个大 FSM（或微码表）：取指→译码→执行→访存→写回是状态，操作码和标志位是输入，ALUop/寄存器写使能是输出（见 微架构入门）。DMA、总线主设备、I2C/SPI 控制器、缓存行填充、仲裁器也都是 FSM。学会把任何"分步骤、有先后、要等条件"的需求先翻译成状态图再写 RTL，就掌握了数字控制逻辑的通用设计语言。

十二、状态太多怎么办：层次化 FSM 与"状态机 + 计数器" ​

真实控制器（USB、PCIe、缓存行状态机）常有几十上百个处境，画成一张扁平状态图既画不下也没法验证。两种工程化压缩手段。

**状态机加计数器（FSM + timer）**是性价比最高的一招：凡是"保持某状态 N 拍"或"在第 k 拍做动作"，绝不要复制出 N 个状态（WAIT1、WAIT2…），而是保留一个等待状态配一个倒计时/累加计数器，状态机只看 to（计数到）标志。一个 10 状态的协议时序因此能压成三四个状态，计数器位宽再大也只花几个触发器，这是新手最容易数多状态的地方，也是第八节"别把数据当状态"的直接应用。

层次化（hierarchical FSM / FSM 分工）：把一个大流程拆成顶层协调 FSM 和若干子 FSM。顶层只有粗粒度状态（如 INIT、IDLE、READ、WRITE、ERROR），进入 READ 后启动"读子状态机"（发地址→等数据→ECC 校验→返回），子机完成后用一个 done 信号通知顶层回到调度。层次之间只通过"启动/忙/完成/错误码"这几个寄存后的握手信号通信，彼此不看对方内部状态——这既避免了组合环（见第九节陷阱 6），又让每个状态机小到可以完备检查、单独验证。仲裁器、DMA 通道、多端口控制器普遍是"一个主 FSM + 每通道一个子 FSM"的结构。再进一步就是 微码/微程序控制器：把"状态+转移"直接存成一张表（ROM），复杂但规则的控制流用表驱动而不是 case 语句，CPU 控制器走的就是这条路。

验证上，状态机还天然适合两种检查：状态覆盖率（仿真工具统计哪些状态和转移从未走到，未覆盖的转移往往就是漏掉的异常路径）和断言（如"busy 期间 req 必须保持""任何状态下收到错误都必须在 N 拍内进入 ERROR"），用 SVA 写成性质，仿真和形式验证都能查。

十三、吞吐与延迟：FSM 何时成为瓶颈 ​

FSM 控制数据通路时，整体性能常常不是数据通路决定的，而是控制状态机的节拍安排决定的。三个量化概念：**延迟（latency）**是一笔事务从进入到完成要几拍；**吞吐（throughput）**是平均多少拍能接受一笔新事务；**启动间隔（II, initiation interval）**是连续两笔事务之间最少相隔的拍数。以"取指→译码→执行→写回"四状态串行的简单机器为例：一笔事务延迟 4 拍、每 4 拍才接一笔，吞吐 1/4；若让状态机每个状态都流水化（不同笔事务分别处在四个阶段），则单笔延迟仍是 4 拍，但每拍都能进一笔，吞吐变成 1——这就是 流水线 的状态机视角，控制上要求每个阶段的输出寄存、阶段间用 valid/ready 反压（见 valid/ready 握手）。

反过来，FSM 也常拖慢数据通路：若次态逻辑里含复杂比较或算术（如在同一个 always_comb 里算 32 位地址译码再决定跳转），关键路径就穿过状态寄存器输入，主频上不去。改法永远是那个原则——把算搬到数据通路、把判断留给状态机：地址比较由独立组合逻辑持续算出标志位，次态逻辑只看一根 eq 线；复杂条件预先打一拍，状态机用上一拍的结论跳转（晚一拍但频率高，多数控制场景划算）。评估一个 FSM 设计时，除了"状态对不对、全不全"，要习惯性再问三句：最坏延迟几拍、稳态吞吐多少、次态逻辑里有没有不该出现的运算。

十四、练习：从需求到可综合骨架 ​

给三个由浅入深的练习，建议都走完"状态图 → 状态表 → 三段式 RTL → 波形"的完整流程，这是掌握 FSM 唯一可靠的方法。

练习一（基础）：单按钮消抖后的"按一下翻转"开关。 输入为同步过的按钮电平和一个 10 ms 到脉冲，输出 led。状态只需 OFF/ON，转移条件是"按钮按下且当前确实完成了一次消抖确认"。陷阱：直接用电平做条件会导致按住期间连续翻转——要用按下的边沿事件（按钮从松开变按下那一拍）。做完体会"状态记住的是上次按钮的相位"。

练习二（完备性）：带超时的 req/ack 控制器。 IDLE 收到 req 进 WAIT；WAIT 下 ack 到则回 IDLE 并拉高一拍 done，超时计数器到（如 1000 拍）则进 ERROR；ERROR 下待错误被软件清除（err_clr）才回 IDLE。要求：每个状态列出所有输入组合的去向；busy/done/error 三个输出分别判断该用 Moore 还是 Mealy（done 若要和 ack 同拍产生必须 Mealy，若允许晚一拍就寄存成 Moore）；画出超时期间 ack 恰好到来时的波形，检查次态优先级（ack 与 timeout 同拍谁赢，必须在代码里用书写顺序或括号明确）。

练习三（数据通路协作）：长度可控的突发传输。 状态机收到 start 和长度 len 后，连续发起 len 次传输，每次等对方 ready。把 len 锁进独立计数寄存器（不要为每种长度造状态），状态机只管 LOAD→REQ→WAIT_ACK→（计数未满回 REQ）→DONE→IDLE。这个练习直接命中第八节"别把数据当状态"和第十二节层次化思想，也是 DMA/总线主设备的最小原型（参见 valid/ready 握手、三个最常见基础模块）。

评审自己代码时固定过一遍：复位态确定吗、next 有默认值吗、case 有 default 吗、野状态能回家吗、输出会不会带组合毛刺、计数/算术有没有混进次态逻辑、状态转移条件里所有握手信号都寄存了吗。这份检查单和 可综合 RTL 编码规范 里的规则一一对应。

十五、FSM 与软件状态机的差别（给有编程背景的读者） ​

有软件背景的读者最容易把硬件状态机写成"带很多状态的 switch-case"，这里把思维差异点破。软件的状态机（或协程）活在一个线程里：语句顺序执行，可以在状态里阻塞等待、调用子函数、让局部变量保存任意多的历史，切换由调度器随时发生。硬件 FSM 则是一块每个时钟沿都在全速求值的电路：不存在"停在某行等待"——WAIT 状态的真实含义是"每个沿都重新计算次态，条件不满足就继续指向自己"；不存在局部变量，所有需要跨拍记住的东西都是显式触发器；不存在函数调用，层次化只能通过"启动子 FSM + 等 done 信号"的握手实现。因此把软件流程翻译成硬件时要做三个转换：把顺序语句改写成状态（每个可能耗时等待的点之后切一个状态）；把局部变量分门别类——只在单个状态内用的组合中间量用组合逻辑，需要跨拍的搬进寄存器，计数类的用独立计数器而不是状态；把"等待事件"改成显式的自循环转移和超时出口。反过来，硬件 FSM 也有软件羡慕的优势：它天然并发——你可以例化任意多个状态机并行跑（多个通道、多个事务同时在途），状态本身只在沿上变化、没有线程安全问题，而且延迟是确定的（每个转移固定一拍），这正是硬件控制器在实时性上胜过轮询式软件的根本原因。理解了"状态机是电路而不是程序"，从本篇到进阶 状态机设计 的三段式模板、编码选择和握手集成就只剩语法细节。

与现有篇目的衔接 ​

总结 ​

一句话总结：任何"记住过去、按情况流转"的控制逻辑都能用有限状态机描述，硬件上它只有状态寄存器、次态组合逻辑、输出组合逻辑三块（计数器就是线性 FSM）；建模时先把"会影响未来行为的处境"归并成有限个状态、指定复位态、为每个状态在每种输入下画全转移并标好输出，再用状态转移表检查完备性以防漏转移导致死锁和锁存器；输出只取决于当前状态的是 Moore 型（随沿更新、毛刺小、常需更多状态），还取决于当前输入的是 Mealy 型（反应快、省状态但组合输出可能有毛刺，关键输出宜寄存一拍）；状态编码上二进制/格雷省触发器而独热码译码最简单速度最快，故 FPGA 偏爱独热、ASIC 状态多时倾向二进制/格雷，综合器也可自动重编码；最后务必让复位进入确定状态、并用 default 保证落入未用"野状态"后能自启动回到正常环路——这套"先建状态图再写 RTL"的方法，是总线握手、控制器和仲裁逻辑的通用设计语言，具体三段式 Verilog 模板在进阶状态机设计中展开。