Verilog有限状态机(6)

HDLBits链接

前言

今天我们来学习几道非常经典的状态机题目，涵盖三个重要应用：

  1. HDLC同步帧检测：通信协议中常用的帧边界检测
  2. 序列检测：米利型状态机的经典应用
  3. 串行补码计算：展示如何用状态机做简单的算术运算

这些题目在实际工程中都能找到对应的应用场景，非常值得深入学习！

题库

Fsm hdlc - HDLC同步帧检测

1

2

3

基础知识：HDLC协议简介

HDLC（High-Level Data Link Control）是一种经典的数据链路层协议。在HDLC中，有几个关键概念：

帧标志（Flag）：序列01111110表示一帧的开始或结束，就像包裹上的”此处拆封”标记。

零插入（Zero Insertion）：为了防止数据中意外出现帧标志，发送方会在每5个连续的1后面插入一个0。接收方则需要检测并丢弃这个插入的0。

错误检测：如果出现7个或更多连续的1，说明出错了！

我们的状态机需要识别三种序列：

  • 0111110：丢弃这个0（disc=1）
  • 01111110：帧标志（flag=1）
  • 01111111...：错误（err=1）

官方提供的状态机设计提示：

4

Solution方式1：用状态计数连续的1

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
module top_module(
    input wire clk,
    input wire reset,    // 同步复位
    input wire in,
    output reg disc,     // 丢弃信号：5个1后的0要丢弃
    output reg flag,     // 帧标志信号：检测到01111110
    output reg err       // 错误信号：7个或更多连续的1
);

    // 状态参数定义：用状态表示连续1的个数
    parameter NONE  = 4'd0;  // 0个连续的1
    parameter ONE   = 4'd1;  // 1个连续的1
    parameter TWO   = 4'd2;  // 2个连续的1
    parameter THREE = 4'd3;  // 3个连续的1
    parameter FOUR  = 4'd4;  // 4个连续的1
    parameter FIVE  = 4'd5;  // 5个连续的1
    parameter SIX   = 4'd6;  // 6个连续的1
    parameter ERROR = 4'd7;  // 7个或更多连续的1
    parameter DISC  = 4'd8;  // 丢弃状态
    parameter FLAG  = 4'd9;  // 帧标志状态

    reg [3:0] current_state;
    reg [3:0] next_state;

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (current_state)
            NONE: begin
                next_state = in ? ONE : NONE;
            end
            ONE: begin
                next_state = in ? TWO : NONE;
            end
            TWO: begin
                next_state = in ? THREE : NONE;
            end
            THREE: begin
                next_state = in ? FOUR : NONE;
            end
            FOUR: begin
                next_state = in ? FIVE : NONE;
            end
            FIVE: begin
                next_state = in ? SIX : DISC;  // 5个1后：1→去SIX，0→丢弃
            end
            SIX: begin
                next_state = in ? ERROR : FLAG; // 6个1后：1→错误，0→帧标志
            end
            DISC: begin
                next_state = in ? ONE : NONE;   // 丢弃后重新开始计数
            end
            FLAG: begin
                next_state = in ? ONE : NONE;   // 帧标志后重新开始计数
            end
            ERROR: begin
                next_state = in ? ERROR : NONE;  // 错误状态：遇到0才退出
            end
            default: begin
                next_state = NONE;
            end
        endcase
    end

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

    // 第三段：输出逻辑
    always @(posedge clk) begin
        if (reset) begin
            disc <= 1'd0;
            flag <= 1'd0;
            err  <= 1'd0;
        end else begin
            case (next_state)  // 注意：用next_state！
                DISC: begin
                    disc <= 1'd1;
                    flag <= 1'd0;
                    err  <= 1'd0;
                end
                FLAG: begin
                    disc <= 1'd0;
                    flag <= 1'd1;
                    err  <= 1'd0;
                end
                ERROR: begin
                    disc <= 1'd0;
                    flag <= 1'd0;
                    err  <= 1'd1;
                end
                default: begin
                    disc <= 1'd0;
                    flag <= 1'd0;
                    err  <= 1'd0;
                end
            endcase
        end
    end

endmodule

Solution方式2：状态+计数器（更简洁）

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
module top_module(
    input wire clk,
    input wire reset,    // 同步复位
    input wire in,
    output reg disc,
    output reg flag,
    output reg err
);

    // 状态参数定义：状态更少！
    parameter NONE  = 3'd0;
    parameter DATA  = 3'd1;  // 用这个状态配合计数器
    parameter DISC  = 3'd2;
    parameter FLAG  = 3'd3;
    parameter ERROR = 3'd4;

    reg [2:0] current_state;
    reg [2:0] next_state;
    reg [2:0] counter;  // 计数器：数连续1的个数

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (current_state)
            NONE: begin
                next_state = in ? DATA : NONE;
            end
            DATA: begin
                case (counter)
                    3'd5:  next_state = in ? DATA : DISC;  // 5个1
                    3'd6:  next_state = in ? ERROR : FLAG; // 6个1
                    default:next_state = in ? DATA : NONE; // 其他情况
                endcase
            end
            DISC: begin
                next_state = in ? DATA : NONE;
            end
            FLAG: begin
                next_state = in ? DATA : NONE;
            end
            ERROR: begin
                next_state = in ? ERROR : NONE;
            end
            default: begin
                next_state = NONE;
            end
        endcase
    end

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

    // 第三段：计数器和输出逻辑
    always @(posedge clk) begin
        if (reset) begin
            disc <= 1'd0;
            flag <= 1'd0;
            err  <= 1'd0;
            counter <= 3'd0;
        end else begin
            case (next_state)
                DATA: begin
                    disc <= 1'd0;
                    flag <= 1'd0;
                    err  <= 1'd0;
                    counter <= counter + 1'd1;  // 继续计数
                end
                DISC: begin
                    disc <= 1'd1;
                    flag <= 1'd0;
                    err  <= 1'd0;
                    counter <= 3'd0;  // 计数器清零
                end
                FLAG: begin
                    disc <= 1'd0;
                    flag <= 1'd1;
                    err  <= 1'd0;
                    counter <= 3'd0;
                end
                ERROR: begin
                    disc <= 1'd0;
                    flag <= 1'd0;
                    err  <= 1'd1;
                    counter <= 3'd0;
                end
                default: begin
                    disc <= 1'd0;
                    flag <= 1'd0;
                    err  <= 1'd0;
                    counter <= 3'd0;
                end
            endcase
        end
    end

endmodule

两种方法的对比

  • 方法1：每个状态表示连续1的个数，逻辑直观，但状态较多
  • 方法2：用一个DATA状态配合计数器，状态更少，可扩展性更好（如果要数更多连续的1，只需增加计数器位宽）

米利型状态机 - 序列检测”101”

题目理解

这是一个经典的序列检测题目：

  • 检测输入序列中是否出现”101”
  • 出现时输出z=1，否则z=0
  • 允许交叠检测：比如输入”10101”，在第3位和第5位都要输出1
  • 只用3个状态
  • 异步低电平复位

这是一个米利型（Mealy）状态机，因为输出不仅取决于当前状态，还取决于当前输入！

Solution：

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
module top_module (
    input wire clk,
    input wire aresetn,    // 异步低电平复位
    input wire x,
    output reg z
);

    // 状态参数定义
    parameter S0 = 2'd0;  // 初始状态，或者没找到匹配的
    parameter S1 = 2'd1;  // 找到了一个'1'
    parameter S2 = 2'd2;  // 找到了'10'

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

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (current_state)
            S0: next_state = x ? S1 : S0;  // 看到1去S1，否则留S0
            S1: next_state = x ? S1 : S2;  // 看到0去S2（找到'10'）
            S2: next_state = x ? S1 : S0;  // 关键点！
        endcase
    end

    // 第二段：时序逻辑，状态更新（异步低电平复位）
    always @(posedge clk or negedge aresetn) begin
        if (~aresetn) begin
            current_state <= S0;
        end else begin
            current_state <= next_state;
        end
    end

    // 第三段：输出逻辑（米利型：看当前状态和输入！）
    always @(*) begin
        z = (current_state == S2) ? x : 1'b0;
    end

endmodule

关键设计要点

交叠检测的技巧：在S2状态（已经找到”10”），如果看到1，我们回到S1而不是S0！因为这个1可以作为下一个”101”的第一个1。

米利型输出：输出z不仅看状态，还要看输入。在S2状态时，如果输入是1，说明找到了”101”，输出1！

Q5a: 串行补码计算器（摩尔型）

6

基础知识：补码计算原理

在二进制中，求一个数的补码（负数表示）通常是”取反加1”。但如果是串行输入（从低位到高位），怎么用状态机实现呢？

核心思路：

  • 从低位开始看，在遇到第一个1之前，输出保持不变（0还是0）
  • 遇到第一个1时，输出这个1，然后进入另一个状态
  • 之后的所有位都取反输出

举个例子：输入00110100（从左到右是低位到高位）

  • 前两个0：输出0
  • 遇到第一个1：输出1，进入取反状态
  • 后面的位：1→0，1→0，0→1，1→0，0→1，0→1
  • 结果就是11001100

这就像跑步接力赛，前半段正常跑，看到接力棒（第一个1）后，后半段就反向跑！

Solution（摩尔型状态机）：

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
module top_module (
    input wire clk,
    input wire areset,     // 异步复位
    input wire x,
    output reg z
);

    // 状态参数定义
    parameter S0 = 2'd0;  // 还没遇到第一个1
    parameter S1 = 2'd1;  // 遇到了第一个1，这一位输出1
    parameter S2 = 2'd2;  // 之后的位都取反

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

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (current_state)
            S0: next_state = x ? S1 : S0;  // 遇到第一个1去S1
            S1: next_state = x ? S2 : S1;  // 看完第一个1去S2
            S2: next_state = x ? S2 : S1;  // 保持在S2
        endcase
    end

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

    // 第三段：输出逻辑（摩尔型：只看当前状态）
    assign z = (current_state == S1);

endmodule

Q5b: 串行补码计算器（米利型）

7

题目理解

同样是串行补码计算，但这次用米利型状态机实现。米利型的特点是输出取决于当前状态和当前输入，所以通常状态数更少！

Solution（米利型状态机）：

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
module top_module (
    input wire clk,
    input wire areset,     // 异步复位
    input wire x,
    output reg z
);

    // 状态参数定义：只用2个状态！
    parameter S0 = 1'b0;  // 还没遇到第一个1
    parameter S1 = 1'b1;  // 已经遇到第一个1了

    reg current_state;
    reg next_state;

    // 第一段：组合逻辑，状态转移
    always @(*) begin
        case (current_state)
            S0: next_state = x ? S1 : S0;  // 遇到第一个1去S1
            S1: next_state = S1;             // 永远留在S1
        endcase
    end

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

    // 第三段：输出逻辑（米利型：看状态和输入！）
    assign z = ((current_state == S0) && x) || ((current_state == S1) && ~x);

endmodule

摩尔型 vs 米利型对比

特性 摩尔型（Moore） 米利型（Mealy）
输出取决于 仅当前状态 当前状态 + 当前输入
状态数 通常较多 通常较少
输出时序 通常晚一个周期 通常提前一个周期
设计复杂度 较简单 稍复杂

入门者避坑指南

在做这几道题时，初学者最容易犯以下错误：

错误1：米利型输出只看状态，忘了输入

错误表现：

1
2
// 米利型却写成摩尔型
assign z = (current_state == S2);  // 没看输入x！

错误原因：

  • 题目明确说了是米利型状态机
  • 米利型的输出必须看当前状态和当前输入

正确做法：

1
2
// 米利型：状态 + 输入
assign z = (current_state == S2) && x;

错误2：序列检测不支持交叠

错误表现：

1
2
// 找到101后直接回S0，不支持交叠
S2: next_state = x ? S0 : S0;  // 错了！

错误原因：

  • 没有理解”交叠检测”的意思
  • 输入”10101”应该在第3位和第5位都输出1

正确做法：

1
2
// 交叠检测：看到1回到S1，作为下一个序列的开始
S2: next_state = x ? S1 : S0;

错误3：异步复位信号名和电平搞反

错误表现：

1
2
3
4
5
6
// 题目说aresetn是低电平有效，却写成posedge
always @(posedge clk or posedge aresetn) begin  // 错了！
    if (aresetn) begin
        current_state <= S0;
    end
end

错误原因：

  • 信号名后缀_n通常表示低电平有效（negative）
  • 低电平有效复位应该用negedge

正确做法：

1
2
3
4
5
6
// 低电平有效复位的正确写法
always @(posedge clk or negedge aresetn) begin
    if (~aresetn) begin
        current_state <= S0;
    end
end

错误4：HDLC状态机中忘记错误状态的自环

错误表现：

1
2
3
ERROR: begin
    // 没有写next_state！
end

错误原因：

  • 错误状态应该保持在错误状态，直到看到0为止
  • 或者根据题目要求，有些设计是一直保持错误

正确做法：

1
2
3
ERROR: begin
    next_state = in ? ERROR : NONE;  // 看到0才退出错误
end

错误5：输出逻辑用state而不是next_state

错误表现：

1
2
3
4
5
6
7
8
9
10
// 输出用state判断，会晚一个周期
always @(posedge clk) begin
    if (reset) begin
        disc <= 1'd0;
    end else begin
        case (state)
            DISC: disc <= 1'd1;  // 晚了一个周期！
        endcase
    end
end

正确做法：

1
2
3
4
5
6
7
8
9
10
// 用next_state判断，刚好在正确的周期输出
always @(posedge clk) begin
    if (reset) begin
        disc <= 1'd0;
    end else begin
        case (next_state)
            DISC: disc <= 1'd1;
        endcase
    end
end

小结

今天我们学习了四道非常经典的状态机题目，涵盖了通信协议、序列检测和数学运算三个应用场景：

  1. HDLC帧检测：展示了如何用状态机做协议解析，有两种方法：

    • 方法1：用状态表示连续1的个数，直观但状态多
    • 方法2：状态+计数器，简洁且可扩展性好

  2. 序列检测”101”：米利型状态机的经典应用，重点是理解交叠检测的技巧

  3. 串行补码计算：分别用摩尔型和米利型实现，对比了两种状态机的区别

作为一名通信IC设计师，笔者想说：这几道题目都是经典中的经典！HDLC帧检测在通信协议中随处可见，序列检测是很多接口的基础，补码计算更是CPU运算单元的一部分。把这几道题吃透，你对状态机的理解会上一个大台阶！