Carry-lookahead adder: Worked examples — Hardware deep dive

Before we count cases, one reminder of the machinery from the parent — written out so nothing is assumed:

The scenario matrix

Every CLA problem falls into one of these cells. The examples below are labelled with the cell(s) they cover.

Cell	What makes it special	Where it can bite
C1 Plain add, $c_{0} = 0$	some generates, some propagates	baseline sanity
C2 Long propagate chain	one generate rides across many $p_{i} = 1$	carry "travels"
C3 All generate	every $g_{i} = 1$	max carries, overflow-out
C4 All zero / degenerate	$A = B = 0$	no carry ever forms
C5 Carry-in $c_{0} = 1$	the $c_{0} \prod p_{j}$ term matters	forgetting $c_{0}$
C6 Carry born, then dies	generate below a $p_{i} = 0$ gap	chain broken
C7 Real-world word problem	decimal → binary → CLA	translation
C8 Exam twist: OR-vs-XOR trap	wrong $p_{i}$ definition	sum breaks

We hit all eight below.

Example 1 — Cell C1 (plain add, $c_{0} = 0$ )

Worked example Add

$A = 0101$ , $B = 0011$ , $c_{0} = 0$ Forecast: $5 + 3 = 8 = 100 0_{2}$ . Guess: do you expect a carry-out? (No — the sum $8$ fits in 4 bits.)

Step 1 — per-bit $p, g$ . Why this step? $g_{i}, p_{i}$ depend only on the inputs, so we build them first — they are the raw predictors nothing waits on.

$i$	$a_{i}$	$b_{i}$	$g_{i} = a_{i} b_{i}$	$p_{i} = a_{i} \oplus b_{i}$
0	1	1	1	0
1	0	1	0	1
2	1	0	0	1
3	0	0	0	0

Step 2 — carries by lookahead. Why this step? Each carry is a flat AND–OR of the $g$ 's and $p$ 's; no carry waits for another.

$c_{1} = g_{0} + p_{0} c_{0} = 1 + 0 = 1$
$c_{2} = g_{1} + p_{1} c_{1} = 0 + 1 \cdot 1 = 1$
$c_{3} = g_{2} + p_{2} c_{2} = 0 + 1 \cdot 1 = 1$
$c_{4} = g_{3} + p_{3} c_{3} = 0 + 0 \cdot 1 = 0$

Step 3 — sums $s_{i} = p_{i} \oplus c_{i}$ . Why this step? The sum bit reuses $p_{i}$ (that's why CLA computes $p_{i}$ once and shares it).

$s_{0} = 0 \oplus 0 = 0$
$s_{1} = 1 \oplus 1 = 0$
$s_{2} = 1 \oplus 1 = 0$
$s_{3} = 0 \oplus 1 = 1$

Result: $S = 1000$ , carry-out $c_{4} = 0$ .

Verify: $010 1_{2} + 001 1_{2} = 5 + 3 = 8 = 100 0_{2}$ . ✓ Carry-out $0$ as forecast.

Notice how the generate at bit 0 was propagated through bits 1 and 2 (both $p = 1$ ) and then stopped at bit 3 (where $p_{3} = 0$ ). That's cell C1's flavour — a carry that lives and dies inside the word.

Example 2 — Cell C2 (long propagate chain)

Worked example Add

$A = 0111$ , $B = 0001$ , $c_{0} = 0$ Forecast: $7 + 1 = 8$ . A single generate at bit 0 must ride up three propagate bits. Watch it travel.

Step 1 — per-bit $p, g$ . Why? Establish that only bit 0 generates and bits 1–3 propagate.

$i$	$a_{i}$	$b_{i}$	$g_{i}$	$p_{i}$
0	1	1	1	0
1	1	0	0	1
2	1	0	0	1
3	0	0	0	0

Step 2 — carries. Why? This is the cell where we see a carry "leap" without waiting.

$c_{1} = g_{0} = 1$ (born here)
$c_{2} = g_{1} + p_{1} c_{1} = 0 + 1 \cdot 1 = 1$ (propagated)
$c_{3} = g_{2} + p_{2} c_{2} = 0 + 1 \cdot 1 = 1$ (propagated again)
$c_{4} = g_{3} + p_{3} c_{3} = 0 + 0 \cdot 1 = 0$ (dies — $p_{3} = 0$ )

Look at the figure: the red carry token is created at bit 0 and copied straight up.

Step 3 — sums.

$s_{0} = 0 \oplus 0 = 0$ , $s_{1} = 1 \oplus 1 = 0$ , $s_{2} = 1 \oplus 1 = 0$ , $s_{3} = 0 \oplus 1 = 1$

Result: $S = 1000$ , carry-out $0$ .

Verify: $011 1_{2} + 000 1_{2} = 7 + 1 = 8 = 100 0_{2}$ . ✓ In ripple-carry this same carry would visit each bit one at a time; in CLA the flat formula produced $c_{2}, c_{3}$ simultaneously — that is the whole point.

Example 3 — Cell C3 (all generate) + Cell C5 seed

Worked example Add

$A = 1111$ , $B = 1111$ , $c_{0} = 0$ Forecast: $15 + 15 = 30$ . That needs 5 bits, so expect carry-out = 1 and $S = 1110$ .

Step 1 — per-bit $p, g$ . Why? When both inputs are 1, $g_{i} = 1$ (generate) and $p_{i} = 1 \oplus 1 = 0$ (no propagate). Every column makes its own carry.

$i$	$a_{i}$	$b_{i}$	$g_{i}$
0	1	1	1
1	1	1	1
2	1	1	1
3	1	1	1

Step 2 — carries. Why? Since every $p_{i} = 0$ , the propagate terms vanish and each carry is just its own generate.

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

Step 3 — sums $s_{i} = p_{i} \oplus c_{i} = 0 \oplus c_{i} = c_{i}$ :

$s_{0} = c_{0} = 0$ , $s_{1} = c_{1} = 1$ , $s_{2} = c_{2} = 1$ , $s_{3} = c_{3} = 1$

Result: $S = 1110$ , carry-out $c_{4} = 1$ → full answer $1111 0_{2}$ .

Verify: $15 + 15 = 30$ . $1111 0_{2} = 16 + 8 + 4 + 2 = 30$ . ✓ This is the CLA's maximum-carry case — no propagation at all, pure generation.

Example 4 — Cell C4 (all zero / degenerate)

Example 5 — Cell C5 (carry-in $c_{0} = 1$ )

Worked example Add

$A = 0011$ , $B = 0100$ , with $c_{0} = 1$ Forecast: $3 + 4 + 1 = 8$ . This is where the often-forgotten $c_{0} \prod p_{j}$ term earns its keep — watch $c_{0}$ ride up.

Step 1 — $p, g$ . Why? Same as always; $c_{0}$ does not change the predictors.

$i$	$a_{i}$	$b_{i}$	$p_{i}$
0	1	0	1
1	1	0	1
2	0	1	1
3	0	0	0

Every lower bit propagates ( $p_{0} = p_{1} = p_{2} = 1$ ); nobody generates. The only carry source is $c_{0}$ itself.

Step 2 — carries. Why? Here we MUST keep the $c_{0}$ term — this cell is the classic "forgot $c_{0}$ " trap.

$c_{1} = g_{0} + p_{0} c_{0} = 0 + 1 \cdot 1 = 1$
$c_{2} = g_{1} + p_{1} c_{1} = 0 + 1 \cdot 1 = 1$
$c_{3} = g_{2} + p_{2} c_{2} = 0 + 1 \cdot 1 = 1$
$c_{4} = g_{3} + p_{3} c_{3} = 0 + 0 \cdot 1 = 0$

Equivalently by the fully-expanded formula: $c_{3} = g_{2} + p_{2} g_{1} + p_{2} p_{1} g_{0} + p_{2} p_{1} p_{0} c_{0} = 0 + 0 + 0 + 1 \cdot 1 \cdot 1 \cdot 1 = 1$ . The last term $p_{2} p_{1} p_{0} c_{0}$ is the whole story.

Step 3 — sums:

$s_{0} = p_{0} \oplus c_{0} = 1 \oplus 1 = 0$
$s_{1} = p_{1} \oplus c_{1} = 1 \oplus 1 = 0$
$s_{2} = p_{2} \oplus c_{2} = 1 \oplus 1 = 0$
$s_{3} = p_{3} \oplus c_{3} = 0 \oplus 1 = 1$

Result: $S = 1000$ , carry-out $0$ .

Verify: $3 + 4 + 1 = 8 = 100 0_{2}$ . ✓ If you had dropped $c_{0}$ , you'd get $c_{1} = 0$ and the wrong answer $0111 = 7$ . The $c_{0}$ term is not optional.

Example 6 — Cell C6 (carry born, then dies at a gap)

Worked example Add

$A = 1001$ , $B = 0011$ , $c_{0} = 0$ Forecast: $9 + 3 = 12 = 110 0_{2}$ . A generate at bit 0 will die at bit 1 (a non-propagate gap), then a fresh generate appears higher up. Two separate carry "events."

Step 1 — $p, g$ .

$i$	$a_{i}$	$b_{i}$	$g_{i}$	$p_{i}$
0	1	1	1	0
1	0	1	0	1
2	0	0	0	0
3	1	0	0	1

Why note the gaps? $p_{2} = 0$ means position 2 blocks any carry from below — the chain can't cross it.

Step 2 — carries. Why? We want to see the carry from bit 0 get killed at the $p_{2} = 0$ wall.

$c_{1} = g_{0} = 1$ (born at bit 0)
$c_{2} = g_{1} + p_{1} c_{1} = 0 + 1 \cdot 1 = 1$ (propagated through bit 1)
$c_{3} = g_{2} + p_{2} c_{2} = 0 + 0 \cdot 1 = 0$ (dies — $p_{2} = 0$ blocks it)
$c_{4} = g_{3} + p_{3} c_{3} = 0 + 1 \cdot 0 = 0$ (nothing to propagate)

Step 3 — sums:

$s_{0} = 0 \oplus 0 = 0$ , $s_{1} = 1 \oplus 1 = 0$ , $s_{2} = 0 \oplus 1 = 1$ , $s_{3} = 1 \oplus 0 = 1$

Result: $S = 1100$ , carry-out $0$ .

Verify: $9 + 3 = 12 = 110 0_{2}$ . ✓ The lesson: a $p_{i} = 0$ position is a carry wall. Compare with C2, where every $p_{i} = 1$ let the carry fly all the way.

Example 7 — Cell C7 (real-world word problem)

Worked example A cash register adds two coin counts stored as 4-bit binary registers. Slot X holds

13 coins, slot Y holds 6 coins. The overflow line feeds a warning LED. Using CLA logic, what does each output wire read? Forecast: $13 + 6 = 19$ , which is bigger than the max 4-bit value $15$ — so the overflow LED (carry-out) lights up, and the 4-bit result wraps to $19 - 16 = 3 = 0011$ .

Step 1 — translate to binary. Why? The CLA operates on bits, so decimal must become $a_{i}, b_{i}$ . $13 = 110 1_{2}$ , $6 = 011 0_{2}$ , and $c_{0} = 0$ (no incoming carry).

Step 2 — $p, g$ .

$i$	$a_{i}$	$b_{i}$	$g_{i}$	$p_{i}$
0	1	0	0	1
1	0	1	0	1
2	1	1	1	0
3	1	0	0	1

Step 3 — carries. Why? The overflow LED is exactly $c_{4}$ ; we must chase the carry to the top.

$c_{1} = g_{0} + p_{0} c_{0} = 0 + 0 = 0$
$c_{2} = g_{1} + p_{1} c_{1} = 0 + 1 \cdot 0 = 0$
$c_{3} = g_{2} + p_{2} c_{2} = 1 + 0 = 1$ (generate at bit 2)
$c_{4} = g_{3} + p_{3} c_{3} = 0 + 1 \cdot 1 = 1$ (propagated → LED on)

Step 4 — sums:

$s_{0} = 1 \oplus 0 = 1$ , $s_{1} = 1 \oplus 0 = 1$ , $s_{2} = 0 \oplus 1 = 1$ … wait, recompute: $s_{2} = p_{2} \oplus c_{2} = 0 \oplus 0 = 0$ ; $s_{3} = p_{3} \oplus c_{3} = 1 \oplus 1 = 0$ .
So $s_{0} = 1, s_{1} = 1, s_{2} = 0, s_{3} = 0$ .

Result: register reads $S = 0011 = 3$ , overflow LED $= 1$ .

Verify: $13 + 6 = 19$ . Modulo $16$ : $19 - 16 = 3 = 001 1_{2}$ , and overflow $= 1$ . ✓ Units check: coin counts (dimensionless integers), result correctly flags that the 4-bit slot can't hold 19.

Example 8 — Cell C8 (exam twist: the OR-vs-XOR trap)

Worked example A student defines propagate as

$p_{i} = a_{i} + b_{i}$ (OR) instead of XOR, then computes the sum with $s_{i} = p_{i} \oplus c_{i}$ . Take $A = 0011$ , $B = 0011$ , $c_{0} = 0$ . Show the carry is still right but the sum bit breaks. Forecast: $3 + 3 = 6 = 011 0_{2}$ . The parent's mistake box warns that OR-propagate corrupts the sum. Let's expose exactly where.

Step 1 — build BOTH tables. Why? We compare correct XOR-propagate against the buggy OR-propagate side by side.

$i$	$a_{i}$	$b_{i}$	$g_{i}$	$p_{i}^{OR}$
0	1	1	1	1
1	1	1	1	1
2	0	0	0	0
3	0	0	0	0

The two definitions differ only where $a_{i} = b_{i} = 1$ (bits 0 and 1) — exactly the columns where $g_{i} = 1$ .

Step 2 — carries are identical. Why? In any differing column $g_{i} = 1$ , so $c_{i + 1} = g_{i} + p_{i} c_{i} = 1$ regardless of $p_{i}$ . The generate dominates.

Correct: $c_{1} = g_{0} = 1$ , $c_{2} = g_{1} + p_{1} c_{1} = 1$ , $c_{3} = g_{2} + p_{2} c_{2} = 0$ , $c_{4} = 0$ .
OR version: $c_{1} = 1$ , $c_{2} = g_{1} + p_{1}^{OR} c_{1} = 1 + 1 \cdot 1 = 1$ , $c_{3} = 0 + 0 = 0$ , $c_{4} = 0$ . Same carries. ✓

Step 3 — sums diverge. Why? $s_{i} = p_{i} \oplus c_{i}$ uses $p_{i}$ directly, so the wrong $p_{i}$ poisons the sum at bit 1.

Correct sum: $s_{0} = p_{0}^{XOR} \oplus c_{0} = 0 \oplus 0 = 0$ ; $s_{1} = 0 \oplus c_{1} = 0 \oplus 1 = 1$ ; $s_{2} = 0 \oplus c_{2} = 0 \oplus 1 = 1$ ; $s_{3} = 0 \oplus 0 = 0$ → $S = 0110 = 6$ . ✓
Buggy sum: $s_{0} = p_{0}^{OR} \oplus c_{0} = 1 \oplus 0 = 1$ (wrong!); $s_{1} = 1 \oplus 1 = 0$ ; $s_{2} = 0 \oplus 1 = 1$ ; $s_{3} = 0$ → $S = 0101 = 5$ . ✗

Result: OR-propagate yields the correct carry-out but the wrong number $5$ instead of $6$ .

Verify: $3 + 3 = 6 = 011 0_{2}$ (correct XOR path). The OR path gives $010 1_{2} = 5 \neq = 6$ . ✓ Moral, straight from the parent: always use $p_{i} = a_{i} \oplus b_{i}$ so the shared signal serves the sum too.

Recall Which cell does each example cover? (quick self-test)

Long-propagate-chain example number? ::: Example 2 (Cell C2). Which example forces you to keep the $c_{0} \prod p_{j}$ term? ::: Example 5 (Cell C5). Which example shows a carry dying at a $p_{i} = 0$ wall? ::: Example 6 (Cell C6). Which example proves OR-propagate breaks only the sum, not the carry? ::: Example 8 (Cell C8). What is special about the all-1s input (Example 3)? ::: Every $g_{i} = 1$ , every $p_{i} = 0$ — maximum carries, no propagation.

Connections

Carry-lookahead adder — parent; this page stress-tests its formulas.
Full Adder — each column here is one full adder's $g, p, s$ logic.
Ripple-Carry Adder — the "carry rides slowly" baseline our Example 2 beats.
Boolean Algebra — Example 8's OR-vs-XOR argument is pure Boolean identity.
Propagation Delay & Fan-in — why all-generate (Example 3) still costs constant depth.
Prefix Adders (Kogge-Stone) — generalizes the "born/ride/die" carry chains logarithmically.