时序逻辑电路——序列检测器

一、序列检测

  序列检测器指的就是将一个指定的序列（以‘10010’为例）从数字码流中识别出来，是一个经典的数字电路实例，也是数字IC和FPGA笔试面试中常考的知识点。写法总共可分为三种：
写法：

• 移位寄存器
• Moore状态机
• Mealy状态机

  常考的题目类型有以下特点，可能取其一类型进行拷打，也可能多个类型进行结合。比如说输入非连续且并行输入，最终需要提取出某个非重叠序列。
题目类型：

• 输入连续/非连续，非连续输入会有使能信号valid
• 重叠/非重叠序列检测
• 含无关项/不含无关项，比如说检测输入信号a是否满足011XXX110序列（长度为9位数据，前三位是011，后三位是110，中间三位不做要求）
• 串行输入/并行输入，比如说并行输入2bit数据

二、牛客真题

1. 输入序列连续的序列检测（输入连续、重叠、不含无关项、串行输入）

  以牛客上比较简单的题目VL25 输入序列连续的序列检测，介绍三种写法。

写法一：移位寄存器

module sequence_detect(
	input clk,
	input rst_n,
	input a,
	output reg match
	);

    reg [7:0] shift_reg;

    always @(posedge clk or negedge rst_n)begin
        if(~rst_n)begin
            shift_reg <= 'd0;
        end
        else begin
            shift_reg <= {shift_reg[6:0], a};
        end
    end
    
    always @(posedge clk or negedge rst_n)begin
        if(~rst_n)begin
            match <= 1'b0;
        end
        else if(shift_reg==8'b0111_0001)begin
            match <= 1'b1;
        end
        else begin
            match <= 1'b0;
        end
    end
endmodule

写法二：Moore状态机

module sequence_detect(
	input clk,
	input rst_n,
	input a,
	output reg match
	);
    localparam idle  = 'd0;
    localparam s0    = 'd1;
    localparam s1    = 'd2;
    localparam s2    = 'd3;
    localparam s3    = 'd4;
    localparam s4    = 'd5;
    localparam s5    = 'd6;
    localparam s6    = 'd7;
    localparam detect= 'd8;
    reg [3:0] curr_state;
    reg [3:0] next_state;

    always @(posedge clk or negedge rst_n)begin
        if(~rst_n)
            curr_state <= idle;
        else 
            curr_state <= next_state;
    end

    always @(*)begin
        case(curr_state)
        idle    : next_state = (a==1'b0)?s0     :idle   ;
        s0      : next_state = (a==1'b1)?s1     :s0     ;
        s1      : next_state = (a==1'b1)?s2     :s0     ;
        s2      : next_state = (a==1'b1)?s3     :s0     ;
        s3      : next_state = (a==1'b0)?s4     :idle   ;
        s4      : next_state = (a==1'b0)?s5     :s1     ;
        s5      : next_state = (a==1'b0)?s6     :s1     ;
        s6      : next_state = (a==1'b1)?detect :s0     ;
        detect  : next_state = (a==1'b1)?s3     :s0     ;
        default : next_state = idle;
        endcase
    end

    always @(posedge clk or negedge rst_n)begin
        if(~rst_n)
            match <= 1'b0;
        else if(curr_state==detect)
            match <= 1'b1;
        else
            match <= 1'b0;
    end

endmodule

写法三：Mealy状态机

  注意:牛客上仿真需要用的是Moore状态机,因此Mealy状态机仿真结果的match会提前一个周期到来.

module sequence_detect(
	input clk,
	input rst_n,
	input a,
	output reg match
	);
    localparam idle  = 'd0;
    localparam s0    = 'd1;
    localparam s1    = 'd2;
    localparam s2    = 'd3;
    localparam s3    = 'd4;
    localparam s4    = 'd5;
    localparam s5    = 'd6;
    localparam s6    = 'd7;
    reg [2:0] curr_state;
    reg [2:0] next_state;

    always @(posedge clk or negedge rst_n)begin
        if(~rst_n)
            curr_state <= idle;
        else 
            curr_state <= next_state;
    end

    always @(*)begin
        case(curr_state)
        idle    : next_state = (a==1'b0)?s0     :idle   ;
        s0      : next_state = (a==1'b1)?s1     :s0     ;
        s1      : next_state = (a==1'b1)?s2     :s0     ;
        s2      : next_state = (a==1'b1)?s3     :s0     ;
        s3      : next_state = (a==1'b0)?s4     :idle   ;
        s4      : next_state = (a==1'b0)?s5     :s1     ;
        s5      : next_state = (a==1'b0)?s6     :s1     ;
        s6      : next_state = (a==1'b1)?s1     :s0     ;
        default : next_state = idle;
        endcase
    end

    always @(posedge clk or negedge rst_n)begin
        if(~rst_n)
            match <= 1'b0;
        else if(curr_state==s6 && a==1'b1)
            match <= 1'b1;
        else
            match <= 1'b0;
    end

endmodule