State Machine Design

Every digital lock, elevator controller, and vending machine is built by following the same systematic procedure. State machine design takes a word description of a sequential problem and converts it into flip-flop equations you can wire up or synthesise in an FPGA.

Core Concept

The design process starts with a state diagram — bubbles for states, arcs for transitions, labels for inputs/outputs. The state diagram is then converted to a state transition table listing the next state and output for every combination of present state and input.

State assignment maps each state name to a binary code. The choice of assignment directly affects the complexity of the flip-flop input equations. After assignment, you fill an excitation table for the chosen flip-flop type (D, JK, or T) and write Boolean expressions using K-maps. The result is a combinational circuit driving the flip-flop inputs.

D flip-flops are the first choice in practice because their excitation equation is simply D = NS — the D input must equal whatever next state you want. JK flip-flops need an excitation table lookup but can yield simpler Boolean expressions. The 74HC74 (dual D-FF) and 74HC112 (dual JK-FF) are the typical ICs used in discrete prototypes.

Boolean Expression

For D flip-flops the design equation is simply D_i = NS_i for each flip-flop i. Write the next-state column, assign binary codes, then read off D equations directly from the K-map. For JK flip-flops use the excitation rule: 0→0: J=0,K=d | 0→1: J=1,K=d | 1→0: J=d,K=1 | 1→1: J=d,K=0 where d is don''t-care.

Design a Moore machine to detect sequence 101 (non-overlapping)

Step 1 — States: S0 (start, Z=0), S1 (got 1, Z=0), S2 (got 10, Z=0), S3 (got 101, Z=1)

Step 2 — State assignment: S0=00, S1=01, S2=10, S3=11  (Q1 Q0)

Step 3 — State transition table:
PS(Q1 Q0)  X=0  Next(Q1 Q0)  X=1  Next(Q1 Q0)  Z
00          00                01                0
01          10                01                0
10          00                11                0
11          10                01                1

Step 4 — D flip-flop equations (D = NS):
Build K-map for D1:
  Q1Q0\X  0   1
  00      0   0
  01      1   0
  11      1   0
  10      0   1
D1 = Q1''Q0X'' + Q1Q0X'' + Q1Q0''X  → simplified: D1 = Q0X'' + Q1X''
   Wait — re-check: Q1''Q0·0=row01,X=0 → NS=10 so D1=1 ✓
   Q1Q0·0=row11,X=0 → NS=10 so D1=1 ✓
   Q1Q0''·1=row10,X=1→NS=11 so D1=1 ✓
   D1 = Q0·X'' + Q1·Q0''·X

Build K-map for D0:
  Q1Q0\X  0   1
  00      0   1
  01      0   1
  11      0   1
  10      0   1
D0 = X  (all X=1 columns give D0=1, all X=0 give D0=0)

Output: Z = Q1·Q0

Final Answer:
  D1 = Q0·X'' + Q1·Q0''·X
  D0 = X
  Z  = Q1·Q0
  Implement with 74HC74 (2 D-FFs) and basic AND/NOT gates.

Exam Tip: Always fill the excitation table before writing K-maps — skipping this step causes wrong D or JK equations. For D flip-flops, the excitation is trivially D=NS, so K-map input is just the next-state column. For JK flip-flops, place J and K don''t-cares carefully — they are the biggest source of errors in GATE questions on sequential circuit design.

Key Properties

• Design steps: state diagram → state table → assignment → excitation table → K-maps → circuit
• D flip-flop excitation: D = NS — simplest; no extra lookup needed
• JK excitation: 0→0: J=0,K=x; 0→1: J=1,K=x; 1→0: J=x,K=1; 1→1: J=x,K=0
• T flip-flop excitation: T=0 if state unchanged; T=1 if state changes
• ICs: 74HC74 (dual D-FF, 14 ns), 74HC112 (dual JK-FF), 74HC175 (quad D-FF)
• State assignment choice changes Boolean expression complexity — Gray code minimises transitions
• Unused states must be handled — assign them to a safe reset state to prevent lock-up

Quick Revision

• State machine design: 7 steps from word description to logic equations
• D FF is easiest — D input equals the desired next-state binary code
• JK FF allows don''t-cares that simplify Boolean expressions when used carefully
• K-map minimisation applies to both next-state and output equations
• Always check unused states — assign next state to S0 to avoid hang states
• Moore output: Z = f(state bits only); Mealy output: Z = f(state, input)
• Gray code assignment reduces bit transitions and can lower dynamic power
• Exam trap: using JK excitation table entries without don''t-cares — missing the don''t-cares means you cannot simplify the K-map properly.