学习 › 第 11 讲
摩尔（Moore）型与米利（Mealy）型状态机：完整设计
阅读约 7 分钟 · bitGateLab 团队
有限状态机（FSM）是一种时序电路，它能“记住”一个过程进行到了哪一步。红绿灯、密码锁、电梯控制器和串行通信接收器都是状态机。本文将介绍两种经典模型，即 Moore 型（摩尔型）和 Mealy 型（米利型），并通过一个 101 序列检测器，带你走完从文字描述到触发器方程的完整设计过程。
状态机的组成部分
所有同步 FSM 都由三个模块组成：
- 状态寄存器：n 个触发器（几乎总是 D 型），用来保存当前状态（现态）；最多可表示 2n 个状态。
- 次态逻辑：组合逻辑；根据当前状态和输入计算下一个状态（次态）。
- 输出逻辑：组合逻辑；计算各输出。
两种模型的区别在于最后一个模块：
- Moore 型：输出只取决于当前状态。输出写在每个状态的圆圈里面（例如 S3/1）。
- Mealy 型：输出取决于状态和输入。输出写在箭头上（输入/输出，例如 1/1）。
问题：101 序列检测器
串行输入 X 与时钟同步到来，每个周期一位。每当最近收到的三位是 1、0、1 时，输出 Z 应为 1。允许重叠：在序列 10101 中有两次检测，因为第一个序列末尾的 1 同时也是下一个序列的开头。
第一步是确定状态机需要记住什么。每个状态代表“序列已经匹配到哪里”：
- S0：还没有任何有用的输入。
- S1：上一位是 1。
- S2：最近几位是 1、0。
- S3：刚刚收到 1、0、1（Z = 1）。
状态图和状态表（Moore 型）
对每个状态和 X 的每个取值，问自己：加上这个新来的位之后，与 101 的开头相匹配的最长后缀是什么？这个后缀决定了次态。
| 现态 | X = 0 | X = 1 | Z |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 |
请注意两个经常出错的转移。在 S1 时又来一个 1：序列以 11 结尾，最后这个 1 仍然可以作为开头，所以状态机留在 S1。在 S3 时来一个 0：序列以 1010 结尾，它的后缀 10 与 101 的开头相匹配，所以转到 S2 而不是 S0。正是这一点使重叠检测成为可能。
状态分配与方程
4 个状态用 2 个 D 触发器（Q1 Q0）就够了。最直接的分配方式是二进制编码：S0 = 00，S1 = 01，S2 = 10，S3 = 11。使用 D 触发器时激励表非常简单，因为 D = Q+。
| Q1 | Q0 | X | Q1+ = D1 | Q0+ = D0 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
化简：
- D0 恰好在 X = 1 的各行为 1，所以 D0 = X。这很合理：在这种分配下，Q0 = 1 表示“上一位是 1”。
- D1 = Σm(2, 5, 6)，变量顺序为 Q1 Q0 X。最小项 2（010）和 6（110）相邻，合并为 Q0·X。最小项 5（101）没有取值为 1 的相邻项，只能单独保留：Q1·Q0·X。D1 = Q0·X + Q1·Q0·X。
- Moore 型的输出只取决于状态：Z = Q1·Q0。
最终电路包括 2 个 D 触发器、一个用于 Z 的 2 输入 AND 门，以及用于 D1 的一个 2 输入 AND 门、一个 3 输入 AND 门和一个 2 输入 OR 门（外加 Q0 和 X 的反相器）。
用测试序列验证
输入 X = 1 0 1 0 1 1 0 1，从 S0 出发。每个时钟沿之后的状态：
| 时钟沿 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| X | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 状态 | S1 | S2 | S3 | S2 | S3 | S1 | S2 | S3 |
| Z | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
共有三次检测：在第 1 到 3 位、第 3 到 5 位（重叠）和第 6 到 8 位。用方程验证第 4 个时钟沿：状态 S3 = 11，X = 0，D1 = 1·1 + 1·0·0 = 1，D0 = 0，次态为 10 = S2。一致。
Mealy 型版本
在 Mealy 型中，输出标在转移上，所以状态 S3 就多余了：检测发生在“处于 S2 时来了 1”的那一刻。用三个状态 A（无）、B（上一位是 1）和 C（最近几位是 1、0）：
| 状态 | X = 0 | X = 1 |
|---|---|---|
| A | A / 0 | B / 0 |
| B | C / 0 | B / 0 |
| C | A / 0 | B / 1 |
仍然需要 2 个触发器，但输出 Z = 1 出现在最后一个 1 到来的同一个周期，比 Moore 型版本早一个周期。
常见错误
- 把所有“失配”的转移都送回 S0，而不检查序列中哪一部分仍然有用；这样会漏掉重叠的检测。
- 在 Moore 型状态机中把输出写在箭头上，或者在 Mealy 型状态机中把输出写在状态里面。
- 忘了未使用的触发器组合（例如 Mealy 型版本中的代码 11）：必须决定它们转到哪里，或者把它们标为 X 并验证状态机能回到正常序列。
- 在任意时刻读取 Mealy 型状态机的输出：应当在紧挨时钟沿之前、输入已经稳定时采样。
- 测试状态机时恰好在时钟沿上改变输入 X。
在模拟器中试一试
有了方程之后，搭出检测器只需几分钟，而时序图可以让你检查每一次转移。
- 放置两个接同一时钟的 D 触发器；把它们的输出命名为 Q1 和 Q0。
- 把输入 X 直接接到 D0。
- 用两个反相器、两个 AND 门和一个 OR 门搭出 D1 = Q0·X + Q1·Q0·X，并接到 D1。
- 把 Q1 和 Q0 接到一个 AND 门，再接到一个指示灯作为 Z。
- 按照序列 1 0 1 0 1 1 0 1，在每个时钟沿之前改变 X，并在时序图上观察 Z 在第 3、5、8 个时钟沿之后点亮。
练习
- 允许重叠时，状态机在序列 1010101 中检测到几次 101？
答案
三次：在第 1 到 3 位、第 3 到 5 位和第 5 到 7 位。
- 重新写出不允许重叠的 101 检测器的 Moore 型状态表（检测到一次后从头开始）。
答案
只有 S3 这一行改变：X = 0 时转到 S0，X = 1 时转到 S1。其余各行不变。
- 采用 Mealy 型版本的状态分配 A = 00，B = 01，C = 10，求 Z。
答案
只有在状态 C 且 X = 1 时 Z = 1：Z = Q1·Q0·X。如果代码 11 永不出现，可以把它标为 X，于是 Z = Q1·X。
- 一个有 9 个状态的状态机至少需要几个触发器？
答案
4 个，因为 23 = 8 不够，而 24 = 16 足够。
要复习构成状态寄存器的触发器，请参阅锁存器与触发器。