Sequence Detector 101

Hi, I plan to do a series of sequence detectors design. A sequence detector is a sequential circuit that outputs 1 when a particular pattern of bits sequentially arrives at its data input. A sequence detector’s functions are achieved by using a finite state machine. For this post, I’ll share my finite state machine diagrams and SystemVerilog code for my design for Mealy and Moore state machines to detect the sequence 101, covering both overlapping and non-overlapping scenarios.

A Mealy Machine is an FSM whose output depends on the present state as well as the present input. Moore machine is an FSM whose outputs depend on only the present state. Generally speaking, Mealy machines tend to have fewer states, and Moore machines are safer to use.

The difference between overlapping and non-overlapping types of sequence detector is whether the final bits of one sequence can be counted as the start of another sequence. For the overlapping sequence detector, the final bits can be used as the start of another new sequence.

1) Moore Machine (Non-Overlapping)

I usually use enum typedef for my finite state machine design, because it is easier to code and debug.

module sd101_moore(input bit clk,
                   input logic reset,
                   input logic din,
                   output logic dout);

  typedef enum logic [1:0] {S0, S1, S2, S3} state_t;
  state_t state;

  always @(posedge clk or posedge reset) begin
    if(reset) begin
      dout <= 1'b0;
      state <= S0;
    end
    else begin
      case(state)
        S0: begin
          dout <=1'b0;
          if(din)
            state <= S1;
        end
        S1: begin
          dout <= 1'b0;
          if(~din)
            state <= S2;
        end
        S2: begin
          dout <= 1'b0;
          if(din)
            state <= S3;
          else
            state <= S0;
        end
        S3: begin
          dout <= 1'b1;
          if(din)
            state <= S1;
          else
            state <= S0;
        end
      endcase
    end
  end


endmodule

2) Mealy Machine (Non-Overlapping)

There are only three states, one state fewer than the Moore machine.

module sd101_mealy(input bit clk,
                   input logic reset,
                   input logic din,
                   output logic dout);

  typedef enum logic [1:0] {S0, S1, S2} state_t;
  state_t state;

  always @(posedge clk or posedge reset) begin
    if(reset) begin
      dout <= 1'b0;
      state <= S0;
    end
    else begin
      case(state)
        S0: begin
          if(din) begin
            state <= S1;
            dout <=1'b0;
          end
          else
            dout <=1'b0;
        end
        S1: begin
          if(~din) begin
            state <= S2;
            dout <=1'b0;
          end
        end
        S2: begin
          if(din) begin
            state <= S0;
            dout <=1'b1;
          end
          else begin
            state <= S0;
            dout <=1'b0;
          end
        end
      endcase
    end
  end

endmodule

3) Moore Machine (Overlapping)
This is quite similar to the non-overlapping design. The only difference is that after S3, if the incoming bit is 0, you will directly go to S2.

module sd101_moore_over(input bit clk,
                   input logic reset,
                   input logic din,
                   output logic dout);

  typedef enum logic [1:0] {S0, S1, S2, S3} state_t;
  state_t state;

  always @(posedge clk or posedge reset) begin
    if(reset) begin
      dout <= 1'b0;
      state <= S0;
    end
    else begin
      case(state)
        S0: begin
          dout <=1'b0;
          if(din)
            state <= S1;
        end
        S1: begin
          dout <= 1'b0;
          if(~din)
            state <= S2;
        end
        S2: begin
          dout <= 1'b0;
          if(din)
            state <= S3;
          else
            state <= S0;
        end
        S3: begin
          dout <= 1'b1;
          if(din)
            state <= S1;
          else
            state <= S2;
        end
      endcase
    end
  end


endmodule

4) Mealy Machine (Overlapping)

module sd101_mealy(input bit clk,
                   input logic reset,
                   input logic din,
                   output logic dout);

  typedef enum logic [1:0] {S0, S1, S2} state_t;
  state_t state;

  always @(posedge clk or posedge reset) begin
    if(reset) begin
      dout <= 1'b0;
      state <= S0;
    end
    else begin
      case(state)
        S0: begin
          if(din) begin
            state <= S1;
            dout <=1'b0;
          end
          else
            dout <=1'b0;
        end
        S1: begin
          if(~din) begin
            state <= S2;
            dout <=1'b0;
          end
          else
            dout <=1'b0;
        end
        S2: begin
          if(din) begin
            state <= S1;
            dout <=1'b1;
          end
          else begin
            state <= S0;
            dout <=1'b0;
          end
        end
      endcase
    end
  end

endmodule

I did some simple testbench checking, and all of them work.

That’s all I’ve got for sequence detector 101. Leave me a comment if you have any questions or I made some silly mistakes.

5 thoughts on “Sequence Detector 101

  1. It would be so awesome if you could upload a video testing it, to see how to enter the values of all the inputs and also to see how to get the ‘1’ after entering the ‘101’!

    I really appreciate it becaus I’m trying to do an essay like this at the moment 🙂

Leave a Reply to Amir Amini Cancel reply

Your email address will not be published.