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.
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.
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.
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.
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).
// 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
// 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
| 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 |
| Current State | Matched prefix | Input = 0 | Input = 1 | ||
|---|---|---|---|---|---|
| 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.
// ============================================================ // 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
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.
| Current State | Output | Matched prefix | Next State | |
|---|---|---|---|---|
| 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).
// ============================================================ // 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
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.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.
// ============================================================ // 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
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.
# ── 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"
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.| 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 |