Appearance
3.1 — Logic Families, Voltage Levels and Boolean Simplification
A digital circuit is an analog circuit that has agreed to ignore most of what its wires are doing. The voltage on a wire is some continuous value between 0 V and the supply; the circuit declares that anything below one number means 0, anything above another number means 1, and the band between them is a place no signal is allowed to linger.
That single act of throwing information away is what makes digital electronics able to copy a signal a billion times with no loss, while an analog copy degrades every time. The noise gets thrown away with everything else.
The switch this chapter builds everything from is the MOSFET of Chapter 2.4, and the algebra it obeys is the Boolean algebra of Volume I Chapter 1.2. What is new here is the bridge between them: how a continuous voltage gets treated as one of exactly two values, and what it costs to insist on that fiction.
1. Voltage levels and noise margins
Every logic family defines four voltages, and the relationships between them are the whole contract.
- V_{OH} — the minimum voltage a driving output guarantees when sending a 1.
- V_{OL} — the maximum voltage an output guarantees when sending a 0.
- V_{IH} — the minimum voltage a receiving input will reliably read as a 1.
- V_{IL} — the maximum voltage an input will reliably read as a 0.
For the system to work, the output must promise more than the input demands. The gap is the noise margin:
NM_H = V_{OH}-V_{IH}, \qquad NM_L = V_{IL}-V_{OL}
Worked example — 5 V CMOS (the HC family). V_{OH} = 4.4 V, V_{IH} = 3.5 V, V_{IL} = 1.5 V, V_{OL} = 0.1 V.
NM_H = 4.4-3.5 = 0.9\ \text{V}, \qquad NM_L = 1.5-0.1 = 1.4\ \text{V}
Nearly a volt of noise can be injected onto the wire and the receiver still reads the right value. Compare 5 V TTL: V_{OH} = 2.4 V, V_{IH} = 2.0 V, giving a high-level margin of just 0.4 V. TTL was much more easily upset, and that is one of several reasons CMOS won.
The forbidden band is where a signal must not sit still. An input held at 2.5 V in a 5 V CMOS system will make both transistors of the input inverter conduct at once, drawing large current and possibly oscillating. That is why every unused CMOS input must be tied high or low, and why a floating input causes chips to run hot and behave erratically.
2. The families, and why CMOS won
TTL (transistor-transistor logic, 1963) is built from bipolar transistors. It is fast for its era, draws several milliamps per gate even when idle, and has that thin high-level noise margin. Its subfamilies — LS, S, ALS, F, AS — traded speed against power. Historically enormous; today essentially gone.
CMOS (complementary metal-oxide semiconductor) uses the NMOS/PMOS pair described in Chapter 2.4. Static power is essentially zero, noise margins are wide, and the supply can be anything from 1.8 V to 15 V depending on family. Everything modern is CMOS.
ECL (emitter-coupled logic) keeps its transistors in the active region and never lets them saturate, so there is no storage delay and it is extremely fast — but it burns enormous power continuously. It ran the fastest mainframes and is now confined to specialist high-speed serial links.
LVDS (low-voltage differential signalling) sends a signal as the difference between two wires with a swing of only 350 mV. Because interference hits both wires equally and the receiver looks only at the difference, it rejects noise brilliantly and radiates almost none. This is how every high-speed link on a modern board works — display interfaces, PCIe, USB 3, Ethernet.
| Family | Supply | Static power/gate | Delay | Where |
|---|---|---|---|---|
| TTL LS | 5 V | 2 mW | 10 ns | historical |
| CMOS HC | 2–6 V | ~0 | 8 ns | glue logic |
| CMOS LVC | 1.65–3.6 V | ~0 | 3 ns | modern boards |
| ECL | −5.2 V | 25 mW | 0.5 ns | historical high speed |
| LVDS | 2.5 V | differential | ps | every fast link |
Mixing supply voltages
Modern boards run 3.3 V, 1.8 V and 1.2 V parts together, and connecting them naively destroys things.
3.3 V driving 5 V: a 3.3 V high may not exceed the 5 V part's V_{IH} of 3.5 V. Sometimes it works, often it does not, and it never works reliably across temperature.
5 V driving 3.3 V: the 5 V high exceeds the 3.3 V part's absolute maximum input, and current flows into its input protection diode (Chapter 2.2) and eventually kills it.
The fixes are a dedicated level shifter chip, a resistor divider for slow signals, or a MOSFET-based bidirectional shifter for buses like I²C. Checking level compatibility is one of the first things to do when a board does not work.
3. Fan-out, drive and loading
Fan-out is how many inputs one output can drive.
For TTL, the limit was current: each input sank a defined current when low, and the driver could only sink so much. The classic answer was 10.
For CMOS, inputs draw essentially no DC current, so the DC fan-out is in the thousands. The real limit is capacitance. Every input presents a few picofarads, and the driver must charge all of them through its own R_{DS(on)}:
t_{rise} \approx 2.2\,R_{DS(on)}\,C_{total}
Worked example. A driver with R_{DS(on)} = 50\ \Omega feeding 20 inputs of 5 pF each, plus 30 pF of track capacitance:
C = 20\times5 + 30 = 130\ \text{pF}, \qquad t_{rise} = 2.2\times50\times130\times10^{-12} = 14.3\ \text{ns}
At 10 MHz that is 14% of the clock period — probably acceptable. At 100 MHz it is 143% and the signal never arrives. So CMOS fan-out is a timing limit, not a current limit, and the fix is a buffer that splits the load into two branches.
Dynamic power also rises with the load, from P = CV^2f (Chapter 2.4). Driving 130 pF at 3.3 V and 50 MHz costs 130\times10^{-12}\times10.9\times5\times10^7 = 71 mW from one output pin.
Output types
Totem pole (push-pull) — the standard. An NMOS pulls low and a PMOS pulls high. Fast and strong. Never connect two of these outputs together: if one drives high while the other drives low, you have a short circuit from supply to ground through two transistors, and something burns.
Open drain (or open collector) — only the pull-down transistor exists; the high state is "not driving". An external pull-up resistor supplies the high. This allows many outputs on one wire: any of them can pull it low, and it goes high only when all of them release. That is a wired-AND, and it is exactly how I²C and interrupt lines work.
The pull-up value is a trade: small means fast rising edges but high current when low; large means low power but slow edges from the RC formed with the bus capacitance. For I²C at 100 kHz with 200 pF of bus capacitance, the standard answer is 4.7 kΩ, giving a rise time of about $2.2\times4700\times200\times10^{-12} = 2\ \mu$s — a fifth of the clock period, which is exactly what the specification allows.
Tri-state — a push-pull output plus an enable that disconnects it entirely. This is what makes a shared bus possible: many devices connected to the same wires, with exactly one enabled at a time. Every memory chip's data pins are tri-state.
4. Boolean algebra — the identities that matter
Volume I, Chapter 1.1 introduced Boolean algebra and the gates. What is needed here is the machinery for simplifying an expression, because a simpler expression is fewer gates, less power, and less delay.
The identities, with the ones people forget marked:
A+0 = A \qquad A\cdot1 = A \qquad A+1 = 1 \qquad A\cdot0 = 0
A+A = A \qquad A\cdot A = A \qquad A+\bar A = 1 \qquad A\cdot\bar A = 0
Distribution works both ways, unlike ordinary algebra:
A(B+C) = AB+AC \qquad\text{and}\qquad A+BC = (A+B)(A+C)
The second one looks wrong and is correct. Check it with A=1: left side is 1, right side is (1)(1) = 1 ✓. With A=0: left is BC, right is BC ✓.
Absorption, the identity that does most of the simplifying work:
A+AB = A \qquad\qquad A(A+B) = A
Proof of the first: A+AB = A(1+B) = A\cdot1 = A. In words: if A alone is enough, adding a term that also requires A changes nothing.
A+\bar AB = A+B \qquad\qquad A(\bar A+B) = AB
Proof: A+\bar AB = (A+\bar A)(A+B) = 1\cdot(A+B) = A+B, using the second distribution law.
De Morgan's laws, the most-used pair in all of digital design:
\overline{A+B} = \bar A\cdot\bar B \qquad\qquad \overline{A\cdot B} = \bar A+\bar B
In plain words: to negate a whole expression, negate every variable and swap every AND with every OR. "Not (A or B)" is "not A and not B" — it is not raining and not snowing, if it is not the case that it is raining or snowing.
The practical importance is that it lets any circuit be built entirely from NAND gates, or entirely from NOR gates. NAND is the cheapest gate to make in CMOS, so a chip designer converts everything to NAND. Volume I, 1.1 showed the conversions; De Morgan is why they exist.
Worked simplification
F = AB + A\bar BC + A\bar B\bar C
Factor A\bar B from the last two terms:
= AB + A\bar B(C+\bar C) = AB + A\bar B(1) = AB+A\bar B
Factor A:
= A(B+\bar B) = A
Three product terms and seven gate inputs collapsed to a plain wire. That is the kind of saving that matters when a design has thousands of such expressions.
5. Karnaugh maps
Algebraic simplification works but requires seeing the right factorisation. A Karnaugh map makes the simplification visual, and for up to about five variables it is faster and more reliable than algebra.
The idea: arrange the truth table in a grid where adjacent cells differ in exactly one variable. Then any pair of adjacent 1s means "this variable does not matter here", and can be merged.
The row and column labels are therefore in Gray code order — 00, 01, 11, 10 — not binary counting order. That is the single most important detail and the one people get wrong.
The rules for grouping
- Group only 1s (for a sum-of-products result).
- Group sizes must be powers of two: 1, 2, 4, 8, 16. A group of three is not allowed.
- Groups must be rectangular, and may wrap around the edges — the left column is adjacent to the right column, and the top row to the bottom row. The map is really a torus.
- Make every group as large as possible. A bigger group eliminates more variables.
- Groups may overlap. Reusing a 1 costs nothing.
- Every 1 must be in at least one group.
- Stop when all 1s are covered. Do not add a group whose 1s are all already covered.
The payoff rule: a group of 2^k cells eliminates k variables. A group of 1 keeps all four; a group of 8 keeps only one.
Worked example with don't-cares
Design a circuit that lights an LED when a BCD digit (0 to 9, four bits ABCD with A the most significant) is a prime: 2, 3, 5, 7.
The map has 1s at 2, 3, 5, 7 and 0s at 0, 1, 4, 6, 8, 9. Inputs 10 to 15 never occur, because BCD only uses 0 to 9, so they are don't-cares, written X. You may treat each X as 0 or 1, whichever makes groups bigger.
Cells (in ABCD): 2 = 0010, 3 = 0011, 5 = 0101, 7 = 0111.
Group 2 and 3 together: they share \bar A\bar BC and differ only in D, giving \bar A\bar BC. Extend using don't-cares 10 and 11 (1010, 1011), which are adjacent in A — now A is eliminated too, giving \bar BC.
Group 5 and 7: both \bar ABD, differing in C, giving \bar ABD. Extend with don't-cares 13 and 15 to eliminate A, giving BD.
F = \bar BC + BD
Two AND gates and one OR gate. Without the don't-cares the answer would have been \bar A\bar BC + \bar ABD, needing two extra inputs. Don't-cares are free simplification and should always be hunted for.
Beyond four variables
Five-variable maps are drawn as two four-variable maps side by side, with groups allowed to span both. Six is drawn as four maps and is at the edge of usefulness.
Beyond that, use the Quine-McCluskey algorithm, which does the same job by systematic tabulation rather than by eye and can be programmed. In practice nobody does either by hand past four variables: a synthesis tool reads a hardware description and does the minimisation, using algorithms far better than both. Karnaugh maps are worth learning because they teach what minimisation is — and because for a four-input problem on paper they remain the fastest route.
6. Propagation delay and glitches
Every gate takes time. Propagation delay t_{pd} is the time from an input changing to the output settling, typically 1 to 10 ns for discrete logic and picoseconds on a chip.
Delays add along a path. The slowest path from any input to any output is the critical path, and it sets the maximum clock frequency of the whole circuit:
f_{max} = \frac{1}{t_{critical} + t_{setup}}
Chapter 3.3 makes this precise.
The hazard
Delays cause a subtler problem. Consider F = AB + \bar AC with B = C = 1. Algebraically F = A + \bar A = 1 always, whatever A does.
But when A falls from 1 to 0, the AB term goes low immediately while the \bar AC term must wait for the inverter's delay. For those few nanoseconds both terms are low, and the output dips to 0. That is a static hazard — a glitch on an output that should have been constant.
In a purely combinational path feeding a clocked flip-flop, glitches are harmless as long as they settle before the clock edge. But if that output feeds an asynchronous reset, a clock input, or an edge-triggered device, the glitch is indistinguishable from a real signal and the circuit fails intermittently in a way that is extremely hard to debug.
The fix is a redundant term. Add BC:
F = AB+\bar AC+BC
The extra term is logically redundant — it never changes the truth table — but it holds the output high during the transition. On a Karnaugh map, a hazard exists wherever two adjacent 1s are not covered by any common group, and the fix is to add an overlapping group that bridges them. That is the practical reason to draw the map even when you already know the algebra.
With the electrical rules and the simplification method in place, the next chapter builds the standard combinational blocks — the adders, multiplexers and decoders that every processor is assembled from.
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.
Logic levels and margins
NM_H = V_{OH}-V_{IH}, \qquad NM_L = V_{IL}-V_{OL}
A link works only when both are positive: the driver must promise more than the receiver demands.
t_{rise} \approx 2.2\,R_{on}C_{load}
Where the 2.2 comes from: rise time is conventionally measured from 10% to 90%. From the RC charging law of Chapter 1.5, reaching 10% takes 0.105\tau and reaching 90% takes 2.303\tau, so the difference is 2.2\tau.
P_{dynamic} = \alpha CV^2f, \qquad P_{static} = I_{leak}V
Boolean identities
A+0=A \quad A\cdot1=A \quad A+1=1 \quad A\cdot0=0
A+A=A \quad A\cdot A=A \quad A+\bar A=1 \quad A\cdot\bar A=0 \quad \bar{\bar A}=A
Distribution, both directions:
A(B+C)=AB+AC \qquad A+BC=(A+B)(A+C)
Proof of the second by cases. If A=1: left is 1, right is 1\cdot1=1 ✓. If A=0: left is BC, right is B\cdot C ✓.
Absorption:
A+AB=A \qquad A(A+B)=A
Proof: A+AB = A(1+B) = A\cdot1 = A.
A+\bar AB = A+B \qquad A(\bar A+B)=AB
Proof: A+\bar AB = (A+\bar A)(A+B) = 1\cdot(A+B).
De Morgan:
\overline{A+B}=\bar A\bar B \qquad \overline{AB}=\bar A+\bar B
Consensus (the hazard-removing term):
AB+\bar AC+BC = AB+\bar AC
The third term is logically redundant but electrically essential — it holds the output steady while the other two swap over.
XOR:
A\oplus B = A\bar B+\bar AB, \qquad A\oplus 0 = A, \qquad A\oplus 1 = \bar A, \qquad A\oplus A = 0