[Verilog]FSM有限状态机

FSM有限状态机

什么是状态机

  • 状态机由状态寄存器和组合逻辑电路构成,能够根据控制信号按照预先设定的状态进行状态转移,是协调相关信号动作、完成特定操作的控制中心。有限状态机简写为FSM(Finite State Machine),主要分为2大类:Moore状态机和Mealy状态机。

Moore型

  • 若输出只和状态有关而与输入无关,则称为Moore状态机

Mealy型状态机

  • 若输出不仅和状态有关而且和输入有关系,则称为Mealy状态机。

什么是好的状态机

  • 好的状态机的标准很多,最重要的几个方面如下:
  1. 状态机要安全,是指FSM不会进入死循环,特别是不会进入非预知的状态,而且由于某些扰动进入非设计状态,也能很快的恢复到正常的状态循环中来。这里面有两层含义:其一要求该FSM的综合实现结果无毛刺等异常扰动;其二要求FSM要完备,即使受到异常扰动进入非设计状态,也能很快恢复到正常状态。
  2. 状态机的设计要满足设计的面积和速度的要求。
  3. 状态机的设计要清晰易懂、易维护。

状态机分类

  • 状态机依照写法的不同,状态机的描述方式可分为:一段式、二段式、三段式。即该状态机,是由一个、两个、还是三个always语句块来进行描述。
  • 1101状态检测器为例,进行三种不同写法的代码讲解。所谓1101状态检测器,即串行输入数据序列,当状态机检测到输入数据中有1101时,会在下一个时钟周期,拉高一个时钟周期的输出。
  • 1101状态检测器的状态转移图如下所示:

一段式状态机

  • 所谓一段式状态机,即只使用一个always块进行状态机的描述。该always块既描述状态转移,又描述状态的输入和输出。
  • 一段式写法简单,但是不利于维护,状态扩展麻烦,状态复杂时易出错,不推荐使用。
  • 一段式状态机代码如下:
module FSM_SequDetection_1(
    input clk,
    input rst_n,
    input data_in,
    output reg data_valid
);
//定义状态,这里采用的独热码(One-Hot),FPGA中推荐用独热码和格雷码(Gray)
//状态较少时(4-24个状态)用独热码效果好,状态多时格雷码(状态数大于24)效果好
// parameter define
parameter IDLE = 5'b00001; 
parameter S1 = 5'b00010;
parameter S2 = 5'b00100;
parameter S3 = 5'b01000;
parameter S4 = 5'b10000;

//reg define
reg [4:0] state; //状态

//一段式FSM,既描述状态转移,又描述状态的输入和输出。
[email protected](posedge clk or negedge rst_n)begin
    if(~rst_n)begin
        state <= IDLE;
        data_valid <= 1'b0;
    end
    else begin
        case(state)
            IDLE: begin
                data_valid <= 1'b0;
                if(data_in == 1'b1) begin  state <= S1; end
                else begin  state <= IDLE; end
            end
            S1: begin
                data_valid <= 1'b0;
                if(data_in == 1'b1) begin  state <= S2; end
                else begin  state <= IDLE; end
            end
            S2: begin
                data_valid <= 1'b0;
                if(data_in == 1'b0) begin  state <= S3; end
                else begin  state <= S2; end
            end
            S3: begin
                data_valid <= 1'b0;
                if(data_in == 1'b1) begin  state <= S4; end
                else begin  state <= IDLE; end
            end
            S4: begin
                data_valid <= 1'b1;
                if(data_in == 1'b1) begin  state <= S2; end
                else begin  state <= IDLE; end
            end
            default:begin
                data_valid <= 1'b0;
                state <= IDLE;
            end
        endcase
    end
end
endmodule
  • 综合后的RTL图:

二段式状态机

  • 两段式状态机,即用到了两个 always 模块来描述状态机,两个always块分别对组合逻辑部分和时序逻辑部分进行了拆分。时序逻辑里进行当前状态和下一状态的切换,组合逻辑实现各个输入、输出以及状态判断。
  • 这种写法不仅便于阅读、理解、维护,而且利于综合器优化代码,利于用户添加合适的时序约束条件,利于布局布线器实现设计。但由于两段式状态机的当前状态输出使用的是组合逻辑,可能出现竞争冒险,产生毛刺,而且不利于约束,不利于综合器和布局布线器实现高性能的设计。
  • 两段式状态机代码如下:
module FSM_SequDetection_2(
    input clk,
    input rst_n,
    input data_in,
    output reg data_valid
);
// parameter define
parameter IDLE = 5'b00001; 
parameter S1 = 5'b00010;
parameter S2 = 5'b00100;
parameter S3 = 5'b01000;
parameter S4 = 5'b10000;

//reg define
reg [4:0] current_state; //当前状态
reg [4:0] next_state; //下一状态

//一个 always 模块采用时序描述状态转移
[email protected](posedge clk or negedge rst_n)begin
    if(~rst_n)begin
        current_state <= IDLE;
    end
    else begin 
        current_state <= next_state;
    end
end

//一个always模块采用组合逻辑实现各个输入、输出以及状态判断。
[email protected](*)begin
    if(~rst_n)begin
        next_state = IDLE;
        data_valid = 1'b0;
    end
    else begin
        case(current_state)
            IDLE: begin
                data_valid = 1'b0;
                if(data_in == 1'b1) begin  next_state = S1; end
                else begin  next_state = IDLE; end
            end
            S1: begin
                data_valid = 1'b0;
                if(data_in == 1'b1) begin  next_state = S2; end
                else begin  next_state = IDLE; end
            end
            S2: begin
                data_valid = 1'b0;
                if(data_in == 1'b0) begin  next_state = S3; end
                else begin  next_state = S2; end
            end
            S3: begin
                data_valid = 1'b0;
                if(data_in == 1'b1) begin  next_state = S4; end
                else begin  next_state = IDLE; end
            end
            S4: begin
                data_valid = 1'b1;
                if(data_in == 1'b1) begin  next_state = S2; end
                else begin  next_state = IDLE; end
            end
            default:begin
                data_valid = 1'b0;
                next_state = IDLE;
            end
        endcase
    end
end
endmodule
  • 综合后的RTL图:
  • 可以看出,在最后一级的输出端上,相较于一段式状态机,少了一个reg寄存器进行打拍,可能会存在竞争与险相。

三段式状态机

  • 两段式状态机,即用到了三个 always 模块来描述状态机。一个时序逻辑采用同步时序的方式描述状态转移,一个采用组合逻辑的方式判断状态转移条件、描述状态转移规律,第三个模块使用同步时序的方式描述每个状态的输出。
  • 实际上,三段式状态机可以理解成,将两段式状态机的输出,进行打拍进行时钟同步,从而解决两段式状态机输出存在毛刺的问题。
  • 三段式状态机的代码容易维护,时序逻辑的输出解决了两段式组合逻辑的毛刺问题,但是从资源消耗的角度上看,三段式的资源消耗多一些。
  • 三段式状态机代码如下:
module FSM_SequDetection_3(
    input clk,
    input rst_n,
    input data_in,
    output reg data_valid
);
// parameter define
parameter IDLE = 5'b00001; 
parameter S1 = 5'b00010;
parameter S2 = 5'b00100;
parameter S3 = 5'b01000;
parameter S4 = 5'b10000;

//reg define
reg [4:0] current_state; //当前状态
reg [4:0] next_state; //下一状态

//一个 always 模块采用时序描述状态转移
[email protected](posedge clk or negedge rst_n)begin
    if(~rst_n)begin
        current_state <= IDLE;
    end
    else begin 
        current_state <= next_state;
    end
end

//一个always模块采用组合逻辑实现各个输入及状态判断。
[email protected](*)begin
    if(~rst_n)begin
        next_state = IDLE;
    end
    else begin
        case(current_state)
            IDLE: begin
                if(data_in == 1'b1) begin  next_state = S1; end
                else begin  next_state = IDLE; end
            end
            S1: begin
                if(data_in == 1'b1) begin  next_state = S2; end
                else begin  next_state = IDLE; end
            end
            S2: begin
                if(data_in == 1'b0) begin  next_state = S3; end
                else begin  next_state = S2; end
            end
            S3: begin
                if(data_in == 1'b1) begin  next_state = S4; end
                else begin  next_state = IDLE; end
            end
            S4: begin
                if(data_in == 1'b1) begin  next_state = S2; end
                else begin  next_state = IDLE; end
            end
            default:begin
                next_state = IDLE;
            end
        endcase
    end
end

//一个always模块采用时序逻辑描述每个状态的输出
[email protected](posedge clk or negedge rst_n)begin
    if(~rst_n) begin
        data_valid = 1'b0;
    end
    else begin
        case(next_state)
            S4: data_valid = 1'b1;
            default: data_valid = 1'b0;
        endcase
    end
end
endmodule
  • 综合后的RTL图:

仿真文件

  • 针对1101状态检测器,编写testbench,串行输入的测试序列为“11101101011010”

testbench

`timescale 1 ns / 100 ps
module tb_FSM_SequDetection();
parameter DATA = 14'b 11101101011010;
reg clk;
reg rst_n;
reg data_in;
wire data_valid;

//时钟信号
initial begin
    clk = 0;
    forever  #10 clk =~clk;
end
//复位信号
initial begin
    rst_n = 0;
    #10
    rst_n = 1;
end
//data_in
integer i;
[email protected](posedge clk or negedge rst_n)begin
    if(~rst_n)begin
        i <= 4'd13;
        data_in <= 1'b0;
    end
    else begin
        if (i>0)begin
            data_in <= DATA[i] ;
            i=i-1'b1;
        end
        else begin
            i <= i;
            data_in <= 1'b0; 
        end
    end
end
// 元件例化
FSM_SequDetection_2  u_FSM_SequDetection_1(
    .clk (clk),
    .rst_n (rst_n),
    .data_in (data_in),
    .data_valid (data_valid)
);
endmodule

仿真波形