Adders, Subtractors, Ripple Carry vs Carry Lookahead Adders
“Gate propagation delays, Half/Full adder synthesis, CLA generate and propagate algebra, and asymptotic speedup.”
1.The Arithmetic Carry Bottleneck
§ 2.1.In digital arithmetic, addition is the primitive operation upon which multiplication, subtraction, and address calculations are built. The critical speed limit of an adder is determined by the carry propagation path.
Ripple Carry Adder (RCA): Chaining n Full Adders connects C_{out} of bit i to C_{in} of bit i+1. In the worst case (e.g., adding 111...1 and 000...1), the carry must ripple through all n stages sequentially. For n=64, this introduces 64 stages of gate delay.
Carry Lookahead Adder (CLA): Eliminates ripple delay by expressing every carry C_{i+1} directly as a function of the primary inputs A, B and initial carry C_0 using two auxiliary terms:
- Generate (G_i = A_i B_i): A carry is generated internally at bit i if both inputs are 1.
- Propagate (P_i = A_i \oplus B_i): A carry entering bit i is passed directly to bit i+1 if one of the inputs is 1.
Since all G_i and P_i are generated in parallel in 1 gate delay, all carries C_1, C_2, C_3, C_4 are computed simultaneously in a 2-level AND-OR logic network, making carry computation independent of word length n.
2. Worked Analysis: Delay Comparison RCA vs CLA
Distinguish between the time required to generate the final carry output vs the final sum bit.
Problem Statement (Modeled on GATE Pattern):
A 4-bit Ripple Carry Adder is constructed from full adders where each full adder has a sum delay of 12 ns and a carry delay of 8 ns.
A 4-bit CLA uses gates with delays: XOR = 10 ns, AND = 4 ns, OR = 4 ns.
Compute the worst-case delay to obtain all 4 sum bits and the final carry out for: (a) The RCA, and (b) The CLA.
Step 1: Calculate RCA worst-case delay:
- Carry out of stage 1: 8 ns.
- Carry out of stage 2: 8 + 8 = 16 ns.
- Carry out of stage 3: 16 + 8 = 24 ns.
- Final carry out (C4): 24 + 8 = 32 ns.
- Final sum bit (S3): requires C3 (24 ns) + sum delay of FA3 (12 ns) = 36 ns.
- Worst-case delay for RCA = max(32 ns, 36 ns) = 36 ns.
Step 2: Calculate CLA worst-case delay:
- Generate Pi, Gi: P_i = A_i XOR B_i (10 ns); G_i = A_i AND B_i (4 ns).
Both available at t = 10 ns.
- Carry lookahead network: Each carry C_i = G_{i-1} + P_{i-1} G_{i-2} + ... is a 2-level AND-OR circuit.
AND gate delay = 4 ns, OR gate delay = 4 ns.
All carries C1, C2, C3, C4 ready at: t = 10 ns (Pi) + 4 ns (AND) + 4 ns (OR) = 18 ns.
- Final sum bits: S_i = P_i XOR C_i.
Carries ready at 18 ns. XOR gate delay = 10 ns.
All sum bits ready at: t = 18 ns + 10 ns = 28 ns.
- Worst-case delay for CLA = 28 ns.
Result: RCA delay = 36 ns; CLA delay = 28 ns.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
The most thorough digital logic series — textbook quality at no cost.
GATE-focused digital logic with exam-style numericals.