Appearance
3.2 — Combinational Building Blocks
A combinational circuit's output depends only on its inputs right now. No memory, no clock, nothing carried over from before. Give it the same inputs and it always gives the same answer, after the propagation delay of Chapter 3.1.
Five blocks make up nearly all of it: adders, multiplexers, decoders, encoders and comparators. Volume I, Chapter 1.2 met the half adder and full adder from the computing side; this chapter builds them properly, prices their delays, and adds the four blocks that chapter skipped.
1. The half adder and full adder
Adding two bits gives a sum and possibly a carry:
| A | B | Sum | Carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
S = A\oplus B, \qquad C = AB
The sum column is exactly XOR — 1 when the inputs differ — and the carry is AND. That is a half adder, and it is useless on its own because it cannot accept a carry coming in from the column to its right.
A full adder takes three inputs: A, B, and C_{in}.
S = A\oplus B\oplus C_{in}
C_{out} = AB + C_{in}(A\oplus B)
Read the carry expression in words: there is a carry out if both A and B are 1, or if exactly one of them is 1 and a carry came in. An equivalent and more symmetric form is C_{out} = AB+BC_{in}+AC_{in}, which says "a carry out whenever at least two of the three inputs are 1" — the majority function.
Built from two half adders and an OR gate, the delay is roughly two XOR delays to the sum and one XOR plus one AND plus one OR to the carry.
2. The ripple-carry adder and why it is too slow
Chain n full adders, each one's C_{out} feeding the next one's C_{in}. That adds two n-bit numbers, and it is the obvious construction.
The problem is the carry. Bit 0's carry must be computed before bit 1 can finish, whose carry must be computed before bit 2, and so on. The worst case propagates all the way:
t_{total} = n\cdot t_{carry}
Worked example. A 32-bit adder from full adders with a 1 ns carry delay takes 32 ns, which caps the clock at about 31 MHz. Every processor built since 1960 needed better.
Watch the worst case concretely: add 0111...111 to 0000...001. Bit 0 produces a carry, which makes bit 1 produce a carry, all the way to the top. One input bit changing forces every bit to change, in sequence.
3. Carry-lookahead — computing the carries in parallel
The insight is that you can decide whether a bit position will produce or pass on a carry without waiting to know whether a carry actually arrives.
Define, for each bit position:
G_i = A_iB_i \qquad\text{(generate — this position makes a carry regardless)}
P_i = A_i\oplus B_i \qquad\text{(propagate — this position will pass a carry through)}
Then
C_{i+1} = G_i + P_iC_i
Substitute repeatedly to eliminate the chain:
C_1 = G_0+P_0C_0
C_2 = G_1+P_1C_1 = G_1+P_1G_0+P_1P_0C_0
C_3 = G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0C_0
C_4 = G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_0
Every carry is now a two-level expression of the original inputs. All the $G$s and $P$s are computed simultaneously in one gate delay, and all four carries in two more. The 4-bit adder's carry delay is three gate delays instead of four full-adder delays, and — crucially — it does not grow with the number of bits in the group.
The cost is gate count and fan-in. C_4 needs a 5-input OR gate and a 5-input AND gate; C_{16} would need 17 inputs, which no real gate has. So lookahead is done in groups of four, with a second level of lookahead across the groups, and a third across those. A 64-bit adder is three levels deep, giving roughly \log delay rather than linear.
Read the trade plainly: ripple-carry is small and slow, lookahead is large and fast. Every processor's arithmetic unit uses lookahead or one of its descendants (carry-select, carry-skip, Kogge-Stone), and the choice is a straight area-versus-speed decision.
4. Subtraction, and why two's complement is free
Volume I, Chapter 1.3 explained two's complement. Here is why hardware loves it: subtraction needs no new circuit at all.
A - B = A + (-B) = A + \bar B + 1
So to subtract, invert every bit of B and add 1. And the "add 1" is free — feed it into the adder's C_{in}, which is otherwise unused at the bottom bit.
One control line does both operations. Put an XOR gate on each B input with the control line as its other input:
- Control = 0: XOR passes B unchanged, C_{in} = 0. The circuit adds.
- Control = 1: XOR inverts every B bit, C_{in} = 1. The circuit subtracts.
n XOR gates and one wire buys you a subtractor. This is the single strongest argument for two's complement, and it is why sign-magnitude and one's complement representations died.
Overflow detection
Adding two numbers of the same sign and getting the opposite sign means overflow. In hardware:
V = C_{n} \oplus C_{n-1}
The carry into the sign bit differs from the carry out of it. That single XOR is the entire overflow flag, and it is why the ALU flags register has a V bit sitting next to the carry bit.
5. The multiplexer
A multiplexer (mux) selects one of several inputs and routes it to a single output, according to select lines. With n select lines it chooses among 2^n inputs.
A 4-to-1 mux:
Y = \bar S_1\bar S_0D_0 + \bar S_1S_0D_1 + S_1\bar S_0D_2 + S_1S_0D_3
Read it as: exactly one of the four AND terms is enabled by the select decoding, and that one passes its data input through.
Where multiplexers actually appear
- Bus sharing. Several sources, one destination, and the select line decides who talks.
- Inside a processor. The ALU's operand comes from a register file, an immediate value or a memory read; a mux picks. Every "choose between" in a datapath is a mux.
- As a universal logic element. A 2^n-to-1 mux can implement any function of n variables: wire each data input to the truth table's output value for that combination. A 4-to-1 mux with the data inputs hard-wired to 0, 1, 1, 0 is an XOR gate. This is why lookup tables inside an FPGA (Chapter 3.6) are built from multiplexers.
- Time-division multiplexing. Cycle the select lines and several signals share one wire in turn — the technique that Chapter 7.4 develops for telephone trunks.
A demultiplexer is the reverse: one input routed to one of many outputs. It is the same circuit with the data and enable roles swapped, which is why a decoder chip usually has "decoder/demultiplexer" on its front page.
6. Decoders
A decoder takes an n-bit address and activates exactly one of its 2^n outputs. A 3-to-8 decoder has
Y_5 = A_2\bar A_1A_0 \quad\text{(since 5 = 101)}
and similarly for the other seven — each output is one distinct AND of the address bits and their complements.
Most real decoders are active-low, meaning the selected output goes to 0 and the rest stay at 1. That is a leftover from TTL, where pulling low was stronger than driving high, and it survives because it composes well with the open-drain and chip-select conventions.
Where it matters: memory address decoding
You have four 16 KB memory chips and want them to appear as one 64 KB space. The address is 16 bits. The bottom 14 bits go to every chip's address pins; the top 2 bits go to a 2-to-4 decoder whose four outputs are each chip's chip select.
\text{Chip 0: } 0000_h - 3\text{FFF}_h, \quad \text{Chip 1: } 4000_h-7\text{FFF}_h, \quad \ldots
Exactly one chip responds to any address, and no logic exists to arbitrate — the decoder makes conflict impossible by construction. Every memory map in every computer is built this way, and the same idea appears in software as a jump table.
A decoder with an enable input becomes a demultiplexer: the enable is the data, and the address chooses where it goes.
A seven-segment decoder is the same idea specialised: four BCD input bits, seven outputs driving the display segments, with the truth table simplified by Karnaugh map into seven expressions. Chapter 3.P works one through.
7. Encoders and priority encoders
An encoder is the reverse of a decoder: 2^n inputs, one of which is active, producing the n-bit number of that input.
The plain encoder has a fatal flaw: if two inputs are active at once, the output is nonsense — the OR of two different codes, which is a third, wrong code. And if no input is active, the output is 0, indistinguishable from input 0 being active.
A priority encoder fixes both. It outputs the number of the highest-numbered active input, and provides a separate "valid" output that is 0 when nothing is active.
For a 4-to-2 priority encoder:
Y_1 = D_3+D_2, \qquad Y_0 = D_3+D_1\bar D_2, \qquad V = D_3+D_2+D_1+D_0
Read Y_0's expression: bit 0 of the answer is set if input 3 is active, or if input 1 is active and input 2 is not. The \bar D_2 is the priority doing its work.
Where it lives: interrupt controllers. Several devices raise interrupt requests at once; the priority encoder decides which the processor is told about first, and the rest wait. It is also the hardware behind the "count leading zeros" instruction that every modern processor has, which is used for floating-point normalisation and for fast logarithms.
8. Comparators
A one-bit equality check is XNOR — 1 when the bits match. An n-bit equality is the AND of all n XNORs:
\text{EQ} = \prod_{i=0}^{n-1}\overline{(A_i\oplus B_i)}
Magnitude comparison needs more care. A is greater than B if its most significant differing bit is 1:
A \gt B = A_3\bar B_3 + \text{EQ}_3(A_2\bar B_2) + \text{EQ}_3\text{EQ}_2(A_1\bar B_1)+\text{EQ}_3\text{EQ}_2\text{EQ}_1(A_0\bar B_0)
where \text{EQ}_i means bits i match. Read it as: compare from the top down, and the first position where they differ decides.
There is a cheaper way when an adder is already present, which it always is in a processor: subtract and look at the flags. A-B produces zero if equal, a negative result if A is smaller, and the carry and overflow bits between them settle signed comparison. That is exactly what a CMP instruction does — a subtraction whose result is discarded and whose flags are kept.
9. Code converters
Two conversions worth knowing because they appear in real systems.
Binary to Gray code. Gray code is an ordering where consecutive values differ in exactly one bit — the same property the Karnaugh map needed in Chapter 3.1. The conversion is beautifully simple:
G_i = B_i \oplus B_{i+1}, \qquad G_{n-1}=B_{n-1}
One XOR per bit. Reverse conversion is a chain: B_{n-1}=G_{n-1}, then B_i = G_i\oplus B_{i+1}.
Why it matters. A rotary position encoder using plain binary would, moving from 3 (011) to 4 (100), change all three bits — and because they never change at exactly the same instant, the reader might momentarily see 111 or 000, giving a wildly wrong position. With Gray code only one bit ever changes, so the worst possible misread is off by one. Every absolute position encoder in every industrial machine uses it, and so does every asynchronous FIFO pointer crossing between two clock domains (Chapter 3.3).
BCD. Binary-coded decimal stores each decimal digit in its own four bits, so 47 is 0100 0111 rather than 00101111. It wastes space and complicates arithmetic — after adding two BCD digits you must add 6 whenever the result exceeds 9, to skip the six unused codes. In exchange, it converts to a display with no division, and it represents decimal fractions exactly, which is why financial and metering systems still use it and why processors kept BCD adjustment instructions for decades.
10. Propagation delay in a real design
Delays add along a path, and the longest path decides everything.
Worked example — an 8-bit ripple-carry adder feeding a comparator.
| Stage | Delay |
|---|---|
| 8 full adders, carry chain | 8\times2 = 16 ns |
| Final sum XOR | 2 ns |
| Comparator, 4 levels | 8 ns |
| Total | 26 ns |
Maximum clock frequency, ignoring flip-flop overheads for now:
f_{max} = \frac{1}{26\ \text{ns}} = 38.5\ \text{MHz}
To go faster, attack the longest term. Replacing the ripple adder with a lookahead one cuts 16 ns to about 6 ns, giving 62.5 MHz — a 60% gain from changing one block. That is what "optimise the critical path" means in practice, and it is the same reasoning as profiling software: measure, find the dominant term, fix that one.
The other route is pipelining: cut the path in half with a register in the middle, so each half runs at nearly double the frequency. The result takes two clock cycles instead of one, so latency is unchanged, but throughput doubles. Volume I, Chapter 1.5 describes what this does inside a processor; the hardware reason is exactly this arithmetic.
Every circuit so far forgets everything the instant its inputs change. Adding one wire that feeds an output back to an input creates memory, and with memory comes the clock, the state machine, and everything that computes rather than merely calculates.
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.
Karnaugh maps
Row and column order is Gray code: 00, 01, 11, 10 — chosen so that adjacent cells differ in exactly one variable.
A group of 2^k adjacent cells eliminates k variables. Group sizes must be powers of two; groups wrap around all edges; groups may overlap; make each as large as possible; cover every 1.
Number of cells: 2^n for n variables.
Arithmetic
Half adder: S = A\oplus B, C = AB.
Full adder:
S = A\oplus B\oplus C_{in}, \qquad C_{out}=AB+C_{in}(A\oplus B) = AB+BC_{in}+AC_{in}
Ripple-carry delay: t = n\,t_{carry}.
Carry lookahead
G_i = A_iB_i, \qquad P_i = A_i\oplus B_i, \qquad C_{i+1}=G_i+P_iC_i
Expanding:
C_4 = G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_0
Every carry becomes a two-level expression of the inputs, so the delay is constant within a group instead of growing with position.
Subtraction and overflow
A-B = A+\bar B+1
Invert B with XOR gates controlled by a mode line, and feed that same line into C_{in}. One control signal turns an adder into a subtractor.
V = C_n\oplus C_{n-1}
Overflow when the carry into the sign bit differs from the carry out of it.
Multiplexer and decoder
Y = \sum_{k=0}^{2^n-1}m_k D_k
where m_k is the minterm of the select lines. A 2^n-to-1 mux implements any function of n variables.
Decoder output k is the minterm m_k of the address; exactly one output is active for any address.
Priority encoder, 4-to-2:
Y_1 = D_3+D_2, \qquad Y_0 = D_3+D_1\bar D_2, \qquad V = D_3+D_2+D_1+D_0
Gray code
G_i = B_i\oplus B_{i+1}, \quad G_{n-1}=B_{n-1}
B_{n-1}=G_{n-1}, \quad B_i = G_i\oplus B_{i+1}
Why it exists: consecutive values differ in one bit only, so a reading taken mid-transition is wrong by at most one count.
What the next chapter fixes
Every circuit in this chapter computes its output from its inputs and nothing else, so it has no memory of what happened a moment ago. That is enough for arithmetic and routing and nothing else — no counting, no sequencing, no state. Chapter 3.3 adds memory using nothing but feedback, and the moment a gate's output can reach its own input, the circuit gains a past.