Chisel进阶之有限状态机（一）——基本有限状态机

有限状态机（FSM，Finite-State Machine）是数字设计中的基本构建块，数字设计中很多状态逻辑都可以抽象为FSM。这一部分将对FSM的Chisel实现进行详细介绍，除了基本有限状态机（Moore有限状态机）以外，还会学习Mealy有限状态机和并将二者进行对比。这一篇文章就首先介绍Moore有限状态机。

有限状态机

有限状态机，即FSM，可以描述一组状态（states）和状态之间的条件状态转移（state transitions）。FSM有一个初始状态，会在复位的时候设置。而FSM还有个名字，叫作同步时序电路，是不是听起来很熟悉，没错，所有的同步时序电路本质上都可以抽象为有限状态机。

一个FSM的实现需要有三个部分：

1. 保存当前状态的寄存器；
2. 基于当前状态和输入信号计算下一个状态的组合逻辑电路；
3. 计算FSM输出的组合逻辑。

原则上来说，任何包含一个用于存储状态的寄存器或其他存储器元素的数字电路都可以用单个有限状态机来描述。然而这么做并不现实，比如你要想用单个FSM来描述我们的电脑那就太离谱了。所以这一部分还是介绍单个FSM，而下一部分则会介绍用过小的FSM的组合构建更大的通信FSM。

基本有限状态机

基本有限状态机也叫Moore有限状态机，下图是FSM的示意图：

如图所示，寄存器包含了当前的状态state，下个状态计算逻辑Next state logic或根据当前state和输入in来计算下一个状态nextState，在下一个周期，nextState就变成了state。输出逻辑Output logic会计算输出out，由于这里输出仅依赖于当前状态，一次你这种状态机叫作基本有限状态机，也叫做Moore机。

状态转换图（State Diagram）可视化地描述FSM的行为，在状态转换图中，每个状态都描绘为以状态名为标签的圆圈，而状态转换用状态之间的箭头来表示。执行某个转换的条件会在状态转换的箭头以标签的形式给出。下图就是一个FSM的状态转换图的例子：

这个FSM有三个状态：green、orange和red，表示不同等级的警告。FSM从green状态开始，如果一个bad event来了，警告等级就会转换为orange，如果再发生了第二个bad event，那就进一步转换为red，此时我们希望可以响铃，ring bell是FSM唯一的输出，我们把输出加到red状态上，如果接受到了clear信号，那警告等级就会重置为green。

尽管状态转换图可以可视化地描述FSM的功能，看起来很舒服，也很容易掌握，但状态转换表用于写代码的时候写起来更快。下表就上面警告FSM的状态转换表：

表中列举了不同当前状态和输入值对应的下一个状态以及当前状态对应的输出。原则上讲，我们需要把所有状态的所有可能性都列举出来，那这个表的话就会有$3\times 4=12$行。但我们可以简化一些，比如如果bad event发生的时候，clear信号就忽视掉了，也就是说bad event比clear有更高的优先级。输出列是有一些重复的，如果我们的FSM更大或者有更多的输出，那我们可以画两个表格，一个用于下个状态逻辑，另一个用于输出逻辑。

在设计好警告等级FSM之后，我们就可以用Chisel代码写出来了，完整代码如下：

// package my.hello

import chisel3._
import chisel3.util._

class SimpleFsm extends Module {
    val io = IO(new Bundle {
        val badEvent = Input(Bool())
        val clear = Input(Bool())
        val ringBell = Output(Bool())
    })

    // FSM的三种状态
    val green :: orange :: red :: Nil = Enum(3)

    // 状态寄存器
    val stateReg = RegInit(green)

    // 状态转换逻辑
    switch (stateReg) {
        is (green) {
            when(io.badEvent) {
                stateReg := orange
            }
        }
        is (orange) {
            when(io.badEvent) {
                stateReg := red
            } .elsewhen(io.clear) {
                stateReg := green
            }
        }
        is (red) {
            when(io.clear) {
                stateReg := green
            }
        }
    }

    // 输出逻辑
    io.ringBell := stateReg === red
}

object MyModule extends App {
    println(getVerilogString(new SimpleFsm()))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

下面解释一下代码：

1. 由于我们需要用到Chisel的Enum类型和switch控制指令，因此需要导入import chisel3.util._；
2. 输入输出我们都使用Chisel的Bool类型；
3. 这个FSM有两个输入和一个输出信号，都包含在一个IO的Bundle里面，这个结构前面说过很多次了；
4. 很多工作研究过最优的状态编码，常见的两种选择是二进制编码或者是独热编码，但是我们在Chisel中选择将这些底层决定交给综合工具，我们只负责写出可读性强的代码，所以我们用了Enum类，还用了符号化的名字表示状态：val green :: orange :: red :: Nil = Enum(3)（当前版本的ChiselEnum用的还是二进制编码，如果想用独热编码可以自己定义Chisel常量）；
5. 接着上一条，这几个状态被描述为一个列表，元素之间通过操作符::进行连接，Nil表示列表的结尾，然后一个ChiselEnum类型的实例被赋值到这个状态列表；
6. 存放状态信息的寄存器定义时给定了复位值：val stateReg = RegInit(green)；
7. FSM的重点是下个状态逻辑，这里我们在状态寄存器上用了Chisel的switch结构，覆盖了所有的状态，在每个is分支里面，我们都基于输入，通过赋新的状态给状态寄存器来实现下个状态逻辑；
8. 最后就是输出逻辑，也就是在状态寄存器值为red的时候就ringing bell，这个没啥好说的。

需要注意的是，我们没有引入一个为寄存器引入一个next_state信号，因为在Verilog和VHDL里面也是这么干的。在Verilog和VHDL里面，寄存器都是用特殊语法描述的，不能通过一个组合逻辑块被赋值和重新赋值。因此，额外的信号通过组合逻辑块计算后直接连接到寄存器的输入上就完事了。不过在Chisel里面寄存器是个基本类型，是可以随便在组合逻辑块里面用的。

结语

这一篇文章介绍了基本有限状态机（FSM），即Moore机，对应的是输出只和当前状态有关的有限状态机，下一篇我们将会学习输出依赖于输入的状态机，即Mealy有限状态机，通过上升沿检测的例子来阐明，进一步地还会比较Moore机和Mealy机的区别。