How to build a 1011 sequence detector (Moore, overlapping)

A 1011 sequence detector is a finite state machine that reads one bit of X per clock and raises its output Z after the last four bits were 1, 0, 1, 1. This Moore version has five states, needs three D flip-flops, and allows overlap, so 1011011 counts twice.

Each state records how much of the pattern has arrived so far: S0 nothing useful, S1 "1", S2 "10", S3 "101" and S4 "1011", the only state with Z = 1. A wrong bit does not always mean starting over. From S3 ("101") a 0 makes "1010", whose last two bits "10" are still a start, so the machine goes to S2, not S0. Overlap works the same way: after a hit, a 1 makes the latest "1" the start of the next pattern (S1) and a 0 makes "10" (S2). In a Moore machine the output depends only on the state, so Z rises on the clock edge that reads the final 1 and stays high for exactly one clock. In the live circuit CLR starts on and holds the machine in S0: turn it off, then set X before each clock tick and watch the state bits Q2 Q1 Q0 walk through the diagram.

Big circuit: pinch, scroll or tap + to zoom in, then drag to move around.

Live circuit: click the inputs to toggle them and watch the outputs update. It runs the real simulator, right here on the page.

Open this circuit in the lab →

What you need

3× D flip-flop: the state Q2 Q1 Q0 (five states need three bits)
2× AND: D2 = Q1 Q0 X: from S3, a 1 completes the pattern
3× AND: the two terms of D1, X' (Q0 + Q2) and X Q1 Q0'
2× OR: Q0 + Q2, and the OR that joins the two D1 terms
1× NAND: NAND(Q1, Q0), which is 0 only in S3
1× AND: D0 = X AND NAND(Q1, Q0): a 1 leads to S1 or S3, both odd codes, except from S3
3× AND: masking each D input with NOT CLR (synchronous reset)
3× NOT: X', Q0' and NOT CLR

Step by step

Draw the state diagram: S0 to S4 as above, with a 0 and a 1 arrow leaving every state. Mark Z = 1 inside S4 only (Moore).
Assign codes S0 = 000, S1 = 001, S2 = 010, S3 = 011, S4 = 100 (Q2 Q1 Q0). Then Z is simply Q2.
Fill the state table below and treat the unused codes 101, 110 and 111 as don't-cares. The K-maps give D2 = Q1 Q0 X, D1 = X'(Q0 + Q2) + X Q1 Q0' and D0 = X (Q1 Q0)'.
Build those three equations, AND each one with NOT CLR so a clock with CLR high returns to S0, and wire them to the D inputs of three flip-flops on one clock.
Probe Z and the state bits. Clear, then feed 1, 0, 1, 1 one bit per clock: Z goes to 1 for one clock. Feed 0, 1, 1 next and it fires again, using the last 1 of the first match.

State table

State	Q2 Q1 Q0	Next if X = 0	Next if X = 1	Z
S0 (nothing)	000	S0	S1	0
S1 (1)	001	S2	S1	0
S2 (10)	010	S0	S3	0
S3 (101)	011	S2	S4	0
S4 (1011)	100	S2	S1	1

The run checked before the page is built clears the machine, feeds the 20-bit stream 10110111010110010110 and compares Z and all three state bits with this table at every clock. Z fires after bits 4, 7, 13 and 19: the second hit overlaps the first (1011011), and the 1010 in bits 8 to 11 correctly does not fire.

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.

Build more parts from gates

half adder full adder half subtractor full subtractor 2:1 multiplexer 4:1 multiplexer XOR gate from NAND gates 2-to-4 decoder SR latch D flip-flop JK flip-flop T flip-flop 4-bit shift register 4-bit ripple carry adder D latch 1-to-4 demultiplexer 4-bit magnitude comparator 4-bit ring counter 4-bit Johnson counter 4-to-2 priority encoder 4-bit synchronous counter 3-to-8 decoder 8-to-1 multiplexer 4-bit carry lookahead adder half adder from NAND gates 2-bit comparator BCD to 7-segment decoder 4-bit up/down counter decade counter 2-bit multiplier 4-bit ALU 4-bit array multiplier NOT, AND, OR and NOR from NAND NOT, OR, AND and XOR from NOR full adder from NAND gates SR latch from NAND gates parity generator and checker 4-bit adder/subtractor BCD adder 4-bit universal shift register mod-6 counter 4-bit ripple counter binary to Gray code converter half adder from NOR gates full adder from NOR gates 4-bit register with parallel load binary to BCD converter D flip-flop from NAND gates 1-bit ALU CMOS inverter CMOS NAND gate CMOS NOR gate PISO shift register SR flip-flop from NAND gates BCD to excess-3 code converter

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 1011 sequence detector in the lab →

Frequently asked

What is a sequence detector?

A clocked finite state machine that watches a serial input one bit per clock and raises its output when a chosen bit pattern has just arrived. It is designed like any state machine: state diagram, state table, state codes, then next-state and output equations.

How many flip-flops does a 1011 sequence detector need?

The Moore version has five states (nothing, 1, 10, 101, 1011), so it needs three flip-flops. The Mealy version needs only four states, because the output is produced on the transition out of 101, so two flip-flops are enough.

What is the difference between a Moore and a Mealy sequence detector?

A Moore detector's output depends only on its state, so it changes only on clock edges and lasts one full clock. A Mealy detector's output depends on the state and the current input, so it can fire in the same clock as the last bit with one state fewer, but it can also glitch if the input changes mid-cycle.

What does overlapping mean in a sequence detector?

That the end of one match can be the start of the next. With overlap, 1011011 contains two matches because the 1 in the middle is shared. A non-overlapping detector returns to the start state after every hit and would find only the first one.