Appearance
3.3 — Latches, Flip-Flops, Counters and State Machines
Take two NOR gates and connect each one's output to the other's input. Nothing else. That circuit remembers.
It is worth sitting with how strange that is. Every gate in Chapter 3.2 was a function: inputs in, outputs out, no history. Cross-couple two of them and the circuit acquires a past, and the entire distinction between a calculator and a computer follows from it.
1. The SR latch — memory from a loop
Two NOR gates, each output feeding the other's input, with S and R as the remaining inputs.
Trace it. Suppose Q = 1 and \bar Q = 0, with S and R both 0. The top gate sees R = 0 and \bar Q = 0, so its output is 1 — which is Q, consistent. The bottom gate sees S = 0 and Q = 1, so its output is 0 — which is \bar Q, consistent. The state holds itself up. The same check works for Q=0.
Now the inputs:
| S | R | Q | Meaning |
|---|---|---|---|
| 0 | 0 | holds | remember |
| 1 | 0 | 1 | set |
| 0 | 1 | 0 | reset |
| 1 | 1 | — | forbidden |
The forbidden state. With both S and R high, both gates output 0, so Q and \bar Q are both 0 — which contradicts their names. Worse, when the inputs are released simultaneously, both gates try to go high at once, each sees the other going high, and which one wins is decided by whichever gate happens to be a picosecond faster. The final state is unpredictable. That is why the row is marked forbidden, and it is the first appearance of a problem that returns in section 8 as metastability.
Built from NAND gates instead, the same structure gives an active-low \bar S\bar R latch, where the inputs rest at 1 and the forbidden combination is 0,0.
The one place a bare SR latch is genuinely useful
Switch debouncing. A mechanical switch's contacts bounce for several milliseconds, producing dozens of transitions. Use a changeover switch with two contacts feeding S and R: the first touch of one contact sets the latch, and further bounces on that same contact do nothing because setting an already-set latch changes nothing. The output is clean from the first microsecond.
2. The gated latch, and why it is not enough
Add an enable line: AND the S and R inputs with it, so the latch only responds while enable is high.
This is a level-sensitive or transparent latch. While enable is high, the output follows the input continuously — the latch is "transparent". When enable falls, the last value is held.
The D latch simplifies this further: one data input D, with S = D and R = \bar D, which makes the forbidden state impossible to reach.
The problem with transparency. During the whole time enable is high, changes on D flow straight through to Q, and from there into whatever the output feeds. If that feeds back — as it does in every counter and every state machine — the circuit races around the loop several times in one enable pulse, and the final state depends on gate delays. Transparent latches cannot be used in feedback loops, which rules them out of almost every sequential circuit.
3. The flip-flop — edge triggering
The fix is to make the device respond only at the instant the clock changes, not throughout its high period. That is an edge-triggered flip-flop, and it is the fundamental unit of all synchronous digital design.
The classic implementation is the master-slave pair: two latches in series with opposite enable polarities.
- While the clock is low, the master latch is transparent and tracks D. The slave is closed, holding the old output.
- At the rising edge, the master closes — freezing whatever D was at that instant — and the slave opens, passing that frozen value to the output.
- While the clock is high, the master is closed, so further changes on D are ignored entirely.
The result: Q changes only at the clock edge, and takes the value D had at that edge. There is no window during which input changes leak through, so feedback loops are safe.
The three timing numbers
- Setup time t_{su} — how long D must already be stable before the clock edge.
- Hold time t_h — how long D must remain stable after the edge.
- Clock-to-Q t_{co} — how long after the edge Q actually changes.
Violate setup or hold and the flip-flop may capture garbage, or go metastable (section 8). These three numbers are what the whole of timing analysis is built from, and section 7 uses them.
The other flip-flop types
JK flip-flop. Like SR but the forbidden combination is redefined to mean "toggle". With J = K = 1 the output flips at every clock edge. Historically important because it is universal, but it needs two inputs where D needs one, and modern design uses D exclusively — a toggle is built by feeding \bar Q back to D.
T flip-flop. A JK with both inputs tied together. T = 1 toggles, T = 0 holds. This is the counter's basic cell.
Asynchronous inputs. Most flip-flops have a preset and a clear that act immediately, ignoring the clock. They are essential for power-on reset and dangerous everywhere else: because they bypass the clock entirely, any glitch on them (Chapter 3.1) is captured as a real command. Use them only for reset, and synchronise the release of that reset.
4. Registers and shift registers
n flip-flops sharing one clock is a register — an n-bit value updated all at once. Every processor register, every pipeline stage, every latched output port is this.
Chain them, each one's Q feeding the next one's D, and you get a shift register: on every clock edge, every bit moves one position along.
The four wiring options give the four standard types, and each has a real job:
| Type | Job |
|---|---|
| Serial in, parallel out | receive a byte arriving one bit at a time |
| Parallel in, serial out | send a byte down one wire |
| Serial in, serial out | delay a signal by n clocks |
| Parallel in, parallel out | plain register |
Where you use them. The 74HC595 — serial in, parallel out — lets three microcontroller pins drive eight outputs, and cascading two of them gives sixteen from the same three pins. Every LED matrix and seven-segment display module works this way. In reverse, the 74HC165 reads eight switches into three pins. This is the standard answer to "I have run out of pins".
Feed the output back through XOR gates at chosen positions and you get a linear feedback shift register, which cycles through 2^n-1 states in an order that looks random. That is how a cheap pseudorandom generator works, how a CRC checksum is computed in hardware, and how the spreading codes of Chapter 7.4 are generated.
5. Counters
Asynchronous (ripple) counters
Chain toggle flip-flops, each clocked by the previous one's output. Each stage divides the frequency by two, so n stages count to 2^n-1.
Simple, and flawed. The stages do not change together — stage 1 waits for stage 0, which waits for the clock. Going from 0111 to 1000, the outputs pass briefly through 0110, 0100, 0000 before settling at 1000. Those transient values are real on the wires, and anything watching the count — a decoder, a comparator — sees them as genuine.
Total settling time is n\times t_{co}, which for a 16-bit counter with 10 ns flip-flops is 160 ns. Ripple counters are fine for dividing a clock and unsafe for anything decoded.
Synchronous counters
Clock every flip-flop from the same signal, and use logic to decide which bits should toggle.
The rule: bit i toggles when all lower bits are 1.
T_0 = 1, \quad T_1 = Q_0, \quad T_2 = Q_0Q_1, \quad T_3 = Q_0Q_1Q_2
Now every output changes at the same edge, and the total delay is one t_{co} plus one AND-chain delay, regardless of width. No transient states appear.
The AND chain does eventually limit speed for wide counters, and the fix is the same as the adder's: compute the enable terms in parallel with lookahead logic.
Modulo-N counters
To count to something other than a power of two, detect the terminal value and reset.
A decade counter (0 to 9): detect 1010 and clear. Only two bits need watching, since 1010 is the first count where Q_3 and Q_1 are both 1:
\text{clear} = Q_3Q_1
But an asynchronous clear creates a hazard. The counter momentarily reaches 1010 before the clear takes effect, so a glitch of a few nanoseconds appears on Q_1 and Q_3. Feed those into a decoder and you get a spurious pulse.
The clean version uses a synchronous load: detect 1001 (the last valid count) and load zero on the next edge. The count never illegally reaches 1010 at all. Preferring synchronous clears and loads over asynchronous ones is one of the most consistent rules of good digital design.
6. Finite state machines
Everything above combines into the general form: a machine with a memory of which state it is in, rules for moving between states, and outputs that depend on the state.
The standard structure is three blocks:
- State register — flip-flops holding the current state.
- Next-state logic — combinational, computing the next state from the current state and the inputs.
- Output logic — combinational, computing the outputs.
Moore machine: outputs depend only on the state. Outputs change only at clock edges, so they are glitch-free. Usually needs more states.
Mealy machine: outputs depend on the state and the inputs. Fewer states and it can react in the same cycle — but its outputs change whenever the input does, so they can glitch. Choose Moore unless you need the extra speed, and if you use Mealy, register the outputs.
Worked design: a sequence detector
Detect the pattern 1011 in a serial bit stream, with overlapping matches allowed.
States, each named by how much of the pattern has been matched so far:
- S0 — nothing matched
- S1 — matched
1 - S2 — matched
10 - S3 — matched
101
Transitions. From each state, ask what each input bit does.
| State | Input 0 | Input 1 | Output |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 on the input 1 |
The subtle rows are the failures. From S1 (matched 1) seeing another 1: you have not failed — the new 1 could start a fresh match, so go to S1, not S0. From S3 (matched 101) seeing a 0: you have 1010, whose last two bits 10 are a valid prefix, so go to S2, not S0. Getting these "partial failure" transitions right is the entire skill of state machine design, and it is the same reasoning as the KMP string-matching algorithm in Volume I, Chapter 4.12.
Encoding. Four states need two bits. Binary encoding (00, 01, 10, 11) uses the fewest flip-flops. One-hot encoding uses one flip-flop per state, with exactly one high — more flip-flops but far simpler next-state logic, since each state's condition is a single bit rather than a decoded combination. Inside an FPGA, where flip-flops are abundant and logic depth costs speed, one-hot is usually the right choice. In an ASIC where area is money, binary usually wins.
Design rule that catches real bugs: with two bits you have four states and all four are used, so any illegal state is impossible. With five states you would use three bits, leaving three unused codes — and a glitch or a power-up transient can land the machine in one of them, where it may loop forever. Always add a default transition that sends unused states back to the reset state.
7. Timing analysis — the calculation that decides the clock speed
Data leaves one flip-flop, passes through combinational logic, and must arrive at the next flip-flop in time to meet its setup requirement.
\boxed{T_{clk} \ge t_{co} + t_{logic} + t_{su} + t_{skew}}
Worked example. t_{co} = 3 ns, longest logic path 12 ns, t_{su} = 2 ns, clock skew 1 ns:
T \ge 3+12+2+1 = 18\ \text{ns} \;\Rightarrow\; f_{max} = 55.6\ \text{MHz}
To go faster you must reduce one of the four terms. The logic path is usually the biggest and the only one you control, which is why pipelining — splitting the logic in half with an extra register — is the standard answer.
The hold violation, which is worse
Setup failures are fixed by slowing the clock. Hold failures cannot be.
t_{co} + t_{logic(min)} \ge t_h + t_{skew}
This says data must not arrive too early — before the receiving flip-flop has finished latching the previous value. Notice that the clock period does not appear. A hold violation fails at every frequency, including DC. The only fixes are adding delay to the data path, or fixing the clock distribution so the skew is smaller.
This is why clock trees are designed so carefully, and why every synthesis tool reports setup and hold as separate problems with different urgencies.
8. Metastability, and crossing clock domains
Section 1's forbidden state was not just a textbook curiosity. Here is the real version.
If D changes during the setup-hold window, the flip-flop's internal cross-coupled pair is pushed to the exact balance point between 0 and 1 — like a pencil balanced on its tip. It will eventually fall one way, but how long it takes is unbounded, and while it is undecided the output sits at an illegal intermediate voltage.
The probability of still being undecided after time t falls exponentially:
\text{MTBF} = \frac{e^{t/\tau}}{T_0\,f_{clk}\,f_{data}}
where \tau is a device constant of a few hundred picoseconds. The exponential is the good news: waiting a couple of nanoseconds longer improves the mean time between failures by orders of magnitude.
The synchroniser
Any signal crossing from one clock domain to another must pass through two flip-flops in series clocked by the destination clock. The first may go metastable; the second samples it a whole clock period later, by which time the exponential has made resolution overwhelmingly likely.
Worked example. A 100 MHz clock, an asynchronous input changing at 1 MHz, \tau = 200 ps, T_0 = 1 ns, and a resolution window of 8 ns available:
\text{MTBF} = \frac{e^{8/0.2}}{10^{-9}\times10^8\times10^6} = \frac{e^{40}}{10^5} = \frac{2.35\times10^{17}}{10^5} = 2.35\times10^{12}\ \text{s}
That is about 75,000 years. With only one flip-flop and 0.5 ns of margin, the same sum gives e^{2.5}/10^5 = 1.2\times10^{-4} s — a failure every tenth of a millisecond. The difference between a working design and an unusable one is one extra flip-flop.
For multi-bit values you cannot simply synchronise each bit, because they may resolve on different clocks and you would read a value that never existed. The standard solutions are a handshake (sender holds the data steady and raises a flag, receiver acknowledges), a FIFO with Gray-coded pointers (which is why Chapter 3.2's Gray code matters — only one bit changes, so a mis-sampled pointer is off by at most one and still safe), or a shared memory with mutually exclusive access.
Every intermittent, un-reproducible digital fault should be checked against this list first. Clock domain crossing bugs fail once a day, pass every test, and are the classic reason a product works on the bench and fails in the field.
The flip-flops of this chapter store one bit each and cost several transistors. The next chapter looks at how to store billions of bits, where the cost per bit is everything and each technology makes a different bargain.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Sequential timing
\boxed{T_{clk} \ge t_{co}+t_{logic(max)}+t_{su}+t_{skew}}
f_{max} = \frac{1}{t_{co}+t_{logic}+t_{su}+t_{skew}}
Hold constraint:
t_{co}+t_{logic(min)} \ge t_h+t_{skew}
The clock period does not appear, which is why a hold violation cannot be fixed by slowing the clock. It fails at every frequency.
Metastability
\text{MTBF} = \frac{e^{t_r/\tau}}{T_0\,f_{clk}\,f_{data}}
t_r is the resolution time available, \tau a device constant of a few hundred picoseconds, T_0 a device constant of around a nanosecond.
The exponential is the whole story: doubling the available settling time squares the mean time between failures. Two flip-flops in series give a full clock period of settling and turn a failure every millisecond into one every geological age.
Counters
Synchronous toggle condition: T_i = \prod_{j<i}Q_j — bit i toggles when every lower bit is 1.
Modulo-N: detect N-1 and load zero synchronously, rather than detecting N and clearing asynchronously.
Ripple counter settling: n\,t_{co}, with invalid intermediate codes throughout.
Frequency division: n stages divide by 2^n.