1. Home
2. Academy
3. State Machines from Zero
4. Volume 03

3.1 Giving states binary codes

To build a state machine from flip-flops, give each state its own pattern of bits, called its code. The number of flip-flops is the number of bits in the code.

A flip-flop stores one bit. So a state register can only hold patterns of bits - it cannot hold the word "LOCKED". Before we can build anything, every state needs a bit pattern of its own. Choosing those patterns is called state assignment.

How many flip-flops?

In Volume 00 you learned that n bits make 2ⁿ patterns. We need at least one pattern per state:

Naming the bits

We call the flip-flops Q1 and Q0, and write a code with Q1 on the left. So the code 10 means Q1 = 1 and Q0 = 0. The value a bit will have after the next clock edge is written with a small plus: Q1⁺, spoken "Q1 next".

An example: the edge detector

The Moore edge detector from Volume 02 has three states, so it needs two flip-flops. Here is one choice of codes:

Now rewrite the state table with codes in place of names. This is the encoded state table:

The code 11 belongs to no state. It is an unused code. The machine should never be there, so we do not care what the logic does with it. We write X, which you will learn to use in sub-module 3.3.

Does the choice of codes matter?

Yes. Every choice works, but different codes give different amounts of logic. Two rules of thumb help when designing by hand:

• Give the reset state the all-zeros code. Resetting then means "clear every flip-flop".
• Where the machine moves from one state to the next along its main path, choose codes that differ in only one bit.

Volume 05 is all about encodings, including the one-hot code you met with the Medvedev traffic light.

3.2 Flip-flop excitation tables (D, T, JK, SR)

An excitation table answers a reverse question: "Q must change from this value to that value - what must the flip-flop's inputs be?"

Volume 00 used only the D flip-flop. There are four classic kinds, shown in Figure 3.1. They have different inputs, but all of them store one bit and change only at the clock edge.

Two ways to read a flip-flop

The usual question is: "given the inputs now, what will Q be after the edge?" The table that answers it is the flip-flop's characteristic table.

When we design, we ask the opposite. We already know how each state bit must change - the encoded state table tells us. We want to know which inputs will cause that change. The table that answers this reverse question is the excitation table.

The D flip-flop

Q⁺ = D. Whatever you want Q to become, put it on D. The excitation table is almost too simple to write:

The T flip-flop

A T flip-flop ("T" for toggle) keeps its value when T = 0, and flips it when T = 1. So T must be 1 exactly when the bit has to change:

The JK flip-flop

A JK flip-flop has two inputs. Its characteristic table is:

Now read it backwards. Suppose Q is 0 and must stay 0. "Keep" (J = 0, K = 0) works. "Reset" (J = 0, K = 1) also works. So J must be 0, but K can be either value. We write K = X, which means don't care: either value gives the right result. Doing the same for all four changes gives the excitation table:

Those X values are a gift. As you will see, every X is a place where the logic may be made smaller.

The SR flip-flop

An SR flip-flop has a set input S and a reset input R. S = 1 sets Q to 1, R = 1 resets it to 0, and both 0 keep it. Both 1 at once is not allowed. Its excitation table:

All four on one page

3.3 Next-state logic with K-maps

A Karnaugh map is a truth table redrawn as a grid, so that circling groups of 1s gives you the simplest gate formula.

The encoded state table tells us what each flip-flop input must be, for every combination of state bits and inputs. Each flip-flop input is therefore a truth table. To build it, we need a formula of AND, OR and NOT gates - a Boolean expression - and we want the smallest one.

How formulas are written

The plus sign means OR here, not adding. So 1 + 1 = 1.

From a truth table to a formula

Any truth table can be written in one standard shape. For every row where the output is 1, write the AND of all the inputs, with a ' on each input that is 0 in that row. Then join these terms with OR. The result is a sum of products. Each AND term for a single row is called a minterm, and minterms are numbered by the row's binary value.

Take a function F of A and B that is 1 in rows 01 and 11:

• Row 01 (A = 0, B = 1) gives the minterm A'·B - minterm number 1.
• Row 11 (A = 1, B = 1) gives the minterm A·B - minterm number 3.

So F = A'·B + A·B. But look closer. B is 1 in both rows, while A is 0 in one and 1 in the other. The output does not depend on A at all, so F is simply B. That is the whole secret of simplifying:

In a big truth table, pairs like this are hard to spot. A Karnaugh map puts them side by side.

The Karnaugh map

A Karnaugh map, or K-map, is a grid with one cell per row of the truth table. The rows and columns are labelled in Gray code order - 00, 01, 11, 10 - and not in counting order. In Gray order each label differs from its neighbour in one bit, so each cell differs from the cell beside it in exactly one input. The map also wraps around: the left column is a neighbour of the right column.

Here is how to group the 1s:

1. Circle only 1s. Never include a 0.
2. Each group must be a rectangle of 1, 2, 4, 8 or 16 cells.
3. Make each group as large as you can.
4. Cover every 1 at least once, using as few groups as you can. Groups may overlap.
5. Groups may wrap around the edges of the map.
6. A don't care (X) may join a group if it makes the group bigger. You never have to cover an X.

To read a group, look at each input. If it has the same value in every cell of the group, keep it - plain if it is 1, with a ' if it is 0. If it changes inside the group, drop it.

Our edge detector: flip-flop Q1

From the encoded table in sub-module 3.1, Q1⁺ is 1 in two rows: Q1 Q0 btn = 011 (minterm 3) and 101 (minterm 5). The unused code gives don't-cares at minterms 6 and 7. Figure 3.2 shows the map. We write b for btn to keep the labels short.

Read the green group, down the 11 column. Q1 is 0 in one cell and 1 in the other, so it drops out. Q0 = 1 and b = 1 in both, so they stay: Q0·b. The blue group, along the bottom row, gives Q1·b in the same way. So:

Flip-flop Q0

Q0⁺ is 1 in only one row: 001, minterm 1. Its neighbours - minterms 0, 3 and 5 - are all 0, and the don't-cares at 6 and 7 are not next to it. So it stands alone, as a group of one:

A group of one cell keeps every input: Q0⁺ = Q1'·Q0'·b. With D flip-flops, the inputs are simply D1 = Q1⁺ and D0 = Q0⁺, so the next-state logic is done.

3.4 Output logic

The output logic is found the same way as the next-state logic: write a truth table for each output, then simplify it with a K-map.

Moore outputs: from the state bits only

In a Moore machine, the outputs depend only on the state. So each output's K-map has only the state bits as inputs. For the edge detector, pulse is 1 in EDGE (code 01) and don't-care in the unused code 11:

pulse = Q0. The output logic is a single wire. That is no accident: EDGE is the only state whose code has Q0 = 1. A good choice of codes can make the output logic vanish - which is the Medvedev idea from Volume 02.

The whole Moore edge detector, built from the three formulas, looks like this in Verilog:

module edge_moore_gates (
  input  wire clk, rst, b,
  output wire pulse
);
  reg  q1, q0;                        // the state register: 2 flip-flops
  wire d1 = (q0 & b) | (q1 & b);      // Q1+ from Figure 3.2
  wire d0 = ~q1 & ~q0 & b;            // Q0+ from Figure 3.3

  always @(posedge clk)
    if (rst) {q1, q0} <= 2'b00;       // reset to ZERO
    else     {q1, q0} <= {d1, d0};    // move to the next state

  assign pulse = q0;                  // output logic from Figure 3.4
endmodule

Mealy outputs: the inputs join in

In a Mealy machine, the outputs depend on the inputs too, so the inputs appear in the output's truth table. Take the two-state Mealy edge detector. Give ZERO the code 0 and ONE the code 1, so one flip-flop Q is enough:

Two things fall straight out of this table. First, Q⁺ always equals btn, so the flip-flop just stores the button's last value. Second, pulse is 1 in one row only, where Q = 0 and btn = 1, so pulse = Q'·btn. That is exactly the one-flip-flop circuit from the interview question at the end of Volume 02.

3.5 Worked design: from story to gates

Every hand design follows the same seven steps, from a story in words to a circuit of flip-flops and gates.

1. Understand the story. List the inputs and outputs, and decide Moore or Mealy.
2. Draw the state diagram.
3. Write the state table. Check that it has every row.
4. Give each state a code.
5. Write the encoded table. Add each flip-flop's inputs from the excitation table.
6. Simplify each flip-flop input and each output with a K-map.
7. Build it, and check it. Write the circuit, then test it against the story.

Step 1: the story

A drink machine sells a drink for three coins. It takes one coin at a time. When the third coin goes in, it releases one drink, and its count starts again from zero.

• Input: coin - 1 during the clock cycle in which a coin arrives.
• Output: vend - 1 for one cycle, to release a drink.

We choose a Moore machine, so that vend is steady for its whole cycle.

Step 2: the state diagram

The machine must remember how many coins it has: none, one or two. It also needs a state in which vend = 1. That gives four states: C0, C1, C2 and VEND. A coin during VEND counts as the first coin of the next drink.

Step 3: the state table

Four states and one input bit need 4 × 2 = 8 cases, and the table covers all of them.

Step 4: the codes

Four states need two flip-flops, and all four codes are used. Along the main path C0, C1, C2, VEND we choose codes that change one bit at a time: C0 = 00, C1 = 01, C2 = 11, VEND = 10.

Step 5: the encoded table

With D flip-flops, each D input is simply the next value of its bit. The last column numbers each row as a minterm of Q1, Q0 and coin:

Step 6: simplify

D1 = Q1⁺ is 1 at minterms 3, 6 and 7:

D0 = Q0⁺ is 1 at minterms 1, 2, 3, 5 and 6:

The output vend is 1 only in VEND, code 10, so vend = Q1·Q0'. The full answer:

Minterm 3 could have been covered by Q1'·Q0 instead of Q1'·coin. A K-map can have more than one answer of the same size, and all of them are correct.

Step 7: build it and check it

module drink_gates (
  input  wire clk, rst, coin,
  output wire vend
);
  reg  q1, q0;                              // C0=00 C1=01 C2=11 VEND=10
  wire d1 = (q0 & coin) | (q1 & q0);
  wire d0 = (~q0 & coin) | (q0 & ~coin) | (~q1 & coin);

  always @(posedge clk)
    if (rst) {q1, q0} <= 2'b00;             // reset to C0
    else     {q1, q0} <= {d1, d0};

  assign vend = q1 & ~q0;                   // 1 only in VEND
endmodule

Check it against the story, by hand. Start in C0 = 00 and put in three coins. With q1 = 0, q0 = 0 and coin = 1: d1 = 0 and d0 = 1, so the next state is 01 (C1). From 01 with coin = 1: d1 = 1 and d0 = 1, giving 11 (C2). From 11 with coin = 1: d1 = 1 and d0 = 0, giving 10 - VEND, where vend = 1. The drink comes out after the third coin, as the story says.

The same machine with JK flip-flops

Now build it again, with JK flip-flops. The states, codes and next values stay the same. Only the flip-flop inputs change. For each row, look up the change in each bit in the JK excitation table:

Half of every column is X. Watch what that does to the K-maps:

So J1 = Q0·coin and K1 = Q0'. In the same way - try it in the practice section - you will find J0 = coin and K0 = Q1·coin. Compare the two designs:

The don't-cares in the JK excitation table made the logic much smaller. That is why exams love JK designs. On a real chip, though, the D flip-flop still wins. A JK flip-flop is itself built from a D flip-flop plus gates, so the gates you save come back inside the flip-flop.

What you learned

• A machine with S states needs the smallest n flip-flops for which 2ⁿ is at least S. Codes left over are unused, and marked don't-care.
• An excitation table says which inputs make a flip-flop change as you want. For D, it is simply D = Q⁺.
• JK and SR excitation tables contain don't-cares, which often make hand designs smaller.
• A K-map lays a truth table out in Gray-code order. Circle groups of 1, 2, 4 or 8, as large and as few as possible, and drop the inputs that change inside a group.
• Moore outputs are simplified from the state bits alone; Mealy outputs need the inputs in their map too.
• The seven steps: story, diagram, table, codes, encoded table, K-maps, build and check.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• State assignment
• Unused state code
• Characteristic table
• Excitation table
• T flip-flop
• JK flip-flop
• SR flip-flop
• Boolean expression
• Sum of products
• Minterm
• Karnaugh map (K-map)
• Gray code
• Don't care (X)

Practice

Interview corner

Next, Volume 04 writes state machines the way engineers really do - in Verilog and SystemVerilog - and lets the tools do the K-maps for you.