A ripple-carry adder is slow because each bit's carry has to wait for the carry from the bit below it — like a line of people passing a bucket, one at a time. The carry-lookahead adder asks a cleverer question: "Can I predict every carry directly from the inputs, without waiting?" The answer is yes — because whether a bit position produces or forwards a carry depends only on its own a i , b i a_i, b_i a i , b i
Definition The problem with ripple-carryIn an n n n c i + 1 c_{i+1} c i + 1 c i c_i c i c i − 1 c_{i-1} c i − 1 O ( n ) O(n) O ( n ) 2 gate delays (an AND then an OR), so a 64-bit ripple adder incurs on the order of 2 × 64 = 128 2\times64 = 128 2 × 64 = 128 in parallel , in constant depth.
WHAT we exploit: For a single full adder at bit i i i a i , b i a_i, b_i a i , b i c i c_i c i
s i = a i ⊕ b i ⊕ c i , c i + 1 = a i b i + ( a i ⊕ b i ) c i s_i = a_i \oplus b_i \oplus c_i, \qquad c_{i+1} = a_i b_i + (a_i \oplus b_i)\,c_i s i = a i ⊕ b i ⊕ c i , c i + 1 = a i b i + ( a i ⊕ b i ) c i
Look at c i + 1 c_{i+1} c i + 1
The bit generates a carry on its own: a i b i = 1 a_i b_i = 1 a i b i = 1
The bit propagates an incoming carry: ( a i ⊕ b i ) c i = 1 (a_i \oplus b_i)\,c_i = 1 ( a i ⊕ b i ) c i = 1
Definition Generate and PropagateDefine two per-bit signals that depend only on a i , b i a_i, b_i a i , b i (available immediately):
g i = a i b i ( ==generate== ) , p i = a i ⊕ b i ( ==propagate== ) g_i = a_i b_i \quad(\text{==generate==}), \qquad p_i = a_i \oplus b_i \quad(\text{==propagate==}) g i = a i b i ( ==generate== ) , p i = a i ⊕ b i ( ==propagate== )
Substituting into the carry equation:
Now unroll the recursion to kill the dependence on the previous carry. Start with c 0 c_0 c 0
c 1 = g 0 + p 0 c 0 c_1 = g_0 + p_0 c_0 c 1 = g 0 + p 0 c 0
c 2 = g 1 + p 1 c 1 = g 1 + p 1 ( g 0 + p 0 c 0 ) = g 1 + p 1 g 0 + p 1 p 0 c 0 c_2 = g_1 + p_1 c_1 = g_1 + p_1(g_0 + p_0 c_0) = g_1 + p_1 g_0 + p_1 p_0 c_0 c 2 = g 1 + p 1 c 1 = g 1 + p 1 ( g 0 + p 0 c 0 ) = g 1 + p 1 g 0 + p 1 p 0 c 0
c 3 = g 2 + p 2 c 2 = g 2 + p 2 g 1 + p 2 p 1 g 0 + p 2 p 1 p 0 c 0 c_3 = g_2 + p_2 c_2 = g_2 + p_2 g_1 + p_2 p_1 g_0 + p_2 p_1 p_0 c_0 c 3 = g 2 + p 2 c 2 = g 2 + p 2 g 1 + p 2 p 1 g 0 + p 2 p 1 p 0 c 0
The payoff: every c i + 1 c_{i+1} c i + 1 2-level AND-OR expression of the g g g p p p c 0 c_0 c 0 g i , p i g_i, p_i g i , p i constant number of gate delays — independent of n n n
Compute all p i , g i p_i, g_i p i , g i 1 gate delay (parallel).
Compute all c i c_i c i 2 gate delays (AND then OR).
Compute all s i = p i ⊕ c i s_i = p_i \oplus c_i s i = p i ⊕ c i 1 more delay .
Total ≈ \approx ≈ constant (~4) gate delays vs. ripple's ≈ 2 n \approx 2n ≈ 2 n fan-in and gate count grow, so real chips build 4-bit CLA blocks and connect them hierarchically.
Worked example Example 1 — AddA = 1011 A=1011 A = 1011 B = 0110 B=0110 B = 0110 c 0 = 0 c_0=0 c 0 = 0 Step 1 — per-bit p , g p,g p , g Why? These are the raw predictors.
i i i a i a_i a i b i b_i b i g i = a i b i g_i=a_ib_i g i = a i b i p i = a i ⊕ b i p_i=a_i\oplus b_i p i = a i ⊕ b i
0
1
0
0
1
1
1
1
1
0
2
0
1
0
1
3
1
0
0
1
Step 2 — carries by lookahead. Why? No waiting; plug into the formula.
c 1 = g 0 + p 0 c 0 = 0 + 1 ⋅ 0 = 0 c_1 = g_0 + p_0 c_0 = 0 + 1\cdot0 = 0 c 1 = g 0 + p 0 c 0 = 0 + 1 ⋅ 0 = 0 c 2 = g 1 + p 1 g 0 + p 1 p 0 c 0 = 1 + 0 + 0 = 1 c_2 = g_1 + p_1 g_0 + p_1 p_0 c_0 = 1 + 0 + 0 = 1 c 2 = g 1 + p 1 g 0 + p 1 p 0 c 0 = 1 + 0 + 0 = 1 c 3 = g 2 + p 2 g 1 + p 2 p 1 g 0 + p 2 p 1 p 0 c 0 = 0 + 1 ⋅ 1 + 0 + 0 = 1 c_3 = g_2 + p_2 g_1 + p_2 p_1 g_0 + p_2 p_1 p_0 c_0 = 0 + 1\cdot1 + 0 + 0 = 1 c 3 = g 2 + p 2 g 1 + p 2 p 1 g 0 + p 2 p 1 p 0 c 0 = 0 + 1 ⋅ 1 + 0 + 0 = 1 c 4 = g 3 + p 3 c 3 = 0 + 1 ⋅ 1 = 1 c_4 = g_3 + p_3 c_3 = 0 + 1\cdot1 = 1 c 4 = g 3 + p 3 c 3 = 0 + 1 ⋅ 1 = 1
Step 3 — sums s i = p i ⊕ c i s_i = p_i \oplus c_i s i = p i ⊕ c i Why? Sum bit reuses p i p_i p i
s 0 = 1 ⊕ 0 = 1 , s 1 = 0 ⊕ 0 = 0 , s 2 = 1 ⊕ 1 = 0 , s 3 = 1 ⊕ 1 = 0 s_0 = 1\oplus0=1,\; s_1=0\oplus0=0,\; s_2=1\oplus1=0,\; s_3=1\oplus1=0 s 0 = 1 ⊕ 0 = 1 , s 1 = 0 ⊕ 0 = 0 , s 2 = 1 ⊕ 1 = 0 , s 3 = 1 ⊕ 1 = 0 = 1 =1 = 1
Result: S = 0001 S = 0001 S = 0001 1 ⇒ 1 0001 2 1 \Rightarrow 1\,0001_2 1 ⇒ 1 000 1 2 1011 2 + 0110 2 = 11 + 6 = 17 = 10001 2 1011_2+0110_2 = 11+6 = 17 = 10001_2 101 1 2 + 011 0 2 = 11 + 6 = 17 = 1000 1 2
Worked example Example 2 — Show propagation,A = 1111 A=1111 A = 1111 B = 0001 B=0001 B = 0001 c 0 = 0 c_0=0 c 0 = 0 g = ( a i b i ) : g 0 = 1 , g 1 = g 2 = g 3 = 0 g = (a_ib_i): g_0=1, g_1=g_2=g_3=0 g = ( a i b i ) : g 0 = 1 , g 1 = g 2 = g 3 = 0 p = ( a i ⊕ b i ) : p 0 = 0 , p 1 = p 2 = p 3 = 1 p=(a_i\oplus b_i): p_0=0, p_1=p_2=p_3=1 p = ( a i ⊕ b i ) : p 0 = 0 , p 1 = p 2 = p 3 = 1
c 1 = g 0 = 1 c_1=g_0=1 c 1 = g 0 = 1 c 2 = g 1 + p 1 c 1 = 0 + 1 ⋅ 1 = 1 c_2=g_1+p_1c_1 = 0+1\cdot1=1 c 2 = g 1 + p 1 c 1 = 0 + 1 ⋅ 1 = 1 Why? bit 0's generate is being propagated upward.c 3 = 1 , c 4 = 1 c_3=1,\; c_4=1 c 3 = 1 , c 4 = 1 Sums: s 0 = 0 ⊕ 0 = 0 s_0=0\oplus0=0 s 0 = 0 ⊕ 0 = 0 s 1 = 1 ⊕ 1 = 0 s_1=1\oplus1=0 s 1 = 1 ⊕ 1 = 0 s 2 = 0 s_2=0 s 2 = 0 s 3 = 0 s_3=0 s 3 = 0 1 1 1 S = 10000 2 = 16 = 15 + 1 S=10000_2 = 16 = 15+1 S = 1000 0 2 = 16 = 15 + 1
p i = a i + b i p_i = a_i + b_i p i = a i + b i Why it feels right: "propagate a carry" sounds like "either input is 1," which is OR. And for the carry equation it actually works — because when a i b i = 1 a_i b_i=1 a i b i = 1 g i = 1 g_i=1 g i = 1 c i + 1 = 1 c_{i+1}=1 c i + 1 = 1 The fix: For the carry , OR is acceptable. But you MUST use XOR for computing s i = p i ⊕ c i s_i = p_i \oplus c_i s i = p i ⊕ c i p i p_i p i p i = a i ⊕ b i p_i = a_i \oplus b_i p i = a i ⊕ b i
Common mistake Thinking CLA has zero delayWhy it feels right: "parallel = instant." The fix: it's constant delay (~4 gate levels), not zero. And wide CLA needs huge fan-in gates, so practical designs are hierarchical (block generate/propagate), which adds a few more levels.
Common mistake Forgettingc 0 c_0 c 0 Why it feels right: examples often use c 0 = 0 c_0=0 c 0 = 0 The fix: the general formula always carries the c 0 ∏ p j c_0\prod p_j c 0 ∏ p j c 0 = 0 c_0=0 c 0 = 0
Why is ripple-carry slow? Each carry waits serially for the previous one →
O ( n ) O(n) O ( n ) delay (~
2 n 2n 2 n gate delays, 2 per carry stage).
Define generate g i g_i g i g i = a i b i g_i = a_i b_i g i = a i b i : bit makes a carry regardless of incoming carry.
Define propagate p i p_i p i p i = a i ⊕ b i p_i = a_i \oplus b_i p i = a i ⊕ b i : bit passes an incoming carry through.
Recursive carry equation? c i + 1 = g i + p i c i c_{i+1} = g_i + p_i c_i c i + 1 = g i + p i c i .
Expanded c 2 c_2 c 2 c 2 = g 1 + p 1 g 0 + p 1 p 0 c 0 c_2 = g_1 + p_1 g_0 + p_1 p_0 c_0 c 2 = g 1 + p 1 g 0 + p 1 p 0 c 0 .
Sum bit formula? s i = p i ⊕ c i s_i = p_i \oplus c_i s i = p i ⊕ c i .
Gate-delay of CLA vs ripple? CLA ~constant (~4 levels); ripple ~
2 n 2n 2 n (2 delays per carry stage).
Group propagate for 4-bit block? P = p 3 p 2 p 1 p 0 P = p_3 p_2 p_1 p_0 P = p 3 p 2 p 1 p 0 .
Group generate for 4-bit block? G = g 3 + p 3 g 2 + p 3 p 2 g 1 + p 3 p 2 p 1 g 0 G = g_3 + p_3 g_2 + p_3 p_2 g_1 + p_3 p_2 p_1 g_0 G = g 3 + p 3 g 2 + p 3 p 2 g 1 + p 3 p 2 p 1 g 0 .
Main cost of wide CLA? Large gate fan-in and gate count → solved by hierarchy.
Recall Feynman: explain to a 12-year-oldImagine passing a note down a row of kids. Ripple-carry = each kid must receive the note before passing it, so the last kid waits a long time. CLA is smarter: before the game starts, each kid decides two things using only their own cards — "I'll definitely raise my hand (generate)" or "I'll copy whoever's below me (propagate)." Now a teacher looks at everyone's cards at once and instantly announces who raises their hand. No waiting in line!
"GAP" — G enerate = A nd (a i b i a_ib_i a i b i P ropagate = xor. And "c c c rhymes as "Generate it, or Propagate it."
Full Adder — the CLA reuses the same s i = a i ⊕ b i ⊕ c i s_i = a_i\oplus b_i\oplus c_i s i = a i ⊕ b i ⊕ c i Ripple-Carry Adder — the slow baseline CLA improves on.Boolean Algebra — unrolling the recursion is pure substitution + distributive law.Carry-Save Adder — different speed trick (defer carries).Propagation Delay & Fan-in — why hierarchy is needed in practice.Prefix Adders (Kogge-Stone) — logarithmic-depth generalization of CLA.
Predict carries from inputs
Generate g_i equals a_i b_i
Propagate p_i equals a_i XOR b_i
Recursive carry c_i+1 equals g_i plus p_i c_i
4-bit CLA blocks hierarchical
Intuition Hinglish mein samjhoDekho, normal ripple-carry adder mein har bit ka carry pichle bit ke carry ka wait karta hai — ek line mein bucket pass karne jaisa. Har carry stage do gate delays leta hai (pehle AND, phir OR), toh 64-bit ripple adder mein worst case around 2 × 64 = 128 2\times64=128 2 × 64 = 128 O ( n ) O(n) O ( n ) generate g i = a i b i g_i = a_i b_i g i = a i b i propagate p i = a i ⊕ b i p_i = a_i \oplus b_i p i = a i ⊕ b i a i , b i a_i, b_i a i , b i
Core formula hai c i + 1 = g i + p i c i c_{i+1} = g_i + p_i c_i c i + 1 = g i + p i c i g g g p p p c 0 c_0 c 0 ek saath, parallel mein compute ho jaate hain, chahe n n n 2 n 2n 2 n
Iska matlab yeh nahi ki delay zero hai — CLA ka cost hai badi fan-in gates aur zyada hardware. Isliye real chips mein 4-bit CLA blocks banate hain, aur upar ek aur layer mein group generate G G G P P P p i = a i ⊕ b i p_i = a_i \oplus b_i p i = a i ⊕ b i s i = p i ⊕ c i s_i = p_i \oplus c_i s i = p i ⊕ c i
