Carry-lookahead adder: Visual walkthrough — Hardware deep dive

Everything here is just Boolean algebra applied to the full adder, turned into pictures.

Step 1 — What is a carry, really?

WHAT. When we add two binary digits (each is $0$ or $1$ ) plus an incoming carry, sometimes the result is too big for one digit and spills over into the next column. That spill is the carry-out.

WHY. Before we can predict carries, we must be crystal-clear on what a carry is and where it comes from. Everything downstream is just re-asking "when does this spill happen?"

PICTURE. Look at the four columns below. Each column adds $a_{i} + b_{i} + c_{i}$ . The tiny arrow leaving the top of a column is the carry $c_{i + 1}$ handed to the column on its left.

The subscript $i$ is just a position label: column $0$ is the rightmost (smallest) column, column $1$ is next, and so on.

Step 2 — The exact rule for when a carry is born

WHAT. A carry-out $c_{i + 1} = 1$ happens exactly when at least two of the three inputs $a_{i}, b_{i}, c_{i}$ are $1$ (two ones make $2$ , which is $1 0_{2}$ — a spill).

WHY. We need the precise boolean condition so we can later split it into pieces we can pre-compute. This is the same $c_{i + 1}$ equation the Full Adder already gives us — we are only re-reading it.

PICTURE. The "majority" gate: shade every input combination that spills.

Notice the split: one reason ignores $c_{i}$ entirely; the other reason multiplies $c_{i}$ . That gap is the whole idea. Hold onto it.

Step 3 — Naming the two reasons: Generate and Propagate

WHAT. We give the two boxes from Step 2 short names, because they depend on only $a_{i}$ and $b_{i}$ — inputs we hold in our hands immediately, with no waiting.

WHY. The slowness of a Ripple-Carry Adder comes entirely from waiting for $c_{i}$ . If we can name the parts that don't need $c_{i}$ , we can compute them for every column at the same time.

PICTURE. Two little machines per column, both fed only by $a_{i}, b_{i}$ , lighting up before any carry exists.

Rewriting Step 2 with the new names gives the seed of everything:

Step 4 — Why the recursive form is still slow (the trap)

WHAT. The equation $c_{i + 1} = g_{i} + p_{i} c_{i}$ contains $c_{i}$ . To get $c_{2}$ you need $c_{1}$ ; to get $c_{1}$ you need $c_{0}$ . That is still a chain.

WHY. We must see the trap before we escape it. If we implemented $c_{i + 1} = g_{i} + p_{i} c_{i}$ directly as hardware, each carry waits 2 gate delays (one AND, one OR) for the carry below — exactly the ripple problem, just renamed. (More on this counting in Propagation Delay & Fan-in.)

PICTURE. The bucket brigade: $c_{1}$ waits for $c_{0}$ , $c_{2}$ waits for $c_{1}$ … the delay stacks column by column.

Step 5 — Unroll the chain: substitute $c_{i}$ away

WHAT. Wherever a $c_{i}$ appears, we replace it by its own formula, again and again, until only $g$ 's, $p$ 's, and the original input carry $c_{0}$ remain.

WHY. This is pure Boolean Algebra: substitution plus the distributive law. Once $c_{i}$ is gone, no carry waits for another — they are all functions of inputs available at time zero.

PICTURE. Watch $c_{2}$ get "unfolded." Each substitution replaces a waiting term with things we already know.

Start from the bottom and expand:

$c_{1} = g_{0} + p_{0} c_{0}$

c_{2} = g_{1} + p_{1} c_{1} = g_{1} + p_{1} substitute c_{1} (g_{0} + p_{0} c_{0}) = col 1 makes it g_{1} + col 0 made it, col 1 passed it p_{1} g_{0} + input carry passed through both p_{1} p_{0} c_{0}

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

Every term now reads as a little story: "some lower column generated a carry, AND every column above it (up to here) propagated it." The $c_{0}$ term is "the input carry rode all the way up."

Step 6 — Why this is now fast (constant depth)

WHAT. Each $c_{i + 1}$ above is one big OR of ANDs — a 2-level AND–OR expression of things known at time zero.

WHY. Depth, not width, sets speed. All $g_{i}, p_{i}$ appear in 1 gate delay. Every carry is then AND then OR = 2 more delays, no matter how many bits. Sums finish in 1 more. Total ≈ 4 levels, independent of $n$ , versus ripple's ≈ $2 n$ .

PICTURE. Left: ripple's staircase of delay grows with $n$ . Right: CLA's flat, constant tower.

Step 7 — Edge & degenerate cases (nothing is left unshown)

WHAT. We check the corners so no scenario surprises you.

WHY. A rule you can't trust at the edges isn't a rule. Contract: cover every case.

PICTURE. Three tiny worlds — all-propagate, all-generate, and $c_{0} = 1$ .

Case A — every column propagates, none generates ( $g_{i} = 0, p_{i} = 1$ for all $i$ ). Then $c_{i + 1} = c_{0} \prod p_{j} = c_{0}$ . The input carry rides untouched to the top. This is $A = 1111, B = 0001$ -style behaviour: one source, a chain of passes.
Case B — a column generates in the middle ( $g_{1} = 1$ , others $0$ ; all $p = 1$ ). Then $c_{2} = c_{3} = c_{4} = 1$ : the born carry floods every column above. Below it, carries stay $0$ .
Case C — degenerate $c_{0} = 1$ but all $g_{i} = 0$ , some $p_{i} = 0$ . As soon as one $p_{j} = 0$ , its product term dies: the input carry is blocked there and does not reach higher columns. Never drop the $c_{0} \prod p_{j}$ term unless you've confirmed $c_{0} = 0$ .

Step 8 — One level up: blocks of four (same picture, bigger tiles)

WHAT. Treat a whole 4-bit chunk exactly like one "super-column" with its own group-generate $G$ and group-propagate $P$ .

WHY. Wide single-level CLA needs impossibly big gates. Grouping keeps fan-in sane while reusing the identical math — self-similarity, like fractal tiles. Compare Carry-Save Adder for a different speed trick entirely.

PICTURE. Four small columns collapse into one big tile obeying $C_{out} = G + P C_{in}$ .

The one-picture summary

This last figure compresses the journey: two numbers → per-column $g_{i}, p_{i}$ (instant) → each carry as a 2-level AND–OR of those → all carries at once → 4-bit blocks stacking the same law. Full-adder sum bits close the loop as $s_{i} = p_{i} \oplus c_{i}$ (reusing Full Adder logic).

Recall Feynman: the whole walkthrough in plain words

Two numbers line up in columns. Each column looks only at its own two cards and decides two facts before the game starts: "I definitely spill a carry" (generate, both cards $1$ ) or "if a carry reaches me I'll pass it on" (propagate, my cards differ). A ripple adder still makes each column wait for the one on its right — a slow bucket brigade. The lookahead trick is to take the sentence "I spill if I generate, or if I propagate an arriving carry," and keep substituting the "arriving carry" with its sentence, over and over, until every carry is written purely in terms of the pre-computed generates and propagates and the single input carry. Now a teacher glances at every column's two facts at once and announces all the carries in a fixed few steps — no line, no waiting. Stack four columns into one big tile with a group-generate and group-propagate, and the exact same trick works one level up, which is how real 64-bit adders stay fast.

Recall Quick self-check

Why does $g_{i}$ not depend on $c_{i}$ ? ::: Because $g_{i} = a_{i} b_{i}$ uses only this column's own inputs — a carry is made regardless of any arriving carry. What single algebraic move turns the recursion into constant depth? ::: Substituting each $c_{i}$ by its own $g_{i} + p_{i} c_{i}$ until only $g$ 's, $p$ 's and $c_{0}$ remain (distributive law). In Case A (all propagate, none generate), what is $c_{4}$ ? ::: $c_{4} = c_{0}$ — the input carry rides straight through. Why isn't CLA zero-delay? ::: It is constant (~4 gate levels), not zero; and large fan-in forces hierarchical blocks.

Connections

Carry-lookahead adder — the parent result this page derives visually.
Full Adder — source of $c_{i + 1} = a_{i} b_{i} + (a_{i} \oplus b_{i}) c_{i}$ and $s_{i} = p_{i} \oplus c_{i}$ .
Ripple-Carry Adder — the slow baseline whose waiting we eliminate.
Boolean Algebra — substitution + distributive law does the unrolling.
Propagation Delay & Fan-in — why depth is constant but fan-in grows.
Carry-Save Adder — a different speed strategy (defer carries).
Prefix Adders (Kogge-Stone) — logarithmic-depth generalization of Step 8.