Multiplexers, Decoders, and the ALU

The last lesson described combinational logic in HCL and claimed the case expression is a multiplexer. This lesson cashes that in. We build the standard combinational function units (multiplexers, decoders, adders, and finally the arithmetic logic unit) that together form the computational core of a processor's datapath. Every block here is pure combinational logic: a Boolean function of its current inputs.

The multiplexer: a data selector

A multiplexer (mux) routes one of several data inputs to a single output, chosen by a set of select lines. A $2 : 1$ mux has two data inputs $d_{0}, d_{1}$ , one select bit $s$ , and output $y = s ? d_{1} : d_{0}$ . As a Boolean function, $y = \overline{s} d_{0} + s d_{1}$ : when $s = 0$ the first AND passes $d_{0}$ and the second is killed; when $s = 1$ the reverse. A $4 : 1$ mux needs two select bits to name one of four inputs.

A 2:1 mux (left) selects d0 or d1 with one select bit s; a 4:1 mux (right) selects one of four inputs with two select bits s1 s0. The select value, read as a binary number, names the chosen input.

Inside, a $4 : 1$ mux is one AND per data input — each gated by the select combination that names it — feeding one OR. Writing the two select bits as $s_{1} s_{0}$ , the Boolean form is

y = \overline{s_{1}} \overline{s_{0}} d_{0} + \overline{s_{1}} s_{0} d_{1} + s_{1} \overline{s_{0}} d_{2} + s_{1} s_{0} d_{3} .

Each product is a data input ANDed with a decoded select: the four select combinations are the one-hot outputs of a 2-to-4 decoder. So a mux is a decoder driving a bank of AND gates whose outputs OR together — one figure below made of parts from this same lesson.

A 4:1 mux built from gates. The select bits s1 s0 are decoded into four one-hot lines; each ANDs with one data input; the four AND outputs OR into y. Only the line matching the select value passes its data.

Trace a selection. With $s_{1} s_{0} = 10$ , the decoded line $s_{1} \overline{s_{0}}$ is $1$ and the other three are $0$ ; the third AND passes $d_{2}$ while the others force $0$ , so the OR sees only $d_{2}$ and $y = d_{2}$ . Change the select to $01$ and the second AND opens instead, routing $d_{1}$ . The select value, read as a binary number, is the index of the data input that reaches the output — a data selector, exactly as promised.

This is the hardware behind HCL's case: a case with $n$ selects compiles to a mux tree, with the top-of-list priority resolving overlapping selects. Mutually exclusive selects, like a one-hot control field, give a clean $n : 1$ mux where the select code names the chosen input directly. Muxes are everywhere in a datapath: choosing whether the ALU's second operand comes from a register or an immediate, choosing which value to write back, choosing the next instruction address.

The decoder: select one of $2^{n}$ lines

A decoder takes an $n$ -bit input and asserts exactly one of $2^{n}$ output lines — the one whose index equals the input value. It is one-hot: output line $i$ is $1$ iff the input equals $i$ , all others $0$ . Each output is one minterm of the input bits, so a $2$ -to- $4$ decoder is four AND gates fed by the inputs and their complements.

A 2-to-4 decoder. The 2-bit input a1 a0 drives exactly one of four output lines high — the one whose index equals the input. Each output is a minterm: y2 is high only when a1 a0 = 10.

Decoders pick out one item from a numbered set: the natural job is address decoding, turning a register number or memory address into a single select this word line, which is how the register file and memory array in the next two lessons choose which storage cell to touch.

The full adder

Arithmetic starts at one bit column. Adding two bits $a$ and $b$ plus an incoming carry $c_{in}$ produces a sum bit and an outgoing carry. This is a full adder, and its two outputs are functions we have already met:

sum = a \oplus b \oplus c_{in}, c_{o u t} = (a \cdot b) + (a \cdot c_{in}) + (b \cdot c_{in}) .

The sum is $1$ when an odd number of the three inputs are $1$ : that is the three-input XOR (parity). The carry is $1$ when at least two of the three inputs are $1$ : the majority function from lesson 1. Check the corner: with $a = b = c_{in} = 1$ , sum $= 1 \oplus 1 \oplus 1 = 1$ and $c_{o u t} = 1$ , i.e. $1 + 1 + 1 = 1 1_{2} = 3$ , sum $1$ carry $1$ . Correct.

A one-bit full adder as two function blocks. A 3-input XOR computes the parity (sum = a XOR b XOR cin); a majority block computes the carry out (1 when at least two of a, b, cin are 1). Each input fans to both blocks.

Ripple-carry: chaining full adders

To add two $n$ -bit numbers, place $n$ full adders side by side, one per bit position, and feed each adder's carry-out into the next adder's carry-in. The carry ripples from the low bit to the high bit. The carry into bit $0$ is the overall carry-in $c_{0}$ (set it to $1$ for subtraction, below), and the carry out of the top bit is the overall carry-out.

A 4-bit ripple-carry adder. Each full adder FAi adds ai, bi, and the carry ci from the stage below, producing sum si and carry c(i+1). The carry chain runs right-to-left from c0 to c4.

Ripple-carry is correct but slow, and the critical-path accounting of the last lesson says exactly how slow. Each stage's carry-out is the majority function, a two-level AND-OR circuit, so the carry chain costs about 2 gate delays per bit: $c_{1}$ settles at $2Δ$ , $c_{2}$ at $4Δ$ , and $c_{64}$ at $128Δ$ . The top sum bit needs $c_{63}$ plus one more XOR, so a 64-bit ripple adder is roughly $130$ gate delays deep. At 25 ps per level that is $3.2$ ns for one addition: a 300 MHz clock in a machine whose other blocks settle ten times faster. The delay is linear in $n$ , and the adder sits on the critical path of nearly every instruction. Real adders spend gates to buy depth.

Carry-lookahead: computing carries in parallel

The ripple is slow because each carry waits for the previous one. But bit $i$ 's relationship to the carry is determined before the carry arrives. From $a_{i}$ and $b_{i}$ alone:

if $a_{i} = b_{i} = 1$ , the column generates a carry no matter what comes in: $g_{i} = a_{i} \cdot b_{i}$ ;
if exactly one of $a_{i}, b_{i}$ is $1$ , the column propagates an incoming carry: $p_{i} = a_{i} \oplus b_{i}$ .

Every $g_{i}$ and $p_{i}$ is ready after one gate level, all in parallel. The carry recurrence $c_{i + 1} = g_{i} + p_{i} c_{i}$ then unrolls by substitution:

c_{1} c_{2} c_{3} c_{4} = g_{0} + p_{0} c_{0} = g_{1} + p_{1} g_{0} + p_{1} p_{0} c_{0} = g_{2} + p_{2} g_{1} + p_{2} p_{1} g_{0} + p_{2} p_{1} p_{0} c_{0} = g_{3} + p_{3} g_{2} + p_{3} p_{2} g_{1} + p_{3} p_{2} p_{1} g_{0} + p_{3} p_{2} p_{1} p_{0} c_{0} .

Read $c_{2}$ aloud: bit $1$ generated a carry, or it propagated one that bit $0$ generated, or both columns propagated the original $c_{0}$ . Each right-hand side is a two-level AND-OR circuit of signals available after one level, so all four carries of a 4-bit group settle in about 3 gate delays, independent of one another, no ripple.

The unrolling cannot continue forever: $c_{16}$ written this way is an OR of 17 terms, one an AND of 16 inputs, and the fan-in cost of such wide gates eats the savings. So the trick is applied hierarchically. A 4-bit group condenses itself into a group generate and group propagate,

G = g_{3} + p_{3} g_{2} + p_{3} p_{2} g_{1} + p_{3} p_{2} p_{1} g_{0}, P = p_{3} p_{2} p_{1} p_{0},

which record whether the group produces a carry and whether it passes one along — the same two facts as for a single column, now at group scale. A second-level lookahead unit treats the groups as super-columns and computes every group's carry-in from the $(G, P)$ pairs and $c_{0}$ in two more levels.

A carry-lookahead tree over 16 bits. Each 4-bit block computes its internal carries plus a group (G, P) in parallel; the second-level unit computes c4, c8, c12 from the four (G, P) pairs and c0. Two levels cover 16 bits; three cover 64. Depth grows with log n, not n.

Count the depth for 64 bits: one level for all $g_{i}, p_{i}$ , two for group $(G, P)$ s, two per tree level for the carries coming back down, one XOR for the sums: on the order of a dozen gate delays regardless of width, against $130$ for the ripple. At 25 ps per level that is roughly $0.3$ ns instead of $3.2$ . The price is the lookahead logic itself, a few extra gates per bit; every serious adder pays it. The pattern — replace a linear chain with a $log$ -depth tree — is the same one the equality net of the previous lesson used, and it recurs throughout hardware design.

The ALU: a function unit with a control input

An arithmetic logic unit packages several operations into one block and uses a control input to select which result appears at the output. The standard teaching ALU (CS:APP's) takes two word operands $A$ and $B$ and a small function code, and produces a result plus condition flags.

An ALU. Two word operands A and B enter; a control code selects which operation drives the result; condition flags (zero, sign, carry, overflow) report properties of that result.

Internally the ALU computes all the operations in parallel and a final mux picks the selected one — exactly the case-to-mux pattern. Two details make it practical. First, subtraction reuses the adder: $A - B = A + \overline{B} + 1$ , so feeding the adder the complement of $B$ and setting the carry-in $c_{0} = 1$ turns add into subtract with no extra adder. Second, the flags are computed from the result: ZF (zero) is $1$ when every result bit is $0$ , SF (sign) is the top result bit, CF (carry) is the adder's carry-out, and OF (overflow) signals signed overflow. These flags are what conditional branches later test. Not every ISA keeps all four: Y86-64's condition codes hold only ZF, SF, and OF — it has no unsigned branches — while CF is needed in ISAs like x86-64, whose unsigned ja/jb family reads it.

One bit of the ALU

Slice the ALU at a single bit position and every idea in this lesson appears in one small circuit. The slice computes AND, OR, and the full adder's sum for its bit, all three at once, and an operation mux steers one to the result. An invert control sits in front of the adder's $b$ input, choosing between $b_{i}$ and $\overline{b_{i}}$ ; drive invert = 1 and $c_{0} = 1$ together and the chained slices compute $a + \overline{b} + 1 = a - b$ .

A one-bit ALU slice. AND, OR, and the adder's sum are all computed in parallel; the op mux selects one as the result. The invert mux feeds the adder b or NOT b, so invert = 1 with carry-in 1 turns add into subtract. Chaining cout to the next slice's cin ripples the design to n bits.

Work one subtraction through the 4-bit version. Compute $6 - 3$ : $a = 0110$ , $b = 0011$ , so $\overline{b} = 1100$ , and with $c_{0} = 1$ the adders produce $0110 + 1100 + 1 = 10011$ . The carry out of the top bit falls off the end, leaving $0011 = 3$ . Discarding that carry is the modular wraparound of two's-complement arithmetic, and the ALU's OF logic checks the top two carries to flag the cases where wraparound changes the sign incorrectly.

alu.hclc

word aluResult = [
    fn == ALU_ADD : A + B;
    fn == ALU_SUB : A - B;
    fn == ALU_AND : A & B;
    fn == ALU_XOR : A ^ B;
];
bool ZF = (aluResult == 0);   /* zero flag: result is all zeros */

The HCL reads as a four-way case on the function code. The gates it stands for: an adder/subtractor, an AND array, an XOR array, and a $4 : 1$ mux steering one result out under fn, with a zero-detect net on the side.

Faster adders and hardware multiply

CS:APP builds the ripple adder, sketches lookahead, and moves on. The public adder literature is deeper, and the same generate/propagate algebra underlies all of it.

Prefix adders. The recurrence $c_{i + 1} = g_{i} + p_{i} c_{i}$ is an instance of a parallel prefix computation: define a combine operator on $(g, p)$ pairs, $(g^{'}, p^{'}) ∙ (g, p) = (g^{'} + p^{'} g, p^{'} p)$ , and every carry is a prefix sum under $∙$ . Because $∙$ is associative, the prefixes can be computed by a balanced tree in $log_{2} n$ depth — which is what carry-lookahead does, stated abstractly. Different tree shapes trade depth against wiring: Kogge–Stone (1973) is shallowest and widest (lots of wires, minimal depth), Brent–Kung (1982) is deeper but far sparser, and Ladner–Fischer and Han–Carlson sit between. A modern 64-bit adder in a high-frequency core is usually a hybrid of these, chosen to fit the wire budget of its slot. All of them compute exactly the carries this lesson unrolled by hand; they differ only in how they share the sub-products.

Multiplication. The ALU here does add, subtract, AND, XOR — not multiply, because multiply does not fit the two-level template. An $n \times n$ multiply is $n$ shifted partial products summed, and the public techniques attack both halves. Booth's algorithm (1951) and its radix-4 modified form roughly halve the number of partial products by recoding the multiplier. A Wallace tree (1964) or Dadda tree (1965) then sums those partial products in $log$ depth using carry-save adders — full adders wired to defer the carry instead of rippling it — collapsing the sum to two numbers that one final fast adder combines. That is why a hardware multiply, naively $O (n)$ additions, costs only a handful of gate levels more than a single add.

Where the ALU went. The single-function-code ALU is the SISD picture. Modern cores replicate it: a superscalar processor has several integer ALUs plus separate multiply, divide, and floating-point units, and SIMD vector units (x86's AVX-512, ARM's SVE) apply one operation across many lanes of a wide register in parallel — the same one-bit slice tiled 512 ways with the carry chains broken at lane boundaries. The condition flags this lesson emits are still the interface a branch reads, unchanged since the 8086.

So far every block forgets its inputs the instant they change. The next lesson adds memory by deliberately introducing the feedback combinational logic forbade.