Sequential logic: state machines and timing
A device that hangs once a day for no apparent reason may have a flip-flop reading an unsynchronized pushbutton. Adding a second flip-flop pushes that failure out to once every tens of thousands of years.
01Synchronous design
Flip-flops, counters and shift registers are covered in the page on sequential logic in the Electronics Technician program. This unit goes up one level: how any sequential system is designed and what limits it.
Almost all modern digital logic is synchronous: a single clock marks the instants at which all the flip-flops take their new value, and between one edge and the next the combinational logic has time to settle. That discipline solves the hazard problem of the previous unit in one stroke: glitches still occur, but the flip-flop looks at its input only right at the edge, when it has already settled.
02State machines: Moore and Mealy
A finite state machine describes a sequential circuit as a set of states and of transitions between them. There are two ways to produce the outputs, and the difference matters:
| Moore | Mealy | |
|---|---|---|
| The output depends on | The state only | The state and the current input |
| In the diagram, the output goes | Inside the state | On the transition |
| When it responds | One cycle later | In the same cycle |
| States needed | Usually needs a few more | Fewer |
| The output can have glitches | No: it comes from flip-flops | Yes: it passes through the input logic |
The machine receives one bit per clock cycle and sets the output to 1 when the last four bits were 1011 (sequences may overlap). You choose Moore or Mealy and feed it bits one at a time; the active state is highlighted in the diagram and the table keeps the last cycles.
03From the diagram to the circuit
The diagram is translated into a state table, and each state receives a binary code. The choice of that code —the state assignment— changes the resulting circuit:
| Encoding | Flip-flops for N states | When it is a good choice |
|---|---|---|
| Binary | \( \lceil \log_2 N \rceil \) | When flip-flops are expensive, as in discrete logic |
| Gray | \( \lceil \log_2 N \rceil \) | If the transitions follow a sequence: one bit changes at a time |
| One-hot | \( N \) | In FPGAs: flip-flops are plentiful and the next-state logic ends up minimal and fast |
With the encoding chosen, each bit of the next state and each output are combinational functions of the state bits and the inputs, and they are minimized exactly as in the previous unit.
04Timing: the maximum frequency
Between two clock edges, the data has to leave the first flip-flop, cross the logic and reach the second with enough time to spare for it to capture the data. That race sets the maximum frequency of the whole system.
There is also a condition in the opposite direction: the data cannot change too soon after the edge, during the hold time (the hold window). And if the clock does not reach all the flip-flops at the same time —the difference is called clock skew— both margins shrink.
05Metastability: when the input does not respect the clock
A signal that comes from outside —a pushbutton, another circuit with its own clock— can change right inside the setup-and-hold window. The flip-flop is then left in a metastable state: neither 0 nor 1, like a ball balanced on top of a hill, and it takes a random time to fall to one side. If the following logic reads it before then, it may read it differently in two places of the circuit and the system fails in a way that is impossible to reproduce.
The probability that it is still undecided decays exponentially with the time it is given to resolve. From this comes the mean time between failures:
An asynchronous input that changes on average one million times per second enters a 100 MHz system, with flip-flops of \( \tau = 50 \) ps and \( T_0 = 1 \) ns (illustrative values, on the order of fast logic). You choose how many flip-flops in a chain the synchronizer uses and how much resolution time each one leaves.
That is why no asynchronous signal enters a synchronous design without first passing through a synchronizer of at least two flip-flops. It does not make failure impossible —no circuit can—: it makes it so improbable that it stops mattering.
06Where it shows up in electronics
| Case | What is used from this unit |
|---|---|
| Controller of a serial protocol (UART, I²C) | A state machine that steps through the bits of each frame |
| Pushbutton on a device | Two-flip-flop synchronizer plus debouncing before it enters the logic |
| FPGA synthesis report | The tool computes the critical path and the maximum frequency reached |
| Passing data between two clock domains | Synchronizers and FIFO memories with Gray-code pointers |
07In the lab
Turn the lab’s Moore machine into a state table, encode it in binary and in one-hot, and compare how many flip-flops and gates each version needs.
Implement both versions on a development board and observe with two channels when the output of each one goes high relative to the clock edge on which the last 1 arrives.
With the timings from the synthesis report of a design of your own, verify the maximum frequency by hand with the critical-path formula.
08Common mistakes
- Using a Mealy output as a clock or an enable. It can have glitches: it passes through the input logic.
- Forgetting the initial state. Every machine needs a reset that takes it to a known state.
- Reading an asynchronous input directly. Without a synchronizer, metastability is a matter of time.
- Believing a synchronizer eliminates metastability. It makes it improbable, not impossible.
- Adding up only the logic delays. The minimum period includes \( t_{cq} \) and \( t_{su} \).
09Self-assessment
What distinguishes a Moore machine from a Mealy machine?
In Moore the output depends only on the state; in Mealy, on the state and the current input, so it responds one cycle earlier.
Why is one-hot encoding used in FPGAs?
Because they have plenty of flip-flops, and so the next-state logic ends up minimal and fast.
What limits the maximum frequency of a synchronous circuit?
The critical path: \( t_{cq} + t_{\text{logic}} + t_{su} \) between two flip-flops.
What is metastability?
The undefined state a flip-flop is left in when its input changes during the setup-and-hold window; it resolves in a random time.
Why does a second flip-flop improve the MTBF so much?
Because it gives the first one an extra period to resolve, and the MTBF grows exponentially with that time.
10Further reading
- John F. Wakerly. Digital Design: Principles and Practices. 5th ed., Pearson, 2018. State machines, timing and the best introductory chapter on metastability and synchronizers.
- William J. Dally and R. Curtis Harting. Digital Design: A Systems Approach. Cambridge University Press, 2012. Synchronous design from the viewpoint of someone who designs processors, with the timing margins in detail.
- Clifford E. Cummings. Clock Domain Crossing (CDC) Design & Verification Techniques Using SystemVerilog. SNUG Boston, 2008. The industry’s reference paper on how to pass signals between clock domains.