Topic 8 of 13
State Machines & Sequential Circuit Design
Describe behaviour as states and transitions, reduce it, and turn it into flip-flops and gates.
← → move between slides · F full screen · M slide list
Before we start
Why this matters
How does a vending machine know you've paid exactly 75 cents, without caring one bit whether you fed it three quarters or fifteen sweaty nickels?
It isn't doing your maths homework — it just tracks which state it's in (0¢, 25¢, 50¢, 75¢…) and hops to the next one per coin, forgetting the coins the instant they're counted. That's a finite state machine, and the same trick runs traffic lights, video-game bosses, and your Wi-Fi's slightly awkward opening handshake.
Outline
Topics in this chapter
Select a topic to jump to the slide that explains it.
- States, state tables, and state diagrams
- Moore vs. Mealy machines
- State reduction
- Equivalent states
- State assignment
- Number of flip-flops
- Sequential circuit design procedure
- D, JK, and T flip-flop design
- Excitation equations
- K-map-based sequential design
- Sequence detectors
- Overlapping sequences
- Unused states and recovery
- FSM applications
Concept 1 of 4
States and machine types
A state is the stored condition of the system. A state diagram draws states as circles and transitions as arrows labelled with the input (and output). A state table lists present state, input, next state and output.
- Moore machine: output = f(present state). Outputs are attached to states.
- Mealy machine: output = f(present state, input). Outputs are attached to transitions and can react to the input immediately. Mealy machines often need fewer states.
N states need at least ⌈log₂N⌉ flip-flops. Five states need 3, ten states need 4.
Concept 1 of 4
States and machine types (cont.)
Concept 2 of 4
State reduction
Two states are equivalent if, for every input, they give the same output and go to the same or equivalent states. Equivalent states can be merged, which saves flip-flops and logic. Procedure: build the state table, find rows that match, merge them (replace the removed state everywhere), and repeat until nothing more merges.
Concept 3 of 4
Design procedure
- Specification, then identify states.
- State diagram and state table.
- State reduction.
- State assignment (binary codes for states).
- Choose flip-flop type (D is often easiest, since D = next state).
- Derive excitation equations from the state table, using the excitation table for JK or T.
- Simplify with K-maps, draw the circuit, verify every transition and the reset behaviour.
Unused states appear when 2n exceeds the number of states. They can be treated as don’t-cares, but the design should be checked so that it returns to a valid state instead of locking up.
Concept 4 of 4
Sequence detectors
A sequence detector watches a serial input and raises its output when a target pattern, such as 101, appears. It must remember recent bits, so it needs states. With overlapping detection, the tail of one match can begin the next: 10101 contains two matches of 101. Try both machine types in the demo below and look at the D flip-flop equations it derives.
Concept 4 of 4
Sequence detectors (cont.)
Truth tables
Truth tables (1 of 3)
101 detector, Moore (overlapping)
| Present state | x = 0 | x = 1 | Output y |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 |
101 detector, Mealy (overlapping)
| Present state | x = 0 → next / y | x = 1 → next / y |
|---|---|---|
| S0 | S0 / 0 | S1 / 0 |
| S1 | S2 / 0 | S1 / 0 |
| S2 | S0 / 0 | S1 / 1 |
Truth tables
Truth tables (2 of 3)
Flip-flops needed for N states
| States N | Flip-flops ⌈log₂N⌉ |
|---|---|
| 2 | 1 |
| 3 | 2 |
| 4 | 2 |
| 5 | 3 |
| 8 | 3 |
| 9 | 4 |
| 10 | 4 |
| 16 | 4 |
| 17 | 5 |
Truth tables
Truth tables (3 of 3)
The 7-state table from Worked example 2, before and after merging equivalent states, with a binary code assigned to each surviving state.
Before reduction (7 states)
| Present state | Next, x=0 | Next, x=1 | Out, x=0 | Out, x=1 |
|---|---|---|---|---|
| a | a | b | 0 | 0 |
| b | c | d | 0 | 0 |
| c | a | d | 0 | 0 |
| d | e | f | 0 | 1 |
| e | a | f | 0 | 1 |
| f | g | f | 0 | 1 |
| g | a | f | 0 | 1 |
After reduction, with binary assignment (5 states)
| Present state | Next, x=0 | Next, x=1 | Out, x=0 | Out, x=1 |
|---|---|---|---|---|
| a 000 | a 000 | b 001 | 0 | 0 |
| b 001 | c 010 | d 011 | 0 | 0 |
| c 010 | a 000 | d 011 | 0 | 0 |
| d 011 | e 100 | d 011 | 0 | 1 |
| e 100 | a 000 | d 011 | 0 | 1 |
Interactive
Demo: 101 sequence detector
Worked example 1 of 3
Worked example 1
Show the solution
- 23 = 8 < 10 ≤ 24 = 16.
- 4 flip-flops.
Worked example 2 of 3
Worked example 2
Show the solution
- g matches e (same next states and outputs). Remove g and replace it with e.
- Now f has next states e,f and d has e,f with the same outputs, so f ≡ d. Replace f with d.
- States a, b, c, d, e remain: 7 states become 5, saving one flip-flop (3 still needed, but simpler logic).
Worked example 3 of 3
Worked example 3
Show the solution
- x = 1: A(t+1) = 1·(0+0) = 0, B(t+1) = 1·1 = 1, y = 0·(0+0) = 0. State becomes A=0, B=1.
- x = 0: A(t+1) = 0, B(t+1) = 0, y = 1·(0+1) = 1. State becomes A=0, B=0.
- x = 1: A(t+1) = 0, B(t+1) = 1, y = 0·(0+0) = 0. State becomes A=0, B=1.
Practice
Practice (1 of 2)
Try each one on paper first, then check your answer.
Show the answer
Show the answer
Show the answer
Practice
Practice (2 of 2)
Try each one on paper first, then check your answer.
Show the answer
Build the 101 detector from D flip-flops using the equations from the simulator.
Gate ForgeA free circuit simulator — place and wire gates, generate truth tables and timing diagrams, and work through 90+ guided problems.Check yourself
Quiz
Summary
Summary
- Moore output depends on state. Mealy output depends on state and input.
- Flip-flops needed = ⌈log₂N⌉.
- Merge equivalent states before assigning codes.
- With D flip-flops, the D input equals the next-state bit.
- Check unused states for lock-up.