State Assignment

After state reduction, you must assign a binary code to each state. The state assignment you choose determines how complex the flip-flop input equations are — a poor choice doubles the gate count, while a good choice can halve it.

Core Concept

With n states you need at least ceil(log2(n)) flip-flops. For 4 states: 2 flip-flops; for 5 states: 3 flip-flops (one code is unused). The number of valid assignments is enormous — for n states there are n!/2 distinct assignments ignoring rotations and reflections, so heuristic rules guide the choice.

The Gray code assignment ensures only one flip-flop changes per state transition. This minimises switching activity and is preferred in low-power designs. The one-hot assignment uses one flip-flop per state — only one FF is HIGH at any time. Although it needs more flip-flops, output decoding becomes trivial and next-state logic is simpler because each state variable is a single FF output.

FPGAs contain abundant flip-flops (each LUT slice has a register), so one-hot is the default in Xilinx Vivado and Intel Quartus for large FSMs. ASIC synthesis tools like Synopsys Design Compiler default to binary or Gray encoding to minimise flip-flop count.

Boolean Expression

The Hartmanis-Stearns guidelines: states that share the same next state under a common input should get adjacent codes (differ in 1 bit). States that appear as next states of the same present state should also be adjacent. Adjacent codes map to neighbouring K-map cells, creating larger groups and simpler SOP expressions. Unused state codes are treated as don''t-cares in K-maps.

Apply state assignment to a 3-state Moore machine (sequence detector for 11)
States: S0 (Z=0), S1 (Z=0), S2 (Z=1)
Minimum flip-flops: ceil(log2(3)) = 2  (Q1 Q0)

Option A — Binary: S0=00, S1=01, S2=10 (state 11 unused)
Option B — Gray:   S0=00, S1=01, S2=11 (state 10 unused)

State table:
PS   X=0 NS   X=1 NS   Z
S0   S0        S1       0
S1   S0        S2       0
S2   S0        S2       1

With Option A (Binary, S0=00, S1=01, S2=10):
D1 equations (K-map with state 11 as don''t-care):
  PS=01,X=1 → NS=10 → D1=1; PS=10,X=1 → NS=10 → D1=1
  D1 = Q0·X + Q1·X = X·(Q0+Q1)
D0 equations:
  PS=00,X=1 → NS=01 → D0=1; all others D0=0
  D0 = Q1''·Q0''·X
Z = Q1·Q0''

With Option B (Gray, S0=00, S1=01, S2=11):
D1 equations:
  PS=01,X=1 → NS=11 → D1=1; PS=11,X=0 → NS=00 → D1=0; PS=11,X=1 → NS=11 → D1=1
  D1 = Q0·X  (same or similar — Gray helps when more states exist)
D0 equations:
  PS=00,X=1 → NS=01 → D0=1; PS=01,X=1 → NS=11 → D0=1; PS=11,X=1 → NS=11 → D0=1
  D0 = X  (simpler!)
Z = Q1·Q0

Final Answer:
  Option B (Gray) gives D0 = X vs D0 = Q1''Q0''X in Option A — one fewer gate level.
  Lesson: Gray code assignment can simplify equations for sequential transitions.

Exam Tip: In GATE problems on state assignment, the question often gives two assignments and asks which yields simpler equations. Always build the K-map for each assignment and count the number of terms. The assignment that groups more adjacent 1s in the K-map wins. Also remember: unused state codes become don''t-care entries in every K-map — leaving them as 0 instead of d is a common error that makes the K-map harder to simplify.

Key Properties

• Minimum flip-flops needed = ceil(log2(n)) for n states
• Binary assignment: compact; unused codes available as don''t-cares in K-maps
• Gray code: one bit change per transition; minimises switching and dynamic power
• One-hot: n FFs for n states; simplest output and NS logic; preferred in FPGAs
• Hartmanis-Stearns rules: assign adjacent codes to states sharing NS or output
• Unused codes are don''t-cares; include them as d in K-maps for maximum grouping
• ASIC tools: binary/Gray default; FPGA tools (Vivado, Quartus): one-hot default for large FSMs

Quick Revision

• State assignment maps state names to binary codes for flip-flop implementation
• Minimum FFs = ceil(log2(number of states))
• Binary: sequential codes; Gray: 1-bit transitions; One-hot: 1 FF per state
• Adjacent codes (1 bit apart) share K-map cells → larger groups → simpler equations
• Hartmanis-Stearns: make states with same NS or same output adjacent
• Unused codes = don''t-care entries in every K-map
• FPGAs favour one-hot; ASICs favour binary or Gray to save flip-flop area
• Exam trap: treating unused state codes as 0 instead of don''t-care — this wastes K-map groupings and gives a more complex equation than necessary.