有限状态机：时序电路的设计方法

概念

到这里，L1 的全部零件都齐了：门（10 篇）、译码器/选择器（11 篇）、ALU（12 篇）、触发器（13 篇）、寄存器与计数器（14 篇）。

最后一步是把它们组装成有"行为"的电路：交通灯要按"红→绿→黄"循环，序列检测器要认得出 1101，CPU 的控制器要按"取指→译码→执行→写回"循环。

有限状态机（FSM） = 有限个状态 + 转移规则 + 输出规则

它的形式化定义只有三句话：

要素	符号	说明
状态集合	$S = {S_{0}, S_{1}, \dots}$	有限个（"有限"二字的由来），每个状态用一个编码表示
转移函数	$δ : S \times X \to S$	现态 + 输入 → 次态
输出函数	$λ$	由现态（和输入）决定输出

硬件结构永远是同一个模子：

   输入 X ──────┬───────────────────┐
                │                   ▼
                │        ┌──────────────────┐
                │        │  次态组合逻辑     │──→ 各触发器的 D 端
                │        │  δ(现态, X)      │
                │        └────────┬─────────┘
                │                 │
                │        ┌────────▼─────────┐
   时钟 CP ─────┼───────→│   状态寄存器      │←──── "现态" Q
                │        │  (n 个 D 触发器)  │
                │        └────────┬─────────┘
                │                 │
                │        ┌────────▼─────────┐
                └───────→│  输出组合逻辑     │──→ 输出 Z
                         │  λ(现态[, X])    │
                         └──────────────────┘

记住这张图："组合逻辑算次态 → 寄存器存状态 → 组合逻辑算输出"。整章的题目，无非是怎么把 $δ$ 和 $λ$ 化成方程。

本层（L1 电路）在这里回答了上一层（L2 组成原理）的终极问题：CPU 的控制器是什么？它就是一个巨型状态机——取指、译码、执行、访存、写回就是它的状态，指令就是它的输入。

原理

一、Moore 与 Mealy：输出从哪来

Moore 型： Z = λ (S) Mealy 型： Z = λ (S, X)

	Moore	Mealy
输出取决于	仅现态	现态 + 输入
状态图上	输出写在圆圈里	输出写在箭头旁
响应速度	慢一拍（要等状态更新）	快一拍（输入一到就出）
输出毛刺	少（输出只在时钟沿变）	多（输入变化可立刻传到输出）
状态数	多（同一"进度"的输出差异要拆成不同状态）	少
触发器数	通常更多	通常更少

一句话记：Moore 把输出存进状态里（所以慢一拍但稳），Mealy 把输出算在箭头上（所以快但会透传输入毛刺）。
"慢一拍"要能算清楚：Mealy 在第 $n$ 拍输入到位时立刻输出；Moore 要到第 $n + 1$ 拍（状态更新完）才输出。

二、两种描述工具

状态图（圆圈 + 箭头）：

           0/0                 1/0
      ┌──────────┐       ┌──────────┐
      ▼          │       ▼          │
   ┌─────┐  1/0 ┌─────┐   0/0  ┌─────┐  1/1 ┌─────┐
   │ S0  │─────→│ S1  │───────→│ S2  │─────→│ S3  │
   └─────┘      └─────┘        └─────┘      └─────┘
      ▲            │  1/0        │            │
      │            └─────────────┘            │ 0/0
      └───────────────────────────────────────┘
   （箭头旁写 "输入/输出"；若是 Moore 型，输出写进圆圈）

状态表（表格形式，便于推导方程）：

现态	$X = 0$ 次态	$X = 1$ 次态	$X = 0$ 输出	$X = 1$ 输出
$S_{0}$	$S_{0}$	$S_{1}$	0	0
$S_{1}$	$S_{0}$	$S_{2}$	0	0
……	……	……	……	……

考试建议：先画状态图想清楚语义，再列状态表推方程。状态图是"人的工具"，状态表是"机器的工具"。

三、设计五步法（把整章的题目都装进来）

① 定义状态集合与含义
      ↓   "S1 表示已匹配到 '1'"——语义先定，否则状态数说不清
② 画状态图 / 列状态表
      ↓   δ 和 λ 都在这里确定
③ 状态化简（等价状态合并）
      ↓   N 个状态 → M 个（M ≤ N），省触发器
④ 状态编码
      ↓   二进制 / 格雷 / 独热，三者代价不同（见第六节）
⑤ 选触发器求激励方程 + 输出方程，画电路
      ↓   用 13 篇的激励表反推输入（D 型最省事：Q* = D）

第 ⑤ 步的关键技巧：

选用触发器	方程怎么来	特点
D	*$D = Q^{}$** （次态就是输入）	最省事，直接抄次态
JK	查激励表逐位反推	方程最简，但要多一步
T	$T = Q \oplus Q^{*}$	只在"翻转/保持"有意义的场合

实战建议：考试若没指定触发器，用 D 型——因为 $D = Q^{*}$ ，可以把"次态方程 = 激励方程"这一步直接省掉。指定 JK 时按激励表老实反推。

四、状态化简：划分法

两个状态等价的定义（两句话，缺一不可）：

等价 ⟺ {\begin{cases} ① 输出完全相同（Moore 看状态输出，Mealy 看所有输入下的输出） \\ ② 对每个输入，次态也落在同一组等价状态里 \end{cases}

划分法（partition method）步骤：

P₁：按"输出"分组
      ↓
P₂：检查每组内，各状态对每个输入的次态是否落在同一个 P₁ 组里
      ↓  不在同一组的，拆开
P₃：对新分组重复上述检查
      ↓
直到分组不再变化 → 收敛，每组即为一个等价类

注意：这是迭代收敛过程，一遍往往不够——第一遍只能保证"输出相同且次态输出相同"，第二遍才检查"次态是否真的等价"。这是最常出错的地方。

五、状态数、触发器数、编码方式的关系

二进制编码所需触发器数 = ⌈ \log_{2} N ⌉ 独热编码所需触发器数 = N

状态数 $N$	二进制触发器	格雷触发器	独热触发器
3	2	2	3
4	2	2	4
8	3	3	8
16	4	4	16
32	5	5	32

三种编码的取舍：

编码	触发器	译码逻辑	毛刺	适用
二进制	最少	复杂（需多输入门）	可能多路同时翻转	状态多、面积敏感
格雷	最少	复杂	相邻只变一位（毛刺少）	状态少、顺序迁移
独热	最多	1 根线即可	少	速度快优先（FPGA 状态机常用）

FPGA 为什么偏爱独热：FPGA 里触发器很便宜（每个逻辑单元都自带），而多输入门很贵（要串起来）。用触发器换译码逻辑，在 FPGA 上是划算的买卖。反过来 ASIC 里触发器占面积大，就偏向二进制。
"用面积换速度、还是用速度换面积"——这是数字设计里唯一永恒的主题（12 篇的 ALU、14 篇的桶形移位器，都是同一件事）。

六、未用状态与自启动

$n$ 个触发器有 $2^{n}$ 个编码，但状态数往往不是 $2^{n}$ 。剩下的编码就是"未用状态"。

必须处理：如果电路因干扰进入了未用状态，会不会永远出不来（形成死循环或游离环）？

处理方式	做法
不在方程里管	未用状态当无关项（don't care）→ 方程最简，但有死锁风险
指定次态回主环	把未用状态的次态显式指向某个有效状态 → 自启动，代价是方程变复杂

考试两种问法：
"用无关项化简" → 求最简方程（不保证自启动）
"设计成自启动的" → 必须给未用状态指定次态，不能当无关项

七、状态机与计数器的关系

计数器 = 没有输入 X 的状态机（输出仅由状态决定）

	计数器	状态机
有无外部输入	无（只有时钟）	有
状态转移	固定顺序	由输入决定
描述工具	可只用计数值	状态图 / 状态表

反过来看：14 篇的约翰逊计数器，就是"状态转移固定"的状态机。学完这一篇，再看计数器就是特例了。

示例

例 1：`1101` 序列检测器（Mealy 版，完整五步设计）

设计一个序列检测器：输入 $X$ 逐位进入，当检测到 1101 时输出 $Z = 1$ （同一拍输出，Mealy 型），允许重叠。

第 ① 步：定义状态（含义要写清）。

状态	含义（已匹配的前缀）
$S_{0}$	什么都没匹配上（初态）
$S_{1}$	已匹配 `1`
$S_{2}$	已匹配 `11`
$S_{3}$	已匹配 `110`

共 4 个状态 → 二进制编码需 $⌈ \log_{2} 4 ⌉ = 2$ 个触发器。

第 ② 步：画状态表（关键在"重叠"怎么处理）。

规则：每来一位，看当前后缀能匹配到哪个前缀。

现态	$X = 0$	$X = 1$	说明
$S_{0}$	$S_{0} / 0$	$S_{1} / 0$	空串：来 0 还是空，来 1 匹配 `1`
$S_{1}$ （`1`）	$S_{0} / 0$	$S_{2} / 0$	`1`+`0`=`10` 无后缀匹配前缀；`1`+`1`=`11` → $S_{2}$
$S_{2}$ （`11`）	$S_{3} / 0$	$S_{2} / 0$	`11`+`0`=`110` → $S_{3}$ ；`11`+`1`=`111`，后缀 `11` 仍是 $S_{2}$ ✓
$S_{3}$ （`110`）	$S_{0} / 0$	$S_{1} / 1$	`110`+`0`=`1100` 无匹配；`110`+`1`=`1101` 命中！后缀 `1` → $S_{1}$

"重叠"为什么要求下一个是 $S_{1}$ 而不是 $S_{0}$ ：1101 的最后一位 1 可以当作下一次匹配的第 1 位。这就是"允许重叠"的硬件含义。

第 ③ 步：状态化简。 4 个状态的输出各不相同（ $S_{3}$ 在 $X = 1$ 时输出 1），划分法检查后无法合并 → 保持 4 个状态。

第 ④ 步：状态编码。

S_{0} = 00, S_{1} = 01, S_{2} = 10, S_{3} = 11

第 ⑤ 步：求激励方程（用 D 触发器， $D = Q^{*}$ ）。

次态表（编码后）：

现态 $Q_{1} Q_{0}$	$X = 0$	$X = 1$
00	00	01
01	00	10
10	11	10
11	00	01

列 $D_{1} = Q_{1}^{*}$ 的真值表（8 行）：

$Q_{1}$	$Q_{0}$	$X$	$Q_{1}^{*}$	最小项
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1	$m_{3}$
1	0	0	1	$m_{4}$
1	0	1	1	$m_{5}$
1	1	0	0
1	1	1	0

卡诺图（行序 $Q_{1} Q_{0}$ ：00, 01, 11, 10；列 $X$ ：0, 1）：

            X=0   X=1
   Q1Q0=00    0     0
   Q1Q0=01    0    [1] m3
   Q1Q0=11    0     0
   Q1Q0=10   [1]m4 [1]m5      ← m4、m5 相邻成一组

$m_{4}, m_{5}$ （行 10，两列）→ 合并为 $Q_{1} {\bar{Q}}_{0}$
$m_{3}$ 孤立（邻居 $m_{2}, m_{7}, m_{1}$ 都是 0）→ 单独一项 ${\bar{Q}}_{1} Q_{0} X$

D_{1} = Q_{1} {\bar{Q}}_{0} + {\bar{Q}}_{1} Q_{0} X

列 $D_{0} = Q_{0}^{*}$ 的真值表：

$Q_{1}$	$Q_{0}$	$X$	$Q_{0}^{*}$
0	0	0	0
0	0	1	1 ← $S_{0} \to S_{1}$
0	1	0	0
0	1	1	0
1	0	0	1 ← $S_{2} \to S_{3}$
1	0	1	0
1	1	0	0
1	1	1	1 ← $S_{3} \to S_{1}$

卡诺图：

            X=0   X=1
   Q1Q0=00    0    [1] m1
   Q1Q0=01    0     0
   Q1Q0=11    0    [1] m7
   Q1Q0=10   [1]m4   0

三个 1 两两都不相邻（ $m_{1}$ 的邻居 $m_{0}, m_{5}, m_{3}$ 全是 0； $m_{4}$ 的邻居 $m_{0}, m_{5}, m_{6}$ 全是 0； $m_{7}$ 的邻居 $m_{6}, m_{5}, m_{3}$ 全是 0）→ 无法合并：

D_{0} = {\bar{Q}}_{1} {\bar{Q}}_{0} X + Q_{1} {\bar{Q}}_{0} \bar{X} + Q_{1} Q_{0} X

输出方程（Mealy：由现态 + 输入决定）：只有处在 $S_{3}$ （ $Q_{1} Q_{0} = 11$ ）且 $X = 1$ 时输出 1：

Z = Q_{1} Q_{0} X

电路：2 个 D 触发器 + 3 个与门/与非门阵列（实现 $D_{1}$ 、 $D_{0}$ ）+ 1 个三输入与门（ $Z$ ）。

例 2：同一个检测器的 Moore 版（多一个状态，慢一拍）

同样的 1101，改成 Moore 型。

Moore 必须为"已命中"单独分配一个状态（因为输出只由状态决定）：

状态	含义	输出 $Z$
$S_{0}$	空	0
$S_{1}$	`1`	0
$S_{2}$	`11`	0
$S_{3}$	`110`	0
$S_{4}$	`1101`（命中）	1

共 5 个状态 → 需 $⌈ \log_{2} 5 ⌉ = 3$ 个触发器（对比 Mealy 的 2 个）。

转移表：

现态	$X = 0$	$X = 1$
$S_{0}$	$S_{0}$	$S_{1}$
$S_{1}$	$S_{0}$	$S_{2}$
$S_{2}$	$S_{3}$	$S_{2}$
$S_{3}$	$S_{0}$	$S_{4}$
$S_{4}$	$S_{0}$	$S_{2}$

注意最后一行： $S_{4}$ （1101）之后若来 1，后缀变 11011，最长能匹配的前缀是 11 → $S_{2}$ ；若来 0 → 11010，无匹配 → $S_{0}$ 。这才是"重叠"在 Moore 型里的正确落地。

两版对比（考试高频问法）：

	Mealy 版	Moore 版
状态数	4	5
触发器数	2	3
输出时刻	输入到位当拍输出	命中下一拍输出
输出方程	$Z = Q_{1} Q_{0} X$ （含输入）	$Z = Q_{2}$ （只看状态）
毛刺	输入毛刺会透到 $Z$	只在时钟沿变

用输入 1101 逐拍对照：

拍	1	2	3	4	5
输入 $X$	1	1	0	1	—
Mealy 状态	$S_{1}$	$S_{2}$	$S_{3}$	$S_{1}$	—
Mealy 输出	0	0	0	1 ← 第 4 拍	—
Moore 状态	$S_{1}$	$S_{2}$	$S_{3}$	$S_{4}$	—
Moore 输出	0	0	0	0	1 ← 第 5 拍

"慢一拍"就是这么来的：Moore 要先把 $S_{4}$ 写进寄存器，输出才变 1。

例 3：状态化简（划分法，完整迭代过程）

化简下面这个 Moore 型状态表（输出列 $Z$ 与次态如下）。

现态	$Z$	$X = 0$ →	$X = 1$ →
$A$	0	$B$	$C$
$B$	0	$A$	$C$
$C$	0	$D$	$C$
$D$	1	$A$	$C$
$E$	0	$D$	$C$

第 1 遍（ $P_{1}$ ）：按输出分组。

P_{1} = {{A, B, C, E}, {D}}

第 2 遍（ $P_{2}$ ）：检查每组内，次态落在哪个 $P_{1}$ 组。

对 ${A, B, C, E}$ ：

状态	$X = 0$ 次态（属哪组）	$X = 1$ 次态（属哪组）	划分
$A$	$B \in G_{1}$	$C \in G_{1}$	(1, 1)
$B$	$A \in G_{1}$	$C \in G_{1}$	(1, 1)
$C$	$D \in G_{2}$	$C \in G_{1}$	(2, 1)
$E$	$D \in G_{2}$	$C \in G_{1}$	(2, 1)

（ $G_{1} = {A, B, C, E}$ ， $G_{2} = {D}$ ）

按"次态组对"再分：

P_{2} = {{A, B}, {C, E}, {D}}

第 3 遍（ $P_{3}$ ）：用新的 $P_{2}$ 再查一遍。

状态	$X = 0$ 次态组	$X = 1$ 次态组	划分
$A$	$B \in {A, B}$	$C \in {C, E}$	(1, 2)
$B$	$A \in {A, B}$	$C \in {C, E}$	(1, 2)
$C$	$D \in {D}$	$C \in {C, E}$	(3, 2)
$E$	$D \in {D}$	$C \in {C, E}$	(3, 2)

分组不再变化 → 收敛：

P_{3} = P_{2} = {{A, B}, {C, E}, {D}}

结论：5 个状态化简为 3 个，令 $G_{1} = {A, B}$ 、 $G_{2} = {C, E}$ 、 $G_{3} = {D}$ ：

化简后状态	$Z$	$X = 0$ →	$X = 1$ →
$G_{1}$	0	$G_{1}$ （ $B$ 在组内 ✓）	$G_{2}$ （ $C$ 在组内 ✓）
$G_{2}$	0	$G_{3}$ （ $D$ ✓）	$G_{2}$ （ $C$ ✓）
$G_{3}$	1	$G_{1}$ （ $A$ ✓）	$G_{2}$ （ $C$ ✓）

一致性检验：每行的次态都落在组内成员，说明合并后无矛盾 ✓。

如果第 2 遍就停下，会误判 $A \equiv C$ （因为 $P_{1}$ 里它们同组）——但 $C$ 的 0 次态是 $D$ （输出 1），而 $A$ 的 0 次态是 $B$ （输出 0），两者根本不等价。这正是"划分法必须迭代到收敛"的原因，也是本节最经典的失分点。

例 4：状态编码的代价对比

一个 16 个状态的 FSM，比较三种编码方式的硬件代价。

二进制编码（ $Q_{3} Q_{2} Q_{1} Q_{0}$ ）

触发器： $⌈ \log_{2} 16 ⌉ = 4$ 个
次态译码：每个次态位是一个 4 变量函数，平均需 3~4 输入的门
输出译码：若某状态是 1010，输出 $Z$ 需一个 4 输入与门

独热编码（ $Q_{15} \dots Q_{0}$ ，每个状态一位）

触发器： $16$ 个（4 倍）
次态逻辑：每个状态的次态就是"各输入条件下前驱状态位之和"，大多是 2 输入或门
输出译码： $Z = Q_{10}$ —— 一根线，零门 ✓

格雷编码（相邻状态只变一位）

触发器：4 个
译码：与二进制同量级
好处：状态迁移时只有一位翻转 → 输出译码组合逻辑不会产生译码毛刺

总账：

编码	触发器	输出译码	毛刺风险	选它的理由
二进制	4	多输入与门	中	面积最小
格雷	4	多输入与门	低	顺序迁移 + 抗毛刺
独热	16	0 个门	低	速度优先 / FPGA

关键路径对比（设门延迟 $t$ 、触发器 $t_{c o}$ ）：

编码	输出组合逻辑级数	关键路径
二进制/格雷	$⌈ \log_{2} 16 ⌉$ 层左右	大
独热	0 层（直接取 $Q_{10}$ ）	小

这就是 FPGA 上"独热更快"的定量解释：把"译码"这一步彻底消灭。代价是 16 个触发器。在 FPGA 里，触发器由逻辑单元免费附带，所以这笔交易稳赚。

例 5：交通灯控制器（Moore 型三状态机）

设计一个"红→绿→黄→红"循环的交通灯控制器。灯色用 3 位独热输出（ $R, G, Y$ ），由定时器信号 $T$ （每 30 秒来一个脉冲）驱动切换。

第 ① 步：状态定义（Moore 型，输出写在状态上）。

状态	灯色	编码（独热，按 $Q_{R} Q_{G} Q_{Y}$ 顺序）	$R$	$G$	$Y$
$S_{R}$	红	`100`	1	0	0
$S_{G}$	绿	`010`	0	1	0
$S_{Y}$	黄	`001`	0	0	1

第 ② 步：状态图（输入只有 $T$ ，"走"或"等"）。

                    T=1
        ┌──────────────────────────┐
        ▼                          │
   ┌─────────┐   T=1   ┌─────────┐ │  T=1
   │  S_R    │────────→│  S_G    │─┘
   │ 红      │         │ 绿      │
   └─────────┘         └────┬────┘
        ▲                   │ T=1
        │                   ▼
        │              ┌─────────┐
        └──────────────│  S_Y    │
              T=1      │ 黄      │
                       └─────────┘
   （每个状态还有一个 T=0 的自环，表示"计时未到，保持"）

第 ③ 步：转移条件。

现态	$T = 0$	$T = 1$
$S_{R}$	$S_{R}$	$S_{G}$
$S_{G}$	$S_{G}$	$S_{Y}$
$S_{Y}$	$S_{Y}$	$S_{R}$

第 ④ 步：独热编码下的次态方程（极简）。

\begin{aligned} D_{R} & = \overset{―}{T} \cdot Q_{R} + T \cdot Q_{Y} \\ D_{G} & = \overset{―}{T} \cdot Q_{G} + T \cdot Q_{R} \\ D_{Y} & = \overset{―}{T} \cdot Q_{Y} + T \cdot Q_{G} \end{aligned}

读这三个式子："保持（ $\bar{T} \cdot Q_{自己}$ ）或被前驱拉起来（ $T \cdot Q_{前驱}$ ）" —— 独热编码的次态方程就是这个固定模板，不需要任何卡诺图。这是独热编码最大的便利。

第 ⑤ 步：输出方程（Moore：只看状态）。

R = Q_{R}, G = Q_{G}, Y = Q_{Y}

三个灯直接接触发器输出，零译码 ✓

验证一轮切换（ $T$ 连续来三个脉冲）：

拍	$T$	$Q_{R} Q_{G} Q_{Y}$	亮灯
0	—	`100`	红
1	1	`010`	绿
2	1	`001`	黄
3	1	`100`	红 ✓

还有一个隐患要处理：独热编码有 5 个未用状态（000、011、101、110、111）。若电路因干扰进入 000，上面三个方程会永远保持 000（全灭）——死锁！

第一步修正（只救 000）：加一项"无灯亮则回 $S_{R}$ "：

D_{R} = \overset{―}{T} Q_{R} + T Q_{Y} + \overset{―}{Q_{R} + Q_{G} + Q_{Y}}

但这一项只救了 000。把另外四个未用状态代进去会发现它们自成一环（例如 011 在 $T = 0$ 时： $D_{R} = 0$ 、 $D_{G} = Q_{G} = 1$ 、 $D_{Y} = Q_{Y} = 1$ → 仍是 011）——照样出不来。

第二步修正（完整自启动）：需要真正检测"非法状态"（不是独热编码）。合法的三个编码恰好是 001/010/100，它们的特征是"只有一个 1"：

I N V = \overset{―}{Q_{R} + Q_{G} + Q_{Y}} + Q_{R} Q_{G} + Q_{G} Q_{Y} + Q_{R} Q_{Y}

（第一项抓 000，后三项抓"有两个及以上 1"的 011/101/110/111。）

代入修正后的方程：

\begin{aligned} D_{R} & = \overset{―}{T} Q_{R} + T Q_{Y} + I N V \\ D_{G} & = (\overset{―}{T} Q_{G} + T Q_{R}) \cdot \overset{―}{I N V} \\ D_{Y} & = (\overset{―}{T} Q_{Y} + T Q_{G}) \cdot \overset{―}{I N V} \end{aligned}

含义：只要状态非法（ $I N V = 1$ ），就无条件把红灯拉起来、把绿黄压下去 → 下一个时钟沿回到 $S_{R}$ 。

完整次态表（8 个编码 × 2 种输入，自启动验证）：

当前编码	是否合法	$T = 0$ →	$T = 1$ →
`100`（红）	✓	`100`	`010`
`010`（绿）	✓	`010`	`001`
`001`（黄）	✓	`001`	`100`
`000`	✗	`100`	`100`
`011`	✗	`100`	`100`
`101`	✗	`100`	`100`
`110`	✗	`100`	`100`
`111`	✗	`100`	`100`

所有非法状态的次态都不在非法集合里 → 最多一个时钟沿就能回到主环 ✓ 这才是"自启动"。

这一小节的考点价值：题目只要说"设计成自启动"，就一定要逐个数一遍未用状态，不能只处理 000。只加"全灭回红"那一项是最常见的错误答案。

例 6：用程序复算

#include <stdio.h>

/* ===== 例1/例2：1101 序列检测器 ===== */

/* Mealy：4 状态，编码 S0=00 S1=01 S2=10 S3=11 */
static void mealy(const int *x, int n) {
    int Q1 = 0, Q0 = 0;                  /* 现态 */
    printf("Mealy 型（4 状态，2 触发器）\n");
    printf("  拍  输入  现态  输入后次态  输出Z\n");
    for (int i = 0; i < n; i++) {
        int in = x[i];
        /* 次态方程（与正文一致） */
        int D1 = (Q1 & !Q0) | (!Q1 & Q0 & in);
        int D0 = (!Q1 & !Q0 & in) | (Q1 & !Q0 & !in) | (Q1 & Q0 & in);
        int Z  = Q1 & Q0 & in;
        printf("  %2d    %d    %d%d       %d%d        %d\n",
               i + 1, in, Q1, Q0, D1, D0, Z);
        Q1 = D1; Q0 = D0;
    }
    printf("  末态 = %d%d\n", Q1, Q0);
}

/* Moore：5 状态，状态 S4 输出 1 */
static int moore_next(int s, int in) {
    /* S0=0 S1=1 S2=2 S3=3 S4=4 */
    static const int nx[5][2] = {
        {0, 1},   /* S0: X=0->S0, X=1->S1 */
        {0, 2},   /* S1 */
        {3, 2},   /* S2 */
        {0, 4},   /* S3 */
        {0, 2}    /* S4 */
    };
    return nx[s][in];
}

static void moore(const int *x, int n) {
    int s = 0;
    printf("Moore 型（5 状态，3 触发器）\n");
    printf("  拍  输入  现态  次态  输出Z\n");
    for (int i = 0; i < n; i++) {
        int Z = (s == 4);                 /* 输出只看状态 */
        int ns = moore_next(s, x[i]);
        printf("  %2d    %d    S%d    S%d     %d\n", i + 1, x[i], s, ns, Z);
        s = ns;
    }
    printf("  末态 = S%d\n", s);
}

/* ===== 例3：状态化简（划分法） ===== */
static void reduce(void) {
    /* 状态 A..E = 0..4 ; 输出 Z ; 次态表 nx[状态][输入] */
    const int Z[5]     = {0, 0, 0, 1, 0};
    const int nx[5][2] = {{1,2},{0,2},{3,2},{0,2},{3,2}};
    int g[5], pass = 1, changed = 1;
    for (int i = 0; i < 5; i++) g[i] = Z[i];        /* P1：按输出分组 */
    while (changed) {
        int key[5], ng[5], nid = 0;
        for (int i = 0; i < 5; i++)
            key[i] = g[i] * 100 + g[nx[i][0]] * 10 + g[nx[i][1]];
        for (int i = 0; i < 5; i++) {
            int found = -1;
            for (int j = 0; j < i; j++) if (key[j] == key[i]) { found = ng[j]; break; }
            ng[i] = (found >= 0) ? found : nid++;
        }
        changed = 0;
        for (int i = 0; i < 5; i++) if (ng[i] != g[i]) changed = 1;
        for (int i = 0; i < 5; i++) g[i] = ng[i];
        printf("  P%d 分组: ", pass++);
        for (int i = 0; i < 5; i++) printf("%c->G%d ", 'A' + i, g[i]);
        printf("\n");
    }
    int m = 0;
    for (int i = 0; i < 5; i++) if (g[i] + 1 > m) m = g[i] + 1;
    printf("  最终等价类数 = %d (期望 3)\n", m);
    printf("  A≡B: %s ; C≡E: %s ; D 单独: %s\n",
           (g[0] == g[1]) ? "是" : "否",
           (g[2] == g[4]) ? "是" : "否",
           (g[3] != g[0]) ? "是" : "否");
}

/* ===== 例4：状态编码代价 ===== */
static void encoding(void) {
    int N = 16;
    int bin = 0;
    while ((1 << bin) < N) bin++;
    printf("  16 状态: 二进制 %d 触发器, 独热 %d 触发器, 输出译码门数 独热=0\n",
           bin, N);
    int sizes[4] = {3, 4, 8, 32};
    for (int k = 0; k < 4; k++) {
        int n = sizes[k], b = 0;
        while ((1 << b) < n) b++;
        printf("    N=%2d -> 二进制 %d ; 独热 %d\n", n, b, n);
    }
}

/* ===== 例5：交通灯（独热 + 完整自启动） ===== */
static void traffic(void) {
    const char *name[3] = {"红", "绿", "黄"};
    int QR = 1, QG = 0, QY = 0;                 /* 初态：红灯 */
    printf("  正常循环（T 在第 1 拍起为 1）：\n");
    printf("   拍  T   Q_RQ_GQ_Y  灯\n");
    for (int i = 0; i < 4; i++) {
        int T = (i == 0) ? 0 : 1;
        int idx = QR ? 0 : (QG ? 1 : 2);
        printf("   %d   %d   %d%d%d      %s\n", i, T, QR, QG, QY, name[idx]);
        int INV = !(QR | QG | QY) | (QR & QG) | (QG & QY) | (QR & QY);
        int DR = ((!T & QR) | (T & QY)) | INV;
        int DG = ((!T & QG) | (T & QR)) & !INV;
        int DY = ((!T & QY) | (T & QG)) & !INV;
        QR = DR; QG = DG; QY = DY;
    }

    printf("  全部 8 个编码的次态（自启动验证）：\n");
    int bad = 0;
    for (int s = 0; s < 8; s++) {
        int r = (s >> 2) & 1, g = (s >> 1) & 1, y = s & 1;
        int legal = (r + g + y == 1);
        printf("   %d%d%d %s ->", r, g, y, legal ? "合法" : "未用");
        for (int T = 0; T <= 1; T++) {
            int INV = !(r | g | y) | (r & g) | (g & y) | (r & y);
            int DR = ((!T & r) | (T & y)) | INV;
            int DG = ((!T & g) | (T & r)) & !INV;
            int DY = ((!T & y) | (T & g)) & !INV;
            printf("  T=%d:%d%d%d", T, DR, DG, DY);
            if (!legal) {
                int ns = DR + DG + DY;             /* 非法状态的次态必须是合法独热 */
                if (ns != 1) bad++;
            }
        }
        printf("\n");
    }
    printf("  自启动检查（未用状态一步内回到合法状态）: %s\n", bad ? "FAIL" : "PASS");
}

int main(void) {
    int x[] = {1, 1, 0, 1};
    printf("--- 例1 ---\n"); mealy(x, 4);
    printf("\n--- 例2 ---\n"); moore(x, 4);
    printf("\n--- 例2 长序列 1101101（验证重叠）---\n");
    int y[] = {1, 1, 0, 1, 1, 0, 1};
    mealy(y, 7);
    printf("\n--- 例3 状态化简 ---\n"); reduce();
    printf("\n--- 例4 编码代价 ---\n"); encoding();
    printf("\n--- 例5 交通灯 ---\n"); traffic();
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出（关键行）：

--- 例1 ---
 拍  输入  现态  输入后次态  输出Z
  1    1    00       01        0
  2    1    01       10        0
  3    0    10       11        0
  4    1    11       01        1
  末态 = 01

--- 例2 ---
  1    1    S0    S1     0
  2    1    S1    S2     0
  3    0    S2    S3     0
  4    1    S3    S4     0
  末态 = S4        ← Moore 要到第 5 拍才输出 1

--- 例3 状态化简 ---
  P1 分组: A->G0 B->G0 C->G0 D->G1 E->G0 
  P2 分组: ...
  最终等价类数 = 3 (期望 3)
  A≡B: 是 ; C≡E: 是 ; D 单独: 是

from itertools import product

# ============ 例1：Mealy 型 1101 检测器（方程驱动） ============
print("=== 例1 Mealy 型（4 状态 / 2 触发器） ===")
def mealy_step(Q1, Q0, x):
    D1 = (Q1 & (not Q0)) | ((not Q1) & Q0 & x)
    D0 = ((not Q1) & (not Q0) & x) | (Q1 & (not Q0) & (not x)) | (Q1 & Q0 & x)
    Z = Q1 and Q0 and x
    return int(D1), int(D0), int(Z)

def mealy_run(bits):
    Q1, Q0 = 0, 0
    rows = []
    for i, b in enumerate(bits, 1):
        n1, n0, Z = mealy_step(Q1, Q0, b)
        rows.append((i, b, f"{Q1}{Q0}", f"{n1}{n0}", Z))
        Q1, Q0 = n1, n0
    return rows, (Q1, Q0)

for row in mealy_run([1, 1, 0, 1])[0]:
    print("  拍%-2d 输入%d 现态%s 次态%s Z=%d" % row)

# 用"参考模型"逐位验证：检查每拍输出是否等于"后缀恰好是 1101"
def ref_mealy(bits):
    s, out = "", []
    for b in bits:
        s += str(b)
        out.append(1 if s.endswith("1101") else 0)
    return out

bad = []
for n in range(1, 9):
    for bits in product((0, 1), repeat=n):
        rows, _ = mealy_run(bits)
        got = [r[4] for r in rows]
        if got != ref_mealy(bits):
            bad.append(bits)
print(f"  方程 vs 参考模型（1~8 位全枚举）: {'PASS' if not bad else 'FAIL ' + str(bad[:3])}")

# ============ 例2：Moore 型（5 状态 / 3 触发器） ============
print("\n=== 例2 Moore 型（5 状态 / 3 触发器） ===")
MOORE = {0: (0, 1), 1: (0, 2), 2: (3, 2), 3: (0, 4), 4: (0, 2)}
def moore_run(bits):
    s, rows = 0, []
    for i, b in enumerate(bits, 1):
        Z = 1 if s == 4 else 0
        ns = MOORE[s][b]
        rows.append((i, b, f"S{s}", f"S{ns}", Z))
        s = ns
    return rows, s

for row in moore_run([1, 1, 0, 1])[0]:
    print("  拍%-2d 输入%d 现态%s 次态%s Z=%d" % row)

print("  Moore 对 1101 的输出:", [r[4] for r in moore_run([1,1,0,1])[0]],
      "→ 第 5 拍才为 1（需再看一拍）")
print("  重叠验证 1101101: Mealy 输出 =",
      [r[4] for r in mealy_run([1,1,0,1,1,0,1])[0]])
print("  Moore 状态序列 =",
      [r[2] for r in moore_run([1,1,0,1,1,0,1])[0]])

# ============ 例3：划分法状态化简 ============
print("\n=== 例3 划分法状态化简（A..E） ===")
Z  = [0, 0, 0, 1, 0]
NX = [(1, 2), (0, 2), (3, 2), (0, 2), (3, 2)]
g = Z[:]                                       # P1：按输出分组
print("  P1:", {chr(65 + i): g[i] for i in range(5)})
for p in range(2, 6):
    key = [(g[i], g[NX[i][0]], g[NX[i][1]]) for i in range(5)]
    uniq = {}
    ng = []
    for k in key:
        if k not in uniq:
            uniq[k] = len(uniq)
        ng.append(uniq[k])
    print(f"  P{p}:", {chr(65 + i): ng[i] for i in range(5)})
    if ng == g:
        print("  收敛（分组不再变化）")
        break
    g = ng
print("  等价类数 =", len(set(g)), " -> A≡B:", g[0] == g[1], ", C≡E:", g[2] == g[4],
      ", D 单独:", g[3] != g[0])

# ============ 例4：编码代价 ============
print("\n=== 例4 状态编码代价 ===")
for N in (3, 4, 8, 16, 32):
    print(f"  N={N:2d} -> 二进制 { (N-1).bit_length() } 触发器"
          f" ; 独热 {N} 触发器 ; 独热输出译码门数 0")

# ============ 例5：交通灯（独热 + 完整自启动） ============
print("\n=== 例5 交通灯（独热编码 + 完整自启动） ===")
QR, QG, QY = 1, 0, 0
for i in range(4):
    T = 0 if i == 0 else 1
    lamp = "红" if QR else ("绿" if QG else ("黄" if QY else "全灭"))
    print(f"  拍{i} T={T} Q_RQ_GQ_Y={QR}{QG}{QY} 灯={lamp}")
    INV = int(not (QR or QG or QY) or (QR and QG) or (QG and QY) or (QR and QY))
    DR = int((not T and QR) or (T and QY) or INV)
    DG = int(((not T and QG) or (T and QR)) and not INV)
    DY = int(((not T and QY) or (T and QG)) and not INV)
    QR, QG, QY = DR, DG, DY

print("  全部 8 个编码的次态（自启动验证）：")
bad = []
for st in product((0, 1), repeat=3):
    r, g, y = st
    legal = (r + g + y == 1)
    row = []
    for T in (0, 1):
        INV = int(not (r or g or y) or (r and g) or (g and y) or (r and y))
        DR = int((not T and r) or (T and y) or INV)
        DG = int(((not T and g) or (T and r)) and not INV)
        DY = int(((not T and y) or (T and g)) and not INV)
        row.append(f"{DR}{DG}{DY}")
        if not legal and (DR + DG + DY) != 1:
            bad.append((st, T))
    print(f"    {r}{g}{y} ({'合法' if legal else '未用'}) -> "
          f"T=0:{row[0]}  T=1:{row[1]}")
print(f"  未用状态一步内回到合法状态: {'PASS' if not bad else 'FAIL ' + str(bad)}")
print(f"  非法状态检测项 INV 覆盖：000/011/101/110/111 = 5 个未用状态")

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出要点：

例 1：Mealy 方程在第 4 拍输出 1，并且与"后缀匹配"参考模型在 1~8 位全枚举下完全一致 → 方程正确。
例 2：Moore 状态序列走到 $S_{4}$ ，输出要到下一拍才为 1（"慢一拍"的现场）。
例 3：划分法迭代 3 遍收敛为 3 个等价类（ $A \equiv B$ 、 $C \equiv E$ 、 $D$ 单独）。
例 5：交通灯三轮切换回到红灯；未用状态 000 在 $T = 0$ 时被自启动项拉回红灯，8 个编码的次态表全部指向有效状态。

考点

1. 必背结论

\begin{aligned} Moore： Z = λ (S) Mealy： Z = λ (S, X) \\ 二进制编码触发器数 = ⌈ \log_{2} N ⌉, 独热 = N \\ 状态等价 = 输出相同 \land 次态落在同一等价类 \\ 计数器 = 无输入的状态机 \end{aligned}

2. 设计流程（大题模板，按这个写不丢分）

① 定义状态（写出每个状态的语义）
② 画状态图 / 列状态表（注意"重叠"、"自环"）
③ 状态化简（划分法迭代到收敛）
④ 状态编码（说明选哪种编码）
⑤ 列次态真值表 → 卡诺图 → 次态方程
⑥ 按触发器类型转换：
     D 型：D = Q*（直接抄）
     JK 型：查激励表逐位反推
⑦ 写输出方程（Moore 只看状态；Mealy 含输入）
⑧ 检验未用状态是否自启动（若题目要求）

3. Moore vs Mealy（选择与对比，必考）

判据	Moore	Mealy
输出写在	圆圈内	箭头旁
输出方程含输入？	不含	含
状态数	多（通常 +1）	少
输出时刻	晚一拍	当拍
抗输入毛刺	强	弱

给一个序列 1101，若问"最少几个状态"：Mealy 4 个，Moore 5 个。

4. 高频陷阱

Moore 输出"慢一拍"：第 4 拍输入到位、第 5 拍才输出。别把两者混为一谈。
"允许重叠"改的是次态，不改输出：1101 检测后再来 1，下一个状态应是 $S_{1}$ （已匹配 1）而不是 $S_{0}$ 。这是序列检测题的头号失分点。
划分法必须迭代到收敛。只做一遍会把"输出相同但次态输出不同"的状态误合并（如例 3 的 $A$ 与 $C$ ）。
Mealy 的状态数少但输出方程含输入——考试要求"写出输出方程"时，漏掉输入项直接判错。
激励表用错触发器。D 型是 $D = Q^{*}$ （直接抄次态）；JK 型必须查表，且 $x$ 可用来化简。
未用状态当无关项会带来死锁。题目说"设计成自启动"时，未用状态的次态必须显式指定，不能填 $x$ 。
独热编码的次态方程有固定模板（保持项 + 被前驱拉起的项），不要傻画卡诺图。
状态编码不是任意的：编码方式直接影响次态方程的复杂度。若题目考"最简方程"，先试着调整编码（相邻状态给相邻编码，能让卡诺图更好地合并）。
触发器数算错： $N$ 个状态用二进制需 $⌈ \log_{2} N ⌉$ 个触发器。5 个状态要 3 个（不是 2.5 个）。

5. 与后续章节的接口

次态方程里"最长组合逻辑路径" 就是下一篇 circuit/16-timing.md 的关键路径，直接决定最高时钟频率。
L2 组成原理的控制器（硬布线控制器）就是一个状态机：状态 = 机器周期，输入 = 指令操作码 + 标志位，输出 = 各路控制信号。本站 arch 课程会直接引用这一篇的"次态方程 + 输出方程"框架。
独热编码 + 状态译码 是 FPGA 实现控制器的标准做法（circuit/21-fpga.md）。

小结

FSM = 有限状态 + 转移函数 + 输出函数；硬件结构永远是**"组合逻辑算次态 → 寄存器存状态 → 组合逻辑算输出"**。
Moore 输出只看状态（稳但慢一拍），Mealy 输出看状态 + 输入（快但透传毛刺）；同一个 1101 检测器，Mealy 4 状态 / 2 触发器，Moore 5 状态 / 3 触发器。
五步法：定义状态 → 状态图/表 → 化简 → 编码 → 求方程画电路。用 D 触发器时 $D = Q^{*}$ ，可以把"激励方程"这一步直接省掉。
状态化简的核心是"输出相同 + 次态等价"两个条件，且必须迭代到收敛（划分法）。
状态编码是权衡：二进制（触发器少、译码复杂）、格雷（抗毛刺）、独热（触发器多、译码为零，FPGA 首选）——"用面积换速度"这个主题贯穿整个 L1。
未用状态必须防死锁；题目要求"自启动"时，未用状态不能当无关项。

回到主线：L1 的逻辑功能部分到此完整了——从门、ALU、触发器，一路到能表达任意"行为"的状态机。理论上，CPU 控制器已经可以用这一篇的方法设计出来了。

但还有一个绕不过去的现实问题：这些电路到底能跑多快？ 状态机的次态逻辑要穿过多少个门、触发器的建立时间要留多少、时钟偏斜会不会让本该稳定的数据被采歪、违反了会发生什么（亚稳态）——"逻辑对不对"和"能不能跑起来"是两件事。

下一篇回答的是整条 L1 链条上最工程化的问题：时序。

下一篇：时序分析：建立时间、保持时间、亚稳态

有限状态机：时序电路的设计方法

概念

原理

一、Moore 与 Mealy：输出从哪来

二、两种描述工具

三、设计五步法（把整章的题目都装进来）

四、状态化简：划分法

五、状态数、触发器数、编码方式的关系

六、未用状态与自启动

七、状态机与计数器的关系

示例

例 1：`1101` 序列检测器（Mealy 版，完整五步设计）

例 2：同一个检测器的 Moore 版（多一个状态，慢一拍）

例 3：状态化简（划分法，完整迭代过程）

例 4：状态编码的代价对比

例 5：交通灯控制器（Moore 型三状态机）

例 6：用程序复算

考点

小结

我的笔记

评论（0）

有限状态机：时序电路的设计方法 ​

概念 ​

原理 ​

一、Moore 与 Mealy：输出从哪来 ​

二、两种描述工具 ​

三、设计五步法（把整章的题目都装进来） ​

四、状态化简：划分法 ​

五、状态数、触发器数、编码方式的关系 ​

六、未用状态与自启动 ​

七、状态机与计数器的关系 ​

示例 ​

例 1：1101 序列检测器（Mealy 版，完整五步设计） ​

例 2：同一个检测器的 Moore 版（多一个状态，慢一拍） ​

例 3：状态化简（划分法，完整迭代过程） ​

例 4：状态编码的代价对比 ​

例 5：交通灯控制器（Moore 型三状态机） ​

例 6：用程序复算 ​

考点 ​

小结 ​

我的笔记

评论（0）

有限状态机：时序电路的设计方法

概念

原理

一、Moore 与 Mealy：输出从哪来

二、两种描述工具

三、设计五步法（把整章的题目都装进来）

四、状态化简：划分法

五、状态数、触发器数、编码方式的关系

六、未用状态与自启动

七、状态机与计数器的关系

示例

例 1：`1101` 序列检测器（Mealy 版，完整五步设计）

例 2：同一个检测器的 Moore 版（多一个状态，慢一拍）

例 3：状态化简（划分法，完整迭代过程）

例 4：状态编码的代价对比

例 5：交通灯控制器（Moore 型三状态机）

例 6：用程序复算

考点

小结