什么是状态机通俗讲解

8．4　有限状态机

有限状态机是一类很重要的时序电路，是许多数字电路的核心部件。有限状态机的一般结构如图8．4．1所示。除了输入信号、输出信号外，有限状态机还包括一组具有“记忆”功能的寄存器，这些寄存器可以记忆状态机的内部状态。在有限状态机中，状态寄存器的下一个状态及输出，不仅与输入信号有关，而且还与寄存器的当前状态有关，因此，有限状态又可以认为是组合逻辑和寄存器逻辑的特殊组合。它包括两个主要部分：组合逻辑部分和寄存器部分。寄存器部分用于存储状态机的内部状态；组合逻辑部分又分为状态译码器和输出译码器，状态译码器确定状态机的下一个状态，即确定状态机的激励方程，输出译码器确定状态机的输出，即确定状态机的输出方程。

图8．4．1　有限状态机的结构示意图

有限状态机的基本操作有以下两种。

（1）有限状态机内部状态转换。有限状态机经历一系列状态，下一状态由状态译码器根据当前状态和输入条件决定。

（2）产生输出信号序列。输出信号由输出译码器根据当前状态和输入条件决定。

用输入信号决定下一状态也称为“转移”。除了转移之外，复杂的状态机还具有重复和历程功能。从一个状态转移到另一个状态称为控制定序，而决定下一状态所需的逻辑称为转移函数。

在产生输出的过程中，由是否使用输入信号可以确定有限状态机的类型。两种典型的有限状态机是摩尔（MOORE）型状态机和米立（MEALY）型状态机。在摩尔状态机中，其输出只是当前状态值的函数，并且仅在时钟边沿到来时才发生变化。米立状态机的输出则是当前状态值、当前输出值和当前输入值的函数。对于这两类状态机，控制程序都取决于当前状态和输入信号。大多数实用的有限状态机都是同步的时序电路，由时钟信号触发状态的转换。时钟信号同所有的边沿触发的状态寄存器和输出寄存器相连，这使得状态的改变发生在时钟的上升沿。此外，还有利用组合逻辑的传播延迟来实现状态机存储功能的异步状态机，这种状态机难以设计并且容易发生故障。

状态机图就是一种表示一个设计实体的各种工作状态、内部各工作状态转换的条件及各工作状态对应的输出信号序列的图形。图8．4．2所示是一个状态机图的示例。

图8．4．2　状态机图

一个控制功能可以用有限状态机实现，也可以用CPU实现。二者相比，前者的性能远高于后者。这是因为，在CPU结构中，需要许多操作和部件；而在有限状态机中，状态存储在多个触发器中，表示行为的代码存储在门级网络中，因而有限状态机性能比较高。下述代码既可以被CPU执行，也可被VHDL描述有限状态机执行。

上述代码对应的波形如图8．4．3所示。

图8．4．3　波形图

上述代码对应的波形如图8．4．4所示。

图8．4．4　波形图

如果上述代码由CPU实现，则上述代码将被转换为10至20条机器指令，这些指令的执行时间既和CPU速度有关，也和执行时所选择的IF语句的分支路径有关，实际的执行时间在最小值和最大值之间波动。如果上述代码由门和触发器实现，则执行时间为一个时钟周期。由此可以得出结论：在执行时间短和执行时间的确定性方面，由门和触发器实现的有限状态机要优于CPU实现的方案。

有限状态机的工作分两个阶段进行：第1阶段计算新状态（次态）；第2阶段将新状态存入寄存器。计算新状态所需的时间限制了有限状态机的最高工作频率。上面的例子中决定新状态（AL或RUN）的条件是：

if cp＞37and d＜7then

有限状态机工作过程的分析如图8．4．5所示，图中黑颜色代表计算新状态的逻辑处于不稳定状态，而白颜色代表计算新状态的逻辑处于稳定状态。时钟信号改变了有限状态机的状态，开始计算新状态，从开始到完成需要一段时间，这一段时间用黑颜色代表。在下一个时钟脉冲到达之前，必须计算出新状态逻辑到达稳定状态的时间。

图8．4．5　有限状态机的工作过程

有限状态机可分为以下两种基本类型。

MEALY型状态机：输出是当前状态和所有输入信号的函数。

MOORE型状态机：输出仅是当前状态的函数。

现态和次态：某一状态在接收信号之前所处的状态称为现态；某一状态在接收信号之后所处的状态称为次态。

次态一般由输入信号的现态Qⁿ的取值来决定。

状态图：形象地表示某一状态与信号取值间关系的几何图形。图8．4．6所示为JK触发器的状态图。

图8．4．6　JK触发器的状态图

图8．4．6中圈内填的是触发器的状态，箭头线表示时钟脉冲触发沿到来时触发器状态的转换方向，箭头线左上方写的是实现相应转换的JK取值。图8．4．6中数值的含义为：若要保持0状态，则J＝0，K为任意；若从0状态转换为1状态，则J＝1，K为任意；同理，若从1状态转换为0状态，则K＝1，J为任意。

注意：

（1）状态转换是由现态到次态，而不是由次态到现态或次态到次态；

（2）输出是现态的函数，而不是次态的函数。

下面的例子是一个判断马达旋转方向（正转／反转）的指示器，通过这个例子可以解释如何构造一个如图8．4．7所示的状态机。图中有两个脉冲传感器，它对白色背景产生“1”，对黑色背景产生“0”。这两个脉冲信号作为状态机的输入，状态机的输出则指明马达旋转的方向。

图8．4．7　状态机原理示意图

脉冲传感器1连接到信号线P1，脉冲传感器2连接到信号线P2，信号P1和P2在相位上相差90°。根据脉冲信号P1、P2之间的时间关系，可以判断马达的旋转方向。状态机的输出信号是：POS和NEG。POS－1且NEG－0表示正转；POS－0且NEG－1表示反转。该指示器应当在任何时候测出旋转方向的变化，如图8．4．8所示，而下面的实现方案仅在P1、P2由“00”变为“01”或“10”时才能指出旋转方向的变化。

图8．4．8　敏感脉冲P1和P2

如图8．4．9所示，具有4个状态的MEALY型状态机可用来描述控制器。可以用2位（bit）表示4个状态，状态及相应的编码如表8．4．1所示。假定当前状态为“＋”，若输入信号P1、P2为“01”，则下一个状态为“POS”，在状态变化的同时输出信号POS、NEG的值变为“10”；若输入信号P1、P2为“10”，则下一个状态为“NEG”，在状态变化的同时输出信号POS、NEG的值变为“01”。这正好符合MEALY型状态机的特点。

图8．4．9　MEALY型状态机

表8．4．1　状态及状态编码