有限状态机

控制与数据通路

打开几乎任何一个数字模块，你都会看到两类逻辑并肩共存。数据通路是数字真正流动的地方——寄存器、多路复用器、加法器，以及那一整套转换数据的组合电路。控制则是站在它之上、拉动各种操纵杆的小单元：*现在加载这个寄存器、选择那个多路复用器的输入、这一拍启动乘法。*数据通路是厨房，控制则是那位喊出操作顺序的大厨。

为什么要在脑子里把它们分开？因为它们出错的方式不同，设计它们的方式也不同。数据通路的 bug 看起来是数字算错了；控制的 bug 看起来是数字算对了、却出现在错误的时刻——或者一台机器永远卡死，等着一个永远不会发生的步骤。当一段行为主要是*「按这个顺序做这些事，并视情况而定」*时，这种排序就是控制，而控制正是状态机的用武之地。

状态机到底是什么

一台有限状态机说穿了就是这样：一小组有名字的状态，任何时刻恰好有一个是「当前」的，再加上一组转移规则，根据输入说明下一个该进入哪个状态。想想红绿灯。它有三个状态——绿、黄、红——它任何时候都只处在其中一个，而时钟（或定时器）的一次滴答就把它推向下一个。它永远不可能「有点儿绿」。这种*恰好 N 选一*的纪律，正是它的全部要义。

从机理上看，一台状态机是由两块你已经熟悉的硬件搭起来的。一个状态寄存器——一组触发器——保存当前状态，并且只在时钟边沿改变；这是时序部分，也就是记忆。围绕它的是次态逻辑——纯组合门电路，它看着当前状态加上输入，算出*下一步该去哪儿*。每一次时钟滴答，寄存器就锁存那个次态，循环往复。

摩尔型与米利型

状态机有两种风味，唯一的区别是输出从哪里来。在摩尔型机器里，输出只取决于当前状态——绿灯亮着，是*因为*你正处在「绿」状态，就这么简单。在米利型机器里，输出取决于状态与当前输入两者的组合，因此一个输入可以*在同一拍内*改变输出，甚至在状态还没动之前。

这个取舍是实打实的。摩尔型的输出无毛刺、像寄存过一样干净——它们只在时钟边沿之后才改变——但米利型机器往往需要更少的状态，并且能早一拍做出反应，因为它不必等着跳进一个专门的输出状态。代价是：米利型的输出是输入的组合函数，所以它们可能产生毛刺，而且会把你的时序绑死在那些驱动这些输入的源头上。

画状态图

在写下一行 Verilog 之前，先把这台机器画出来。这套记号很小：每个状态是一个圆圈，每个转移是一根箭头，箭头上标着触发它的输入条件，还有一根凭空而来的箭头标出复位状态。对摩尔型机器，把每个输出写*在圆圈里*；对米利型，把它写*在箭头上*。这张图就是规格——在纸上把它做对，代码几乎就自己写出来了。

我们拿一个自动售货机控制器把它讲具体：它在 15 美分时出货，只收 5 美分（nickel）和 10 美分（dime）的硬币。状态就是它已经看到了多少钱：S0（0 美分）、S5（5 美分）、S10（10 美分）、S15（出货，然后回到 S0）。从 S0，投一枚 5 美分到 S5，投一枚 10 美分到 S10；从 S5，投 5 美分到 S10，投 10 美分就达到 15；从 S10，无论哪种硬币都达到 15 或以上，触发出货输出。四个圆圈、几根箭头——这就是整个大脑。

列出状态：把这个模块可能处于的每一种不同情形都写下来（这里是：已经投了多少钱），并给每一个起一个清晰的名字。
选定复位状态——机器上电后进入的那个状态。给它画上那根独一无二的入箭头（这里是 S0，没有钱）。
对每个状态，问一句「对于每一种可能的输入，我该去哪儿？」，并为每种情况画一根带标注的箭头。漏掉一种情况，就是一个无声无息的 bug。
放置输出：摩尔型放在圆圈里（出货住在 S15 里），米利型放在箭头上。到这里，这张图就是一份完整的、可以照着写代码的规格了。

用 Verilog 写一台状态机

我们推崇的写法是两段式状态机，它和第 2 节里的硬件一一对应。一个时钟驱动的块是状态寄存器——它什么都不做，只是在每个时钟边沿把 *next_state* 拷进 *state*（并在复位时跳回起点）。一个组合块是次态逻辑——一条干净的 case 语句，针对当前状态决定该往哪儿走。把这两者分开，是写出可读、可综合状态机的头号好习惯。

// Block 1: the state register (sequential)
always @(posedge clk or posedge rst)
  if (rst) state <= S0;          // reset to the start state
  else     state <= next_state;  // latch next state each clock edge

状态寄存器——一组触发器。这是状态机里唯一的记忆，每个时钟边沿改变一次。（这里用的是异步复位；若要同步复位，就把 rst 从敏感列表里去掉。）

// Block 2: next-state logic (combinational)
always @(*) begin
  next_state = state;            // DEFAULT: stay put — no latches
  case (state)
    S0:  if (nickel) next_state = S5;
         else if (dime) next_state = S10;
    S5:  if (nickel) next_state = S10;
         else if (dime) next_state = S15;
    S10: if (nickel || dime) next_state = S15;
    S15: next_state = S0;        // dispensed; back to start
    default: next_state = S0;    // covers unused encodings
  endcase
end

次态逻辑：纯组合门电路。默认赋值加上 default 分支，正是让它安全无虞的关键。

输出就挂在这同一副骨架上。对摩尔型机器，只用 *state* 来驱动它们（assign dispense = (state == S15);）。对米利型，再把输入也揉进去。有些团队会专门加一个第三段来写输出——这没问题，只要状态寄存器、次态逻辑和输出逻辑在视觉上依然分得清清楚楚。

状态编码（二进制与独热）

你的状态有 S0、S10 这样的名字，可触发器只认得比特——所以每个状态都需要一个二进制位型，而你如何分配这些位型，就叫*编码*。两个经典选择是二进制和独热，它们的区别正是一道教科书式的「触发器换逻辑」的取舍题。

二进制编码把 N 个状态压进大约 ceil(log2(N)) 个触发器——4 个状态用 2 比特就放得下（00、01、10、11）。寄存器很少，但次态逻辑必须*解码*这些比特，于是你在组合门上付出代价。独热编码给每个状态各自一个触发器——任何时刻恰好有一位是热的（0001、0010、0100、1000）。这要烧掉更多触发器，但每个转移判断都变成一次单比特检查，于是逻辑既浅又快。