Verilog Designs · Module 26

Leave a Comment / By
Verilog Designs — Sequence Detector 1101 Overlapping (Mealy & Moore) — VLSI Trainers
Verilog Designs · Module 26

Sequence Detector — 1101

Mealy Machine & Moore Machine · Overlapping

Complete overlapping FSM design for 1101 — after each detection, the FSM reuses the longest suffix of the detected sequence that can start a new match, enabling back-to-back detections in streams like 11011011101.

🔄 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

1
t=1
1
t=2
0
t=3
1
t=4 ★
1
t=5
0
t=6
1
t=7 ★
0
t=8
1
t=9
1
t=10
0
t=11
1
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)
S0 initial S1 got “1” S2 got “11” S3 got “110” 0/0 1/0 0/0 1/0 1/0 0/0 1/1 → S1 ★ OVERLAPPING! 0/0 ★ This arc changed from Non-Overlapping S3+1/1 → S1 (was → S0)

Mealy Overlapping State Transition Table

Current State Matched prefix Input = 0 Input = 1
Next StateOutput Next StateOutput
S0“” S00 S10
S1“1” S00 S20
S2“11” S30 S20
S3“110” S00 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

1
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)
S0 out=0 S1 out=0 S2 out=0 S3 out=0 S4 out=1 DETECT 0 1 0 1 1 0 1 0 0 → S0 1 → S1 ★ OVERLAPPING! ★ Changed from non-overlapping: S4+input=1 → S1 (was → S0). S4+input=0 → S0 unchanged.

Moore Overlapping State Transition Table

Current State Output Matched prefix Next State
Input = 0Input = 1
S00“” S0S1
S10“1” S0S2
S20“11” S3S2
S30“110” S0S4
S41 ← 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

2
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)

PropertyNon-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.

TB
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
clk in state(M) mealy moore 0 10 20 30 40 50 60 70 80 1 1 0 1★ 1 0 1★ 0 S0 S1 S2 S3 S1←reuse S2 S3 S0 1 DETECT #1 1 DETECT #2 0 1 DETECT #1 1 DETECT #2 0 Mealy detect #1 Mealy detect #2 ★ reused ‘1’

💻 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

PropertyMealy Non-OL (M25)Moore Non-OL (M25)Mealy OverlappingMoore Overlapping
States 4 (S0–S3)5 (S0–S4) 4 (S0–S3)5 (S0–S4)
Post-detect state (in=1) S0S0 S1S1
Post-detect state (in=0) S0S0 S0S0
Detections in 1101101 11 22
Detections in 11011011101 22 33
Lines changed vs non-OL —— 1 line1 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.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top