FSM Design Procedure
The 9-Step Design Procedure
Designing a synchronous finite state machine from a specification follows a systematic procedure. The steps are:
-
Understand the problem and define the states. Draw an informal state diagram. Identify all distinct situations the machine must remember and the transitions between them.
-
Determine the number of flip-flops needed. If there are m states, you need at least ⌈log₂ m⌉ FFs. For example, 4 states → 2 FFs; 5-8 states → 3 FFs.
-
Assign binary codes to each state. This is the state assignment problem and has a dramatic effect on logic complexity (covered in detail in /modules/digital-electronics/08-synchronous-state-machines/03-state-assignment-strategies/).
-
Draw the formal state diagram with Moore or Mealy notation, including FF labels and output values.
-
Write the state transition table. For each combination of current state and input values, determine the next state and output(s).
-
Derive the excitation equations for each FF input. For D-FFs, Dᵢ = Qᵢ’ (the desired next state). This is where the excitation table from /modules/digital-electronics/06-latches-and-flip-flops/05-jk-and-t-flip-flops/ comes in: for D-FFs, D = Q’; for JK-FFs, use the JK excitation table.
-
Use K-maps to minimise the excitation equations. Unused states (states not in the state diagram, such as binary codes not assigned to any state) are treated as don’t-care conditions. This allows maximal simplification.
-
Draw the schematic. Show the FFs, the next-state combinational logic, and any output logic.
-
Analyse unused states. Check what happens if the machine powers up in an unused state: does the next-state logic eventually lead to a valid (used) state? If not, the machine could become stuck. Remedies: modify the logic to transition unused states to used states, or use asynchronous preset/clear to force a known initial state.
The Modified State Transition Table
For D-FF design, the modified state transition table adds columns for the FF inputs alongside the current and next states. For D-FFs this is often redundant (D = next state), but the discipline is important:
| Current state | Inputs | Next state | FF inputs |
|---|---|---|---|
| Q₂ Q₁ Q₀ | e, r | Q₂’ Q₁’ Q₀’ | D₂ D₁ D₀ |
| … | … | … | … |
For D-FFs, the FF input columns are identical to the next state columns. If you were using JK-FFs, you would fill in J₂, K₂, J₁, K₁, J₀, K₀ using the JK excitation table. This adds a step but may simplify the next-state logic due to the don’t-cares in the excitation table.
Excitation Table for D-FFs
The excitation table for a D-FF is trivial:
| Q | Q’ | D |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
D must equal the desired next state Q’. This is independent of Q, which is why the FF input columns in the modified table are identical to the next-state columns. For a deeper treatment of excitation tables, see /modules/digital-electronics/06-latches-and-flip-flops/05-jk-and-t-flip-flops/.
K-Map Minimisation with Don’t-Cares
The unused states provide don’t-care entries in the K-maps. For an FSM with m states implemented with n FFs, there are 2ⁿ - m unused states. Each unused state row in the transition table has X (don’t-care) for its next state. In the K-map, these cells can be made either 0 or 1 to maximise groupings.
Example: A 5-state FSM uses 3 FFs, leaving 3 unused states (101, 110, 111). For the K-map determining D₂ (the MSB FF input):
(Note: the column represents used states in row , but is an unused don’t-care state in row ).
The X entries at 101, 111, 110 can be set to 1 to form a larger group with 011 (Q₂’Q₁Q₀) and 010 (Q₂’Q₁Q₀’), or to 0 if that produces a better grouping.
The Golden Rule of Don’t-Cares
Do NOT make unused-state don’t-cares all 0s or all 1s indiscriminately. Set each don’t-care to whichever value produces the simplest expression (fewest literals, fewest product terms) for that specific FF input. Different FF inputs may use the same don’t-care cell differently (D₀ might want it as 1 while D₁ wants it as 0), and that is perfectly valid: the don’t-care states never occur during normal operation, so the actual behaviour for those states is irrelevant as long as the machine either reaches a used state or is initialised by a reset.
Unused State Analysis (Self-Start Check)
After deriving the minimised next-state logic, check where unused states transition to by plugging their binary codes into the equations. For example, in the traffic light controller (states: R=100, RA=110, G=001, A=010), the unused states are 000, 011, 101, 111. Plugging each into the next-state equations confirms that all transition to valid used states within one clock cycle (see the worked example in the traffic light note for details).
The point: check the next-state logic output for each unused state. If all unused states eventually transition to used states, the machine is self-starting. If any unused state forms a cycle among unused states or leads to a dead-end that stays unused, the machine must be initialised with an asynchronous reset.
This IS the Tripos Question Type
FSM design is one of the most heavily examined topics in the Digital Electronics Tripos paper. A typical question provides:
- A state diagram (Moore or Mealy).
- A state assignment (or asks you to propose one).
- Asks for the state transition table, K-map minimisation, and the resulting logic equations.
- May ask you to implement the design with a specific FF type (D or JK).
- May ask about unused states, self-starting, or state minimisation.
The worked examples in the subsequent notes (/modules/digital-electronics/08-synchronous-state-machines/04-fsm-worked-example-traffic-light/ and /modules/digital-electronics/08-synchronous-state-machines/05-fsm-tripos-example/) demonstrate the complete procedure on Tripos-style problems.