101 sequence detector: overlapping Moore FSM, live
A 101 sequence detector reads one bit of X per clock and raises Z when the last three bits were 1, 0, 1. This Moore version allows overlap, so 10101 counts twice, and needs only two D flip-flops: Q0+ = X, Q1+ = X'Q0 + XQ1Q0', and Z = Q1Q0.
The four states record how much of the pattern has arrived: A (00) nothing useful, B (01) "1", C (10) "10" and D (11) "101", the only state with Z = 1. Overlap decides what happens after a hit: from D, a 1 means the newest bit can start a new pattern (go to B), and a 0 means "10" is already in place (go to C), so 10101 finds two hits sharing the middle 1. With this state assignment the next-state logic is small: Q0 simply stores the latest bit (Q0+ = X), Q1 becomes 1 after a 0 that follows a 1 (X'Q0) or after a 1 that completes 101 from state C (XQ1Q0'), and Z = Q1 AND Q0 depends only on the state, which is what makes it a Moore machine. Each D input is ANDed with NOT CLR, a synchronous clear to state A. The longer 1011 sequence detector uses the same method with five states, and the Mealy machine page shows the Mealy alternative.
Open this circuit in the lab →
What you need
- 2× D flip-flop: the state Q1 Q0, on one clock
- 1× NOT: X'
- 1× NOT: Q0'
- 3× AND: X'Q0, Q1Q0' and XQ1Q0'
- 1× OR: Q1+ = X'Q0 + XQ1Q0'
- 1× AND: Z = Q1 Q0
- 3× AND, NOT: synchronous clear: NOT CLR and each D ANDed with it
Step by step
- Assign the states: A = 00, B = 01, C = 10, D = 11, with Z = 1 only in D.
- Write the state table (below) and read off the equations: Q0+ = X and Q1+ = X'Q0 + XQ1Q0'.
- Wire two D flip-flops on one clock: D0 = X, and D1 from two ANDs and an OR.
- AND each D input with NOT CLR, and probe Z = Q1 AND Q0.
- Clear once, then feed X = 1, 0, 1, 0, 1: Z goes high after the third bit and again after the fifth.
101 detector state table
| State | Seen so far | X = 0 goes to | X = 1 goes to | Z |
|---|---|---|---|---|
| A (00) | nothing | A | B | 0 |
| B (01) | 1 | C | B | 0 |
| C (10) | 10 | A | D | 0 |
| D (11) | 101 | C | B | 1 |
Before the page is built, the live circuit runs 18 clocks of a test stream with overlapping hits (10101), a near miss (1001) and a final hit, and Z, Q1 and Q0 are checked after every clock.
You can also read the full theory in the lesson on sequence detectors. Prefer to build it yourself from scratch? Open the digiwleea lab and place the gates on the canvas, or start from the logic gate simulator.
More builds: State machines
All 246 build guides, by topic
Each of these is one step from a transistor to a working CPU. Build every gate from CMOS transistors and work all the way up in the free digiwleea lab, with the free theory reference alongside.
Open the 101 sequence detector in the lab →Frequently asked
How many flip-flops does a 101 sequence detector need?
Two for the Moore version: it has four states (nothing, 1, 10, 101), and two flip-flops give exactly four. The Mealy version needs only three states but still two flip-flops.
What is an overlapping sequence detector?
One that lets the end of a match start the next one. For 101, the stream 10101 gives two hits because the middle 1 ends the first 101 and begins the second.
What is the difference between a Moore and a Mealy 101 detector?
The Moore detector's output depends only on its state, so Z rises one clock after the last bit, in a dedicated state. The Mealy detector's output also depends on the current input, so it needs one state fewer and signals during the last bit.