State Encoding and Minimization Techniques

In this lesson, you will learn how to shrink complex state machines by removing redundant behaviors and how to assign binary codes to your states to minimize the hardware logic required to implement them.

State Minimization

A Finite State Machine (FSM) might accidentally have two states that behave exactly the same way. If two states produce the same output for every possible input and transition to the same next state, they are equivalent.

We can use the Row Matching Method to simplify these machines. Imagine a state table where two rows have identical outputs and destination states. If we find such a pair, we can delete one row and point all transitions that previously led to the deleted state toward the remaining one. This reduces the number of flip-flops needed in our hardware, as fewer bits are required to identify unique states.

State Encoding

Once we have the minimum number of states, we must represent them in binary. If you have $N$ states, you need at least $k = \lceil \log_2 N \rceil$ flip-flops. However, the assignment of those binary patterns (e.g., $S_0=00, S_1=01, S_2=10$) drastically changes the complexity of your combinational logic.

Common encoding strategies include:

1. Binary Encoding: Uses the minimum number of flip-flops. This saves space but can lead to complex decoding logic.
2. One-Hot Encoding: Uses one flip-flop per state (e.g., $S_0=001, S_1=010, S_2=100$). While it uses more flip-flops, it often simplifies the next-state logic because the transition conditions become simpler to extract from the bits.

Consider a 3-state machine where we choose One-Hot:

State | Flip-Flops (Q2 Q1 Q0)
S0    | 0 0 1
S1    | 0 1 0
S2    | 1 0 0

By selecting specific patterns, you can often make the logic expressions for your inputs fall into nice patterns on a Karnaugh Map, allowing you to use fewer logic gates. In practice, we evaluate the "cost" of the logic gates versus the "cost" of adding an extra flip-flop to decide which encoding style to prioritize.

Key Takeaway: State minimization reduces the number of states to the absolute essential, while clever state encoding allows you to trade off flip-flop count against the complexity of your combinational logic gates.