数字IC手撕代码-有限状态机FSM-饮料机

        大家好我是酸菜鱼，这个系列着重讲解数字ic或FPGA实习面试及秋招面试的高频手撕代码题。

往期专栏：

数字ic手撕代码-导览目录 - 哔哩哔哩 (bilibili.com)

数字ic手撕代码-格雷码的编码与解码 - 哔哩哔哩 (bilibili.com)

数字IC手撕代码-序列检测（移位寄存器写法） - 哔哩哔哩 (bilibili.com)

专栏众多，不一一列举，详情请看导览目录... 

有限状态机介绍

        有限状态机（Finite state machine）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图，也就是我们常说的在写FSM之前要先画状态转移图。

有限状态机写法   

有限状态机常见的有三种写法：

※ 一段式写法：将下一个状态计算、状态跳转和信号输出在一个进程中完成。

※ 二段式写法：将状态跳转在一个进程中完成，将下一个状态计算和信号输出在一个进程中完成。

※ 三段式写法：将下一个状态计算、状态跳转和信号输出分别在三个进程中完成。

上面所说的进程也就是用一个过程语句块（always）描述。

        这里建议在写状态机的时候，都采用三段式写法，原因很简单，在写只有几个状态的FSM时候，一段式也好两段式也好，都可以快速的写出来而且思路清晰。但是实际工程中的状态机经常会出现有十几个状态相互跳转，甚至状态机嵌套的情况，这时候一段、两段式的状态机书写的思路就不是特别清晰， 更重要的代码维护性不强。所以本文只讲解三段式状态机的写法。

三段式状态机基本结构

三段式的状态机分为两种：Mealy型和Moore型。它们的区别在于摩尔型（Moore）输出只和状态有关而与输入无关，米莉型（Mealy）输出不仅和状态有关而且和输入有关系。

※ 根据状态的个数确定状态机编码。

※ 状态机第一段：时序逻辑，非阻塞赋值，传递状态机的状态（state<=next_state）

※ 状态机第二段：组合逻辑，阻塞赋值，根据当前的状态和输入，确定下一个状态机的状态。

※ 状态机第三段：时序或组合逻辑，非阻塞赋值，根据当前状态和当前输入（Mealy型状态机）或者当前状态（Moore型状态机），确定输出信号。

下面以一个饮料机为例子来写一个三段式状态机：

问：请用FSM设计一个饮料机，画出状态转移图并编写代码实现。（其中，投币可以是1元，也可以是五角，当投币满2元就可以出一瓶饮料，饮料机应该还具有找零功能）。

        第一步画状态转移图，我们得先确定有几种状态，状态之间的转换关系是怎么样的，然后再画出状态转移图。

首先分析有几种状态：

IDLE状态：即饮料机的初始状态，此时没有往饮料机里投一毛钱。

GET05状态：饮料机里有五角钱。

GET10状态：饮料机里有一块钱，可能是投两次五角到达该状态，也可以是投一次一元到达该状态。

GET15状态：饮料机里有一块五，可能是投三次五角、一次五角一次一块、一次一块一次五角到达该状态。

上面总共说了四种状态，用两比特即可完全描述状态。

    还有没有别的状态？没有了！饮料机不会有两块的状态！比如在GET15状态，饮料机里有一块五，投入一块，总投入两块五，此时饮料机会给一瓶饮料并找零五角，饮料机回到初始状态。如果投入五角，则总投入两块，此时饮料机会给一瓶饮料且不找零。如果是在GET10状态，投入一块，饮料机也会回到初始状态并给一瓶饮料不找零。综上，我们画出状态转移图。

        根据我们写的状态转移图写出接口定义，输入时钟、复位和投币。输出找零和饮料。如果drink为高，则找零五角，如果drink为高，则给一瓶饮料。

状态机的状态编码，我们采取独热码的形式，即one-hot编码，每个状态只有1bit为1。再定义当前状态和下个状态的变量。

第一段：状态转移

第二段：根据当前状态，确定下一个状态

第三段：根据当前状态和输入，确定输出

第三段控制输出，如果当前状态为GET10且投币一元，或者当前状态为GET15且投币五角，则饮料一瓶不找零。如果当前状态为GET15且投币一元，则饮料一瓶找零五角。其他情况均不出饮料且不找零。

testbench：省略了端口定义及模块例化部分。

仿真波形：

以上为饮料机的FSM。记住三段式即可，第一段：状态转移。第二段：根据当前状态和输入确定下一个状态。第三段：根据当前状态和输入，确定输出。