Sequence Detectors

When detecting a pattern like "101" in a stream, how you handle reused bits defines the architecture.

• Non-Overlapping: Once a pattern is detected, the machine resets. Bits cannot be reused.
  Input: 1 0 1 0 1
  Output: 0 0 1 0 0 (Only the first "101" is counted. The final "1" is start of new, but middle "01" is skipped).
• Overlapping: The last bits of a detected pattern can serve as the start of the next pattern.
  Input: 1 0 1 0 1
  Output: 0 0 1 0 1 (Detects at index 3 and index 5).

State Diagram Logic

We need to track progress: `S0` (Reset), `S1` (Saw '1'), `S2` (Saw '10'), `S3` (Saw '101').

• If in `S3` ('101') and receive '1': Pattern '1011' Complete! Go to `S1` (since final '1' can start next sequence).
• If in `S3` ('101') and receive '0': Sequence broken, but '10' is valid start. Go to `S2`.

module seq_det_1011 (
    input  wire clk, rst_n,
    input  wire data_in,
    output reg  detected
);
    parameter S0 = 2'b00, // Idle
              S1 = 2'b01, // Saw 1
              S2 = 2'b10, // Saw 10
              S3 = 2'b11; // Saw 101
    reg [1:0] state, next_state;
    // State Register
    always @(posedge clk or negedge rst_n) begin
        if (!rst_n) state <= S0;
        else        state <= next_state;
    end
    // Next State & Output Logic (Mealy)
    always @(*) begin
        next_state = state;
        detected   = 1'b0;
        case (state)
            S0: next_state = data_in ? S1 : S0;
            S1: next_state = data_in ? S1 : S2; // 1->1 (Stay), 1->0 (Go S2)
            S2: next_state = data_in ? S3 : S0; // 10->1 (Go S3), 10->0 (Reset)
            S3: begin
                if (data_in) begin
                    detected = 1'b1; // Output goes High IMMEDIATELY
                    next_state = S1; // '1' is consumed for next pattern
                end else begin
                    next_state = S2; // '10' is potential start
                end
            end
        endcase
    end
endmodule