Exercises — Carry-lookahead adder

$g_i=a_i{b}_i=1\cdot 1=1$. $p_i=a_i\oplus b_i=1\oplus 1=0$ (equal bits → XOR is 0). Because $g_i=1$, this bit generates a carry no matter what comes in. Because $p_i=0$, it does not propagate — an incoming carry is absorbed. (This is the "kill/generate" corner: both inputs 1 always outputs a carry and never forwards the old one.)

$c_{i+1}=g_i+p_i{c}_i$ First term $g_i$: this bit makes a carry on its own. Second term $p_i{c}_i$: this bit forwards whatever carry arrived ($c_i$), but only when it is in propagate mode ($p_i=1$). The OR ($+$) says "carry out if either happens."

Bits (index 0 = rightmost): $A=a_3{a}_2{a}_1{a}_0=0110$, $B=0101$.

Carries by lookahead ($c_0=0$):

• $c_1=g_0+p_0{c}_0=0+1\cdot 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\cdot 0=1$
• $c_4=g_3+p_3{c}_3=0+0\cdot 1=0$

Sums $s_i=p_i\oplus c_i$:

• $s_0=1\oplus 0=1$, $s_1=1\oplus 0=1$, $s_2=0\oplus 0=0$, $s_3=0\oplus 1=1$.

Result: carry-out $c_4=0$, $S=1011_2$. Check: $6+5=11=1011_2$. ✓

From the parent note: $c_3=g_2+p_2{g}_1+p_2{p}_1{g}_0+p_2{p}_1{p}_0{c}_0$. Bits: $A=1011\Rightarrow a_0=1,a_1=1,a_2=0$; $B=0110\Rightarrow b_0=0,b_1=1,b_2=1$.

• $g_0=1\cdot 0=0$, $p_0=1\oplus 0=1$
• $g_1=1\cdot 1=1$, $p_1=1\oplus 1=0$
• $g_2=0\cdot 1=0$, $p_2=0\oplus 1=1$

$c_3=0+(1)(1)+(1)(0)(0)+(1)(0)(1)(1)=0+1+0+0=1$. Answer: $c_3=1$. (The $c_0=1$ term dies because $p_1=0$ blocks it — a propagate chain is only as strong as its weakest link.)

$g_3=1\cdot 1=1$, all other $g_i=0$; $p_3=1\oplus 1=0$. $c_4=g_3+p_3{c}_3=1+0\cdot c_3=1$. The carry is generated at bit 3 itself, so nothing below it is consulted — $g_3$ alone forces $c_4=1$. Sum $S=0000$, carry-out $1$, i.e. $10000_2=16=8+8$. ✓

$p_i=a_i\oplus b_i=a_i{\bar{b}}_i+{\bar{a}}_i{b}_i$ (XOR expanded, where $\bar{x}$ = NOT $x$). $g_i{p}_i=a_i{b}_i(a_i{\bar{b}}_i+{\bar{a}}_i{b}_i)=a_i{b}_i{a}_i{\bar{b}}_i+a_i{b}_i{\bar{a}}_i{b}_i$. Each product contains a variable ANDed with its complement: $b_i{\bar{b}}_i=0$ in the first, $a_i{\bar{a}}_i=0$ in the second. So $g_i{p}_i=0+0=0$. ∎ Meaning: the two signals partition the "carry active" cases cleanly — no double-counting, which is why the OR in $c_{i+1}=g_i+p_i{c}_i$ is safe.

Ripple: worst-case carry travels through all 16 stages $\Rightarrow 2\times 16=32$ gate delays. (Then 1 more for the last sum XOR, but the standard comparison quotes the carry path: $32$.) CLA: $1+2+1=4$ gate delays (constant, independent of width). Speed-up $=32/4=8\times$. Interpretation: CLA converted an $O(n)$ carry path into $O(1)$ depth — at the cost of much wider gates (fan-in), which is the price analysed in Propagation Delay & Fan-in.

The longest term is $c_0{\prod }_{j=0}^{n-1}{p}_j$, a product of $n$ propagate signals ANDed with $c_0$ → an AND gate with $n+1$ inputs. The final OR that forms $c_n$ has $n+1$ terms. For $n=8$: largest AND fan-in $=8+1=9$ inputs; the OR forming $c_8$ has $9$ terms. Why this matters: a 9-input gate is already awkward in real silicon, and it grows linearly with $n$. This exploding fan-in is exactly why designers stop at 4-bit blocks and go hierarchical.

Read bit positions: $p_0=1,p_1=1,p_2=0,p_3=1$; $g_0=0,g_1=0,g_2=1,g_3=0$. $P=p_3{p}_2{p}_1{p}_0=1\cdot 0\cdot 1\cdot 1=0.$ $G=g_3+p_3{g}_2+p_3{p}_2{g}_1+p_3{p}_2{p}_1{g}_0=0+(1)(1)+(1)(0)(0)+(1)(0)(1)(0)=1.$ $P=0$, $G=1$. The block generates a carry (bit 2 did) but does not propagate one across, because $p_2=0$ breaks the chain.

$C_4=G_0+P_0{C}_0=1+0\cdot 0=1$. Block 0 generated a carry. $C_8=G_1+P_1{C}_4=0+1\cdot 1=1$. Block 1 didn't generate, but its $P_1=1$ propagated block 0's carry across the whole 4-bit group in one step. Answer: $C_4=1$, $C_8=1$. This is the CLA idea recursively applied — blocks behave exactly like single bits.

Map $g_i\leftrightarrow G$, $p_i\leftrightarrow P$, $c_i\leftrightarrow C_{\text{in}}$, $c_{i+1}\leftrightarrow C_{\text{out}}$. Both read "output carry = generate OR (propagate AND input carry)" — same OR-of-(term, AND-term) structure. Why powerful: the same lookahead unrolling you did for bits can now be applied to blocks, and to groups-of-blocks, etc. Depth grows like $\log$ rather than linearly, which is the seed of tree-structured designs like Prefix Adders (Kogge-Stone).

$A=1101\Rightarrow a_0=1,a_1=0,a_2=1,a_3=1$; $B=1011\Rightarrow b_0=1,b_1=1,b_2=0,b_3=1$.

Carries ($c_0=1$):

• $c_1=g_0+p_0{c}_0=1+0\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=1+0\cdot 1=1$

Sums $s_i=p_i\oplus c_i$:

• $s_0=0\oplus 1=1$, $s_1=1\oplus 1=0$, $s_2=1\oplus 1=0$, $s_3=0\oplus 1=1$.

Result: carry-out $1$, $S=1001_2\Rightarrow 11001_2$. Check: $13+11+1=25=11001_2$. ✓ Notice the single carry generated at bit 0 rides the propagate chain (bits 1,2) all the way up — a beautiful full example of the "generate once, propagate through" motion.

Every $g_i=0\cdot 0=0$ and every $p_i=0\oplus 0=0$.

• $c_1=0+0\cdot 1=0$, and likewise $c_2=c_3=c_4=0$. The input carry $c_0=1$ is killed immediately at bit 0 because $p_0=0$ (both inputs 0 → kill mode). Sums: all $s_i=p_i\oplus c_i=0\oplus 0=0$… except $s_0=p_0\oplus c_0=0\oplus 1=1$. Result: $S=0001$, carry-out $0$, i.e. $0+0+1=1$. ✓ The lone carry-in surfaces as the LSB sum bit and never becomes a carry-out, because nothing propagates.

We need every bit in propagate mode ($p_i=1\Rightarrow a_i\ne b_i$) and no bit in generate ($g_i=0\Rightarrow$ not both 1). Choose $A=1111$, $B=0000$, $c_0=1$. Then $p_i=1\oplus 0=1$ for all $i$, and $g_i=1\cdot 0=0$ for all $i$.

• $c_1=0+1\cdot 1=1$, $c_2=0+1\cdot 1=1$, $c_3=1$, $c_4=1$. The input carry $c_0=1$ propagates cleanly through all four bits. Sums: $s_i=p_i\oplus c_i=1\oplus 1=0$ for all $i$. Result: $S=0000$, carry-out $1$ → $10000_2=16=15+0+1$. ✓ This is the worst case for ripple-carry (delay proportional to the whole chain) but constant-depth for CLA — the entire reason the CLA exists.