State Assignment

State assignment is the choice of binary code for each state of a finite state machine. With $n$ states, you need at least $\lceil {\log }_{2}n\rceil$ flip-flops; the assignment decides which bit pattern represents which state.

Different assignments produce different next-state and output logic — sometimes very different in cost.

Example

Take a 3-state FSM with states A, B, C. You need $\lceil {\log }_{2}3\rceil =2$ bits, giving 4 possible bit patterns ($00,01,10,11$). Three are used, one is unused (don’t-care):

One reasonable assignment: $A=00$, $B=01$, $C=10$, leaving $11$ as a don’t-care.

Another: $A=00$, $B=11$, $C=01$.

A third: one-hot — use 3 flip-flops with $A=001$, $B=010$, $C=100$.

All three implement the same FSM. The synthesis cost differs.

Common assignment strategies

1. Sequential / binary. Just number the states in order. Simple to read; usually small enough flip-flop count. Default for hand designs.

2. One-hot. Use one flip-flop per state. More flip-flops but simpler next-state logic — checking “are we in state X?” is just looking at one bit, no decoding needed. Common for FPGAs where flip-flops are cheap.

3. Gray code. Assign codes so adjacent states differ in one bit. Reduces switching activity and avoids glitches when the state changes — useful in low-power and high-speed designs.

4. Optimization-driven. Use a tool to try many assignments and pick the one that minimizes total gate count. This is what synthesizers do internally.

Why it matters

The state assignment determines what truth tables the next-state functions $Y_1,Y_2,\dots$ have. Different assignments give different K-maps, different prime implicants, and different total cost. For a small FSM, the difference can be 2–3× in gate count.

The output function is similarly affected. A Moore machine’s output is a function of the state code; with a clever code, the output may turn out to be just one of the state bits directly.

Tools like Synopsys, Vivado, and Quartus try many assignments behind the scenes; for hand-designed FSMs, picking a good assignment is part of the craft.

For the worked example showing how state assignment feeds into K-maps and final logic, see Sequence detector (FSM design example).