State Reduction & Assignment
Merge equivalent states to shrink the machine, then assign binary codes to states.
Description
Removing redundant states, then encoding the remaining states in binary. Fewer states → fewer flip-flops and simpler logic; good encoding cuts gate count. Find equivalent states (same outputs + same next states) and merge; then pick codes.
- Two states are equivalent if, for every input, they give the same output and go to equivalent states.
- Merge equivalent states — m states may need fewer flip-flops (⌈log₂ m⌉).
- Assign a unique binary code to each state.
- Binary, Gray, and one-hot are common; the choice affects logic complexity.
- One-hot uses more flip-flops but simpler, faster next-state logic (good for FPGAs).
- What: Removing redundant states, then encoding the remaining states in binary.
- Why: Fewer states → fewer flip-flops and simpler logic; good encoding cuts gate count.
- How: Find equivalent states (same outputs + same next states) and merge; then pick codes.
- Where: FSM optimization before implementation.
- When: After the state diagram, before deriving flip-flop logic.
At a glance
What
Removing redundant states, then encoding the remaining states in binary.
Why
Fewer states → fewer flip-flops and simpler logic; good encoding cuts gate count.
How
Find equivalent states (same outputs + same next states) and merge; then pick codes.
Where
FSM optimization before implementation.
When
After the state diagram, before deriving flip-flop logic.
Think of it like…
Reduction is like merging duplicate contacts in your phone; assignment is choosing each merged contact's speed-dial number — a smart number scheme makes dialing (logic) easier.
State reduction
- Two states are equivalent if, for every input, they give the same output and go to equivalent states.
- Merge equivalent states — m states may need fewer flip-flops (⌈log₂ m⌉).
State assignment
- Assign a unique binary code to each state.
- Binary, Gray, and one-hot are common; the choice affects logic complexity.
- One-hot uses more flip-flops but simpler, faster next-state logic (good for FPGAs).
Encoding styles
| Style | Flip-flops for n states | Note |
|---|---|---|
| Binary | ⌈log₂ n⌉ | fewest FFs |
| Gray | ⌈log₂ n⌉ | one bit changes per step |
| One-hot | n | simplest, fastest logic |
The 5 Whys
- 1
Why reduce states? Fewer states need fewer flip-flops.
- 2
Why fewer flip-flops? Less area and simpler next-state logic.
- 3
Why does assignment matter? The codes shape the combinational logic cost.
- 4
Why one-hot on FPGAs? Plentiful flip-flops + faster, simpler decoding.
- 5
Root cause: minimizing and encoding states directly minimizes the final hardware.
Cheat sheet
Working principle
- Find equivalent states (same outputs + same next states) and merge; then pick codes.
- Removing redundant states, then encoding the remaining states in binary.
Key facts
- Two states are equivalent if, for every input, they give the same output and go to equivalent states.
- Assign a unique binary code to each state.
Why it exists
- Root cause: minimizing and encoding states directly minimizes the final hardware.