Clocked circuits and state machines

Memory from feedback ended with flip-flops, registers and a clock. This page puts them together with the logic from the pages before it, into the pattern that every processor is built from: registers hold the present, logic works out what comes next, and each tick of the clock makes the next the present.

1 · A loop through a register

The simplest example is a counter. Take a register, feed its output into a circuit that adds 1 (an adder from Adding, with 1 as its other input), and feed the adder’s output back into the register. Between ticks, the adder works out the register’s value plus 1. On each tick, the register takes it. So the register counts up by one, every tick.

A 4-bit counter driving a 7-segment display. Click Clock tick, or Run the clock to tick twice a second. Past 9 the display shows the hex digits A to F, then the register wraps round to 0. Switch to 0 to 9 and the logic in the loop does a little more: add 1, unless the value is 9, in which case go back to 0. That’s how a digital clock counts its seconds.

The pattern is the same however big the circuit: flip-flops hold the state, the logic between them works out the next state from the state (and any inputs), and the clock moves everything on together. Circuits built this way are called synchronous, and the logic in the loop is just the kind of logic the earlier pages built. The counter that wraps after 9 is already a small state machine.

2 · State machines

A state machine is a circuit that remembers where it’s got to, as one of a fixed list of states, and moves between them according to its inputs. It’s drawn as a diagram: a circle for each state, and an arrow for each transition, labelled with the input that causes it. The same information can be written as a transition table: for each state and each input, the next state.

The example here is a door lock with a keypad, whose code is 2-7-1. It has to remember how much of the code it has heard so far, so its states are locked, heard 2, heard 2 7 and open. Here each key press counts as one tick of the clock. (A real keypad circuit runs on a fast clock and treats each new key press as an input, but the machine is the same.)

Type on the keypad and follow the highlighted state and arrow. Type 2 7 1: the door opens, and the next key locks it again. Now try 2 2 7 1, as someone who hits the 2 twice might. The first try at the table stays locked: its second 2 counts as a wrong key and sends it back to the start, and the 7 that follows is wasted. Edit the table to fix it (a 2 should always mean “heard 2”), or switch to fixed to see one answer.

That bug is typical. A state machine does exactly what its table says, in every state, for every input, including the combinations nobody thought about. Drawing the diagram and asking “what happens on each input, from every state?” is how they’re designed, and how they’re checked.

3 · From a table to gates

A state machine becomes a circuit in three steps, all from earlier pages:

Number the states, and store the number in flip-flops. Four states need two bits: locked 00, heard 2 01, heard 2 7 10, open 11.
Encode the inputs. The machine only cares whether a key is 2, 7, 1 or something else: four cases, two bits, from a small decoder on the keypad’s key code.
The next state is a truth table, with four inputs (two state bits, two key bits) and two outputs (the next state’s bits). It’s built as a sum of products and simplified, exactly as on Combining gates. The door’s output is one more: open when both state bits are 1.

Numbering states in binary uses the fewest flip-flops. Another common choice gives each state its own flip-flop, exactly one of which is 1 at a time (“one-hot”): more flip-flops, but simpler logic, a good trade on chips that have flip-flops to spare.

A processor’s control unit, the part that steps through fetching and carrying out each instruction, is a state machine too: a bigger table, built the same way.

4 · How fast can the clock go?

Each tick, the logic has until the next tick to work out its answer. If the clock ticks before the logic has settled, the flip-flops store whatever the logic happens to be showing at that moment: a half-finished answer, or a glitch. So the clock can only go as fast as the slowest path through the logic allows, the critical path.

The flip-flops add a little more. A flip-flop needs its input to be steady for a short time before the clock edge, its setup time, and to stay steady for a moment after, its hold time. Here the setup time is 1 gate delay.

An 8-bit counter whose +1 is the ripple-carry adder from Adding, with the clock period set in gate delays. The adder’s slowest path takes 15 gate delays, plus 1 to set up, so with a period of 16 or more it counts correctly forever. Slide it lower. The chart shows the adder’s outputs during the tick that goes wrong (or, when nothing does, the hardest one, from 127), and the shaded column is when the register samples them. At 15, the step from 126 gives 255: a glitch left over from the tick before is still running up the carry chain when the register samples it.

Notice that, a little too fast, it counts correctly most of the time, and only goes wrong at particular numbers, where the carry has far to travel. That’s what makes timing bugs nasty: a circuit can pass a quick test and still be broken. Chip designers don’t rely on testing for this. Tools add up the delay along every path through the logic (static timing analysis), and the slowest one sets the clock.

5 · Metastability

Everything above assumes the inputs change at sensible times: just after a clock edge, with a whole tick to settle. Signals from the outside world don’t know about the clock. A key press can arrive at any moment, including the instant the clock rises, and then the flip-flop’s setup time is broken.

What happens then is the forbidden input of the SR latch all over again. The latch inside the flip-flop is caught halfway, and has to fall one way or the other. Usually it does so quickly. Occasionally it hovers, metastable, for longer, and whatever reads it meanwhile may see a 0, a 1, or something in between.

It can’t be prevented, only made very unlikely. The standard fix is a synchroniser: the outside signal goes through two flip-flops in a row before anything uses it, so the first has a whole tick to settle before the second reads it. The chance of a hover lasting that long falls off exponentially with the time allowed, so one extra tick turns “now and then” into “practically never”.

Summary

A synchronous circuit is registers and logic in a loop: the registers hold the state, the logic works out the next state, and each clock tick moves everything on together. A counter is the simplest.
A state machine has a fixed set of states and moves between them on its inputs: drawn as a diagram, written as a transition table. It does exactly what its table says, in every case, wanted or not.
To build one, number the states in flip-flops; the next-state logic is a truth table, built as on the earlier pages.
The clock can only go as fast as the slowest path, the critical path, plus the flip-flops’ setup time. Too fast, and the circuit fails only at particular values.
Inputs from outside can break the setup time and leave a flip-flop metastable; a synchroniser of two flip-flops makes that vanishingly rare.