Sequence detector (FSM design example)

A sequence detector is a finite state machine that watches a serial input bit by bit and asserts an output when it sees a target pattern. The design walkthrough below uses one as a worked example for the standard FSM design flow — useful for any FSM, not just sequence detection.

The target: detect two or more consecutive $1$s on input $w$. When the input has been $1$ for at least two consecutive cycles, output $z$ should be $1$.

The standard FSM design steps

1. Obtain circuit specification — what should the circuit do?
2. Derive a State diagram — graphical representation of states and transitions.
3. Create a State table — tabular form of the diagram.
4. Minimize states (see State Reduction).
5. Perform State Assignment — assign binary codes to states.
6. Choose a flip-flop type (D, T, or JK).
7. Derive next-state logic — Boolean expressions for the flip-flop inputs.
8. Derive output logic — Boolean expressions for the outputs.
9. Implement the circuit — draw the final schematic.

This is the universal flow. Every FSM you build follows the same steps; only the specifics of each step change.

The walkthrough below executes those nine steps for this sequence detector. Step 1 (specification) is the prose paragraph above. Step 4 (state reduction) is skipped — the three states identified are already minimal. The remaining steps map onto the section headers:

9-step	Section heading below
2	State diagram
3	State table
5	State assignment
6, 7, 8	Choose flip-flop type and derive logic
9	Final implementation

Step 2 — State diagram

Three states are needed: A (no recent 1s, the reset state), B (just saw one 1), and C (have seen two consecutive 1s — output asserted).

Reading: from A on input 0 stay; on input 1 go to B. From B on 0 return to A; on 1 advance to C. From C on 0 return to A; on 1 stay at C.

The output $z$ is associated with the state (Moore machine style): $A:z=0$, $B:z=0$, $C:z=1$.

Step 3 — State table

Present state	Next ($w=0$)	Next ($w=1$)	Output $z$
A	A	B	0
B	A	C	0
C	A	C	1

Step 5 — State assignment

Three states need 2 bits. Use $y_2{y}_1$ as the state variables, encoded as:

State	$y_2{y}_1$
A	00
B	01
C	10

The fourth pattern $11$ is unused (a don’t-care).

Steps 6, 7, 8 — Choose flip-flop type and derive logic

Pick D flip-flops — they make the next-state logic the simplest, since $D=$ next-state value directly.

State-assigned table:

Present $y_2{y}_1$	Next ($w=0$)	Next ($w=1$)	$z$
A: 00	00	01	0
B: 01	00	10	0
C: 10	00	10	1
11 (don’t care)	dd	dd	d

Now build K-maps for $Y_1$, $Y_2$, and $z$ (each as a function of $w,y_2,y_1$).

Reading off the K-maps (with don’t-cares used to enlarge groups):

$Y_1=w\overline{y_1}\overline{y_2}$

$Y_2=w(y_1+y_2)$

$z=y_2$

The output happens to collapse to just $y_2$ — the second state bit is the output. That’s a consequence of the lucky state assignment.

The general structure of the FSM:

Two flip-flops hold the state; combinational logic feeds their D inputs from $w$ and the current state; another piece of combinational logic produces $z$ (here trivially: $z=y_2$).

Step 9 — Final implementation

The completed circuit:

• $D_1=w\overline{y_1}\overline{y_2}$ — small AND chain.
• $D_2=w(y_1+y_2)$ — OR followed by AND.
• $z=y_2$ — direct wire.
• Both flip-flops share a clock and a Resetn (asynchronous reset, active low) input that initializes the FSM to state A on power-up.

Lessons from the example

• A state diagram is the right place to start. Don’t go to logic until you’ve drawn one.
• State assignment matters. The choice $A=00,B=01,C=10$ made $z=y_2$ — a different assignment would have required gates for $z$.
• Don’t-cares from unused state codes can simplify the next-state logic substantially. Use them in K-map grouping.
• D flip-flops + K-map minimization is the simplest path. T or JK can save a gate or two but rarely justify the complexity.

For variations of this problem and other FSM patterns (vending machine, traffic light, parity checker), the same nine-step flow applies — only the state diagram changes.