跳转至

有限状态机

★ 2.1 FSM 的概念

一般来说，典型的数字电路都可以归结为以下两种基本结构，即便是较为复杂的电路也可以对其进行细化，最终肯定可以对应到其中一种结构上。

Image title

结构示意图 1

Image title

结构示意图 2

注意到电路中存在一个名为状态寄存器的特殊结构，该结构存储了电路当前的状态信息。设寄存器位宽为 n，则该电路的状态数量不会超过 \(2^n\)，即其状态数量是有限的，因此这种电路结构称为有限状态机（Finate State Machine, FSM）。

顾名思义，有限状态机就是由一系列数量有限的状态组成的循环机制。它是由寄存器和组合逻辑构成的硬件时序电路。状态机通过控制各个状态的跳转来控制流程，使得整个代码看上去更加清晰易懂，在控制复杂流程的时候，状态机有着明显的设计优势。

2.1.1 Moore VS Mealy

有限状态机可分为两种。第一种输出信号只与当前状态有关，输入信号不会直接影响到输出信号，而是与当前状态（简称现态）信号一起生成下一状态（简称次态）信号，在时钟的上升沿之后次态转换为现态，才能影响到输出，这种结构称为摩尔型（Moore）有限状态机；另外一种其输出信号由现态与输入信号共同生成，输入信号可立刻对输出信号产生影响，这种结构称为米莉（Mealy）型有限状态机。

两种结构的有限状态机各有优缺点：Moore 型时序更好，但响应要慢一拍，Mealy 型响应最快，但时序上要差一些。一般来说，如果对电路相应速度要求不是非常苛刻的话，推荐使用 Moore 型有限状态机。

2.1.2 设计 FSM

设计 FSM 的基本步骤可以概括如下：

（1）画出状态转移图

把实际系统进行逻辑抽象，即实际问题转化为设计要求。首先确定电路输入输出引脚；然后根据实际需要列出所有的状态情况，并对状态顺序进行编号；最后根据状态转移条件画出状态转移图。

（2）确定状态编码和编码方式

编码方式的选择对所设计的电路复杂与否起着重要作用，要根据状态数目确定状态编码和编码方式。

（3）给出状态方程和输出方程

列写状态转移表，选定触发器类型，通过卡诺图化简给出状态方程和输出方程。（此步在 FPGA 编程中可省略）

（4）编写 Verilog 代码

按照步骤（1）~（2）编写具有可综合的 Verilog 代码。

★ 2.2 Verilog 实现 FSM

通过分析有限状态机的结构图，我们可以发现其包含三个部分，第一部分为纯组合逻辑，通过现态和输入信号生成次态信号，第二部分为时序逻辑，该时序逻辑非常简单，只包含一个带有复位功能的寄存器单元，复位时现态信号变为初始值，否则在每个时钟的上升沿将次态信号赋值给现态信号。第三部分为组合逻辑，该部分通过现态信号生成各输出信号。

其对应的代码结构为：

FSM.v
 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
module FSM (
    input           clk,
    input           rst,
    // ......
    // 其他输入输出信号
);
// 状态空间位数 n
parameter WIDTH = 3;
// 状态变量
reg [WIDTH-1: 0] current_state, next_state;

// 为了便于标识，我们用局部参数定义状态的别名代替状态编码
localparam STATE_NAME_1 = 3'd0;
localparam STATE_NAME_2 = 3'd1;
// ......

// ==========================================================
// Part 1: 使用同步时序进行状态更新，即更新 current_state 的内容。
// ==========================================================
always @(posedge clk) begin
    // 首先检测复位信号
    if (rst)  
        current_state <= RESET_STATE;
    // 随后再进行内容更新
    else 
        current_state <= next_state;
end

// ==========================================================
// Part 2: 使用组合逻辑判断状态跳转逻辑，即根据 current_state 与
//         其他信号确定 next_state。
// ==========================================================
// 一般使用 case + if 语句描述跳转逻辑
always @(*) begin
    // 先对 next_state 进行默认赋值，防止出现遗漏
    next_state = current_state;
    case (current_state)
        STATE_NAME_1: begin
            // ......
        end
        STATE_NAME_2: begin
            // ......
        end
        default: begin
            // ......
        end
    endcase
end

// ==========================================================
// Part 3: 使用组合逻辑描述状态机的输出。这里是 mealy 型状态机
//         与 moore 型状态机区别的地方。
// ==========================================================
// 可以直接使用 assign 进行简单逻辑的赋值
assign out1 = ......;
// 也可以用 case + if 语句进行复杂逻辑的描述
always @(*) begin
    case (current_state)
        STATE_NAME_1: begin
            // ......
        end
        STATE_NAME_2: begin
            // ......
        end
        default: begin
            // ......
        end
    endcase
end
endmodule
注意

有的时候状态机内的输出信号不止一种，为了保证低耦合性，避免可能发生的错误，我们建议每一个 always 块内仅进行一个变量的赋值。例如：

always @(*) begin
    if (condition) begin
        a = 1;
        b = 2;
    end
    else begin
        a = 2;
        b = 1;
    end
end

可以修改为

always @(*) begin
    if (condition) 
        a = 1;
    else
        a = 2;
end
always @(*) begin
    if (condition) 
        b = 2;
    else
        b = 1;
end

2.3 一个例子

为了便于理解，我们以一个例子带大家完整体验时序逻辑电路的设计流程。

例子：数字锁

某助教有一个神奇的锁。锁盘上只有两个按键，我们不妨记为 0 和 1。只有按键按照 0100 的顺序按下时才能解锁成功。例如，连续按下 01010 时并不会解锁，但再按下 0 后便会解锁（因为最近的四次输入为 0100）。我们想用一个数字电路判断给定的按键顺序能否解锁。

模块的输入包含一个时钟信号 clk 以及按下的按键编号 in。由于只有两个按键，所以我们可以根据 in 的高低电平区分按下的按键（例如高电平代表按下 1）。在 clk 的上升沿模块接收一个按键信息，同时输出一个 unlock 信号，当 unlock 信号为高电平时表明最近四次输入的序列可以解锁。

下面是一段波形图示例：

Image title

首先来考虑如何确定状态。自然，我们可以根据当前最近的四个输入标识状态，则对应的状态共有 \(2^4=16\) 种。但包含十六个状态的有限状态机无论设计上还是实现上都较为复杂，尽管我们可以通过状态化简消去一部分，但这个过程依然是十分繁琐的。

让我们再次分析这个问题。对于一个给定的输入序列，想要判断其能否开锁，我们只需要关注其最近的输入能否组成 0100 序列。先前我们固定观察最近的四次输入，但实际上有些情况近期是一定不能解锁的，例如序列 1110 至少要再经过三次输入才有可能解锁。

基于这一事实，我们可以只关注输入序列是否包含 0100 及其子序列，即考察最近的输入内容为 0、01、010、0010 四种情况。我们称之为后缀识别。

在最开始没有任何输入时，我们可以引入一个初始状态（不妨记作 - ），用于代表不属于上述四种的情况。接下来当输入一个 0 时，我们就识别到了后缀 0，即可进入下一状态；若输入一个 1，则不属于任何一种后缀，因此依然在初始状态。以此类推，我们就得到了下图所示的状态机。

Image title

基于后缀识别的状态机

Image title

构建流程

于是，我们就可以确定下来，这个问题的状态机一共有五个基本状态。我们约定如下的对应关系：

  • \(S_0\)：对应 -

  • \(S_1\)：对应 0

  • \(S_2\)：对应 01

  • \(S_3\)：对应 010

  • \(S_4\)：对应 0100

初始状态为 \(S_0\)，仅在 \(S_4\) 状态时输出解锁信号。由于输出仅和当前状态有关，因此我们可以选择 Moore 型状态机进行设计。五个状态可以使用 3bits 位宽的编码进行处理。接下来我们编写三段式 Moore 型状态机的代码。

首先定义状态变量以及状态名称：

reg [2:0] current_state, next_state;
localparam S0 = 3'd0;
localparam S1 = 3'd1;
localparam S2 = 3'd2;
localparam S3 = 3'd3;
localparam S4 = 3'd4;

接下来编写第一段：状态更新。假定 reset 信号的效果是清除之前所有的输入，恢复初始状态。则按下 reset 后状态机应当跳转到 \(S_0\)。

always @(posedge clk) begin
    if (reset)
        current_state <= S0;
    else
        current_state <= next_state;
end

接下来编写第二段：状态转移。根据状态转换图，我们可以编写如下的代码：

always @(*) begin
    next_state = current_state;
    case (current_state)
        S0: begin   // -
            if (in)
                next_state = S0;    // -
            else
                next_state = S1;    // 0
        end

        S1: begin   // 0
            if (in)
                next_state = S2;    // 01
            else
                next_state = S1;    // 0
        end

        S2: begin   // 01
            if (in)
                next_state = S0;    // -
            else
                next_state = S3;    // 010
        end

        S3: begin   // 010
            if (in)
                next_state = S2;    // 01
            else
                next_state = S4;    // 0100
        end

        S4: begin   // 0100
            if (in)
                next_state = S2;    // 01
            else
                next_state = S1;    // 0
        end
    endcase
end

最后，我们编写第三段：输出。

assign unlock = (current_state == S4) ? 1'B1 : 1'B0;

这样就完成了模块的编写。

参考资料

暂无

最后更新: November 16, 2023

评论

Authors: wintermelon008