State encoding

Also called: state assignment, state code, state coding

Choosing a bit pattern for each state of a finite state machine, which fixes how many flip-flops it needs and how complex its logic is.

Before an FSM can be built, each state needs a code: a pattern of bits to store in the state flip-flops. That choice is the state encoding (or state assignment).

The main options:

Binary encoding: number the states 0, 1, 2, … in binary. Uses the fewest flip-flops, ⌈log₂ N⌉ (see flip flops needed).
One-hot encoding: one flip-flop per state, exactly one of them 1. More flip-flops, but the next-state logic is very simple.
Gray encoding: neighboring states in a sequence differ in one bit, which can simplify logic and reduce switching.

The codes you choose change the next-state equations and output equations, sometimes a lot. Codes left over with binary encoding are unused states: they can be don't-cares in the logic, but you must check they can't cause a lock up state.

A useful habit: when the states have meanings that map onto bits ("last input was 1"), use those bits as the code. The equations often fall straight out.

Worked examples

Example

Encoding the Mealy 110 detector

The detector has 3 states, A, B and C. Encode it in binary and in one-hot.

1.
Binary: 3 states need 2 flip-flops (2² = 4 ≥ 3). Choose A = 00, B = 01, C = 10. Code 11 is unused.
2.
With these codes the equations are D1 = , D0 = and Z = (see next state logic).
3.
One-hot: 3 flip-flops named A, B and C after their states, so A = 001, B = 010, C = 100 (written CBA). The equations become A⁺ = , B⁺ = , C⁺ = .

Example

Flip-flops for each encoding

A machine has 6 states.

1.
Binary: 2² = 4 < 6 ≤ 8 = 2³ → 3 flip-flops, 2 codes unused.
2.
One-hot: 6 flip-flops, one per state.
3.
Gray: also 3 flip-flops; only the order of codes changes.

Common mistakes

Rounding log₂ N down. 5 states need 3 flip-flops in binary, not 2.
Assuming the encoding doesn't matter. Different codes can give very different amounts of logic.
Ignoring unused codes after encoding. Check where each one goes so the machine can't get stuck.

Practice State encoding

Interactive questions with instant feedback and a worked solution for every wrong answer.

Finite State Machines lesson full course

And 4 more in the Finite State Machines lesson.

Practice exams

Learn it step by step

State encoding is taught in Finite State Machines.

Finite State Machines →

All terms