有限状态机（Finite State Machine）

有限状态机（Finite State Machine）

简介

有限状态机（Finite State Machine，简称FSM）是指状态节点数和输入、输出范围皆有限的状态机。

状态机的组成六要素

(1) 状态集合

状态集合是组成状态机的必备要素，该集合里包含了状态机所能达到的所有状态：

{起床, 找小明, 找小强, 踢足球, 喝冷饮, 看电影, 吃火锅, 打游戏, 睡觉}

Summary: 状态集合定义了状态机可以存在的所有状态。

(2) 初态

初态是状态机的第二个必备要素，它是整个状态机开始工作的起点。

Summary: 初态决定了状态机的起始状态。

(3) 终态

终态是状态机的结束状态，即若状态机到达终态，它的使命也将完成，从此不再工作。事实上，大部分运行在FPGA上的状态机是没有终态的，因为它们都需要用有限的状态来处理无限的事件。

Summary: 终态表示状态机的任务完成状态，但在FPGA中很少存在真正的终态。

(4) 输入符号集

输入符号集是驱动状态机进行状态转换的主要因素，不过状态机的状态转换不一定需要外界的事件触发，因此输入符号集也不是组成状态机的必备要素。但是大部分运行在FPGA上的状态机还是需要输入符号集的，至少大多数情况下，它们都需要一个复位信号来让状态机进入初态。

Summary: 输入符号集用于驱动状态转换，但在某些情况下可以没有输入符号集。

(5) 输出符号集

输出符号集是状态机输出结果的集合。状态机的输出是由现态或现态和输入共同决定的。

Summary: 输出符号集定义了状态机可能产生的所有输出。

(6) 状态转移函数

状态转移函数定义了状态机如何从一个状态转移到另一个状态。它决定了在给定输入的情况下，状态机会转移到哪个下一个状态。

Summary: 状态转移函数决定了状态机的状态转换规则。

状态机的工作四要素

状态机在工作时，将状态机的工作状态划分为四个要素——现态、输入、输出、次态。其中，“现态”和“输入”是因，“输出”和“次态”是果，分别介绍如下。

(1) 现态

现态指状态机当前所处的状态。

Summary: 现态是状态机在某一时刻的具体状态。

(2) 输入

输入一般指外部事件，当一个外部事件发生后，状态机便会根据状态转移函数发生相应的状态跳转，或者状态机将会更新自己的输出情况。在FPGA中，根据输入信号是异步的还是同步的又可将状态机分为异步状态机和同步状态机。鉴于稳定性的考虑，以后提到和FPGA相关的状态机全部为同步状态机。对于异步输入信号，可以参考【本篇→编程思路→时钟及时钟域→跨时钟域问题】中的相关处理方法，同步化后再送至状态机。

Summary: 输入是触发状态机状态转换的条件。

(3) 输出

输出是由现态或者现态和输入共同决定的，如果这两者都没有变化，那么输出也不应该有变化。输出符号集是必需的，但具体到某一状态或者某一输入触发事件，输出并不是必需的，有时候带来的仅仅是状态迁移而已。

Summary: 输出是状态机在某一状态下可能产生的结果。

(4) 次态

次态是根据现态、输入及状态转移函数所得出的状态机将要跳转至的新状态。次态是相对于现态而言的，一旦状态迁移完成，次态便成为了新的现态。

Summary: 次态是状态机即将进入的新状态。

FPGA中的状态机模型

按照状态机的输出与其现态、输入之间的关系，可将FPGA中的状态机抽象为三种基本模型——Moore、Mealy和Mix，即摩尔型、米利型和混合型，分别介绍如下。

1. Moore型状态机

如果一个状态机的输出仅由现态决定，那么它就是一个Moore型的状态机。而按照驱动输出的数字电路特性，又将Moore型状态机细分为Moore l型、Moore 2型、Moore 3型，详细介绍如下。

(1) Moore l型

Moore 1型状态机的原理结构框图如下所示：

从图中可以看出，Moore 1型状态机的结构可以划分为两大部分——状态转移部分和输出生成部分。

• 状态转移部分：输入和现态（现态寄存器的输出）通过组合逻辑共同作用产生次态，当下一次时钟有效边沿到来的时候，现态寄存器发生更新，刚才产生的次态即成为了新的现态，而新的现态将和新的输入共同作用产生新的次态，如此往复。
• 输出生成部分：现态（现态寄存器的输出）直接通过组合逻辑产生当前的输出（这点也是Moore状态机区别于Mealy状态机最显著的特点）。有时候，我们不希望将这部分的组合逻辑的延迟影响到后续模块的处理，那么可以仿照图通过添加输出寄存器来解决这个问题，但是需要特别注意的一点是，由于输出寄存器的更新需要等到下次时钟的有效边沿，因此经过输出寄存器寄存后的输出其实对应的是状态机上一个状态。

Summary: Moore 1型状态机的输出仅由现态决定，存在输出延迟的问题。

(2) Moore 2型

Moore 2型状态机的原理结构框图如下所示：

从图中可以看出，Moore 2型状态机的结构仍划分为状态转移和输出生成两大部分。与Moore 1型状态机相比，输出生成部分的输入端由之前的现态（现态寄存器的输出）变为了次态（由输入和现态通过组合逻辑产生）。这样一来，由于次态和次态决定的输出在同一个时钟周期内变得有效，那么在下一次时钟有效边沿到来时，现态寄存器和输出寄存器将会同时进行更新，至此，次态变成新的现态，次态决定的输出变成新的输出。因此，Moore 2型状态机中经过寄存后的输出是对应于当前状态的。

Summary: Moore 2型状态机通过改变输出生成部分的输入端，解决了输出延迟的问题。

(3) Moore 3型

Moore 3型状态机的原理结构框图如下所示：

通过上图可以看出，Moore 3型状态机就是将那些适合使用组合逻辑的输出采用Moore 1型的方式来处理，而将那些适合使用寄存器的输出采用Moore 2型的方式来处理，因此Moore 3型也叫混合型Moore状态机。

Summary: Moore 3型状态机结合了Moore 1型和Moore 2型的优点，适用于不同的输出需求。

2. Mealy型状态机

如果一个状态机的输出是由现态和输入共同决定的，那么它就是一个Mealy型的状态机。而按照驱动输出的数字电路特性，又将Mealy型状态机细分为Mealy l型、Mealy 2型、Mealy 3型，详细介绍如下。

(1) Mealy l型

Mealy 1型状态机的原理结构框图如下所示：

从图中可以看出，对于Mealy 1型状态机来说，由于次态和输出均由现态和输入通过组合逻辑共同决定，因此可以将状态转移部分和输出生成部分合并成一个部分，兼并产生状态机的次态和输出。当下一次时钟有效边沿到来后，现态寄存器完成刷新，次态成为了新的现态，而新的现态和新的输入共同作用产生新的次态和新的输出，如此往复。

Summary: Mealy 1型状态机的输出由现态和输入共同决定，可能产生输出延迟的问题。

(2) Mealy 2型

Mealy 2型状态机的原理结构框图如下所示：

从图中可以看出，Mealy 2型状态机重新将状态转移部分和输出生成部分分开，并做成级联的形态。输出生成部分由次态和输入共同作用产生次态对应的输出。这样，由于次态和次态决定的输出在同一个时钟周期内变得有效，那么在下一次时钟有效边沿到来时，现态寄存器和输出寄存器将会同时进行更新，至此，次态变成新的现态，次态决定的输出变成新的输出。因此，Mealy 2型状态机中经过寄存后的输出是对应于当前状态的。

Summary: Mealy 2型状态机通过将状态转移部分和输出生成部分分开，解决了输出延迟的问题。

(3) Mealy 3型

Mealy 3型状态机的原理结构框图如下所示：

与Moore型状态机类似，Mealy l型和Mealy 2型状态机也各有其优缺点。它们的本质区别仍在于“由状态产生输出”这部分的组合逻辑所处的位置。如果像Mealy l型那样，将该部分逻辑和次态产生逻辑并联，那么该组合逻辑的时间延迟将会影响到后续电路的工作；反之，如果像Mealy 2型那样，将该部分逻辑和次态产生逻辑串联，那么该组合逻辑的时间延迟将会影响到状态机自身的工作。因此，为了将Mealy l型和Mealy 2型状态机的缺点最小化、优点最大化，便有了Mealy 3型状态机。

Summary: Mealy 3型状态机结合了Mealy 1型和Mealy 2型的优点，适用于不同的输出需求。

3. Mix型状态机

如果一个状态机有多个输出，且其中一些仅由现态决定，而另一些是由现态和输入共同决定的，那么它就是一个Mix型的状态机。其实，Mix型状态机就是一个Moore型状态机和Mealy型状态机的组合体，而每一个Moore型状态机可以有Moore 1型、Moore 2型、Moore 3型三种选择，每一个Mealy型状态机也可以有Mealy l型、Mealy 2型、Mealy 3型三种选择，因此Mix型状态机可以细分为9种类型。

Summary: Mix型状态机结合了Moore型和Mealy型状态机的优势，适用于复杂的输出需求。