The Tutorial for FPGA Player - Episode 4: State Machine

22 Feb 2021

大家好，欢迎回到FPGA教程的第四期。说是FPGA教程，结果一直在和大家讲数字电路的事情，但是毕竟数字电路是一切的基础，如果不理解数字电路，也许一开始玩FPGA不会有太大问题，但是越到后面就会觉得越玄。所以拥有良好的基础还是相当必要的。不过好消息是，本期就是数字电路基础的最后一期了。下一期开始就可以开始写Verilog玩FPGA了。

什么是状态机

其实各位可能之前已经听说过了状态机这个名词。状态机是个软硬件中都非常常用的设计。其实更像是一种设计模板，把需要实现的功能，划分成状态，然后套进状态机的模板中，最后实现这个状态机。那为什么要这么麻烦套成状态机再实现状态机，而不是直接实现这个电路呢？原因其实也很简单，一旦逻辑复杂到一定程度，“直接实现”会变得很难管理，而最后为了提高可维护性通常还是得引入状态机的设计。这样还不如一开始就做状态机呢。

状态机，顾名思义，必然是和 状态 相关的。状态机的主要思想就是，把一个机器的运行情况人为划分成很多不同的状态，而机器的输出，根据当前所处的状态来决定，而机器的输入则会影响到机器之后的状态。进一步到具体机器的设计，其实无非也就是要回答两个问题：

1. 在什么状态下要做什么事情

2. 怎么样会导致状态发生改变

比如最简单的例子，一盏灯，按一下会亮，再按一下会灭。这个机器就可以定义为有两个状态，一个是灯亮，一个是灯灭。回答第一个问题，什么状态下要做什么事情：灯亮的状态下，输出亮；灯灭的状态下，输出灭。回答第二个问题，怎么样会导致状态发生改变：灯亮的状态下，如果按键按下，就进入灯灭的状态；灯灭的状态下，如果按键按下，就进入灯亮的状态。无论何种状态下，如果没有按键按下，则停留在当前的状态。如果画成状态图的话，大致如下：

从这个图里也能清楚的看到之前提的两个问题。圆圈就是表示状态，这里只有两个状态，每个状态有一个自己的编号（0和1）以及状态对应的输出（灭和亮），回答了第一个问题；箭头则是表示状态的转换，不同的输入会导致什么样的结果，回答了第二个问题。

再看一个稍微复杂些，但是也很常见的例子，自动贩卖机。假设一个贩卖机，只卖矿泉水，价格定为2元，只接受1元硬币或者5角硬币，多不找零，设计一个状态机来描述它的行为。这个机器的话，它有两个输入，投入5角或者投入1元；以及一个输出，是否已经付了足够多的钱。

一个简单的想法，仍然按照之前的做法，设计两个状态，一个是付够钱了，另外一个是还没付够钱。那输出也就是直接和状态对应的。然后，考虑输入，就出问题了。如果当前没付够钱，怎么样知道投入5角或者1元之后就付够了呢？加个变量来记录？如果考虑到“当前状态”这个说法本身就是一个变量的话，完全可以把“付了多少钱”这一信息也编码到状态当中。把状态分为，没有付钱，付了0.5元，付了1元，付了1.5元和付了2元这五种状态。这样状态转换也就容易设计的，比如从0.5元这个状态，如果付0.5元就到1元的状态，如果付1元就到1.5元的状态。状态图示如下：

注意代表每个状态的圆圈中都有两行，第一行写的是状态的名称，通常为了之后实现（程序或者电路）方便，会标注一个从0开始的数字，而第二行则是这个状态对应的输出，如这里只能是 是 或者 否，而前4个状态都是否，只有投够钱，到达最后一个状态才会变成 是。其它的箭头则是表示如何进入下一个状态。

以上的两个例子听起来很简单，但是这并不表示状态机只能用来实现这类很简单的东西。在以后的教程中就会看见，整个GameBoy的设计当中，许多关键的地方都需要用状态机来实现。所以，理解状态机的概念和实现还是很有必要的。当然，也如前面所说，状态机并不一定需要要用74或者FPGA来实现，软件设计中也经常会使用到状态机的思想，这是一个通用的框架。

用逻辑电路实现状态机

不过当然，这个教程讲的是逻辑电路和FPGA，所以自然还是讲讲如何用逻辑电路来实现状态机。还记得之前说过的组合逻辑和时序逻辑吧？状态机就是一个同时需要用到两部分的电路。具体而言，进入下个状态由时序逻辑电路控制，而状态控制的输出则是由组合逻辑电路控制。

之前的第二个例子当中提到了，“状态”这个东西本身就是变量，为此，在设计状态机的时候可以不引入别的变量。变量，自然需要有可以存储数据的元件来存储，而在逻辑电路中，就是上一节中讲的触发器。一个触发器可以存储1个bit的数据，比如要实现上面那个售货机的电路，因为可以有5个不同的状态，这也就至少需要3个bit来存储（1个bit显然只能是两个状态，0或者1，而2个bit则可以有4个状态，从00到11，3个就可以有8个状态了，虽然这里只需要5个），那么这个状态机的中心就是三个触发器。而这三个触发器，也就是这个状态机的时序逻辑电路部分了。

那么组合逻辑电路部分呢？还记得之前说的设计状态机的两个基本问题吗？用逻辑电路实现状态机无非也就是回答这两个问题。

首先第一个问题，在什么状态下要做什么事情。可以根据上面的信息列一个表，这个表描述的是当前状态和输出信号的关系：

其中Q2 Q1和Q0其实也就是3个触发器所存储的值，分别可以是0或者1。在这个简单的例子当中，不难看出输出值就等于Q2的值，或者说如果希望让1只对应S4（1 0 0）的话，可以写成

C = Q2 && !Q1 && !Q0

回答第二个问题，怎么样会导致状态发生改变。定义两个输入，一个a表示投入5角，一个b表示投入1元，列一个当前状态，输入信号，和下一个状态的关系表。

这个表，如之前所说，回答的是第二个问题，不同状态如何变化。注意到这里出现了一些无效状态，这里就不多加考虑他们的处理，但是如果是做正式的产品，这些状态自然也需要纳入考虑，提高产品的稳定性。

但是这个表怎么用呢？从设计电路的角度来说，电路上关心的是，如何设计一个电路，给定当前状态和输入信息，产生下一个状态的编码。比如考虑其中的D2信号，也就是下一个状态编码的其中一位，在S0、S1的时候保持为0，在S2且输入为01时为1否则为0，在S3且输入为01和10是为1否则为0，而在S4是则始终为1。各位可能已经听出来了，这就一个输入为5bit（3位状态+2位外部输入）输出为1bit的组合逻辑电路。而把这些关系输入到软件当中（当然也可以手动化简），这样就能得到如下的逻辑表达式，表示了输入和输出的关系：

**D2 = (Q1 && b)

(Q1 && Q0 && a)

Q2**

**D1 = (!Q2 && !Q1 && b)

(!Q1 && Q0 && a)

(Q1 && !Q0 && !b)

(Q1 && !a && !b)**

**D0 = (!Q1 && Q0 && !a)

(!Q2 && !Q0 && a)

(Q0 && !a && !b)**

如图是D2这一位的设置，A B C D E分别是Q2 Q1 Q0（状态）a b（输入）。X表示这个结果无所谓，如无效状态和未使用的状态。

到这里为止，就得到了所有需要的表达式，一个输出表达式，三个下一状态的表达式。

把这些电路全部画出来，并且连接起来的话，这个状态机也就完成了。

回过来再考虑一下整个状态机的架构的话，也就是分为三个部分，最左边的是用来产生下一状态的三个组合逻辑，中间的是保存当前状态的触发器，而右边的则是输出逻辑。这个套路可以用于各类的状态机的设计。

其实，从下一节开始，我们就不会再这样画表、具体考虑各种逻辑了，而是用Verilog直接写代码来描述需要的行为，而不是需要的逻辑。但是这一节仍然介绍这些内容，是希望大家能明白，即使以后不用画这些表设计这些电路了，Verilog到最后产生的仍然是这些东西。如果写Verilog却不知道实际对应的电路，就很容易写出不能用实际硬件实现的代码，或者说对应到软件里，也就是无法编译的代码了。