The FSM Design Procedure
Take a machine from words to a diagram, a table, codes and D or JK equations, then check every unused state.
You Will Be Able To
- Turn a word description into a state diagram and a state table.
- Assign state codes and derive next-state equations for D flip-flops with don't-cares.
- Derive J and K equations from the excitation table, and write equations from a transition list.
- Check where every unused state code goes, and make it safe.
- Lesson
- G7.3
- Time
- 35 min
- Runs on
- Your browser
- Check
- 5 questions
A vending machine passed every test that started from reset. After a power dip in the field, it sold an item for a single dime. Its state register had powered up in 11, a code no state uses.
- Cycle 0
The register wakes up in 11. No state was designed for it.
- Cycle 2
With no coin, the equations send 11 back to 11. The machine is stuck there.
- Cycle 3
One dime, 10 cents, and vend = 1. The item costs 15.
Measured: the predict check at the end of this lesson runs the same equations on Icarus Verilog 12.
Step 1: Words to a Diagram
- Neutral
- Step
- Structure
- Behaviour
Decide what the machine must remember, then draw and tabulate it.
- Hardware
Codes fix the flip-flops; the excitation table of the flip-flop type gives the equations.
- Safety
Every unused code still has a next state. Compute it.
Read the diagram as text
- Words: what must be remembered
- State diagram: one arc per input value
- State table: with don't-cares
- State codes: unused codes appear here
- Equations: D maps, or J and K maps
- Check unused codes: where does each one go?
- Words → State diagram
- State diagram → State table
- State table → State codes
- State codes → Equations: excitation table
- Equations → Check unused codes
The vending machine below goes through every box.
The description: sell an item for 15 cents. Coins are a nickel n (5 cents) or a dime d (10 cents), at most one per cycle. No change is given. Signal vend in the cycle the credit reaches 15.
The state is what the machine must remember: the credit so far. So the states are 0, 5 and 10 cents. Credit of 15 or more sells at once, so it needs no state.
Step 2: State Table and State Codes
Write the arcs as a table. Then give each state a binary code. Three states need two flip-flops, so one code is left over.
| State | Code q1 q0 | no coin | n | d | n and d |
|---|---|---|---|---|---|
| S0 | 00 | S0, 0 | S5, 0 | S10, 0 | X |
| S5 | 01 | S5, 0 | S10, 0 | S0, 1 | X |
| S10 | 10 | S10, 0 | S0, 1 | S0, 1 | X |
| unused | 11 | X | X | X | X |
Each entry is the next state and vend. X is a don't-care: an input that never comes, or a code no state uses.
Step 3: Equations for D Flip-Flops
For a D flip-flop, D is the next value of its bit. Fill a K-map for each bit from the table, use the don't-cares, and read the minimum cover.
| Signal | Minimum with 11 as a don't-care | Literals |
|---|---|---|
| d1 | q0 n + q1' q0' d + q1 n' d' | 8 |
| d0 | q0 n' d' + q1' q0' n | 6 |
| vend | q0 d + q1 d + q1 n | 6 |
Computed by an exact minimizer over all covers; each cover is unique. 20 literals in all.
Step 4: Equations for JK Flip-Flops
For JK flip-flops, each row gives a change Q to Q+ for each bit. The excitation table of lesson G5.7 turns it into J and K, and half of them are don't-cares.
| Bit change | J | K |
|---|---|---|
| 0 → 0 | 0 | X |
| 0 → 1 | 1 | X |
| 1 → 0 | X | 1 |
| 1 → 1 | X | 0 |
The JK excitation table: when Q = 0 only J matters, when Q = 1 only K matters.
| Input | Minimum with 11 as a don't-care | Literals |
|---|---|---|
| J1 | q0' d + q0 n | 4 |
| K1 | n + d | 2 |
| J0 | q1' n | 2 |
| K0 | n + d | 2 |
The extra don't-cares shrink the next-state logic from 14 literals (d1, d0) to 10 here. vend does not change.
Transition Lists
A transition list writes one line per arc: the present state, the input condition and the next state. A bit's D equation is the OR of the lines whose next code has that bit at 1.
| From | Condition | To | Term |
|---|---|---|---|
| S0 (00) | d | S10 (10) | q1' q0' d → d1 |
| S0 (00) | n | S5 (01) | q1' q0' n → d0 |
| S5 (01) | n | S10 (10) | q1' q0 n → d1 |
| S5 (01) | n' d' | S5 (01) | q1' q0 n' d' → d0 |
| S10 (10) | n' d' | S10 (10) | q1 q0' n' d' → d1 |
Arcs into S0 add no term: its code is 00. These are the equations of the lab.
Every term holds the full state code. So the unused code 11 matches no term, and its next state is 00.
Step 5: Check the Unused States
The last step is not optional. For every unused code, compute the next state from the final equations. It must reach a used state, and it should not do anything harmful on the way.
| Version | Unused code 11 | Cells (synthesized) |
|---|---|---|
| Minimum, 11 as a don't-care | holds while idle; a dime sells | 12 |
| Transition list, full codes | goes to S0 at the next edge | 17 |
Measured on the pinned synthesis flow. Safety cost five cells here.
Asked in interviews
Walk me through designing a state machine.
Words to a state diagram, then a state table. Assign codes. Derive next-state and output equations for the flip-flop type, with don't-cares. Check every unused code, then draw or write the circuit.
Why do JK flip-flops give simpler logic than D flip-flops?
Their excitation table has a don't-care in every row: J is free when Q = 1 and K when Q = 0. More don't-cares mean bigger groups on the maps.
What happens to unused states in your design?
I compute their next states from the final equations. Each must reach a used state quickly and without a wrong output. If not, I give it explicit arcs to a safe state.
Try It
Each line shows the coin, the credit (5 × the code) and vend in that cycle. vend rises in the cycle of the coin that reaches 15.
Cycles 10 and 11: two dimes give 20 cents. The machine sells and keeps the extra nickel, as the description says.
Replace the three equations with the free ones (q0 & n | ...) and press Synthesize: 12 cells. The run still sells 4 items, because it never visits 11.
Synthesize the design to measure its cells and inspect the mapped gates.
cycle 0 coin=n credit=0 vend=0 cycle 1 coin=n credit=5 vend=0 cycle 2 coin=n credit=10 vend=1 cycle 3 coin=- credit=0 vend=0 cycle 4 coin=d credit=0 vend=0 cycle 5 coin=n credit=10 vend=1 cycle 6 coin=- credit=0 vend=0 cycle 7 coin=n credit=0 vend=0 cycle 8 coin=d credit=5 vend=1 cycle 9 coin=- credit=0 vend=0 cycle 10 coin=d credit=0 vend=0 cycle 11 coin=d credit=10 vend=1 cycle 12 coin=- credit=0 vend=0 cycle 13 coin=n credit=0 vend=0 items sold: 4Original design · 17 cells · 2 flip-flops · 0 latches · 4 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
// tb.sv: the bench (read-only). One coin (or none) per cycle: '-' none, 'n' 5 cents, 'd' 10 cents.
module tb;
logic clk = 0, rst = 1, n = 0, d = 0;
logic q1, q0, vend;
vend15 dut (.clk(clk), .rst(rst), .n(n), .d(d), .q1(q1), .q0(q0), .vend(vend));
string coins = "nnn-dn-nd-dd-n";
int sold = 0;
initial begin
#1 clk = 1; #1 clk = 0; rst = 0;
for (int i = 0; i < coins.len(); i++) begin
n = (coins[i] == "n"); d = (coins[i] == "d");
#1 $display("cycle %0d coin=%s credit=%0d vend=%b", i, coins.substr(i, i), 5 * {q1, q0}, vend);
sold += vend;
#1 clk = 1; #1 clk = 0;
end
$display("items sold: %0d", sold);
end
endmodule
Check Yourself
Common Mistakes
Wrong Leave an unused state code as a don't-care and never check it.
The minimum equations still send it somewhere. Here 11 held itself while idle and then sold an item for one dime.
Fix After deriving the equations, compute the next state of every unused code. Make it go to a safe state if it does not.
Wrong Read the characteristic table to fill J and K.
The design question runs backwards: which J and K give this change of state? That is the excitation table.
Fix For each row, look up Q to Q+ in the excitation table. For example, 0 to 1 needs J = 1 with K free.
Wrong Draw only the arcs that the description mentions.
A state with no arc for "no coin" has no next state for that input. Every input value needs an arc.
Fix For every state, list every input value, including "nothing happens", which is usually a self-loop.
Wrong Write a transition-list term with only part of the state code.
Short terms such as q1 n' d' and q0 n' d' also match the unused code 11. Together they make 11 hold itself.
Fix Use the full code in each term (q1' q0 n), or check the unused codes after you shorten the terms.
Remember
- Words, diagram, state table, codes, equations, circuit: then check the unused codes.
- Don't-cares come from inputs that never occur and from unused codes; they shrink the equations.
- JK flip-flops have a don't-care in every excitation row, so their equations are smaller.
- An unused code left as a don't-care can hold itself or act wrongly. Transition lists with full codes send it to 00.