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.

Powered up in the Unused CodeOne column per clock cycle. The state is q1 q0; vend is the Mealy output in that cycle.
0123clkcoin-dq1 q011vend
Scroll horizontally ↔
  1. Cycle 0

    The register wakes up in 11. No state was designed for it.

  2. Cycle 2

    With no coin, the equations send 11 back to 11. The machine is stuck there.

  3. 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

The Design ProcedureArrows show the order of the steps. The last step checks the result of all the others.
  • Neutral
  • Step
  • Structure
The design procedureArrows show the order of the steps. The last step checks the result of all the others. neutral Words what must beremembered neutral State diagram one arc per inputvalue neutral State table with don't-cares neutral State codes unused codes appearhere neutral Equations D maps, or J and Kmaps step Check unusedcodes where does each onego? excitation table
  1. neutral Wordswhat must be remembered
    • State diagram
  2. neutral State diagramone arc per input value
    • State table
  3. neutral State tablewith don't-cares
    • State codes
  4. neutral State codesunused codes appear here
    • excitation table → Equations
  5. neutral EquationsD maps, or J and K maps
    • Check unused codes
  6. step Check unused codeswhere does each one go?
  1. Behaviour

    Decide what the machine must remember, then draw and tabulate it.

  2. Hardware

    Codes fix the flip-flops; the excitation table of the flip-flop type gives the equations.

  3. 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 1: The Vending Machine as a Diagram
Step 1: The Vending Machine as a Diagram00/010/001/011/000/010/001/111/100/010/101/111/1S00 centsS55 centsS1010 cents
  1. 0 cents · S0
    • ↓00 → S0 / 0
    • ↓10 → S5 / 0
    • ↓01 → S10 / 0
    • ↓11 → S10 / 0
  2. 5 cents · S5
    • ↓00 → S5 / 0
    • ↓10 → S10 / 0
    • ↓01 → S0 / 1
    • ↓11 → S0 / 1
  3. 10 cents · S10
    • ↓00 → S10 / 0
    • ↓10 → S0 / 1
    • ↓01 → S0 / 1
    • ↓11 → S0 / 1
StateInputNextOutput
S000S00
S010S50
S001S100
S011S100
S500S50
S510S100
S501S01
S511S01
S1000S100
S1010S01
S1001S01
S1011S01

Current state: S0 · Output: 1

Sampled input, state and output waveformStepState0S01S52S103S04S05S106S0n—111001d—000010vend—001001
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step0123456
Input—101010000110
StateS0S5S10S0S0S10S0
Output—001001

  1. Step 3. Three nickels: 0, 5, 10, and the third arc carries vend = 1 back to S0.
  2. Step 6. A dime then a nickel also reach 15 cents. vend is on the arc, so it is a Mealy output.

Inputs are written n d. Both coins at once never happens; the widget needs an arc for 11, so it is drawn like a dime. The table treats it as a don't-care.

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.

StateCode q1 q0no coinndn and d
S000S0, 0S5, 0S10, 0X
S501S5, 0S10, 0S0, 1X
S1010S10, 0S0, 1S0, 1X
unused11XXXX

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.

Step 3: The Map of d1, With the Unused Code as a Don't-Care
q1q0 / nd00011110
00
01
11
10

~q1 & ~q0 & d | q0 & n | q1 & ~n & ~d

Minimum SOP: 3 terms · 8 literals.

  1. S5 with a nickel. The cell 0110 (S5, n) is 1. The don't-cares of row 11 and column nd = 11 let it grow to a group of four: q0 n.
  2. S0 with a dime. Cell 0001 joins the don't-care 0011: q1' q0' d.
  3. S10 with no coin. Cell 1000 joins the don't-care 1100 of the unused code: q1 n' d'.

Three groups, eight literals. The cells of row q1 q0 = 11 are don't-cares only because that code is unused.

SignalMinimum with 11 as a don't-careLiterals
d1q0 n + q1' q0' d + q1 n' d'8
d0q0 n' d' + q1' q0' n6
vendq0 d + q1 d + q1 n6

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 changeJK
0 → 00X
0 → 11X
1 → 0X1
1 → 1X0

The JK excitation table: when Q = 0 only J matters, when Q = 1 only K matters.

InputMinimum with 11 as a don't-careLiterals
J1q0' d + q0 n4
K1n + d2
J0q1' n2
K0n + d2

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.

FromConditionToTerm
S0 (00)dS10 (10)q1' q0' d → d1
S0 (00)nS5 (01)q1' q0' n → d0
S5 (01)nS10 (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.

VersionUnused code 11Cells (synthesized)
Minimum, 11 as a don't-careholds while idle; a dime sells12
Transition list, full codesgoes to S0 at the next edge17

Measured on the pinned synthesis flow. Safety cost five cells here.

Asked in interviews
  1. 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.

  2. 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.

  3. 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.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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: 4

Original 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

ConceptWhich step of the procedure decides how many flip-flops the machine needs?
ConceptA JK flip-flop bit must go from 1 to 1. Which J and K does the excitation table give?
ConceptWhy did the free version of the vending machine sell for a dime from code 11?
Predict the outputThe vending machine powers up in the unused code with the free equations and sees no coin, no coin, then a dime. The program prints q1 q0 and vend each cycle. Predict the exact line.
module tb;
  // The vending machine built with the unused code 11 left as a don't-care, powered up in 11.
  logic q1 = 1, q0 = 1, n = 0, d = 0, vend;
  string coins = "--d", s = "";
  initial begin
    for (int i = 0; i < coins.len(); i++) begin
      n = (coins[i] == "n"); d = (coins[i] == "d");
      vend = (q0 & d) | (q1 & d) | (q1 & n);
      if (i > 0) s = {s, " "};
      s = {s, $sformatf("%b%b/%b", q1, q0, vend)};
      {q1, q0} = {(q0 & n) | (~q1 & ~q0 & d) | (q1 & ~n & ~d), (q0 & ~n & ~d) | (~q1 & ~q0 & n)};
    end
    $display("%s", s);
  end
endmodule
ConceptIn a transition list, why does the arc S5 to S0 on a dime add no term to d1 or d0?

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.

Practice

Report a problem with this page