Overlapping 1101 Sequence Detector Using Mealy and Moore Machines

🔄 Overlapping vs Non-Overlapping

The only difference between overlapping and non-overlapping detectors is what happens after a detection. In a non-overlapping detector, the FSM resets to S0 and discards all consumed bits. In an overlapping detector, the FSM transitions to the state representing the longest suffix of the detected sequence that is also a valid prefix of the target — allowing the very bits just detected to contribute to the next match.

🔁 Non-Overlapping (Module 25)

Input:   1 1 0 1 1 1 0 1
         └──────┘ └──────┘
Detect:        ↑       ↑
After detect: go to S0
(last bit '1' is discarded)
Count = 2 detections

🔄 Overlapping (This Module)

Input:   1 1 0 1 1 0 1
         └──────┘
             └──────┘
Detect:        ↑   ↑
After detect: go to S1
(last bit '1' reused!)
Count = 2 detections in 7 bits!

🔑

The Key Change

Only the post-detection transition changes. Everything else — states S0, S1, S2, S3, all other transitions — is identical to the non-overlapping version.

📐

KMP Failure Function

The post-detection state is determined by the KMP failure function: the longest proper suffix of “1101” that is also a prefix of “1101”.

🔢

Same State Count

Mealy: 4 states. Moore: 5 states. Identical to non-overlapping — only one transition arrow changes direction.

📡

Application

Used in communications receivers, pattern matching engines, and protocol decoders where a detected codeword may begin a new frame immediately.

🔍 Overlap Analysis for 1101

To determine the post-detection state, we apply the KMP failure function to the pattern “1101”. This finds the longest proper suffix of the pattern that is also a prefix of the pattern.

Fig 1 — KMP failure function: finding the overlap in “1101”

Pattern: 1  1  0  1
Index:   0  1  2  3

For the complete pattern "1101", examine all proper suffixes:
  Suffix "1"    → is it a prefix of "1101"? YES ("1...") → length 1
  Suffix "01"   → is it a prefix of "1101"? NO
  Suffix "101"  → is it a prefix of "1101"? NO

Longest proper suffix that is also a prefix: "1" (length 1)

Therefore: after detecting "1101", the last bit '1' is REUSED
and the FSM transitions to S1 (= "matched prefix '1'")

Overlapping example:
Input:  1  1  0  1  1  0  1
                ↑           ↑
         detect here    detect here (reused '1' from first detect)

First  match: bits 0-3 = 1101 → detect, go to S1 (keep '1')
Second match: bits 3-6 = 1101 → detect, go to S1 (keep '1')

⚠️ The ONLY change from Non-Overlapping

Non-Overlapping (Module 25)

S3 + in=1 → S0, out=1

Reset to initial — no reuse

Overlapping (This Module)

S3 + in=1 → S1, out=1

Go to S1 — reuse the last ‘1’

Overlapping Stream Example

t=1

t=2

t=3

t=4 ★

t=5

t=6

t=7 ★

t=8

t=9

t=10

t=11

t=12 ★

★ = detection events. Bits t=4 and t=7 are shared between two consecutive matches (the ‘1’ at end of first 1101 starts the next). 3 detections in 12 bits.

🔵 Mealy FSM — State Diagram & State Table

Identical to non-overlapping except the detection transition from S3 (on input=1) goes to S1 instead of S0. The ‘1’ that completes 1101 is immediately reused as the start of the next potential 1101 sequence.

Fig 2 — Mealy overlapping FSM: detection arc returns to S1 (not S0)

Mealy Overlapping 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	S1 ★	1 ← DETECT

★ The ONLY change from non-overlapping: detection returns to S1 instead of S0, reusing the last ‘1’ as the first bit of the next potential match.

💻 Mealy FSM — Verilog Implementation

seq_det_mealy_ovlp

Mealy FSM · 4 states · Overlapping 1101 · Detection returns to S1

🔵 Mealy Overlapping

// ============================================================
// Module   : seq_det_mealy_ovlp
// Type     : Mealy FSM — Overlapping 1101 detector
// Key diff : After detection, go to S1 (not S0) — reuse last '1'
// States   : S0=init, S1=got"1", S2=got"11", S3=got"110"
// ============================================================
`timescale 1ns/1ps
`default_nettype none

module seq_det_mealy_ovlp (
  input      clk,
  input      rst_n,
  input      in,
  output reg detected
);

  localparam [1:0]
    S0 = 2'b00,
    S1 = 2'b01,
    S2 = 2'b10,
    S3 = 2'b11;

  reg [1:0] state, next_state;

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

  // ── Combinational: next state + Mealy output ──────────────
  always @(*) begin
    next_state = S0;
    detected   = 1'b0;

    case (state)
      S0: next_state = in ? S1 : S0;

      S1: next_state = in ? S2 : S0;

      S2: next_state = in ? S2 : S3;  // "111"→stay S2, "110"→S3

      S3: begin
        if (in) begin
          // ★ OVERLAPPING: reuse last '1' → go to S1, not S0
          next_state = S1;     // 1101 → last '1' starts next match
          detected   = 1'b1;  // 1101 detected!
        end else begin
          next_state = S0;     // 1100 → reset
        end
      end

      default: next_state = S0;
    endcase
  end

endmodule
`default_nettype wire

Compared to Module 25 Mealy: Exactly one line changed — next_state = S0 became next_state = S1 inside the S3, in=1 branch. Every other line is byte-for-byte identical. This tiny change enables overlapping detection.

🟢 Moore FSM — State Diagram & State Table

The Moore overlapping detector uses 5 states (S0–S4), same as non-overlapping. The only change: from S4 (detection state), input=1 transitions to S1 instead of S0, reusing the bit received during S4 as the start of the next match.

Fig 3 — Moore overlapping FSM: S4 on input=1 returns to S1 (not S0)

Moore Overlapping 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	S1 ★

★ Moore overlapping: from S4 (detection state), input=1 goes to S1 — the ‘1’ received while in S4 becomes the start of the next match. Input=0 from S4 still goes to S0.

💻 Moore FSM — Verilog Implementation

seq_det_moore_ovlp

Moore FSM · 5 states · Overlapping 1101 · S4 on 1 returns to S1

🟢 Moore Overlapping

// ============================================================
// Module   : seq_det_moore_ovlp
// Type     : Moore FSM — Overlapping 1101 detector
// Key diff : S4 + input=1 → S1 (not S0) — reuse bit during detect state
// States   : S0=init, S1="1", S2="11", S3="110", S4=DETECT
// ============================================================
`timescale 1ns/1ps
`default_nettype none

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

  localparam [2:0]
    S0 = 3'b000,
    S1 = 3'b001,
    S2 = 3'b010,
    S3 = 3'b011,
    S4 = 3'b100;

  reg [2:0] state, next_state;

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

  // ── Combinational: next state ─────────────────────────────
  always @(*) begin
    next_state = S0;
    case (state)
      S0: next_state = in ? S1 : S0;
      S1: next_state = in ? S2 : S0;
      S2: next_state = in ? S2 : S3;
      S3: next_state = in ? S4 : S0;
      S4: begin
        // ★ OVERLAPPING: input=1 during detect state → S1, not S0
        next_state = in ? S1 : S0;
      end
      default: next_state = S0;
    endcase
  end

  // ── Output: purely state-dependent (Moore) ────────────────
  assign detected = (state == S4);

endmodule
`default_nettype wire

Compared to Module 25 Moore: Exactly one ternary changed in the S4 case: next_state = S0 (non-overlapping) became next_state = in ? S1 : S0 (overlapping). The output line assign detected = (state == S4) is unchanged — Moore output logic never changes regardless of overlapping/non-overlapping.

🔄 Key Differences from Non-Overlapping (Module 25)

Property	Non-Overlapping (Module 25)	Overlapping (This Module)
Post-detection state (Mealy)	`S3 + in=1 → S0` (reset)	`S3 + in=1 → S1` (reuse ‘1’)
Post-detection state (Moore)	`S4 → S0` always	`S4 + in=1 → S1`, `S4 + in=0 → S0`
Lines changed (Mealy)	—	1 line: `S0` → `S1` in S3 branch
Lines changed (Moore)	—	1 line: `S0` → `in ? S1 : S0` in S4 case
State count	Mealy: 4, Moore: 5	Identical — Mealy: 4, Moore: 5
Example: input 11011101	Detects at t=4, resets. Detects at t=8. Count=2	Detects at t=4, goes to S1. Detects at t=7. Count=2 in fewer bits
Example: input 11011011101	Detects at t=4 and t=11. Count=2	Detects at t=4, t=7, t=11. Count=3

Fig 4 — Side by side: the single line that changes between overlapping and non-overlapping

🔴 Non-Overlapping (Module 25 Mealy)

S3: begin
  if (in) begin
    next_state = S0;  ← discards '1'
    detected   = 1'b1;
  end else
    next_state = S0;
end

🟢 Overlapping (This Module Mealy)

S3: begin
  if (in) begin
    next_state = S1;  ← reuses '1'
    detected   = 1'b1;
  end else
    next_state = S0;
end

🧪 Comprehensive Testbench

The testbench specifically exercises overlapping detection scenarios — streams where non-overlapping would miss detections but overlapping finds them. It runs both FSMs simultaneously and checks that extra detections occur at the correct cycles.

seq_det_ovlp_tb

Both overlapping FSMs · Overlapping scenarios · Timing verification · Boundary cases

🧪 Testbench

// ============================================================
// Testbench  : seq_det_ovlp_tb
// DUT 1      : seq_det_mealy_ovlp
// DUT 2      : seq_det_moore_ovlp
// Focus      : Overlapping detection — consecutive 1101 patterns
//              where last bit of one match is first bit of next
// ============================================================
`timescale 1ns/1ps
`default_nettype none

module seq_det_ovlp_tb;

  reg  clk=0, rst_n=1, in=0;
  wire mealy_det, moore_det;

  seq_det_mealy_ovlp dut_m(.clk(clk),.rst_n(rst_n),.in(in),.detected(mealy_det));
  seq_det_moore_ovlp dut_r(.clk(clk),.rst_n(rst_n),.in(in),.detected(moore_det));

  always #5 clk = ~clk;

  initial begin
    $dumpfile("seq_det_ovlp.vcd");
    $dumpvars(0, seq_det_ovlp_tb);
  end

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

  task apply_bit; input b;
    begin in=b; @(posedge clk); #1; end
  endtask

  task chk;
    input exp_m, exp_r;
    input [255:0] msg;
    begin
      test_num++;
      if(mealy_det===exp_m && moore_det===exp_r) begin
        $display("  PASS [%2d] %s | M=%b R=%b",test_num,msg,mealy_det,moore_det);
        pass_cnt++;
      end else begin
        $display("  FAIL [%2d] %s | got M=%b R=%b exp M=%b R=%b",
          test_num,msg,mealy_det,moore_det,exp_m,exp_r);
        fail_cnt++;
      end
    end
  endtask

  initial begin
    $display("\n=======================================================");
    $display("  1101 OVERLAPPING Detector — Mealy & Moore");
    $display("=======================================================");

    rst_n=0; @(posedge clk); #1; rst_n=1;

    // ── Test 1: Single clean 1101 ──────────────────────────
    $display("\n  --- Test 1: Single 1101 ---");
    apply_bit(1); chk(0,0, "bit1=1: no detect");
    apply_bit(1); chk(0,0, "bit2=1: no detect");
    apply_bit(0); chk(0,0, "bit3=0: no detect");
    apply_bit(1); chk(1,0, "bit4=1: Mealy DETECT, Moore not yet");
    apply_bit(0); chk(0,1, "idle: Moore DETECT (from S4)");

    // ── Test 2: Overlapping — 1101101 (2 detections in 7 bits)
    $display("\n  --- Test 2: Overlapping 1101101 (2 detections) ---");
    rst_n=0; @(posedge clk); #1; rst_n=1;
    apply_bit(1); apply_bit(1); apply_bit(0); apply_bit(1);
    chk(1,0, "1st 1101: Mealy DETECT (same cycle)");
    // After detection, Mealy goes to S1 (overlapping!)
    // Next bits: 1 0 1 = complete second 1101 starting from last '1'
    apply_bit(1); chk(0,1, "bit5=1: Moore 1st DETECT, Mealy in S2");
    apply_bit(0); chk(0,0, "bit6=0: in S3 now");
    apply_bit(1); chk(1,0, "bit7=1: Mealy 2nd DETECT! (overlapping!)");
    apply_bit(0); chk(0,1, "Moore 2nd DETECT");

    // ── Test 3: 11011101 — prove reuse works correctly ─────
    $display("\n  --- Test 3: 11011101 overlapping ---");
    rst_n=0; @(posedge clk); #1; rst_n=1;
    apply_bit(1); apply_bit(1); apply_bit(0); apply_bit(1);
    chk(1,0, "1st detect at bit4");
    apply_bit(1); apply_bit(1); apply_bit(0); apply_bit(1);
    chk(1,0, "2nd detect at bit8");
    apply_bit(0); chk(0,1, "Moore 2nd detect confirmed");

    // ── Test 4: No detection stream ────────────────────────
    $display("\n  --- Test 4: 1100111 — no detection ---");
    rst_n=0; @(posedge clk); #1; rst_n=1;
    apply_bit(1);apply_bit(1);apply_bit(0);apply_bit(0);
    apply_bit(1);apply_bit(1);apply_bit(1);
    chk(0,0, "1100111 = no detect");

    // ── Test 5: Three back-to-back in 11011011101 ──────────
    $display("\n  --- Test 5: 11011011101 (3 Mealy detections) ---");
    rst_n=0; @(posedge clk); #1; rst_n=1;
    // bits: 1 1 0 1 1 0 1 1 1 0 1
    apply_bit(1);apply_bit(1);apply_bit(0);apply_bit(1);
    chk(1,0, "1st detect t4");           // 1101↑ → S1
    apply_bit(1);apply_bit(0);apply_bit(1);
    chk(1,0, "2nd detect t7 (overlapping)"); // 1101↑ → S1
    apply_bit(1);apply_bit(1);apply_bit(0);apply_bit(1);
    chk(1,0, "3rd detect t11 (overlapping)");

    // ── 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 overlapping stream 1101101 — two detections in 7 bits. The last ‘1’ of the first detection immediately becomes the first ‘1’ of the second match, demonstrating the state reuse.

Fig 5 — Overlapping detection: 1101101 → two Mealy detections in 7 bits

💻 Simulation Console Output

======================================================= 1101 OVERLAPPING Detector — Mealy & Moore ======================================================= — Test 1: Single 1101 — PASS [ 1] bit1=1: no detect | M=0 R=0 PASS [ 2] bit2=1: no detect | M=0 R=0 PASS [ 3] bit3=0: no detect | M=0 R=0 PASS [ 4] bit4=1: Mealy DETECT, Moore not yet | M=1 R=0 PASS [ 5] idle: Moore DETECT (from S4) | M=0 R=1 — Test 2: Overlapping 1101101 (2 detections) — @41 in=1 | mealy=1 moore=0 ← 1st detection, Mealy goes to S1! PASS [ 6] 1st 1101: Mealy DETECT (same cycle) | M=1 R=0 @51 in=1 | mealy=0 moore=1 ← Moore 1st detect, Mealy now in S2 PASS [ 7] bit5=1: Moore 1st DETECT, Mealy in S2 | M=0 R=1 PASS [ 8] bit6=0: in S3 now | M=0 R=0 @71 in=1 | mealy=1 moore=0 ← 2nd detection! Only 7 bits used! PASS [ 9] bit7=1: Mealy 2nd DETECT! (overlapping!) | M=1 R=0 PASS [10] Moore 2nd DETECT | M=0 R=1 — Test 3: 11011101 overlapping — PASS [11] 1st detect at bit4 | M=1 R=0 PASS [12] 2nd detect at bit8 | M=1 R=0 PASS [13] Moore 2nd detect confirmed | M=0 R=1 — Test 4: 1100111 — no detection — PASS [14] 1100111 = no detect | M=0 R=0 — Test 5: 11011011101 (3 Mealy detections) — PASS [15] 1st detect t4 | M=1 R=0 PASS [16] 2nd detect t7 (overlapping) | M=1 R=0 PASS [17] 3rd detect t11 (overlapping) | M=1 R=0======================================================= RESULTS: 17 / 17 PASS | 0 FAIL ======================================================= ✅ ALL TESTS PASSED

How to Run

Compile both overlapping FSMs and the testbench

# ── Icarus Verilog ────────────────────────────────────────────
iverilog -o ovlp_sim \
    seq_det_mealy_ovlp.v \
    seq_det_moore_ovlp.v \
    seq_det_ovlp_tb.v
vvp ovlp_sim
gtkwave seq_det_ovlp.vcd

# ── ModelSim ──────────────────────────────────────────────────
vlog seq_det_mealy_ovlp.v seq_det_moore_ovlp.v seq_det_ovlp_tb.v
vsim -c seq_det_ovlp_tb -do "run -all; quit -f"

🔬 Design Analysis

Complete Four-Way Comparison

Property	Mealy Non-OL (M25)	Moore Non-OL (M25)	Mealy Overlapping	Moore Overlapping
States	4 (S0–S3)	5 (S0–S4)	4 (S0–S3)	5 (S0–S4)
Post-detect state (in=1)	`S0`	`S0`	`S1`	`S1`
Post-detect state (in=0)	`S0`	`S0`	`S0`	`S0`
Detections in 1101101	1	1	2	2
Detections in 11011011101	2	2	3	3
Lines changed vs non-OL	—	—	1 line	1 line
Detection latency	Same cycle as last bit	+1 cycle	Same cycle as last bit	+1 cycle

When to Use Overlapping Detection

✅ Use Overlapping When

The same symbol sequence can appear back-to-back in the protocol
A detected frame marker can also serve as the start of the next frame
Maximum detection sensitivity is required (no missed consecutive patterns)
The pattern has a non-trivial KMP failure function (suffix that is also a prefix)

⚠️ Use Non-Overlapping When

Each detection should trigger a distinct action (counter, interrupt, state change)
The detected bits are consumed and must not contribute to the next detection
The protocol defines a minimum guard interval after each occurrence
Double-counting of overlapping patterns would cause incorrect behavior

The KMP connection: The overlapping FSM’s post-detection transition is exactly the KMP failure function applied to the full pattern. For pattern “1101”, the failure function at position 3 (the last character) gives failure[3]=1, meaning the FSM goes to state 1 (= S1). For a pattern with failure[last]=0 (e.g., “1010” → failure function gives 2, state S2), the post-detection state would be S2. This generalises: overlapping detector design is equivalent to building the KMP automaton for the pattern.

Pattern “1101” overlap depth = 1: Only the last ‘1’ of “1101” overlaps with the pattern start (“1…”). Compare this to pattern “1010” where failure[3]=2 — the last two bits “10” overlap with the start “10”, giving the FSM more reuse. Patterns with longer overlaps (like “1001001” where the last “001” = first “001”) produce more aggressive overlapping behaviour and more complex post-detection transitions.