1 / 4概念
Finite State Machines and Timing
状态机是控制逻辑的最小完备模型:触发器记住“现在”,组合逻辑算出“下一步”,时钟把两者隔开。读完能画出状态图、选对状态编码,并把下一状态逻辑的关键路径压进一个时钟周期。
1 概念
1.1 一句话定义
有限状态机由有限个状态、一个转移函数和一个输出函数组成;状态保存在触发器中,转移与输出由组合逻辑计算。
1.2 它解决什么问题
- 控制流建模:协议握手、总线仲裁与存储控制器都把“下一步做什么”写成状态与转移,而不是散落的标志位。
- 可穷举验证:状态图是有限图,形式工具能证明死锁、不可达状态与输出互斥。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 触发器内部结构、setup/hold、亚稳态 | Combinational and Sequential Logic |
| 自动机理论、正则语言与状态最小化算法 | Techniques |
| RTL 综合、布局布线、时序报告 | HDL, EDA and FPGA |
| 数据通路、寄存器堆与旁路 | Datapath Building Blocks |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| Moore 机 | 输出只由当前状态决定 | 不是“没有输入” |
| Mealy 机 | 输出由状态与输入共同决定 | 输出可随输入立即变化 |
| 转移表 | 状态与输入到下一状态的映射 | 不是真值表,多一个状态维度 |
| 状态编码 | 用位模式表示状态 | 不是状态最小化 |
| 独热编码 | 每个状态占一位 | 不是“只能用于 FPGA” |
2 机制
2.1 心智模型
把 FSM 想成一张地铁图:状态是站,转移是轨道,时钟是每站停一次的车。组合逻辑在车进站时算出下一站,触发器保存当前站;输出是站台广播,Moore 只看站名,Mealy 还要看刚上车的乘客。
2.2 机制拆解
- Moore 与 Mealy:Moore 输出稳定、天然无毛刺,但比输入晚一个周期;Mealy 输出随输入立即变化,组合路径更长。
- 状态编码:二进制用
ceil(log2 N)个触发器、译码更深;独热用 N 个触发器换一级译码;格雷码让相邻状态只翻一位。 - 三段式写法:状态寄存器、下一状态逻辑、输出逻辑分开写,避免在一个
always块里混合时序与组合。 - 默认分支:
case必须带default回到初始状态,否则可能推断出锁存器,非法编码也可能卡死。 - 关键路径:从状态触发器的 clock-to-Q 出发,穿过下一状态逻辑,到达下一级触发器的 setup,延迟必须小于一个时钟周期。
2.3 完整枚举
| 变体 | 输出依赖 | 响应延迟 | 毛刺风险 | 典型用途 |
|---|---|---|---|---|
| Moore | 仅状态 | 1 个周期 | 低 | 安全关键控制 |
| Mealy | 状态与输入 | 组合延迟 | 高 | 协议快速应答 |
| 寄存器输出 Moore | 仅状态 | 2 个周期 | 无 | 高速接口 |
| Medvedev | 仅状态位本身 | 0 | 低 | 简单序列检测 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| 触发器数量 | 二进制 ceil(log2 N),独热 N | 独热用面积换译码级数 |
| 时钟周期 | 3–5 GHz 对应 200–333 ps | 下一状态逻辑的预算 |
| 触发器 clock-to-Q | 20–50 ps | 先进节点 |
| setup 时间 | 10–40 ps | 随工艺角变化 |
3 实践
3.1 最小示例
module seq1011(input logic clk, rst_n, in, output logic det);
typedef enum logic [2:0] {S0, S1, S2, S3, S4} st_t;
st_t state, next;
always_ff @(posedge clk or negedge rst_n) // 状态寄存器
if (!rst_n) state <= S0; else state <= next;
always_comb case (state) // 下一状态与输出
S0: next = in ? S1 : S0; S1: next = in ? S1 : S2;
S2: next = in ? S3 : S0; S3: next = in ? S4 : S0;
S4: next = in ? S1 : S2; default: next = S0;
endcase
assign det = (state == S4); // Moore 输出
endmodule
S4 表示已连续收到 1011;default 让非法编码在下一拍回到 S0,这是可综合性要求,不是防御性编程。
3.2 常用操作与参数
| 操作 | 命令 | 说明 |
|---|---|---|
| 功能仿真 | iverilog -g2012 -o fsm.vvp seq1011.v tb.v | testbench 跑完整状态序列 |
| 综合 | yosys -p 'read_verilog -sv seq1011.v; synth; stat' | 看触发器与 LUT 数量 |
| 形式验证 | sby -f fsm.sby | 证明无死锁、覆盖可达状态 |
3.3 标准流程
- 画状态图,标出输入、输出与复位后的初始状态。
- 列转移表,标出无关输入与不可达状态。
- 选编码,写三段式 RTL,
case加default。 - 用 testbench 覆盖每条转移,再跑形式验证查死锁。
3.4 与相邻技术的组合
- 数据通路:FSM 输出控制信号,选择 ALU 操作、寄存器写使能与 MUX 通路。
- 跨时钟域:两个状态机之间用请求/应答握手或异步 FIFO,不能直接传状态位。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| 状态数 | 少于 16 / 16–64 / 更多 | 决定编码方式与是否分层 |
| 输出时序 | 同拍 / 晚一拍 | Moore 与 Mealy 的选择 |
| 目标器件 | ASIC / FPGA | 独热在 FPGA 通常更省 LUT |
3.6 决策规则
- 输出驱动异步信号或跨时钟域:用寄存器输出,不用 Mealy。
- 状态少于 16 且目标为 FPGA:优先独热,LUT 用量通常更小。
- 关键路径吃紧:先寄存输出,再考虑重编状态或拆状态。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 硬连线 FSM | 快、面积小 | 改需求要改电路 | 固定协议 |
| 微码控制器 | 易改、可存 ROM | 每步多一次查表 | 复杂指令控制 |
| 外部处理器 | 灵活、易调试 | 延迟与抖动大 | 慢速控制 |
3.8 何时不该用
- 不要用 FSM 表达纯数据计算:那是数据通路或软件的工作。
- 不要在状态里塞计数器:计数放进数据通路,状态只记阶段。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 输出出现窄脉冲 | Mealy 组合输出随输入抖动 | 寄存输出 |
| 上电后卡死 | 非法编码无 default 恢复 | 加默认分支与非法状态检测 |
| 高频下状态错乱 | 下一状态路径超过时钟周期 | 寄存输出、重编码、拆状态 |
| 复位后行为不定 | 复位未覆盖全部状态寄存器 | 统一复位、加复位同步 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
一个 always 块混写状态与输出 | 推断锁存器、难综合 | 三段式 |
| 用状态位直接跨时钟域握手 | 亚稳态、丢事件 | 请求/应答同步器 |
| 靠加大时钟周期修时序 | 频率下降、问题被掩盖 | 缩短路径或寄存 |
4.3 可观测信号
仿真波形的 state 与 next;综合报告的触发器与 LUT 数量;形式验证的不可达状态与反例;静态时序的最差负裕量;上板后逻辑分析仪抓到的状态位与输出。
4.4 安全 / 性能 / 一致性边界
- 安全:单粒子翻转会把状态寄存器打到非法编码,安全状态机必须有自恢复路径。
- 性能:Mealy 把输入到输出的组合路径算进时钟周期,接口越快越应寄存输出。
- 一致性:复位必须覆盖全部状态位,部分复位会让上电状态依赖工艺与温度。