always_ff
Search

Sequence detector generator: Moore and Mealy FSMs in SystemVerilog

Write a bit pattern and get the state machine that detects it, Moore or Mealy, overlapping or not, as a live state diagram and its SystemVerilog.

Limit
6 bits
Published
Authorship
Drafted with AI assistance, reviewed by İsmail

Read this page in Turkish

1 to 6 bits, the first to arrive first.

Overlap
Output
Processes
Encoding

5 states, 10 transitions. Moore: found is high in S1011.

1001line 4210100line 531line 54rst_nIDLES1S10lines 44–47S101S1011found=1

Run plays this scenario from the start; driving an input continues from here.

A state machine that runs: a state diagram and its waveform on one time axis. Inputs: rst_n, sig_in. Outputs: found. clk runs at 8 ticks a period. It has 5 states, IDLE, S1, S10, S101 and S1011, and starts in IDLE on reset; 10 transitions. The waveform shows clk, rst_n, sig_in, state, found.

Figure 1. Press Run. sig_in carries 1011, one bit a clock period, and the lit state walks it to S1011.

sequence_detector_1011.sv
// sequence_detector_1011: generated from a state diagram on alwaysff.com.
// Detects 1011 on sig_in, overlapping: 1011011 holds it twice.
// Moore: found is high for the clock period after the last bit.
// Reset style: asynchronous, active low.
module sequence_detector_1011 (
    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: ;
    endcase
  end

endmodule

How to read the result

Each state is how much of the pattern has arrived. IDLE has seen none of it; S1, S10 and S101 have seen its first one, two and three bits; a Moore machine's last state, S1011 for the pattern 1011, has seen all of it and is the one state where found is high. Two arrows leave every state, one for each value of sig_in, labelled 1 or 0 as the code tests sig_in and !sig_in. In the code, each state's first if is the arrow on the bit that carries the match a step further; on a Mealy machine the arrow that completes the match also reads / found.

The figure runs two scenarios. Detect releases the reset and plays the pattern once, one bit a clock period: the machine walks it state by state and pauses where found rises. Overlap is there when the pattern can overlap itself. It plays the shortest input that holds the pattern twice with the two matches sharing bits, 1011011 for 1011, and the waveform shows whether this detector finds it once or twice.

The code is written in the site's house style, the style of the reference pages. Each state is an arm of the unique case, each arrow a branch of that arm's if chain. Point at a state or an arrow in the drawing, or reach it from the keyboard, and its lines light up in the code; point at a line and its part of the drawing lights. Copy in the code block's bar copies the code, and Download saves it as a file named after the module.

How the machine is built

The construction is the prefix function of the pattern, the table at the heart of the Knuth–Morris–Pratt search. For every prefix of the pattern it records the longest proper suffix that is also a prefix of the whole pattern, and that decides where a mismatch goes. After 101, a 0 does not send 1011's detector back to IDLE: the input now ends in 10, the pattern's first two bits, so the machine goes to S10. Going to IDLE would miss every match that begins inside one that failed.

A match can leave the machine in two places. Overlapping, the bits that end one match may begin the next: after 1011 the final 1 is the pattern's first bit, so the machine carries on as if in S1. Non-overlapping, a match spends its bits and the machine starts again from IDLE. A pattern with no proper suffix that is also a prefix, such as 1000, cannot overlap itself; both choices then build the same machine, and the line under the controls says so.

Moore and Mealy, and the code's forms

A Moore machine reports the match in a state of its own: n + 1 states for n bits, and found is high for the clock period after the edge that took the last bit. A Mealy machine reports it on the arrow that completes the match: n states, and found is high while the last bit is on sig_in, before the edge, because it depends on the input as well as on the state.

Processes is how the code is split. Three processes are the state register, the next-state logic and the output logic in three blocks. Two put the next state and the outputs in one always_comb. One puts everything inside the always_ff, so the outputs become registers that change on the edge with the state. A Moore output changes on that edge anyway; a Mealy output answers its input before the edge, and as a register it would answer a clock period late, so one process is offered for Moore machines only.

Encoding sets the codes the typedef enum declares and the state row of the waveform: binary counts the states in order, Gray changes one bit between neighbouring codes, and one-hot gives each state a bit of its own.

Limits

Patterns run from 1 to 6 bits. The machine has one input, sig_in, and one output, found, with the names the reference page uses, and an asynchronous, active-low reset, rst_n, which the code states in its header. Every drawing but two is laid out automatically, and up to 4 bits each fits a 360 px phone; wider ones scroll inside their frame. The two, 00 and 11, non-overlapping and Mealy, have three arrows between one pair of states, which the layout cannot draw, and are placed by hand. What a detector does before its first reset, when the register holds no known state, is the subject of the reference page for 1011, whose machine is this generator's default.

Found an error? Send a correction