Designing a state machine
From a state diagram to gates and flip-flops, the same way every time.
The procedure
The last lesson promised that once a machine is a state table, turning it into a circuit is mechanical. Here is the procedure, the same for every machine, and then the 101 detector worked through it.
- Draw the state diagram. One circle per situation the machine must remember, one arrow per input value from each.
- Write the state table. Every present state and input, with the next state and the output.
- Assign codes. Give each state a binary pattern. Each bit of the pattern will live in one flip-flop.
- Choose flip-flops. D flip-flops are the usual choice, for a reason you will see in a moment.
- Derive the equations. Each next-state bit and each output is a boolean function of the state bits and the inputs. Simplify each one with a Karnaugh map.
- Draw the circuit and check it against the table.
Assigning codes
A state is an idea; a flip-flop holds a bit. To build the machine, each state gets a code, a pattern of bits, and the machine's state is then simply the contents of a small register. With n states you need enough bits to give each one a different pattern: two bits for up to four states, three bits for up to eight, and in general the smallest b with 2b at least n. The detector has four states, so two bits, held in two flip-flops whose outputs we call Q1 and Q0: S0 = 00, S1 = 01, S2 = 10, S3 = 11.
With the codes in place the state table becomes a truth table. Its inputs are the state bits and x; its outputs are the bits of the next state, called d1 and d0, and the machine output z. Step through the widget and watch the table turn into equations.
Why D flip-flops
A D flip-flop copies its D input to Q on the clock edge. So if the flip-flop holding Q1 must show the next state's top bit after the edge, its D input must be that bit before the edge: d1 is simply the next-state column for Q1, and d0 the column for Q0. There is nothing to translate. Other flip-flops need a lookup: with a T flip-flop you must ask "does this bit change?". The tables of what to put on a flip-flop's inputs to get from one state to another are called excitation tables, which is why the equations are often called excitation equations. With D, the excitation equation and the next-state equation are the same thing.
The equations
Take each output column of the truth table in turn, put it on a Karnaugh map with Q1, Q0 and x as the variables, and group the 1s exactly as in stage 4. The maps give, with ∧ for AND, ∨ for OR and ¬ for NOT:
- d1
- = Q0 ∧ ¬x ∨ Q1 ∧ ¬Q0 ∧ x
- d0
- = x
- z
- = Q1 ∧ Q0
Read them in words. d0 = x: the low state bit is simply a copy of the input, because every state with a 1 in the low bit (S1 and S3) is reached on a 1 and every state with a 0 there on a 0. z = Q1 ∧ Q0: the output is 1 only in the state coded 11, which is S3, and it depends on the state bits alone, which is what makes this a Moore machine. d1 is the one with real work in it, and the map did that work for you.
Worked example. Check the equations on one row: the machine is in S2 (10, seen 10) and x = 1.
From the table, the next state should be S3, coded 11, so we need d1 = 1 and d0 = 1, and the output in S2 should be 0. Now put Q1 = 1, Q0 = 0, x = 1 into the equations: d1 comes out 1, d0 comes out 1 and z comes out 0. All three agree with the table. Doing this for every row is the check in step 6, and the site's test suite does exactly that for this machine.
Drawing the circuit
The circuit is now fixed: two D flip-flops on one clock, their outputs Q1 and Q0 fed back into a block of gates together with x, that block computing d1, d0 and z from the equations above, and d1 and d0 wired to the D inputs. The gates are the combinational part, the flip-flops are the memory, and that shape, gates in a loop with a register, is every sequential circuit you will ever meet.
Why?: why simplify with a map rather than just wire up the table?
A table with three inputs could be wired directly, one gate per row, but a real machine may have ten state bits and several inputs, and its table thousands of rows. The Karnaugh map finds the few gates that do the same job: in the detector, d1 has eight rows and comes out as two terms.
Unused states
Two bits give four codes and the detector uses all four. A machine with three states would leave one code spare, and during design that row of the table is a don't care: the map may treat it as 0 or 1, whichever gives the simpler equation. But a real circuit can land in that code at power-up or after a glitch, and the equations will send it somewhere. Either check that every unused code finds its way back to a proper state, or give each one an explicit arrow to the reset state and pay for the extra gate. Doing neither is how a machine gets stuck.
Common mistake: reading the present state where the next state should be
The d columns come from the next state's code, not the present one. It is easy, filling in the table, to copy the code of the row's own state into d1 d0. The check in the worked example catches it: with the present code in the d columns the machine would never move.
What to remember
- Design order: diagram, table, codes, flip-flops, equations, circuit, check.
- n states need the smallest number of bits b with 2b at least n, one flip-flop per bit.
- With D flip-flops each D input is simply the next-state bit, so the equations come straight off the table.
- Each next-state bit and output is a boolean function of the state bits and inputs; a Karnaugh map simplifies it.
- Unused codes are don't cares in the map, but check where they lead in the real circuit.
Check yourself
Get 5 right in a row and the lesson is done. A wrong answer costs the run, not the lesson.
The 101 detector uses the codes shown. The row of its state table for present state S2 with x = 0 has next state S0. With D flip-flops, what must d1 d0 be for that row, d1 first?
S0 = 00, S1 = 01, S2 = 10, S3 = 11
Already know this? and come back to the quiz any time.