Capstone: an overlapping 101 pattern detector

Fix the requirements first

Accept one bit_in at rising edges^{iRising edge The instant at which the clock changes from 0 to 1. Distinguish it from a level, which refers to the entire interval during which CLK=1. Learn more} with valid=1. If the accepted sequence ends in 101, assert hit for one cycle after that edge. Overlap is allowed, so 10101 must assert hit on its third and fifth accepted bits. With valid=0, hold state and clear hit; reset initializes both state and hit.

Store only the necessary history

S0 means no matching prefix, S1 means the sequence ends in 1, and S10 means it ends in 10. After completing 101, the final 1 can start the next match, so return to S1.

Each column below records a rising edge. Inputs are pre-edge; states labeled “after” are post-update. Alignment shows sampling order, not physical propagation delay^{iPropagation delay The time from an input change until the output settles to the correct value. Logical equivalence and timing behavior are separate properties. Learn more}. Start at S0 after reset, with valid=1 in every column. Retaining S1 after detecting the third bit enables another detection at the fifth.

Implement a registered detection output

module pattern_101 (
  input logic clk, rst, valid, bit_in,
  output logic hit
);
  typedef enum logic [1:0] {S0, S1, S10} state_t;
  state_t state;
  always_ff @(posedge clk) begin
    if (rst) begin
      state <= S0;
      hit <= 1'b0;
    end else begin
      hit <= 1'b0;
      if (valid) begin
        case (state)
          S0: state <= bit_in ? S1 : S0;
          S1: state <= bit_in ? S1 : S10;
          S10: begin
            state <= bit_in ? S1 : S0;
            hit <= bit_in;
          end
          default: state <= S0;
        endcase
      end
    end
  end
endmodule

hit stores in a register^{iRegister A circuit that stores multiple bits of state. The synchronous registers in this course store their specified inputs at a clock edge. Learn more} a result computed from state and the input accepted at that edge. Unlike a simple combinational Mealy output, it does not immediately react to bit_in changes between edges. Review this example as general SystemVerilog; supported syntax and execution evidence for the provided single-clock lab engine must be checked separately.

Compute acceptance criteria independently

Build a reference model by collecting only accepted bits into a string and, once its length is at least three, testing whether its last three characters are 101. There is no need to copy the FSM^{iState machine A model that determines the next state and outputs from stored state and inputs. Define state transitions, outputs and reset rules together. Learn more} state encoding.

• 101 → hit at position 3
• 10101 → hit at positions 3 and 5
• 11101 → hit at position 5
• 1001 → no detection
• 1,0, then reset, then 1 → no detection
• Insert valid=0 between or after 1,0 → unchanged results by accepted-input number

The bit-sequence exercise below checks continuous valid inputs. Do not interpret it as also verifying reset, valid stalls or physical timing.