Sequence detector for 1011

How it works, edge by edge

At the start rst_n is low, and the reset is asynchronous: the register is IDLE at once, with no clock edge needed. The reset is released at tick 2, between edges, so nothing moves until the first rising edge.

At edge 0 sig_in is 1, so the machine takes the arrow from IDLE to S1. That arrow stays heavy until the next edge: it is the transition that fired. The state row of the waveform prints the state's name, and the digits it stands for are the encoding, three bits counting states in the order the code declares them.

At edges 1 and 2 the bits are 0 and 1, and the machine reaches S10 and then S101. At edge 3 the fourth bit, a 1, takes it to S1011, and found rises with it. Look at when: not while the fourth bit is on sig_in, but at the edge that samples it. A Moore output waits for the state.

Overlap plays 1011011. After the first match the next bit is 0, and the machine goes to S10, not to IDLE: the 1 at the end of 1011 and the 0 after it are the start of the next 1011. Three edges later it is found again, starting on the last bit of the first.

No reset never asserts rst_n. The register holds no known value, so every state is drawn dashed — the register could hold any of their codes, or one of the three that name none — and the state row is hatched. found is X too, because one of those states is S1011. While sig_in stays 1 nothing changes: a 1 leads to S1, S101 or S1011 depending on where the machine was, and their codes, 001, 011 and 100, differ in every bit, so the register stays X. Press sig_in once, to 0, and run two edges: every state goes to IDLE on two 0s, and the machine finds its way out of X without a reset. 00 is the shortest synchronizing sequence for this machine, and its only two-bit one: whatever the register starts in, S1011 or a code that names no state, those two bits leave it in IDLE. That says something about this machine, not about resets.

The code

// Detects the bit sequence 1011 on sig_in, with overlap: 1011011 is found twice.
//
// Reset style for this module: asynchronous, active low. One style per page,
// stated up front, so nothing on the page has to be read twice.
module sequence_detector (
    input  logic clk,
    input  logic rst_n,
    input  logic sig_in,
    output logic found
);

  typedef enum logic [2:0] {
    IDLE  = 3'd0,
    S1    = 3'd1,
    S10   = 3'd2,
    S101  = 3'd3,
    S1011 = 3'd4
  } state_t;

  state_t state, next;

  // The state register: the only flip-flops in the module.
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      state <= IDLE;
    end else begin
      state <= next;
    end
  end

  // Next state. The default assignment holds the state when no branch fires,
  // so no arm can leave a latch behind.
  always_comb begin
    next = state;
    unique case (state)
      IDLE: begin
        if (sig_in) next = S1;
        else if (!sig_in) next = IDLE;
      end
      S1: begin
        if (!sig_in) next = S10;
        else if (sig_in) next = S1;
      end
      S10: begin
        if (sig_in) next = S101;
        else if (!sig_in) next = IDLE;
      end
      S101: begin
        if (sig_in) next = S1011;
        else if (!sig_in) next = S10;
      end
      S1011: begin
        if (!sig_in) next = S10;
        else if (sig_in) next = S1;
      end
      default: next = IDLE;
    endcase
  end

  // Moore output: a function of the state alone.
  always_comb begin
    found = 1'b0;
    unique case (state)
      S1011:   found = 1'b1;
      default: found = 1'b0;
    endcase
  end

endmodule

The code and the drawing are one thing. The typedef enum lists the states, the always_ff block is the only register the machine has, each arm of the first case is a state and each if or else if line is one arrow. Point at a state and its arm lights; point at an arrow and its line does; the reset marker lights the register. The FSM viewer draws a state machine of your own from its code, linked the same way.

The next-state block opens with next = state;, so a state whose conditions are all false keeps its state rather than leaving a latch behind. Here every state draws both of its arrows, so that default never decides anything; it is there so that no arm can forget. The output block is separate and reads the state alone, which is what makes found a Moore output.

Synthesis result

Yosys's generic synthesis turns sequence_detector.sv into 17 cells, 3 of them flip-flops. The cells are Yosys's own gate library, not an FPGA's or a standard-cell library's: the count measures the logic, not the area of any chip.

The code gives state a 3-bit encoding, and these numbers keep it. Left to its fsm pass, Yosys re-encodes it one-hot: 5 flip-flops, 14 cells in all.

Lint by Verilator 5.052, the testbench by Icarus Verilog 13.0, synthesis by Yosys 0.66.

Icarus replayed two of this page's three scenarios on this code, and all 470 values the waveform draws for them match. No reset is left out: it starts from an unknown register, which an RTL simulation reads more optimistically than this engine.

Pitfalls

Forgetting the overlap. An arrow from S1011 back to IDLE on 0 looks tidier and finds 1011011 only once. Every arrow out of a partial match has to go to the longest suffix of what has been seen that is still a prefix of the pattern. For another pattern, the sequence detector generator builds the machine by this rule, overlapping or not, Moore or Mealy, with its code.

Expecting found a cycle early. A Mealy version, with found on the arrow from S101 on 1, would raise it while the fourth bit is still arriving, a clock period sooner — and combinationally from sig_in, so any glitch on the input reaches the output.

No reset. The X is this figure's answer, and an RTL simulation gives another. Run the same code with rst_n never asserted and the X state matches no case item, so the default: arm is taken: next is IDLE and found is 0 from time 0, and the register is X until the first edge and IDLE after it. The simulation looks healthy. On an ASIC the register powers up in any code, the three unused ones included, and in S1011 it reports found for a cycle before a single bit has been seen. On most FPGAs, configuration loads each flip-flop's initial value, 0 unless the code sets one, so this machine starts in IDLE; but that value is loaded once, at configuration, and it is not a reset the design can assert. This X-optimism is why a missing reset survives RTL simulation.