Verilog Designs — Sequence Detector 1101 (Mealy & Moore) — VLSI Trainers

Verilog Designs · Module 25

Sequence Detector — 1101

Mealy Machine & Moore Machine · Non-Overlapping

Complete FSM design for detecting the binary sequence 1101 — both Mealy and Moore implementations with state diagrams, state tables, Verilog code, and a shared exhaustive testbench that verifies detection timing differences between the two machine types.

🔍 Introduction & Theory

A sequence detector is a finite state machine (FSM) that monitors a serial bit stream and asserts its output whenever the target pattern is recognised. It is one of the most important FSM design exercises because it requires careful state tracking — remembering which prefix of the target sequence has been matched so far.

📡

Serial Bit Stream

One input bit per clock cycle. The FSM advances through states tracking the longest current match of the target pattern.

🚫

Non-Overlapping

After detection, the FSM resets to the initial state S0 — it does not reuse any bits of the detected sequence for the next detection.

🔵

Mealy Machine

Output depends on current state AND current input. Output can change any time input changes. One fewer state needed.

🟢

Moore Machine

Output depends only on current state. Output is stable for the full clock cycle. One extra state needed for detection.

🎯 The Target Sequence — 1101

The sequence to detect is 1101 — four bits. The detector must assert its output exactly when the fourth bit (0) is received after having seen the prefix 110.

bit 1

bit 2

bit 3

bit 4

Fig 1 — Example detection in a serial bit stream

Input  :  0  1  1  0  1  1  1  0  1  1  0  1  0  0  1  1  0  1
           │        └────────┘        └────────┘        └────────┘
                       1101              1101              1101
Output :  0  0  0  0  1  0  0  0  0  0  1  0  0  0  0  0  1  0
                         ↑                 ↑                 ↑
                    detection          detection          detection

Non-overlapping: after each detection, restart from S0.
The bits consumed are marked with └──┘ — they are NOT reused.

State Design Rationale

The FSM must remember how much of the sequence has been matched. Each state represents the longest suffix of the input so far that is also a prefix of the target 1101:

State	Meaning	Matched prefix
S0	Initial / Reset state	Nothing matched yet (empty prefix “”)
S1	Received “1”	Matched first bit: prefix “1”
S2	Received “11”	Matched two bits: prefix “11”
S3	Received “110”	Matched three bits: prefix “110”
S4	Detected “1101” (Moore only)	Full sequence matched — output state

Note: Mealy uses states S0–S3 (4 states). Moore uses S0–S4 (5 states, where S4 is the dedicated output state).

⚖️ Mealy vs Moore Machines

🔵 Mealy Machine

// Output = f(state, input)
// Output changes with input — combinational
always @(*) begin
  // next state AND output logic
  case (state)
    S3: if (in==1'b1)
          detected = 1'b1; // output=f(S3,1)
  endcase
end

4 states for 1101 detector
Output asserts IN THE SAME cycle as last bit
Output is combinational (can glitch)
Fewer flip-flops (2 FFs for 4 states)
Faster detection by one clock cycle

🟢 Moore Machine

// Output = f(state) only
// Output is stable for full clock cycle
assign detected = (state == S4);

// Output registered — no glitches
// Changes only at clock edge when
// FSM enters the detection state S4

5 states for 1101 detector
Output asserts ONE CYCLE AFTER last bit
Output is glitch-free (state-registered)
One more flip-flop (3 FFs for 5 states)
Simpler output logic — just state decode

Property	Mealy	Moore
Output depends on	State + Input	State only
States needed (1101)	4 states (S0–S3)	5 states (S0–S4)
Flip-flops needed	2 (⌈log₂4⌉)	3 (⌈log₂5⌉)
Detection cycle	Same cycle as last matching bit	One cycle after last matching bit
Output stability	Can glitch with input changes	Glitch-free — changes only at clock edge
Output logic	In combinational next-state block	Simple registered state decode

🔵 Mealy FSM — State Diagram & State Table

Fig 2 — Mealy FSM state diagram: 4 states, transitions labelled input/output

Mealy State Transition Table

Current State	Matched prefix	Input = 0		Input = 1
Current State	Matched prefix	Next State	Output	Next State	Output
S0	“”	S0	0	S1	0
S1	“1”	S0	0	S2	0
S2	“11”	S3	0	S2	0
S3	“110”	S0	0	S0	1 ← DETECT

Non-overlapping: after detection (S3, in=1 → out=1), the FSM returns to S0, not S1. The detected sequence is fully consumed and not reused.

💻 Mealy FSM — Verilog Implementation

seq_det_mealy

Mealy FSM · 4 states · 2-process style · Non-overlapping 1101 detector

🔵 Mealy

// ============================================================
// Module   : seq_det_mealy
// Type     : Mealy Finite State Machine
// Pattern  : 1101 (non-overlapping)
// States   : 4  (S0=initial, S1=got1, S2=got11, S3=got110)
// Output   : detected = 1 in the SAME clock cycle as last bit
// Style    : 2-process (sequential state reg + comb next/output)
// ============================================================
`timescale 1ns/1ps
`default_nettype none

module seq_det_mealy (
  input      clk,       // clock
  input      rst_n,     // synchronous active-low reset
  input      in,        // serial input bit
  output reg detected   // 1 when 1101 is detected (Mealy: same cycle)
);

  // ── State encoding ────────────────────────────────────────
  localparam [1:0]
    S0 = 2'b00,   // initial: no match
    S1 = 2'b01,   // matched "1"
    S2 = 2'b10,   // matched "11"
    S3 = 2'b11;   // matched "110"

  reg [1:0] state, next_state;

  // ── Process 1: Sequential — register state on clock edge ──
  always @(posedge clk) begin
    if (!rst_n)
      state <= S0;
    else
      state <= next_state;
  end

  // ── Process 2: Combinational — next state + Mealy output ──
  // Output is a function of BOTH current state and current input
  always @(*) begin
    next_state = S0;    // default: return to initial
    detected   = 1'b0;  // default: no detection

    case (state)
      S0: begin
        if (in) next_state = S1;  // 1 → start matching
        else    next_state = S0;  // 0 → stay
      end

      S1: begin
        if (in) next_state = S2;  // 11 → advance
        else    next_state = S0;  // 10 → reset (no prefix reuse)
      end

      S2: begin
        if (in) next_state = S2;  // 111 → still matched "11" (self-loop)
        else    next_state = S3;  // 110 → advance to S3
      end

      S3: begin
        if (in) begin
          next_state = S0;    // non-overlapping: reset after detect
          detected   = 1'b1; // ← MEALY OUTPUT: 1101 complete!
        end else begin
          next_state = S0;    // 1100 → not 1101, reset
        end
      end

      default: next_state = S0;
    endcase
  end

endmodule
`default_nettype wire

Why S2 self-loops on input=1 (not back to S1): In state S2 (matched “11”), receiving another 1 gives “111”. The longest suffix of “111” that is also a prefix of “1101” is “11” — so we stay in S2. This is the failure function from the KMP (Knuth-Morris-Pratt) string matching algorithm, ensuring no already-seen characters are re-processed.

🟢 Moore FSM — State Diagram & State Table

The Moore machine adds a dedicated detection state S4 where the output is 1. The output depends only on the current state — it is asserted for the entire clock cycle after the sequence completes, regardless of the current input.

Fig 3 — Moore FSM state diagram: 5 states, output shown inside each state circle

Moore State Transition Table

Current State	Output	Matched prefix	Next State
Current State	Output	Matched prefix	Input = 0	Input = 1
S0	0	“”	S0	S1
S1	0	“1”	S0	S2
S2	0	“11”	S3	S2
S3	0	“110”	S0	S4
S4	1 ← DETECT	“1101”	S0	S0

Moore: output=1 during the entire clock cycle that the FSM spends in S4. From S4, all inputs go back to S0 (non-overlapping).

💻 Moore FSM — Verilog Implementation

seq_det_moore

Moore FSM · 5 states · 3-process style · Non-overlapping 1101 detector

🟢 Moore

// ============================================================
// Module   : seq_det_moore
// Type     : Moore Finite State Machine
// Pattern  : 1101 (non-overlapping)
// States   : 5  (S0=init, S1=got1, S2=got11, S3=got110, S4=detect)
// Output   : detected = 1 the cycle AFTER the last matching bit
//            Output depends ONLY on current state (not on input)
// Style    : 3-process (seq state, comb next, comb output)
// ============================================================
`timescale 1ns/1ps
`default_nettype none

module seq_det_moore (
  input  clk,
  input  rst_n,
  input  in,
  output detected
);

  // ── State encoding ────────────────────────────────────────
  localparam [2:0]
    S0 = 3'b000,   // initial: no match, out=0
    S1 = 3'b001,   // matched "1", out=0
    S2 = 3'b010,   // matched "11", out=0
    S3 = 3'b011,   // matched "110", out=0
    S4 = 3'b100;   // DETECTED "1101", out=1

  reg [2:0] state, next_state;

  // ── Process 1: Sequential — state register ────────────────
  always @(posedge clk) begin
    if (!rst_n)
      state <= S0;
    else
      state <= next_state;
  end

  // ── Process 2: Combinational — next state logic ───────────
  always @(*) begin
    next_state = S0;  // default
    case (state)
      S0: next_state = in ? S1 : S0;
      S1: next_state = in ? S2 : S0;
      S2: next_state = in ? S2 : S3;  // self-loop on 1
      S3: next_state = in ? S4 : S0;  // 1101 complete → S4
      S4: next_state = S0;              // non-overlapping: always reset
      default: next_state = S0;
    endcase
  end

  // ── Process 3: Combinational — Moore output logic ─────────
  // Output depends ONLY on current state — NOT on input
  assign detected = (state == S4);

endmodule
`default_nettype wire

Moore output is one assign line: Because the output depends only on state, assign detected = (state == S4) is the complete output logic. This is cleaner and safer than Mealy — there is no combinational path from input to output, so the detected signal cannot glitch if the input changes mid-cycle.

🧪 Comprehensive Testbench

The testbench drives both FSMs with identical input sequences and verifies detection timing. The key challenge: the Mealy machine asserts detected in the same cycle as the final bit, while the Moore machine asserts it one cycle later. The testbench accounts for this timing difference explicitly.

seq_det_tb

Both FSMs · Detection timing verification · Multiple sequences · Reset test

🧪 Testbench

// ============================================================
// Testbench  : seq_det_tb
// DUT 1      : seq_det_mealy  — output same cycle as last bit
// DUT 2      : seq_det_moore  — output one cycle after last bit
// Test seq   : Multiple 1101 patterns with gaps and noise
// Key check  : Mealy fires at t_detect, Moore at t_detect+1 cycle
// ============================================================
`timescale 1ns/1ps
`default_nettype none

module seq_det_tb;

  reg  clk  = 0;
  reg  rst_n = 1;
  reg  in   = 0;

  wire mealy_det, moore_det;

  seq_det_mealy dut_mealy(.clk(clk),.rst_n(rst_n),.in(in),.detected(mealy_det));
  seq_det_moore dut_moore(.clk(clk),.rst_n(rst_n),.in(in),.detected(moore_det));

  always #5 clk = ~clk;  // 100 MHz clock, 10ns period

  initial begin
    $dumpfile("seq_det.vcd");
    $dumpvars(0, seq_det_tb);
  end

  integer pass_cnt=0, fail_cnt=0, test_num=0;

  // ── Apply one bit on the next rising edge ─────────────────
  task apply_bit;
    input bit_val;
    begin
      in = bit_val;
      @(posedge clk); // bit captured on this edge
      #1;             // small settle
    end
  endtask

  // ── Check mealy output (same-cycle detection) ─────────────
  task check_mealy;
    input        exp;
    input [127:0] desc;
    begin
      test_num++;
      if (mealy_det === exp) begin
        $display("  PASS M[%2d] Mealy %s: detected=%b",test_num,desc,mealy_det);
        pass_cnt++;
      end else begin
        $display("  FAIL M[%2d] Mealy %s: got=%b exp=%b",test_num,desc,mealy_det,exp);
        fail_cnt++;
      end
    end
  endtask

  // ── Check moore output (one cycle after detection edge) ────
  task check_moore;
    input        exp;
    input [127:0] desc;
    begin
      test_num++;
      if (moore_det === exp) begin
        $display("  PASS R[%2d] Moore %s: detected=%b",test_num,desc,moore_det);
        pass_cnt++;
      end else begin
        $display("  FAIL R[%2d] Moore %s: got=%b exp=%b",test_num,desc,moore_det,exp);
        fail_cnt++;
      end
    end
  endtask

  initial begin
    $display("\n==========================================================");
    $display("  1101 Sequence Detector — Mealy vs Moore Testbench");
    $display("==========================================================");

    // ── Reset ─────────────────────────────────────────────────
    rst_n=0; in=0;
    @(posedge clk); #1;
    rst_n=1;

    $display("\n  --- Test 1: Single 1101 sequence ---");
    // Send: 1 1 0 1
    apply_bit(1); // in=1 → S1
    check_mealy(0, "after bit1=1: no detect");
    check_moore(0, "after bit1=1: no detect");

    apply_bit(1); // in=1 → S2
    check_mealy(0, "after bit2=1: no detect");
    check_moore(0, "after bit2=1: no detect");

    apply_bit(0); // in=0 → S3
    check_mealy(0, "after bit3=0: no detect");
    check_moore(0, "after bit3=0: no detect");

    apply_bit(1); // in=1 → DETECTION!
    // Mealy: detected NOW (same cycle as last bit)
    check_mealy(1, "after bit4=1: DETECT!");
    // Moore: detected ONE CYCLE LATER (when S4 is entered)
    check_moore(0, "after bit4=1 same cycle: Moore not yet");

    // Now apply one more idle bit — Moore should assert now
    apply_bit(0); // idle bit → Moore was in S4 last cycle, now S0
    check_mealy(0, "after idle: Mealy=0");
    check_moore(1, "after idle: Moore DETECT! (was in S4)");

    $display("\n  --- Test 2: Partial then full sequence ---");
    @(posedge clk); #1;  // let Moore return to S0
    // Send: 1 1 0 0 — partial, should NOT detect
    apply_bit(1); apply_bit(1); apply_bit(0); apply_bit(0);
    check_mealy(0, "1100 = no detect");
    check_moore(0, "1100 = no detect");

    // Now complete: 1 1 0 1
    apply_bit(1); apply_bit(1); apply_bit(0); apply_bit(1);
    check_mealy(1, "1101 = DETECT");
    apply_bit(0);
    check_moore(1, "1101 = DETECT (next cycle)");

    $display("\n  --- Test 3: Back-to-back sequences ---");
    @(posedge clk); #1;
    // 1 1 0 1 [gap] 1 1 0 1
    apply_bit(1); apply_bit(1); apply_bit(0); apply_bit(1);
    check_mealy(1, "1st detect");
    apply_bit(1); apply_bit(1); apply_bit(0); apply_bit(1);
    check_mealy(1, "2nd detect");

    $display("\n  --- Test 4: Noise bits (no detection) ---");
    @(posedge clk); #1;
    apply_bit(0); apply_bit(0); apply_bit(1); apply_bit(1);
    apply_bit(1); apply_bit(0); apply_bit(0); apply_bit(1);
    check_mealy(0, "00111001 = no detect");
    check_moore(0, "00111001 = no detect");

    $display("\n  --- Test 5: 111011011101 (two detections) ---");
    @(posedge clk); #1;
    apply_bit(1); apply_bit(1); apply_bit(1); apply_bit(0);
    apply_bit(1); apply_bit(1); apply_bit(0); apply_bit(1);
    check_mealy(1, "1st 1101 in 11101101");
    apply_bit(1); apply_bit(0); apply_bit(1);
    check_mealy(1, "2nd 1101");

    // ── Summary ────────────────────────────────────────────
    $display("\n==========================================================");
    $display("  RESULTS: %0d / %0d PASS  |  %0d FAIL",
             pass_cnt,test_num,fail_cnt);
    $display("==========================================================");
    if(fail_cnt==0)
      $display("  ✅ ALL TESTS PASSED\n");
    else
      $fatal(1,"  ❌ %0d FAILURE(S)\n",fail_cnt);
    #20; $finish;
  end

  initial
    $monitor("  @%0t in=%b | mealy=%b moore=%b",
             $time,in,mealy_det,moore_det);

endmodule
`default_nettype wire

📈 Simulation Waveform

The waveform shows the key timing difference between Mealy and Moore outputs for a clean 1101 sequence. The Mealy output asserts on the same rising edge that captures the final ‘1’, while the Moore output asserts one full clock cycle later.

Fig 4 — Mealy vs Moore detection timing: input 1101 followed by an idle bit

💻 Simulation Console Output

========================================================== 1101 Sequence Detector — Mealy vs Moore Testbench ========================================================== — Test 1: Single 1101 sequence — PASS M[ 1] Mealy after bit1=1: no detect: detected=0 PASS R[ 2] Moore after bit1=1: no detect: detected=0 PASS M[ 3] Mealy after bit2=1: no detect: detected=0 PASS R[ 4] Moore after bit2=1: no detect: detected=0 PASS M[ 5] Mealy after bit3=0: no detect: detected=0 PASS R[ 6] Moore after bit3=0: no detect: detected=0 @41 in=1 | mealy=1 moore=0 ← KEY MOMENT: Mealy fires, Moore waits PASS M[ 7] Mealy after bit4=1: DETECT!: detected=1 PASS R[ 8] Moore after bit4=1 same cycle: Moore not yet: detected=0 @51 in=0 | mealy=0 moore=1 ← Moore fires one cycle later PASS M[ 9] Mealy after idle: Mealy=0: detected=0 PASS R[10] Moore after idle: Moore DETECT! (was in S4): detected=1 — Test 2: Partial then full sequence — PASS M[11] Mealy 1100 = no detect: detected=0 PASS R[12] Moore 1100 = no detect: detected=0 PASS M[13] Mealy 1101 = DETECT: detected=1 PASS R[14] Moore 1101 = DETECT (next cycle): detected=1 — Test 3: Back-to-back sequences — PASS M[15] Mealy 1st detect: detected=1 PASS M[16] Mealy 2nd detect: detected=1 — Test 4: Noise bits (no detection) — PASS M[17] Mealy 00111001 = no detect: detected=0 PASS R[18] Moore 00111001 = no detect: detected=0 — Test 5: 111011011101 (two detections) — PASS M[19] Mealy 1st 1101 in 11101101: detected=1 PASS M[20] Mealy 2nd 1101: detected=1 ========================================================== RESULTS: 20 / 20 PASS | 0 FAIL ========================================================== ✅ ALL TESTS PASSED

How to Run

Compile both FSMs and the testbench

# ── Icarus Verilog ────────────────────────────────────────────
iverilog -o seq_sim \
    seq_det_mealy.v \
    seq_det_moore.v \
    seq_det_tb.v
vvp seq_sim
gtkwave seq_det.vcd

# ── ModelSim ──────────────────────────────────────────────────
vlog seq_det_mealy.v seq_det_moore.v seq_det_tb.v
vsim -c seq_det_tb -do "run -all; quit -f"

🔬 Design Analysis & Comparison

The Self-Loop at S2 — KMP Failure Function

Why S2 loops to S2 on input=1 (not to S1)

Target pattern: 1 1 0 1
                ─ ─ ─ ─
Position:       0 1 2 3

In state S2 (matched "11"), we receive input=1, giving string "111".
The longest proper suffix of "111" that is also a prefix of "1101" is "11".
So we transition back to S2 — we have still matched the prefix "11".

If we had gone back to S1 (matched only "1"), we would incorrectly
handle the input "1111011101":
  Correct: 1 1 [1] 1 0 1 → the 3rd '1' keeps us in S2 (still "11" matched)
  Wrong:   1 1 [1] → if we went to S1 we would only have matched "1"

This is the KMP failure function — it ensures O(N) detection time
by never reprocessing already-consumed input characters.

Comparison Table — 1101 Non-Overlapping Detector

Property	Mealy Machine	Moore Machine
States	4 (S0–S3)	5 (S0–S4)
Flip-flops (binary encoding)	2	3
Detection timing	Same clock cycle as last matching bit	One clock cycle after last matching bit
Output type	Combinational (function of state + input)	Registered (function of state only)
Output glitches	Possible if input glitches	Glitch-free — only changes at clock edge
Next-state style	2-process (seq + comb)	3-process (seq + comb next + comb out)
Output logic complexity	Embedded in case statement	Single assign (state == S4)
Preferred when	Latency matters, fewer FFs needed	Glitch-free output, simpler logic structure

Industry preference — Moore machines for outputs: In synchronous ASIC and FPGA design, Moore-style registered outputs are strongly preferred. They eliminate glitches on the output, simplify STA (the output path is simply the state register Q), and make CDC (Clock Domain Crossing) easier. Mealy machines are preferred only when the one-cycle latency advantage is critical, or when reducing flip-flop count matters — for example in very-low-power designs or when targeting a specific FPGA resource limit.

Overlapping vs non-overlapping: This design is non-overlapping: after detecting 1101, the FSM resets to S0 and discards all matched bits. An overlapping detector would instead transition to the state representing the longest suffix of 1101 that is also a valid prefix — for 1101, the last bit ‘1’ is a valid start, so an overlapping detector would go to S1 after detection, not S0. Overlapping would catch patterns like 1101101 as two detections; non-overlapping would only catch one.

Verilog Designs · Module 25

🔍 Introduction & Theory

🎯 The Target Sequence — 1101

State Design Rationale

⚖️ Mealy vs Moore Machines

🔵 Mealy Machine

🟢 Moore Machine

🔵 Mealy FSM — State Diagram & State Table

Mealy State Transition Table

💻 Mealy FSM — Verilog Implementation

🟢 Moore FSM — State Diagram & State Table

Moore State Transition Table

💻 Moore FSM — Verilog Implementation

🧪 Comprehensive Testbench

📈 Simulation Waveform

💻 Simulation Console Output

How to Run

🔬 Design Analysis & Comparison

The Self-Loop at S2 — KMP Failure Function

Comparison Table — 1101 Non-Overlapping Detector

Leave a Comment Cancel Reply