Overlapping 101 Sequence Detector
Two D flip-flops and combinational logic implement a Mealy machine that recognizes overlapping 101 patterns. Because the output depends on current state and current input, it can change between clock edges and requires a defined sampling convention downstream.
This Mealy finite-state machine watches one serial input and asserts its output when the most recent three-bit window is 101, including overlapping occurrences.
What You'll Learn
- Define states from the useful suffixes of the target pattern 101.
- Derive Q0(next) = X, Q1(next) = Q0X̅, and Detected = Q1X.
- Trace state transitions for arbitrary serial input sequences.
- Explain how retaining suffix 1 enables overlapping detections.
- Distinguish a Mealy output from a registered or Moore-style output.
How It Works
Two D flip-flops encode the machine's recent input history. Q0(next) = X, so Q0 remembers the latest sampled bit. Q1(next) = Q0·X̅, so Q1 becomes HIGH after the sampled suffix 10. The combinational Mealy output is Detected = Q1·X.
Starting from Q1Q0 = 00, sampling 1 produces 01. Sampling 0 next produces 10, which means the required prefix 10 has been observed. When the current X then becomes 1, Q1·X asserts the detector immediately; the next edge captures state 01. Retaining suffix 1 after detection permits overlap: stream 10101 asserts on both the third and fifth bits.
Because the output depends on current state and current input, it can change when X changes between clock edges. A synchronous receiving system must sample it according to a defined timing convention, or register the output if a full-cycle pulse is required. The complete transition table includes state 11 for logical completeness even though reset-state operation through this network does not normally enter it.
Truth Table
Inputs are current Q1, current Q0, and X; outputs are next Q1, next Q0, and the current Mealy detection output. State 11 is included although it is not part of the normal reset-reachable set.
| Inputs | Output | |||||
|---|---|---|---|---|---|---|
| Current Q1 | Current Q0 | X | Next Q1 | Next Q0 | Detected 101 | |
| 0 | 0 | 0 | 0 | 0 | 0 | No useful suffix has been observed and X remains 0. |
| 0 | 0 | 1 | 0 | 1 | 0 | Sampling 1 retains the one-bit suffix needed to begin 101. |
| 0 | 1 | 0 | 1 | 0 | 0 | Current suffix 1 followed by 0 forms prefix 10. |
| 0 | 1 | 1 | 0 | 1 | 0 | Another 1 restarts the useful suffix at 1. |
| 1 | 0 | 0 | 0 | 0 | 0 | From prefix 10, input 0 abandons the partial match. |
| 1 | 0 | 1 | 0 | 1 | 1 | From prefix 10, current input 1 completes 101 and retains suffix 1. |
| 1 | 1 | 0 | 1 | 0 | 0 | The normally unreachable 11 state with X = 0 moves to prefix state 10. |
| 1 | 1 | 1 | 0 | 1 | 1 | The normally unreachable 11 state also satisfies Q1X and asserts detection for X = 1. |
Boolean Expression
Q0 records the current serial input on the next rising edge.
Q1 records that the previous sampled bit was 1 and the current sampled bit is 0.
The Mealy output asserts when the stored prefix 10 is followed by current input 1.
Try It Step-by-Step
Set the listed controls in the embedded circuit, then compare the observed modeled state with the expected result.
- 1Clock=one rising edge per bitInitial state=reload templateX sequence=1, 0Expected:
State Q1 Q0 = 10; Detected 101 = 0What you'll see:After sampling 1 then 0, Q1Q0 = 10 encodes the partial match. The target is not complete yet. - 2Clock=observe before and after the next rising edgeX=1Expected:
Detected 101 becomes HIGH when X = 1; after the edge Q1 Q0 = 01What you'll see:Setting X to 1 makes Q1X true, so the detector asserts before the edge. The edge then retains the suffix 1 as state 01. - 3Clock=one rising edge per bitContinuation=0, 1Expected:
The fifth bit completes a second detection in the overlapping stream 10101What you'll see:Sampling 0 establishes prefix 10 again; the following 1 completes a second occurrence that shares the middle 1 with the first occurrence. - 4Clock=one rising edge per bitInitial state=reload templateX sequence=1, 1, 1Expected:
Detected 101 remains LOW for the stream 111What you'll see:Without an intervening 0, Q1 never records prefix 10, so three consecutive 1s do not match 101.
Components Used
Applications and Design Context
Serial framing and preamble recognition. State machines identify short synchronization or command patterns in incoming bit streams.
Protocol control. A detector can trigger parsing when a defined control sequence arrives.
Digital locks and event sequences. The same state-machine method recognizes ordered input histories rather than simultaneous levels.
Streaming hardware. FPGA and ASIC datapaths use compact FSMs to recognize token boundaries and bit-level markers.
Formal design education. The circuit connects a pattern specification to state encoding, next-state equations, and a Mealy output.
Frequently Asked Questions
Why are two D flip-flops sufficient?
The detector needs to distinguish three useful history states: no match, suffix 1, and suffix 10. Two state bits can encode at least three states.
What makes this a Mealy machine?
Detected depends on both stored state Q1 and the current input X. A Moore output would depend only on registered state and would normally require an additional detection state or different timing.
What does overlapping detection mean?
The ending 1 of one match can be the starting 1 of the next. In 10101, windows 1–3 and 3–5 are both 101, so the detector asserts twice.
Can the output change between clock edges?
Yes. While Q1 is HIGH, changing X changes the AND-gate output combinationally. Register the output or define a precise sampling point if downstream logic requires a clock-aligned pulse.
How would I detect a different pattern?
Create states for every useful prefix of the target pattern, define transitions for X = 0 and X = 1, choose Mealy or Moore output timing, assign state bits, and synthesize the resulting next-state and output equations.