State Assignment Strategies
The State Assignment Problem
State assignment is the mapping of symbolic state names to binary codes. For a machine with m states, the trivial requirement is ⌈log₂ m⌉ FFs. But how you assign the codes dramatically affects the complexity of the resulting next-state logic. The same FSM with a different state assignment can produce equations ranging from a single gate to a multi-level network. There is no universally optimal algorithm suitable for manual execution; the strategies below represent practical heuristics.
Strategy 1: Sequential (Binary) Assignment
Assign states in increasing natural binary order: S₀ = 000, S₁ = 001, S₂ = 010, S₃ = 011, etc. This is the default assignment and is simple, but often suboptimal: the binary codes of adjacent states in the state diagram may differ in multiple bits, requiring complex next-state logic.
Example: For a divide-by-5 counter using 3 FFs (c, b, a):
| State | c b a |
|---|---|
| S₀ | 0 0 0 |
| S₁ | 0 0 1 |
| S₂ | 0 1 0 |
| S₃ | 0 1 1 |
| S₄ | 1 0 0 |
The next-state equations (derived via K-maps with unused states 101, 110, 111 as don’t-cares):
These are moderately complex (2, 2, and 1 gates respectively). FF a requires a 2-input AND with an inverter; FF b requires an XOR; FF c requires a 2-input AND.
Strategy 2: Sliding (Gray-Code-Like) Assignment
Assign codes such that adjacent states in the state diagram differ in only one bit. This is inspired by Gray coding: transitions between successive states involve a single FF change, which tends to simplify the next-state logic because each FF’s behaviour correlates cleanly with the state transitions.
Same divide-by-5 counter, sliding assignment:
| State | c b a |
|---|---|
| S₀ | 0 0 0 |
| S₁ | 0 0 1 |
| S₂ | 0 1 1 |
| S₃ | 1 1 0 |
| S₄ | 1 0 0 |
Note the sequence: 000 → 001 → 011 → 110 → 100 → 000. Each transition flips exactly one bit except 100 → 000 which flips one bit. The resulting equations:
FF a requires one AND gate. FFs b and c require NO gates: D_b is simply connected to the a output, and D_c to the b output. This is a dramatic simplification from the sequential assignment. The shift register-like pattern emerges because the state sequence forms a ring, and adjacent codes differ by one bit.
Strategy 3: Shift Register Assignment
The FFs are connected as a shift register: the output of each FF feeds the D input of the next, and the final FF output feeds back to the first. This is only applicable to FSMs with a simple cyclic state sequence (like counters or the traffic light controller).
Divide-by-5 with shift register (5 FFs):
| State | e d c b a |
|---|---|
| S₀ | 0 0 0 1 1 |
| S₁ | 0 0 1 1 0 |
| S₂ | 0 1 1 0 0 |
| S₃ | 1 1 0 0 0 |
| S₄ | 1 0 0 0 1 |
The next-state equations: D_a = e, D_b = a, D_c = b, D_d = c, D_e = d. No logic gates at all: just wires. The trade-off is 5 FFs instead of 3, but zero combinational logic. This strategy is sometimes called “one-cold” or “ring counter” assignment when exactly one 0 circulates.
Strategy 4: One-Hot Encoding
One FF per state, exactly one FF holds a 1 at any time. For m states, this requires m FFs (compared to ⌈log₂ m⌉ for binary). The next-state logic becomes trivial: the next state’s FF is activated by a logical OR of the conditions that lead to that state. The output logic is also trivial: an OR of the state FFs that should produce each output.
Traffic light controller (4 states) with one-hot encoding:
States: r (Red), ra (Red+Amber), g (Green), a (Amber).
| State | r ra g a |
|---|---|
| R | 1 0 0 0 |
| RA | 0 1 0 0 |
| G | 0 0 1 0 |
| A | 0 0 0 1 |
The state sequence: R → RA → G → A → R → …
From the state transition table (and because one-hot forms a shift register structure where only one FF is 1 at a time):
Each D input depends on exactly one other FF output. No gates. The outputs (R, A, G lights):
Only two OR gates for the output logic. Total: 4 FFs, 2 OR gates. Compare with the binary-encoded version in the slides (3 FFs, several gates for next-state logic). The one-hot version uses one more FF but dramatically less combinational logic.
Trade-offs Summary
| Strategy | FFs needed | Logic complexity | Best for |
|---|---|---|---|
| Sequential | ⌈log₂ m⌉ | Variable (often complex) | Default; when FF count matters most |
| Sliding | ⌈log₂ m⌉ | Often simpler than sequential | Cyclic state sequences |
| Shift register | m | Zero logic | Simple cycles; when wiring simplicity matters |
| One-hot | m | Near-zero logic | FSMs with few states; FPGAs where FFs are abundant |
Why One-Hot Favours FPGAs
In an FPGA, each logic element contains both a LUT and a FF. The FF is there whether you use it or not. Using one-hot encoding uses more FFs (which are free, in the sense that the silicon is already there) and fewer LUTs (which are the scarce resource). The synthesis tool often selects one-hot automatically for FSMs on FPGA targets.
In contrast, for a custom ASIC or a 74-series discrete design, each FF costs chip area or a physical chip, so binary encoding is preferred.
The Key Insight
State assignment determines how much “work” the combinational logic must do. A good assignment makes the next state depend on the current state in a simple, systematic way. The extreme cases (shift register and one-hot) essentially eliminate the next-state logic by embedding the state transition pattern directly in the wiring between FFs. The traffic light controller’s natural ring structure (R → RA → G → A → R) is why these assignments work so effectively: the states form a simple cycle, which maps cleanly onto a shift register or one-hot pattern.