Verilog Pattern Detector

A pattern detector is a finite state machine that monitors a serial bit stream and raises its output whenever a specific multi-bit pattern has been received. The Verilog Sequence Detector article built a detector for a short pattern. This article applies the same method to a longer pattern, 110101, where choosing the right state after a mismatch becomes more important.

12 min read | Intermediate Level

What You'll Learn

• Derive every state transition of a pattern detector with the longest-suffix rule
• Write an overlapping 110101 detector as a Moore FSM in Verilog
• Compare an FSM detector with a shift register and comparator
• Choose test stimulus that actually exposes transition bugs

Deriving the Transitions

The detector has one state for each prefix of the pattern that has been matched: IDLE (nothing), S1, S11, S110, S1101, S11010 and S110101 (full match). When the next bit continues the pattern, the FSM moves forward one state. When it does not, the FSM moves to the state for the longest ending of the received bits that is also a start of the pattern. This is the longest-suffix rule.

The two transitions in bold are easy to get wrong. In S1101, a 1 breaks the pattern, but the last two bits received are "11", which is the start of a new "110101", so the FSM goes to S11, not IDLE. In S110101, a 1 again leaves "11" at the end of the stream. Taking that transition makes this an overlapping detector: a pattern that begins with the last bit of the previous match is still detected.

Design

module det_110101 ( input clk,
                  	 input rstn,
                  	 input in,
                  	 output out );

  // 7 states need a 3-bit state register
  localparam IDLE 	= 0,
  			S1 		= 1,
  			S11 	= 2,
  			S110 	= 3,
  			S1101 	= 4,
  			S11010 	= 5,
  			S110101 = 6;

  reg [2:0] cur_state, next_state;

  // Moore output: high only in the state where the full pattern has been received
  assign out = cur_state == S110101 ? 1 : 0;

  // State register
  always @ (posedge clk) begin
    if (!rstn)
      	cur_state <= IDLE;
     else
     	cur_state <= next_state;
  end

  // Next-state logic, following the transition table
  always @ (cur_state or in) begin
    case (cur_state)
      IDLE : begin
        if (in) next_state = S1;
        else 	next_state = IDLE;
      end

      S1: begin
        if (in) next_state = S11;
        else 	next_state = IDLE;
      end

      S11: begin
        if (!in) next_state = S110;
        else 	next_state = S11;       // "111": stay, still have "11"
      end

      S110 : begin
        if (in) next_state = S1101;
        else 	next_state = IDLE;
      end

      S1101 : begin
        if (!in) next_state = S11010;
        else 	next_state = S11;       // "11011": keep the trailing "11"
      end

      S11010: begin
        if (in) next_state = S110101;
        else 	next_state = IDLE;
      end

      S110101: begin
        if (in) next_state = S11;       // "1101011": keep the trailing "11" (overlap)
        else 	next_state = IDLE;
      end

      default : next_state = IDLE;      // Code 7 is unused
    endcase
  end
endmodule

Synthesis result: The tool builds a 3-bit state register with synchronous reset, next-state logic for the 14 transitions, and a decoder for state 6 (3'b110) that drives out. Synthesis tools usually recognize this as an FSM and may re-encode it, for example as one-hot with 7 flip-flops, if that meets timing better.

Testbench

The testbench holds reset for five clock edges, then drives the pattern twice, back to back. A $strobe at each rising edge prints in and out after all updates for that edge.

module tb;
  reg clk, in, rstn;
  wire out;
  integer l_dly;

  always #10 clk = ~clk;

  det_110101 u0 ( .clk(clk), .rstn(rstn), .in(in), .out(out) );

  // Print the values at the end of each rising-edge time step
  always @ (posedge clk)
    $strobe ("T=%0t in=%0b out=%0b", $time, in, out);

  initial begin
  	clk <= 0;
    rstn <= 0;
    in <= 0;

    repeat (5) @ (posedge clk);
    rstn <= 1;

    @(posedge clk) in <= 1;
    @(posedge clk) in <= 1;
    @(posedge clk) in <= 0;
    @(posedge clk) in <= 1;
    @(posedge clk) in <= 0;
    @(posedge clk) in <= 1;   // First 110101 complete
    @(posedge clk) in <= 1;
    @(posedge clk) in <= 1;
    @(posedge clk) in <= 0;
    @(posedge clk) in <= 1;
    @(posedge clk) in <= 0;
    @(posedge clk) in <= 1;   // Second 110101 complete

    #100 $finish;
  end
endmodule

ncsim> run
T=10 in=0 out=0
T=30 in=0 out=0
T=50 in=0 out=0
T=70 in=0 out=0
T=90 in=0 out=0
T=110 in=1 out=0
T=130 in=1 out=0
T=150 in=0 out=0
T=170 in=1 out=0
T=190 in=0 out=0
T=210 in=1 out=0
T=230 in=1 out=1
T=250 in=1 out=0
T=270 in=0 out=0
T=290 in=1 out=0
T=310 in=0 out=0
T=330 in=1 out=0
T=350 in=1 out=1
T=370 in=1 out=0
T=390 in=1 out=0
T=410 in=1 out=0
Simulation complete via $finish(1) at time 430 NS + 0

The first pattern is driven from 110 to 210 ns, and out is 1 at 230 ns, one clock after the last bit, as expected for a Moore output. The second pattern is driven from 230 to 330 ns and detected at 350 ns. Each detection lasts exactly one clock cycle.

reg [5:0] sh;
always @(posedge clk)
  if (!rstn) sh <= 6'b0;
  else       sh <= {sh[4:0], in};    // Last 6 bits, newest at bit 0

assign out = (sh == 6'b110101);

module tb_check;
  reg clk = 0, rstn = 0, in = 0;
  wire out;
  reg [5:0] sh;                 // Reference model: last 6 sampled bits
  integer i, errors = 0;

  always #10 clk = ~clk;

  det_110101 u0 ( .clk(clk), .rstn(rstn), .in(in), .out(out) );

  // Reference model, clocked exactly like the design
  always @(posedge clk)
    if (!rstn) sh <= 6'b0;
    else       sh <= {sh[4:0], in};

  // Compare on the falling edge, away from the rising edge updates
  always @(negedge clk)
    if (rstn && (out !== (sh == 6'b110101))) begin
      $display("[%0t] ERROR: out=%b expected=%b", $time, out, (sh == 6'b110101));
      errors = errors + 1;
    end

  initial begin
    repeat (3) @(posedge clk);
    rstn <= 1;

    for (i = 0; i < 500; i = i + 1)
      @(posedge clk) in <= $random;   // Bit 0 of a random number

    @(posedge clk);
    if (errors == 0) $display("PASS: 500 random bits, no mismatches");
    else             $display("FAIL: %0d mismatches", errors);
    $finish;
  end
endmodule