有限状态机

有限状态机

有限状态机,也称为FSM(Finite StateMachine)，其在任意时刻都处于有限状态集合中的某一状态。当其获得一个输入字符时，将从当前状态转换到另一个状态，或者仍然保持在当前状态。任何一个FSM都可以用状态转换图来描述，图中的节点表示FSM中的一状态，有向加权边表示输入字符时状态的变化。(说明：有限状态机理论知识可以参考《数字设计原理与实践第四版》P452 clocked synchronous state-machine analysis 部分。)

而有限状态机又分为Moore型有限状态机和Mealy型有限状态机。简而言之，Moore型有限状态机输出仅仅和当前状态有关；Mealy 型状态机输出和当前状态以及输入信号都有关。但是二者的下一状态都是仅和当前状态以及输入信号有关，它们之间的关系是组合逻辑关系。

接下来我们学习一下如何用 Logisim 实现有限状态机。

在搭建有限状态机前，首先要对状态机进行设计，这是整个电路搭建工作的重点和难点，设计好了，之后制作电路的过程就是非常程式化的了。最基本的，你首先要根据问题设计出状态转移图；下一步就是对状态进行二进制编码。我们来看下面的这个状态转移图。

这个有限状态机有三个状态，我们可以采用最简单的方式对其进行编码：

三个状态至少需要 2 位二进制数才能不重复地表示出来：

 状态    编码

   S1         00
   S2         01
   S3         10

也可以使用独热编码(每一个状态的编码中仅有一位是 1，其余全是 0 的编码)：

状态     编码

   S1        001
   S2        010
   S3        100

还可以采用其他任意方式编码，总之能用 m 位二进制数表示出每一个状态即可（实际生产中独热编码使用较多）。

有限状态机的输入 n 位（本题 n=1），输出 k 位（本题 k=1）。

接下来就是实现状态转移逻辑：

首先写出状态转移表：

当前状态   输入    下一状态

     S1           0            S2
     S1           1            S3
     S2           0            S3
     S2           1            S2
     S3           0            S2
     S3           1            S1

根据状态转移表，使用 Logisim 的 Analyze Circuit功能生成状态转移电路：这里对状态采用第一种编码方式。

我们的状态编码是两位的，state0 表示编码第 0 位，state1 表示编码第 1 位。

如上图，我们的状态转移电路就完成了。

接下来我们需要完成状态输出电路。根据状态转移图可知，这是一个 Moore型有限状态机，输出仅跟当前状态相关。

这道题的输出逻辑比较简单，就是当且仅当当前状态为 S3 时，输出 1，否则输出 0。

所谓状态存储，就是一个寄存器，例如你的状态编码是 3 位的，那么就准备一 个3 位寄存器即可，本题中采用的是 2 位编码，因此选一个 2 位寄存器。

如上图所示，一个 Moore 型有限状态机就搭建好了。

Mealy 型状态机的搭建方法和 Moore 型相同，唯一区别就是状态输出部分需要把输入信号也考虑进去，整体上看起来就是比 Moore 型多一根输入信号到状态输出电路的连线，下面是一个 Mealy 型状态机的示意图。

有限状态机是一个常用的时序电路模型，它并不复杂，因为除了寄存器部分外，状态转移和状态输出电路都是都是纯组合逻辑，只要画好状态转移图，接下来的电路设计就易如反掌。

Tips: 大家在完成课下实验2,3之前可以参考后面章节的有限状态机例题进行模仿学习。