前言

在Verilog等HDL中，有限状态机（Finite-State Machine）是一个比较重要的知识点，而且在软件工程、编译器设计等其他领域也是一个值得注意的方面。本文讨论的是有限状态机在Logisim、Verilog以及MIPS汇编中的具体实现。在本文的后面也会讨论同步复位以及异步复位的问题。

关于FSM

有限状态机的构成包括输入、状态转移与输出。本文主要讨论的有限状态机有两种——Moore型状态机以及Mealy型状态机。

关于状态转移逻辑

状态转移是状态机中最主要的部分，这一部分代表着状态机的主要运作机理。状态转移逻辑的构成主要包括当前状态、输入以及下一状态，也就是。创建状态转移关系时尤其要注意次态的指向问题，比如字符串匹配电路，当字符串成功匹配时如果后半部分可以作为下一次匹配的前缀，则次态的指向不应该为初始状态，而是前缀匹配的状态（具体题目的要求可能不同，需要具体分析）。通常情况下，Mealy机的状态可能比Moore机状态要少，这是因为Mealy机的输出还与输入有关系，可以在相同状态下根据不同的输入得到不同的输出。

关于输出内容

输出的内容与输入和状态的关系是两种状态机的主要区别。假设当前的状态为，输入为，输出为，在Moore型状态机中，输出的内容仅与当前的状态有关，即；而在Mealy型状态机中，输出的内容与当前的状态和输入有关，即。输出的内容也有时间上的区别，形象地说Mealy机的输出可以随时改变（这也导致其对于毛刺敏感）而Moore机只能在完整时钟周期改变；Mealy机的输出时长是状态与输入的AND，而Moore机是完整的时钟周期；Mealy机的输出比Moore机的输出要“早”。原因很好解释，Mealy机的输出与当前输入有关，并且此输出对应着Moore机下一个状态的输出。

输出关于时间的区别

Logisim实现有限状态机

搭建Moore型状态机

在Logisim中，寄存器（Register）对于状态机等时序逻辑电路的搭建是十分重要的。它的端口主要有输入、输出、使能信号、时钟信号以及复位信号，其中复位信号为异步复位，即只要信号为1则立即复位（输出端变0）。对于有限状态机，我们用寄存器控制电路的时序逻辑。其主要电路如下：

Moore型状态机电路

对于其中的转移电路与输出电路，偷懒的话我们只需用Logisim中的Analyze Circuit或者Combinational Analysis功能即可，如下图

转移电路

输出电路

搭建Mealy型状态机

Mealy型状态机与Moore型状态机总体上是同的，只是输出部分需要稍作改变（也可以有输出部分外其他部分的考虑，不过出于简便本文只考虑输出部分的不同）。

Mealy型状态机电路

Verilog实现有限状态机

步骤说明

在Verilog HDL中，搭建有限状态机电路流程是：理清状态转移逻辑，针对逻辑及需求写出电路，最后对电路进行调试。Verilog中的状态转移逻辑与上文Logisim的逻辑类似。我们需要对各状态进行编码，方便在代码实现时更好的组织电路。编码可以用普通的序号表示，如：

1
2
3
4
5
6
7
8
9
10
11
12
13
model example(
    input clk,
    input in,
    output out
);

reg [2:0] state, next_state;
parameter A = 0, B = 1, C = 2; //...

assign out = state == A; // Moore机输出
assign out = (state == A) && in; // Mealy机输出

endmodule

这样编码的好处是简洁方便，代码更加容易理解。除了上述编码，我们还可以使用独热码进行表示，独热码表示的好处是校验处于某种状态或者转移到某种状态时只需要考虑某一位即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
model example(
    input clk,
    input in,
    input [3:0] state,
    output [3:0] next_state,
    output out
);

parameter A = 0, B = 1, C = 2, D = 3; //...

next_state[A] = (state[A] & ~in) | (state[B] & in); 
//...

assign out = state[D]; // Moore机输出
assign out = state[D] & in; // Mealy机输出

endmodule

状态机的写法

通常来说Verilog实现有限状态机有三种写法——一段式、两段式、三段式。三种不同类型的写法以代码中状态转移、状态更新、输出逻辑的相对位置区分。一段式写法中三者在同一个always块内，这是极其令人唾弃的写法，因为难以调试（虽然看起来比较简短）。常用的写法是后两者，即将组合逻辑与时序逻辑分开的写法。代码中的always块可以有很多个，要根据需求确定。下面给出三段式写法的例子(Moore型状态机，异步复位)：

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
model example(
    input clk,
    input in1,
    input in2,
    input areset, // 异步复位信号
    output out1,
    output out2
);

// 常量、变量设定
parameter A = 0, B = 1, C = 2, D = 3; //...
reg [1:0] state, next_state;

// 状态更新
always @(*)
    begin
        case(state)
            A: next_state = in1 ? in2 ? B : C : D;
            //...
        endcase 
    end

// 状态转移
always @(posedge clk, posedge areset)
    begin
        if(areset)
            state <= 0;
        else
            state <= next_state;
    end

// 输出逻辑
always @(posedge clk, posedge areset)
    begin
        if(areset)
            {out1, out2} = 2'b0;
        else
            begin
                case(state)
                    A: {out1, out2} = 2'b10;
                    //...
                endcase
            end
    end

endmodule

两种状态机的区别

两种状态机在Verilog中的区别与Logisim一样，主要在于输出逻辑，下面举例：

Moore型状态机

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
module MooreStateMachine(
    input clk,
    input areset, // 异步复位信号
    input x,
    output reg y
);

// 定义状态寄存器和初始状态
reg [1:0] current_state, next_state;
initial current_state = S0;

// 状态转移
always @(posedge clk or posedge areset) begin
    if (areset) begin
        current_state <= S0; // 复位时回到初始状态
    end else begin
        current_state <= next_state; // 更新状态
    end
end

// 状态更新
always @(posedge clk or posedge areset) begin
    if (areset) begin
        next_state <= S0; // 复位时回到初始状态
    end else begin
        case (current_state)
            S0: next_state <= (x == 1'b1) ? S1 : S0;
            S1: next_state <= (x == 1'b0) ? S2 : S0;
            S2: next_state <= (x == 1'b1) ? S3 : S0;
            S3: next_state <= S0;
            default: next_state <= S0; // 默认情况下下一个状态为S0
        endcase
    end
end

// 输出逻辑
always @(current_state) begin
    case (current_state)
        S0: y = 1'b0;
        S1: y = 1'b0;
        S2: y = 1'b1;
        S3: y = 1'b0;
        default: y = 1'b0; // 默认情况下输出为0
    endcase
end

endmodule

Mealy型状态机

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
module MealyStateMachine(
    input clk,
    input areset, // 异步复位信号
    input x,
    output reg y
);

// 定义状态寄存器和初始状态
reg [1:0] current_state, next_state;
initial current_state = S0;

// 状态转移
always @(posedge clk or posedge areset) begin
    if (areset) begin
        current_state <= S0; // 复位时回到初始状态
    end else begin
        current_state <= next_state; // 更新状态
    end
end

// 状态转移
always @(posedge clk or posedge areset) begin
    if (areset) begin
        next_state <= S0; // 复位时回到初始状态
    end else begin
        case (current_state)
            S0: next_state <= (x == 1'b1) ? S1 : S0;
            S1: next_state <= (x == 1'b0) ? S2 : S0;
            S2: next_state <= (x == 1'b1) ? S2 : S0;
            default: next_state <= S0; // 默认情况下下一个状态为S0
        endcase
    end
end

// 输出逻辑
always @(current_state or x) begin
    case (current_state)
        S0: y = (x == 1'b1) ? 1'b0 : 1'b0;
        S1: y = (x == 1'b0) ? 1'b0 : 1'b0;
        S2: y = (x == 1'b1) ? 1'b1 : 1'b0;
        default: y = 1'b0; // 默认情况下输出为0
    endcase
end

endmodule

MIPS汇编实现有限状态机

MIPS实现状态机的应用不多，但是作为汇编语言也是可以实现有限状态机的，下面仅举一个小例子：

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
.data
    state:     .word 0   # 存储当前状态的变量
    input:     .word 0   # 存储输入信号的变量

.text
    main:
        # 读取输入信号
        lw $t0, input
        
        # 读取当前状态
        lw $t1, state
        
        # 根据当前状态和输入信号进行状态转换
        beq $t1, $zero, state0   # 如果当前状态是0，则跳转到状态0的处理
        beq $t1, $t0, state1    # 如果当前状态是1，并且输入信号与状态相同，则跳转到状态1的处理

    state0:
        # 在状态0执行的操作
        # 可以在这里添加任何你需要的代码
        li $t1, 0    # 设置新状态为0
        j done       # 跳转到完成状态

    state1:
        # 在状态1执行的操作
        # 可以在这里添加任何你需要的代码
        li $t1, 1    # 设置新状态为1
        j done       # 跳转到完成状态

    done:
        # 存储新状态
        sw $t1, state

        # 继续处理下一个输入信号或完成程序
        # 可以在这里添加你的程序逻辑

        # 退出程序
        li $v0, 10
        syscall

同步复位与异步复位

同步复位与异步复位是电路中不可忽视的一部分，此类功能用于在异常情况下重启电路。同步复位是指复位信后到来后，在下一个时钟信号上升沿将电路复位，而异步复位是指不考虑时钟信号的影响，复位信号到来即复位。在构造电路时要注意二者的区别。本节只讨论Logisim和Verilog有限状态机中的同步/异步复位。

Logisim实现同步/异步复位

在Logisim中，实现异步复位非常简单，由于寄存器的复位端口默认是异步复位的，所以只需要将复位信号连接至寄存器的复位端口即可。

异步复位

而同步复位需要考虑时钟信号，所以需要将复位信号与时钟信号结合以对寄存器进行复位，最简单的方法是多路选择器（Mutiplexer）的运用。

同步复位

除了上述方法，我们还可以将复位信号与寄存器的输入信号与与门（AND Gate）相连，再接到寄存器输入端口，其原理与多路选择器相似。

与门同步复位

Verilog实现同步/异步复位

Verilog有限状态机中同步复位与异步复位的区别主要在于时序逻辑中敏感列表的不同，同步复位电路的时序逻辑模块敏感列表只有时钟沿：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
module SynchronousReset(
    input clk,
    input reset, // 同步复位
    input in,
    output out
);

// 时序逻辑电路
always @(posedge clk)
    begin
        if(reset)
            // 复位操作
        else
        // do something
    end

endmodule

而异步复位电路的时序逻辑模块敏感列表需要加上复位信号的上升/下降沿：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
module AsynchronousReset(
    input clk,
    input reset, // 同步复位
    input in,
    output out
);

// 时序逻辑电路
always @(posedge clk)
    begin
        if(reset)
            // 复位操作
        else
        // do something
    end

endmodule

总结

本文主要讨论了计算机组成原理中的有限状态机以及同步/异步复位问题，希望对读者关于此方面的理解有所帮助。