HDLBits答案(16)_Verilog有限状态机(3)

Verilog有限状态机(3)

HDLBits链接

---

前言

今天我们来做一组非常有趣的状态机题目——Lemmings（旅鼠）游戏系列！这组题目会从一个简单的左右走动的小人开始，逐步增加掉落、挖掘、甚至死亡等功能。通过这组题目，你能很好地体会到如何逐步扩展一个复杂的状态机。

想象一下，你在设计一个游戏角色的AI控制器，每次增加一个新功能都要考虑如何与原有功能配合。这在实际工程中非常常见——需求总是在变化的，我们需要学会如何优雅地扩展设计。

---

题库

题目10：Lemmings1 - 基础版：左右走动的小人

题目理解

我们有一个可爱的旅鼠小人，它只有两种状态：

• 向左走（LEFT）
• 向右走（RIGHT）

规则很简单：

• 左边碰到障碍物（bump_left=1）就向右走
• 右边碰到障碍物（bump_right=1）就向左走
• 两边都碰到？没关系，还是往当前方向的反方向走（其实和碰一边是一样的效果）
• 复位时小人向左走

这就像你在一个走廊里走路，碰到墙就掉头，是不是很简单？

基础知识：Moore型状态机

这个题目是一个典型的Moore型状态机，因为输出只由当前状态决定：

• 状态在LEFT时，walk_left=1，walk_right=0
• 状态在RIGHT时，walk_left=0，walk_right=1

输出和当前输入没有关系，只看你现在在哪个状态。

Solution10：

module top_module(
    input wire clk,
    input wire areset,           // 异步复位：小人刚被洗脑，向左走
    input wire bump_left,        // 左边碰到障碍物
    input wire bump_right,       // 右边碰到障碍物
    output reg walk_left,        // 输出：向左走
    output reg walk_right        // 输出：向右走
);

    // 状态参数定义
    parameter LEFT  = 1'b0;
    parameter RIGHT = 1'b1;

    reg state;
    reg next_state;

    // 为了方便判断，把两个bump信号拼起来
    wire [1:0] bump;
    assign bump = {bump_left, bump_right};

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (state)
            LEFT: begin
                // 左边有障碍物，或者两边都有，就向右走
                if ((bump == 2'b10) || (bump == 2'b11)) begin
                    next_state = RIGHT;
                end else begin
                    next_state = LEFT;
                end
            end
            RIGHT: begin
                // 右边有障碍物，或者两边都有，就向左走
                if ((bump == 2'b01) || (bump == 2'b11)) begin
                    next_state = LEFT;
                end else begin
                    next_state = RIGHT;
                end
            end
            default: begin
                next_state = LEFT;
            end
        endcase
    end

    // 第二段：时序逻辑，状态更新（异步复位）
    always @(posedge clk or posedge areset) begin
        if (areset) begin
            state <= LEFT;       // 复位时向左走
        end else begin
            state <= next_state;
        end
    end

    // 第三段：输出逻辑（Moore型，只由当前状态决定）
    assign walk_left  = (state == LEFT);
    assign walk_right = (state == RIGHT);

endmodule

代码优化思考

其实，这个状态转移逻辑可以写得更简洁：

• 在LEFT状态时，只要bump_left为1就转RIGHT，不用管bump_right
• 在RIGHT状态时，只要bump_right为1就转LEFT

不过原文的写法也很清晰，把所有情况都列出来了，对初学者更友好。

---

题目11：Lemmings2 - 进阶版：会掉落的小人

现在游戏升级了！我们增加了一个ground信号：

• ground=1时：小人在地面上，规则和之前一样
• ground=0时：小人掉下去了！
  • 它会发出”aaah”的叫声（aaah=1）
  • 但它不会忘记之前在往哪个方向走
  • 等ground=1回到地面时，继续往掉落前的方向走

题目理解

这时候我们需要扩展状态了！原来的2个状态不够用了，因为我们要记录：

• 小人在地面上向左走
• 小人在地面上向右走
• 小人掉下去了，之前是向左走的
• 小人掉下去了，之前是向右走的

所以现在我们有4个状态了！

状态设计思路

把状态信息拆成两部分：

1. 动作状态：在走路？还是在掉落？
2. 方向记忆：之前是往左还是往右？

这样设计状态，信息就不会丢失了。

Solution11：

module top_module(
    input wire clk,
    input wire areset,           // 异步复位：小人刚被洗脑，向左走
    input wire bump_left,        // 左边碰到障碍物
    input wire bump_right,       // 右边碰到障碍物
    input wire ground,           // 地面信号：1=在地面，0=掉落
    output reg walk_left,        // 输出：向左走
    output reg walk_right,       // 输出：向右走
    output reg aaah              // 输出：掉落时的叫声
);

    // 状态参数定义：4个状态
    parameter LEFT     = 2'b00;  // 在地面上向左走
    parameter RIGHT    = 2'b01;  // 在地面上向右走
    parameter AH_LEFT  = 2'b10;  // 掉落中，记得向左走
    parameter AH_RIGHT = 2'b11;  // 掉落中，记得向右走

    reg [1:0] state;
    reg [1:0] next_state;

    wire [1:0] bump;
    assign bump = {bump_left, bump_right};

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (state)
            LEFT: begin
                if (ground == 1'b0) begin
                    next_state = AH_LEFT;   // 地面没了，开始掉落，记住方向
                end else if ((bump == 2'b10) || (bump == 2'b11)) begin
                    next_state = RIGHT;     // 碰到障碍，右转
                end else begin
                    next_state = LEFT;
                end
            end
            RIGHT: begin
                if (ground == 1'b0) begin
                    next_state = AH_RIGHT;  // 地面没了，开始掉落，记住方向
                end else if ((bump == 2'b01) || (bump == 2'b11)) begin
                    next_state = LEFT;      // 碰到障碍，左转
                end else begin
                    next_state = RIGHT;
                end
            end
            AH_LEFT: begin
                if (ground == 1'b0) begin
                    next_state = AH_LEFT;   // 还在掉落，继续保持
                end else begin
                    next_state = LEFT;      // 回到地面，继续向左走
                end
            end
            AH_RIGHT: begin
                if (ground == 1'b0) begin
                    next_state = AH_RIGHT;  // 还在掉落，继续保持
                end else begin
                    next_state = RIGHT;     // 回到地面，继续向右走
                end
            end
            default: begin
                next_state = LEFT;
            end
        endcase
    end

    // 第二段：时序逻辑，状态更新（异步复位）
    always @(posedge clk or posedge areset) begin
        if (areset) begin
            state <= LEFT;
        end else begin
            state <= next_state;
        end
    end

    // 第三段：输出逻辑
    assign walk_left  = (state == LEFT);
    assign walk_right = (state == RIGHT);
    assign aaah       = ((state == AH_LEFT) || (state == AH_RIGHT));

endmodule

关键设计要点

优先级很重要！ 注意在LEFT和RIGHT状态中，我们先判断ground信号，再判断bump信号。因为掉落比走路更紧急——地面都没了，还管什么障碍物！

---

题目12：Lemmings3 - 高级版：会挖掘的小人

游戏继续升级！现在小人还会挖掘了！增加一个dig信号：

• ground=1且dig=1时：小人开始挖掘（digging=1）
• 挖掘时如果ground=0：还是会进入掉落状态
• 优先级规则：掉落 > 挖掘 > 改变方向

题目理解

状态又要扩展了！现在我们需要6个状态：

• 在地面向左走（LEFT）
• 在地面向右走（RIGHT）
• 向左挖掘中（DIG_LEFT）
• 向右挖掘中（DIG_RIGHT）
• 向左掉落中（FALL_LEFT）
• 向右掉落中（FALL_RIGHT）

Solution12：

module top_module(
    input wire clk,
    input wire areset,           // 异步复位：小人刚被洗脑，向左走
    input wire bump_left,        // 左边碰到障碍物
    input wire bump_right,       // 右边碰到障碍物
    input wire ground,           // 地面信号
    input wire dig,              // 挖掘信号
    output reg walk_left,        // 输出：向左走
    output reg walk_right,       // 输出：向右走
    output reg aaah,             // 输出：掉落叫声
    output reg digging           // 输出：正在挖掘
);

    // 状态参数定义：6个状态
    parameter LEFT      = 3'b000;
    parameter RIGHT     = 3'b001;
    parameter DIG_LEFT  = 3'b010;
    parameter DIG_RIGHT = 3'b011;
    parameter FALL_LEFT = 3'b100;
    parameter FALL_RIGHT= 3'b101;

    reg [2:0] state;
    reg [2:0] next_state;

    wire [1:0] bump;
    assign bump = {bump_left, bump_right};

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (state)
            LEFT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_LEFT;      // 优先级最高：掉落
                end else if (dig == 1'b1) begin
                    next_state = DIG_LEFT;       // 次之：挖掘
                end else if ((bump == 2'b10) || (bump == 2'b11)) begin
                    next_state = RIGHT;           // 最后：改变方向
                end else begin
                    next_state = LEFT;
                end
            end
            RIGHT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_RIGHT;
                end else if (dig == 1'b1) begin
                    next_state = DIG_RIGHT;
                end else if ((bump == 2'b01) || (bump == 2'b11)) begin
                    next_state = LEFT;
                end else begin
                    next_state = RIGHT;
                end
            end
            DIG_LEFT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_LEFT;      // 挖掘时也可能掉落！
                end else begin
                    next_state = DIG_LEFT;        // 继续挖掘
                end
            end
            DIG_RIGHT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_RIGHT;
                end else begin
                    next_state = DIG_RIGHT;
                end
            end
            FALL_LEFT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_LEFT;       // 继续掉落
                end else begin
                    next_state = LEFT;            // 回到地面
                end
            end
            FALL_RIGHT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_RIGHT;
                end else begin
                    next_state = RIGHT;
                end
            end
            default: begin
                next_state = LEFT;
            end
        endcase
    end

    // 第二段：时序逻辑，状态更新
    always @(posedge clk or posedge areset) begin
        if (areset) begin
            state <= LEFT;
        end else begin
            state <= next_state;
        end
    end

    // 第三段：输出逻辑
    assign walk_left  = (state == LEFT);
    assign walk_right = (state == RIGHT);
    assign digging    = ((state == DIG_LEFT) || (state == DIG_RIGHT));
    assign aaah       = ((state == FALL_LEFT) || (state == FALL_RIGHT));

endmodule

状态机扩展的技巧

看出来了吗？每次增加新功能，我们都是：

1. 识别新的状态：把每个”动作+方向”的组合都定义成独立状态
2. 保持状态的连续性：比如DIG_LEFT只能转到FALL_LEFT或保持，不能跳到其他方向的状态
3. 明确优先级：在状态转移时，先判断高优先级的事件（如掉落）

---

题目13：Lemmings4 - 终极版：会死亡的小人

现在游戏来到了终极版本！小人会死亡了！规则是：

• 如果小人掉落超过20个时钟周期，那么当它接触地面时就会直接死亡
• 死亡后，所有输出（dig、fall、left、right）都置零
• 只有复位才能让它复活

手绘状态转移图（注意：Dead状态少画了一个自己到自己的转移）：

题目理解

现在我们需要计数器了！因为要数掉落了多少个周期。同时还要增加两个新状态：

• SPLATTER：即将死亡（掉落时间够了，但还没落地）
• DEAD：彻底死亡

所以现在总共有8个状态！

Solution13：

module top_module(
    input wire clk,
    input wire areset,           // 异步复位：小人刚被洗脑，向左走
    input wire bump_left,        // 左边碰到障碍物
    input wire bump_right,       // 右边碰到障碍物
    input wire ground,           // 地面信号
    input wire dig,              // 挖掘信号
    output reg walk_left,        // 输出：向左走
    output reg walk_right,       // 输出：向右走
    output reg aaah,             // 输出：掉落叫声
    output reg digging           // 输出：正在挖掘
);

    // 状态参数定义：8个状态
    parameter LEFT       = 3'b000;
    parameter RIGHT      = 3'b001;
    parameter DIG_LEFT   = 3'b010;
    parameter DIG_RIGHT  = 3'b011;
    parameter FALL_LEFT  = 3'b100;
    parameter FALL_RIGHT = 3'b101;
    parameter DEAD       = 3'b110;
    parameter SPLATTER   = 3'b111;

    reg [2:0] state;
    reg [2:0] next_state;

    reg [4:0] cycle_count;  // 计数器：记录掉落时间，20需要5位

    wire [1:0] bump;
    assign bump = {bump_left, bump_right};

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (state)
            LEFT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_LEFT;
                end else if (dig == 1'b1) begin
                    next_state = DIG_LEFT;
                end else if ((bump == 2'b10) || (bump == 2'b11)) begin
                    next_state = RIGHT;
                end else begin
                    next_state = LEFT;
                end
            end

            RIGHT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_RIGHT;
                end else if (dig == 1'b1) begin
                    next_state = DIG_RIGHT;
                end else if ((bump == 2'b01) || (bump == 2'b11)) begin
                    next_state = LEFT;
                end else begin
                    next_state = RIGHT;
                end
            end

            DIG_LEFT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_LEFT;
                end else begin
                    next_state = DIG_LEFT;
                end
            end

            DIG_RIGHT: begin
                if (ground == 1'b0) begin
                    next_state = FALL_RIGHT;
                end else begin
                    next_state = DIG_RIGHT;
                end
            end

            FALL_LEFT: begin
                if ((ground == 1'b0) && (cycle_count < 5'd20)) begin
                    next_state = FALL_LEFT;   // 还在掉落，时间不够20
                end else if ((ground == 1'b0) && (cycle_count >= 5'd20)) begin
                    next_state = SPLATTER;    // 还在掉落，时间够20了
                end else begin
                    next_state = LEFT;         // 回到地面，还没死
                end
            end

            FALL_RIGHT: begin
                if ((ground == 1'b0) && (cycle_count < 5'd20)) begin
                    next_state = FALL_RIGHT;
                end else if ((ground == 1'b0) && (cycle_count >= 5'd20)) begin
                    next_state = SPLATTER;
                end else begin
                    next_state = RIGHT;
                end
            end

            SPLATTER: begin
                if (ground == 1'b1) begin
                    next_state = DEAD;         // 落地了，彻底死亡
                end else begin
                    next_state = SPLATTER;     // 还没落地，继续splatter
                end
            end

            DEAD: begin
                next_state = DEAD;             // 死了就不动了
            end

            default: begin
                next_state = LEFT;
            end
        endcase
    end

    // 第二段：时序逻辑，状态更新
    always @(posedge clk or posedge areset) begin
        if (areset) begin
            state <= LEFT;
        end else begin
            state <= next_state;
        end
    end

    // 第三段：计数器逻辑
    always @(posedge clk or posedge areset) begin
        if (areset) begin
            cycle_count <= 5'd0;
        end else if ((next_state == FALL_LEFT) || (next_state == FALL_RIGHT)) begin
            cycle_count <= cycle_count + 1'b1;  // 继续掉落，计数+1
        end else begin
            cycle_count <= 5'd0;                 // 不是掉落状态，清零
        end
    end

    // 第四段：输出逻辑
    assign walk_left  = (state == LEFT);
    assign walk_right = (state == RIGHT);
    assign aaah       = ((state == FALL_LEFT) || (state == FALL_RIGHT) || (state == SPLATTER));
    assign digging    = ((state == DIG_LEFT) || (state == DIG_RIGHT));

endmodule

计数器设计要点

注意计数器是看next_state而不是state！因为：

• 如果看state，计数会延迟一个周期
• 我们希望进入掉落状态的第一个周期就开始计数

这是一个常见的小技巧，在设计带计数器的状态机时要注意。

---

入门者避坑指南

在做Lemmings这组题目时，初学者最容易犯以下错误：

错误1：状态定义不全，遗漏状态

错误表现：

// 只定义了LEFT和RIGHT，忘记定义掉落状态
parameter LEFT  = 1'b0;
parameter RIGHT = 1'b1;
// 缺少AH_LEFT和AH_RIGHT！

错误原因：

• 没有仔细分析需求，每个”动作+方向”的组合都需要独立状态
• 比如”掉落且记得向左”和”掉落且记得向右”是两个不同的状态

正确做法：

• 列出所有可能的场景
• 每个场景都分配一个独立状态
• 画状态转移图帮助理清思路

错误2：状态转移优先级搞反

错误表现：

LEFT: begin
    if ((bump == 2'b10) || (bump == 2'b11)) begin
        next_state = RIGHT;     // 先判断碰撞
    end else if (ground == 1'b0) begin
        next_state = AH_LEFT;    // 后判断掉落！这是错的！
    end
end

错误原因：

• 题目明确说了优先级：fall > dig > switch direction
• 地面都没了，还管什么碰撞！

正确做法：

LEFT: begin
    if (ground == 1'b0) begin           // 先判断掉落（最高优先级）
        next_state = FALL_LEFT;
    end else if (dig == 1'b1) begin     // 再判断挖掘
        next_state = DIG_LEFT;
    end else if ((bump == 2'b10) || (bump == 2'b11)) begin
        next_state = RIGHT;             // 最后判断方向
    end
end

错误3：计数器逻辑错误

错误表现：

// 计数器看当前状态而不是下一状态
always @(posedge clk) begin
    if (areset) begin
        cycle_count <= 5'd0;
    end else if ((state == FALL_LEFT) || (state == FALL_RIGHT)) begin
        cycle_count <= cycle_count + 1'b1;  // 会延迟一个周期！
    end else begin
        cycle_count <= 5'd0;
    end
end

错误原因：

• 状态在时钟边沿更新
• 看state的话，进入掉落状态的第一个周期不会计数

调试技巧：

• 当你不确定时，画个波形图！
• 把state、next_state、cycle_count都画出来
• 看看计数是不是从进入掉落状态的第一个周期就开始了

错误4：输出逻辑忘记新状态

错误表现：

// 增加了DEAD状态，但aaah输出没更新
assign aaah = ((state == FALL_LEFT) || (state == FALL_RIGHT));
// 忘记了SPLATTER状态也应该aaah=1！

错误原因：

• 每增加一个新状态，都要记得检查所有输出
• SPLATTER状态也是在掉落中，应该叫”aaah”

正确做法：

• 每次修改状态机，都做一个”输出检查清单”
• 对每个输出，逐个状态确认应该是0还是1

错误5：死亡状态没有自环

错误表现：

DEAD: begin
    // 没有指定next_state！
end

错误原因：

• DEAD状态应该永远保持在DEAD
• 如果没有default分支，或者case没写全，会生成锁存器

正确做法：

DEAD: begin
    next_state = DEAD;  // 死亡状态自环
end

---

小结

这组Lemmings题目非常有意思，它展示了如何从零开始，逐步构建一个复杂的状态机。让我们总结一下要点：

1. 状态扩展法：每次增加新功能时，分析需要哪些新状态，把”动作+方向”的每个组合都定义成独立状态

2. 优先级很重要：在状态转移时，要按照重要性排序判断条件——紧急的事件先判断

3. 状态+计数器：当需要计时时，用状态机控制计数器的清零和计数，用计数器的值决定状态转移

4. 输出检查：每次修改状态机，都要检查所有输出在每个状态下的值是否正确

5. 画状态图：在写代码前先画状态转移图，能避免很多错误

作为一名通信IC设计师，笔者想说：状态机是数字电路设计的灵魂，小到一个简单的接口协议，大到一个复杂的处理器控制器，都离不开状态机。多做这类题目，培养良好的状态机设计习惯，对未来的工程设计非常有帮助！