Fast adders and carry look-ahead
Carry look-ahead (fast) adders speed up multi-bit binary addition by computing carry bits in parallel using generate/propagate signals and group logic, reducing worst-case delay from O(n) to O(log n) for large n.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Fast adders are used wherever arithmetic speed matters: ALU design in CPUs, DSPs, and hardware multipliers. Engineers choose carry look-ahead designs to lower the addition latency that limits overall CPU instruction throughput (see topics "CPU structure and function" and "Superscalar architecture").
Key ideas
Start from first principles. A binary adder adds two n-bit binary numbers A and B with an input carry C0, producing sum bits Si and a final carry-out Cn.
Full adder: a combinational circuit that adds single bits Ai, Bi and an input carry Ci to produce sum Si and carry-out Ci+1. It implements Si = Ai ⊕ Bi ⊕ Ci and Ci+1 = Ai·Bi + (Ai ⊕ Bi)·Ci. Equivalently, since pi = Ai ⊕ Bi, the sum can be written Si = pi ⊕ Ci.
Generate (bit-level): gi ≡ Ai · Bi. A bit generates a carry independently of the input carry when both inputs are 1.
Propagate (bit-level): pi ≡ Ai ⊕ Bi. A bit propagates the input carry when exactly one input bit is 1; then the output carry equals the input carry. Note: some textbooks define propagate as pi ≡ Ai + Bi (logical OR); with that convention the recurrence Ci+1 = gi + pi·Ci still holds and group P uses ANDs of the OR terms. Be aware of both conventions for exams.
Using gi and pi we can write the exact carry recurrence used in look-ahead logic: Ci+1 = gi + pi · Ci. This is an algebraic identity derived from the full-adder carry expression; it assumes logical OR for +, logical AND for ·, and ⊕ for exclusive OR.
- Group propagate and group generate (multi-bit blocks): for a block of bits 0..k define
- Pk:0 ≡ p_k · p_{k-1} · ... · p_0 (the block propagates if every bit propagates),
- Gk:0 ≡ g_k + p_k·g_{k-1} + p_k·p_{k-1}·g_{k-2} + ... + p_k·p_{k-1}·...·p_1·g_0.
Group generate gives the condition the block will produce a carry-out regardless of C0. The standard 4-bit carry look-ahead formulas (for bits 0..3) follow by repeated substitution: C1 = g0 + p0·C0 C2 = g1 + p1·g0 + p1·p0·C0 C3 = g2 + p2·g1 + p2·p1·g0 + p2·p1·p0·C0 C4 = g3 + p3·g2 + p3·p2·g1 + p3·p2·p1·g0 + p3·p2·p1·p0·C0 = G3:0 + P3:0·C0.
Derivation universities commonly ask for: start with Ci+1 = gi + pi·Ci and expand C2 in terms of C0 by substitution repeatedly until Cn expressed as function of g's, p's and C0. Show algebraic grouping to identify group generate and group propagate.
How to draw diagrams (what to draw and label):
- For a ripple-carry adder: draw n full-adders horizontally. For each full-adder box label inputs Ai, Bi, Ci and outputs Si, Ci+1. Show the carry chain connecting Ci+1 of stage i to Ci+1 input of stage i+1.
- For a 4-bit CLA block: draw 4 small boxes computing gi and pi from Ai & Bi. Draw AND gates implementing the multi-term products p3·p2·g1, etc., and OR gates summing those to make C1..C4. Label the final group G3:0 and P3:0 and show C0 entering the block and C4 leaving. Also show XOR gates computing the sums Si = pi ⊕ Ci for each bit.
Assumptions: boolean algebra with + = OR, · = AND, ⊕ = XOR. All signals are binary. Logic gates are ideal; propagation delays handled in delay analysis separately.
Formulas
gi = Ai · Bi — gi is bit-generate; Ai, Bi are binary inputs (unitless logical values). Applies at any bit position i.
pi = Ai ⊕ Bi — pi is bit-propagate; ⊕ is exclusive-OR. Unitless. Applies at any bit position i.
Ci+1 = gi + pi · Ci — carry recurrence; Ci is the carry into bit i (0 or 1). Unitless. Exact for full adder logic.
Pk:0 = p_k · p_{k-1} · ... · p_0 — group propagate for bits 0..k. Unitless.
Gk:0 = g_k + p_k·g_{k-1} + p_k·p_{k-1}·g_{k-2} + ... + p_k·p_{k-1}·...·p_1·g_0 — group generate. Unitless.
Ck+1 = Gk:0 + Pk:0 · C0 — carry-out of block 0..k in terms of group signals and input carry. For two's complement addition, the overflow flag can be computed as V = Cn ⊕ Cn-1 (XOR of carry into and out of the MSB).
For timing (qualitative):
T_ripple ∝ n · T_fa — ripple-carry delay grows linearly with number of bits n where T_fa is worst-case delay per full adder.
T_CLA ∝ T_gen + T_prefix_tree — CLA carry delay depends on time to compute gi, pi plus the carry-lookahead network depth which tends to grow like O(log n) for hierarchical/tree CLA designs.
Worked examples
Example 1 — 4-bit binary add using bit generate/propagate (numerical). Add A = 1011 (A3=1,A2=0,A1=1,A0=1) and B = 0110 (B3=0,B2=1,B1=1,B0=0) with C0 = 0. Step 1: compute gi and pi for i=0..3.
- i=0: A0=1,B0=0 ⇒ g0 = 1·0 = 0; p0 = 1 ⊕ 0 = 1.
- i=1: A1=1,B1=1 ⇒ g1 = 1·1 = 1; p1 = 1 ⊕ 1 = 0.
- i=2: A2=0,B2=1 ⇒ g2 = 0·1 = 0; p2 = 0 ⊕ 1 = 1.
- i=3: A3=1,B3=0 ⇒ g3 = 1·0 = 0; p3 = 1 ⊕ 0 = 1.
Step 2: compute carries using Ci+1 = gi + pi·Ci.
- C1 = g0 + p0·C0 = 0 + 1·0 = 0.
- C2 = g1 + p1·C1 = 1 + 0·0 = 1.
- C3 = g2 + p2·C2 = 0 + 1·1 = 1.
- C4 = g3 + p3·C3 = 0 + 1·1 = 1.
Step 3: compute sums Si = Ai ⊕ Bi ⊕ Ci.
- S0 = 1 ⊕ 0 ⊕ 0 = 1.
- S1 = 1 ⊕ 1 ⊕ 0 = 0.
- S2 = 0 ⊕ 1 ⊕ 1 = 0 (since 0⊕1=1; 1⊕1=0).
- S3 = 1 ⊕ 0 ⊕ 1 = 0. Final result bits S3..S0 = 0001 with carry-out C4 = 1 ⇒ final sum = 1 0001 = 10001₂ = 17₁₀.
Example 2 — derive C4 symbolically for 4-bit block (proof-style): Start: C1 = g0 + p0·C0. C2 = g1 + p1·C1 = g1 + p1·(g0 + p0·C0) = g1 + p1·g0 + p1·p0·C0. C3 = g2 + p2·C2 = g2 + p2·g1 + p2·p1·g0 + p2·p1·p0·C0. C4 = g3 + p3·C3 = g3 + p3·g2 + p3·p2·g1 + p3·p2·p1·g0 + p3·p2·p1·p0·C0 = G3:0 + P3:0·C0. QED.
Common mistakes
- Wrong order of terms in group-generate expression and missing products of pi terms.
- For timing problems, failing to count gate-level depth correctly (forgetting the cost to compute pi = Ai⊕Bi and gi = Ai·Bi).
- Confusing sum formula Si = Ai ⊕ Bi ⊕ Ci with Si = pi ⊕ Ci (note pi = Ai ⊕ Bi so both are equivalent but only if pi already computed).
For your exam
Question types you will see: definitions (define generate/propagate), short notes (compare ripple vs CLA), derivations (expand Ci+1 to Cn and derive group generate), diagram drawing (draw 4-bit CLA block and label gi/pi and carry logic), numerical examples (compute sums using CLA signals), timing comparisons (compute worst-case delay given gate delays).
What full-marks answers include:
- Clear definitions with bold term names and the exact formula gi = Ai·Bi, pi = Ai⊕Bi.
- Correct step-by-step expansion for carries showing algebraic steps and grouping into G and P.
- A labelled diagram if asked: show gi/pi blocks, AND/OR trees, input C0 and output Cn.
- For timing questions: state assumptions for gate delays, show path(s) for sum and carry, compute numeric delay for ripple and CLA and compare.
Quick check
- Define bit-generate gi and bit-propagate pi in formulas.
- For a 4-bit block, write the formula for C4 in terms of g's, p's and C0.
- Why is CLA faster than ripple for large n? Answers: 1. gi = Ai·Bi, pi = Ai ⊕ Bi. 2. C4 = g3 + p3·g2 + p3·p2·g1 + p3·p2·p1·g0 + p3·p2·p1·p0·C0. 3. CLA computes carries in parallel using generate/propagate and group logic so carry computation grows like O(log n) with hierarchical trees rather than O(n) sequential stages.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?