FSM design procedure

Also called: FSM design, state machine design, FSM design recipe

The step-by-step method for turning a word description into a state machine circuit: states, transitions, table, encoding, equations, then a check.

Designing a finite state machine from a word problem follows the same path every time:

States in words. Write down what each state must remember. Decide Moore or Mealy.
Transitions. For every state and every input value, choose the next state (and Mealy output). For detectors, use the suffix rule.
State table. One row per state, so no arrow is missed. Merge any equivalent states.
Encode. Give each state a bit pattern; note the unused codes.
Equations. Derive one next state logic per flip-flop and an output equation per output, using unused codes as don't-cares.
Build and check. Wire D flip-flops and gates, check that unused codes can't lock up, and trace a test input you've worked out by hand.

Each step needs the result of the one before, so the order matters. Skipping step 1 is the usual cause of tangled designs.

Worked example

Example

Spec: output Z = 1 on the input that completes 110, with overlaps allowed.

1.
1. States: A = nothing, B = seen 1, C = seen 11. Mealy, so the match happens on an arrow.
2.
1. Transitions: A: 0 → A, 1 → B. B: 0 → A (10 starts nothing), 1 → C. C: 0 → A with Z = 1 (match; no ending of 110 starts 110), 1 → C (111 still ends in 11).
3.
1. Table: A: A/0, B/0. B: A/0, C/0. C: A/1, C/0. No two rows match, so nothing to merge.
4.
1. Encode: A = 00, B = 01, C = 10. Code 11 unused.
5.
1. Equations (the table above): D1 = , D0 = , Z = .
6.
1. Check: unused 11 goes to 00 or 10, both real. Trace 1, 1, 0, 1, 1, 0 → Z = 0, 0, 1, 0, 0, 1 ✓.

Drawing arrows before deciding what each state means.
Encoding before checking for equivalent states, and so paying for an extra flip-flop.
Skipping the final trace. A single wrong arrow is easy to miss and easy to catch by testing.

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

FSM design procedure is taught in Finite State Machines.