A full adder adds one column. To add two n-bit numbers you need n columns, and the columns are connected by carries. How you handle those carries decides how fast the adder is. In this chapter we build the simple ripple-carry adder, measure exactly why it is slow, and then derive the carry look-ahead adder (CLA), which computes all carries in parallel. Delay calculations on these two adders are a GATE favourite, so we will be careful with the delay model and verify every number by simulation.
We use the results of Half & Full Adders: S = A ⊕ B ⊕ Cin and Cout = AB + Cin(A ⊕ B).
Ripple-Carry Adder (RCA)
An n-bit ripple-carry adder is a chain of n full adders in which the carry output of stage i is connected to the carry input of stage i + 1.
A3 B3 A2 B2 A1 B1 A0 B0
| | | | | | | |
+------+ C3 +------+ C2 +------+ C1 +------+
C4| FA3 |<----| FA2 |<----| FA1 |<----| FA0 |<-- C0
+------+ +------+ +------+ +------+
| | | |
S3 S2 S1 S0
C0 is 0 for plain addition (or 1 when the adder is used for subtraction, as in Subtractors). The design is simple, regular and small: n full adders and nothing else. A 4-bit example, 1011 + 0110 (11 + 6):
Stage | Ai | Bi | Ci (in) | Si | Ci+1 (out) |
|---|---|---|---|---|---|
0 | 1 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 | 1 |
2 | 0 | 1 | 1 | 0 | 1 |
3 | 1 | 0 | 1 | 0 | 1 |
Result: C4S3S2S1S0 = 1 0001 = 17. Correct.
Why It Is Slow
Stage 3 cannot produce its final outputs until C3 is correct, C3 waits for C2, and so on. The carry has to ripple through every stage, like a row of falling dominoes. The worst case is when a carry is created at bit 0 and every higher bit passes it on, for example 1111 + 0001.
The Standard Delay Model
Exam problems usually count delay in gate delays: every AND, OR and XOR gate takes 1 unit, and all A and B bits (and C0) are ready at time 0. The model of one full adder used in most textbooks and GATE-style problems is:
P = A ⊕ B 1 gate delay after A, B
Cout = AB + A·Cin + B·Cin two-level AND-OR: 2 gate delays after its latest input
S = P ⊕ Cin 1 gate delay after Cin (P is ready long before)
In words: each stage adds 2 gate delays to the carry, and a sum bit is ready 1 gate delay after its carry-in. Always state the model you use; if a question gives other gate delays, redo the count with those numbers. Following the worst-case carry with this model:
C_i ready at 2i (C1 at 2, C2 at 4, ..., C_n at 2n)
S_i ready at 2i + 1 (needs C_i, then one XOR; for i ≥ 1. S_0 = P_0 ⊕ C_0 is ready at 2)
n-bit RCA: C_n at 2n gate delays, S_(n-1) at 2n − 1 gate delays
4-bit: C4 at 8, S3 at 7
16-bit: C16 at 32, S15 at 31
32-bit: C32 at 64, S31 at 63
64-bit: C64 at 128, S63 at 127
The delay grows linearly with n: O(n). Doubling the word length doubles the adder delay.
Delay with Full-Adder Delays Given in ns
Some questions give full-adder level delays instead: tc from Cin to Cout, and ts from Cin to S. With A and B ready early enough:
C_n ready at n · t_c
S_(n-1) ready at (n − 1) · t_c + t_s
Adder delay = max of the two
Example: 8-bit RCA, t_c = 2 ns, t_s = 3 ns
C8 at 8 × 2 = 16 ns, S7 at 7 × 2 + 3 = 17 ns → the adder needs 17 ns
Carry Look-Ahead Adder (CLA)
The ripple happens because each carry is computed from the previous carry. The CLA idea is simple: express every carry directly in terms of the A and B inputs and C0, so no carry waits for another.
Generate and Propagate
For bit position i: Generate Gi = AiBi (this bit produces a carry by itself) and Propagate Pi = Ai ⊕ Bi (this bit passes an incoming carry on). Then Ci+1 = Gi + PiCi and Si = Pi ⊕ Ci.
This is just the full-adder carry Cout = AB + Cin(A ⊕ B) with names. A quick table of what each column does:
Ai Bi | Gi | Pi | Effect on the carry |
|---|---|---|---|
0 0 | 0 | 0 | Kill: Ci+1 = 0 whatever Ci is |
0 1 or 1 0 | 0 | 1 | Propagate: Ci+1 = Ci |
1 1 | 1 | 0 | Generate: Ci+1 = 1 whatever Ci is |
Expanding the Carries
Substitute each carry into the next:
C1 = G0 + P0·C0
C2 = G1 + P1·C1 = 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
Read C4 aloud: "there is a carry into bit 4 if bit 3 generates one, or bit 2 generates one and bit 3 propagates it, or bit 1 generates one and bits 2 and 3 propagate it, or bit 0 generates one and bits 1 to 3 propagate it, or C0 comes in and all four bits propagate it." Each carry is now a two-level AND-OR expression of G's, P's and C0, all of which are available almost immediately.
Structure of a 4-bit CLA
A3 B3 A2 B2 A1 B1 A0 B0
| | | | | | | |
[P,G ] [P,G ] [P,G ] [P,G ] level 1: Pi = Ai ⊕ Bi, Gi = AiBi
| | | |
+-------------------------------+
| carry look-ahead logic | <-- C0 levels 2-3: AND-OR for C1..C4
+-------------------------------+
|C3 |C2 |C1 |C0 |C4
[XOR] [XOR] [XOR] [XOR] | level 4: Si = Pi ⊕ Ci
| | | | |
S3 S2 S1 S0 C4
Delay of a 4-bit CLA
All Pi, Gi ready at 1 (one XOR / AND level, all in parallel)
All carries C1 ... C4 ready at 3 (AND level + OR level)
All sums Si = Pi ⊕ Ci ready at 4
Compare with the 4-bit ripple-carry adder: C4 at 3 instead of 8, and every sum at 4 instead of up to 7. More importantly, in the idealised CLA the delay does not depend on n: C32 would also be ready at 3 gate delays.
The Catch: Fan-in and Gate Count
Look at the gates the expansion needs. Ci has i + 1 product terms, the biggest with i + 1 literals. So:
Carry | AND gates (excluding Gi−1) | Largest AND fan-in | OR fan-in |
|---|---|---|---|
C1 | 1 | 2 | 2 |
C2 | 2 | 3 | 3 |
C3 | 3 | 4 | 4 |
C4 | 4 | 5 | 5 |
Cn (general) | n | n + 1 | n + 1 |
So the look-ahead logic of an n-bit CLA needs 1 + 2 + ... + n = n(n + 1)/2 AND gates and n OR gates (on top of the n AND gates for Gi and n XOR gates for Pi). For n = 4 that is 10 AND and 4 OR gates. For n = 32, it would be 528 AND gates and a 33-input OR gate. Gates with that many inputs do not exist in practice, and a big gate is slow anyway (in CMOS, delay rises quickly with fan-in). That is why the "constant delay" of the CLA only holds for small blocks, and real wide adders are built hierarchically.
Building Wider Adders from 4-bit CLA Blocks
Option 1: Ripple the Carry Between Blocks
Connect four 4-bit CLA blocks so that each block's C4 output is the next block's carry input. Inside a block, the carries are look-ahead; between blocks, they ripple.
16-bit adder = 4 × (4-bit CLA), block carries rippled
All Pi, Gi: 1
C4 (block 0 out): 3 each block adds 2 gate delays to the carry
C8 (block 1 out): 5
C12 (block 2 out): 7
C16 (block 3 out): 9
S15 = P15 ⊕ C15: C15 is computed inside block 3 from C12: 7 + 2 = 9, so S15 at 10
General (n bits, 4-bit blocks, n/4 blocks): C_n at 2(n/4) + 1, last sum at 2(n/4) + 2
Versus 32 and 31 for the plain 16-bit ripple-carry adder. Still linear in n, but with a 4 times smaller slope.
Option 2: A Second Level of Look-Ahead
Treat each 4-bit block as one "super bit" with its own generate and propagate:
Block propagate P* = P3·P2·P1·P0 (1 AND level: ready at 2)
Block generate G* = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 (AND-OR: ready at 3)
Block carry-out C4 = G* + P*·C0
P* = 1 means "a carry entering this block will leave it"; G* = 1 means "this block produces a carry out by itself". Now a second look-ahead unit (the classic chip for this is the 74182 look-ahead carry generator) computes all block carries with the very same formulas, using P*, G* instead of P, G:
C4 = G*0 + P*0·C0
C8 = G*1 + P*1·G*0 + P*1·P*0·C0
C12 = G*2 + P*2·G*1 + P*2·P*1·G*0 + P*2·P*1·P*0·C0
C16 = G*3 + P*3·G*2 + P*3·P*2·G*1 + P*3·P*2·P*1·G*0 + P*3·P*2·P*1·P*0·C0
Timing: G*, P* ready at 3
C4, C8, C12, C16 at 3 + 2 = 5
carries inside each block (from its block carry-in) at 5 + 2 = 7
sums at 7 + 1 = 8
The pattern repeats: each extra level of look-ahead groups 4 times as many bits and adds a constant number of gate delays. So a full look-ahead tree has delay that grows as O(log n).
Verifying These Numbers by Simulation
Rather than trusting the arithmetic, here is a gate-level SystemVerilog model in which every gate has a delay of exactly 1 time unit (a two-level AND-OR expression is written with #2). It builds the three 16-bit adders, checks them on 20,000 random additions, and then measures how long each takes to settle when a carry generated at bit 0 must travel to bit 15 (input changes from 0 + 0 to FFFF + 0001):
// Unit-delay model: every gate (AND, OR, XOR) takes 1 time unit.
// A two-level AND-OR expression is therefore written with #2.
module fa (input a, b, cin, output s, cout);
wire p;
xor #1 (p, a, b); // P = A xor B, ready at 1
assign #2 cout = a&b | a&cin | b&cin; // two-level AND-OR: 2 gate delays
xor #1 (s, p, cin); // S = P xor Cin: 1 gate delay
endmodule
module rca16 (input [15:0] a, b, input c0, output [15:0] s, output c16);
wire [16:0] c;
assign c[0] = c0;
genvar i;
for (i = 0; i < 16; i++) begin : bit_
fa f (a[i], b[i], c[i], s[i], c[i+1]);
end
assign c16 = c[16];
endmodule
// 4-bit carry look-ahead block: carries are two-level SOPs of p, g, cin.
module cla4 (input [3:0] a, b, input cin,
output [3:0] s, output cout, pg, gg);
wire [3:0] p, g;
wire [4:1] c;
assign #1 p = a ^ b;
assign #1 g = a & b;
assign #2 c[1] = g[0] | p[0]&cin;
assign #2 c[2] = g[1] | p[1]&g[0] | p[1]&p[0]&cin;
assign #2 c[3] = g[2] | p[2]&g[1] | p[2]&p[1]&g[0] | p[2]&p[1]&p[0]&cin;
assign #2 c[4] = g[3] | p[3]&g[2] | p[3]&p[2]&g[1] | p[3]&p[2]&p[1]&g[0]
| p[3]&p[2]&p[1]&p[0]&cin;
assign #1 s = p ^ {c[3:1], cin};
assign cout = c[4];
assign #1 pg = &p; // block propagate
assign #2 gg = g[3] | p[3]&g[2] | p[3]&p[2]&g[1] | p[3]&p[2]&p[1]&g[0]; // block generate
endmodule
// 16 bits: four CLA blocks, carry rippling from block to block
module cla16_ripple (input [15:0] a, b, input c0, output [15:0] s, output c16);
wire [4:0] c; wire [3:0] pg, gg;
assign c[0] = c0;
genvar k;
for (k = 0; k < 4; k++) begin : blk
cla4 u (a[4*k+3:4*k], b[4*k+3:4*k], c[k], s[4*k+3:4*k], c[k+1], pg[k], gg[k]);
end
assign c16 = c[4];
endmodule
// 16 bits: four CLA blocks + a second-level look-ahead unit (like the 74182)
module cla16_2level (input [15:0] a, b, input c0, output [15:0] s, output c16);
wire [3:0] pg, gg, unused; wire [4:1] c;
assign #2 c[1] = gg[0] | pg[0]&c0;
assign #2 c[2] = gg[1] | pg[1]&gg[0] | pg[1]&pg[0]&c0;
assign #2 c[3] = gg[2] | pg[2]&gg[1] | pg[2]&pg[1]&gg[0] | pg[2]&pg[1]&pg[0]&c0;
assign #2 c[4] = gg[3] | pg[3]&gg[2] | pg[3]&pg[2]&gg[1] | pg[3]&pg[2]&pg[1]&gg[0]
| pg[3]&pg[2]&pg[1]&pg[0]&c0;
cla4 u0 (a[3:0], b[3:0], c0, s[3:0], unused[0], pg[0], gg[0]);
cla4 u1 (a[7:4], b[7:4], c[1], s[7:4], unused[1], pg[1], gg[1]);
cla4 u2 (a[11:8], b[11:8], c[2], s[11:8], unused[2], pg[2], gg[2]);
cla4 u3 (a[15:12], b[15:12], c[3], s[15:12], unused[3], pg[3], gg[3]);
assign c16 = c[4];
endmodule
module tb;
reg [15:0] a, b; reg c0;
wire [15:0] s1, s2, s3; wire k1, k2, k3;
rca16 r (a, b, c0, s1, k1);
cla16_ripple cr (a, b, c0, s2, k2);
cla16_2level c2 (a, b, c0, s3, k3);
time t0, last1, last2, last3, tc1, tc2, tc3;
integer errors = 0, n;
always @(s1 or k1) last1 = $time; // time of the last output change
always @(s2 or k2) last2 = $time;
always @(s3 or k3) last3 = $time;
always @(k1) tc1 = $time; // time the carry-out changed
always @(k2) tc2 = $time;
always @(k3) tc3 = $time;
initial begin
// functional check: 20000 random additions
for (n = 0; n < 20000; n++) begin
a = $random; b = $random; c0 = $random; #50;
if ({k1, s1} !== a + b + c0 || {k2, s2} !== a + b + c0 || {k3, s3} !== a + b + c0)
errors++;
end
$display("random functional check: %0d errors", errors);
// timing: carry generated in bit 0 must travel to bit 15
a = 0; b = 0; c0 = 0; #50;
t0 = $time; a = 16'hFFFF; b = 16'h0001; #50;
$display("FFFF + 0001 = %h carry %b", s1, k1);
$display("ripple-carry : C16 at %0d, all outputs settled at %0d", tc1 - t0, last1 - t0);
$display("4-bit CLA, rippled : C16 at %0d, all outputs settled at %0d", tc2 - t0, last2 - t0);
$display("2-level CLA : C16 at %0d, all outputs settled at %0d", tc3 - t0, last3 - t0);
end
endmodule
Output (Icarus Verilog with -g2012):
random functional check: 0 errors
FFFF + 0001 = 0000 carry 1
ripple-carry : C16 at 32, all outputs settled at 32
4-bit CLA, rippled : C16 at 9, all outputs settled at 10
2-level CLA : C16 at 5, all outputs settled at 8
The simulator reproduces the hand calculations exactly: 32 gate delays for the ripple-carry adder, C16 at 9 and sums at 10 for rippled CLA blocks, and C16 at 5 and sums at 8 with two levels of look-ahead.
Comparison
Point | Ripple-carry adder | Carry look-ahead adder |
|---|---|---|
How carries are computed | One after another, Ci+1 from Ci | In parallel, from G, P and C0 |
Delay (gate delays, n bits) | 2n for Cn: O(n) | Constant for one block (C at 3, S at 4); O(log n) for a hierarchical tree |
16-bit example | C16 at 32, S15 at 31 | Rippled blocks: C16 at 9, S at 10. Two-level: C16 at 5, S at 8 |
Hardware | n full adders: minimal | Extra look-ahead logic: n(n + 1)/2 AND gates in a single-level n-bit CLA |
Fan-in | Small and constant | Grows to n + 1 in a single level, so blocks are limited to about 4 bits |
Layout | Very regular | Less regular |
Used where | Small widths, low power, low area | Fast ALUs and address calculation |
Other Fast Adders (for Awareness)
Carry-skip (carry-bypass) adder: if a block's P* = 1, the incoming carry skips past the block on a fast path instead of rippling through it.
Carry-select adder: each upper block computes its sum twice, once for carry-in 0 and once for 1, and a 2-to-1 selector (a multiplexer, the subject of the next chapter) picks the right one when the real carry arrives.
Parallel-prefix adders (Kogge-Stone, Brent-Kung, Sklansky): compute the G/P combinations with a tree of small cells, giving O(log n) delay with bounded fan-in. Modern processor adders are of this family.
Common Mistakes
Not stating the delay model. "2 gate delays per carry, 1 for the sum" is standard, but if the question gives different numbers (for example XOR = 2 units), recompute instead of quoting 2n.
Using Sn−1's time as the adder delay without checking Cn (or vice versa). The adder is done when the slowest output is done: take the maximum.
Saying the CLA has constant delay for any n. Only with unlimited fan-in. Practical CLAs are hierarchical and their delay grows as O(log n) (or linearly if blocks are simply rippled).
Writing C2 = G1 + P1G0 + P0C0. Every term must contain the P's of all stages above the one that generates: the last term is P1P0C0.
Mixing up the two definitions of P. Some books use Pi = Ai + Bi. The carry equations still work (when both bits are 1, Gi already gives the carry), but then Si must be computed as Ai ⊕ Bi ⊕ Ci, not Pi ⊕ Ci.
Forgetting that C15, not C16, feeds S15. In the rippled-block 16-bit adder, S15 is ready at 10 because C15 arrives at 9 (from C12 at 7), not because of C16.
GATE and Interview Questions
Q1. In a 32-bit ripple-carry adder, each full adder's carry output is ready 2 gate delays after its inputs, and its sum 1 gate delay after its carry input (Pi already available). How long until all outputs are valid?
C32 at 2 × 32 = 64; S31 at 2 × 31 + 1 = 63. All outputs are valid after 64 gate delays.
Q2. Write C3 for a carry look-ahead adder.
C3 = G2 + P2G1 + P2P1G0 + P2P1P0C0, with Gi = AiBi and Pi = Ai ⊕ Bi.
Q3. How many AND and OR gates does the carry look-ahead logic of an n-bit single-level CLA need (not counting the G and P gates)?
Ci needs i AND gates (one for each term containing a P), so 1 + 2 + ... + n = n(n + 1)/2 AND gates, and one OR gate per carry: n OR gates. For n = 4: 10 AND, 4 OR.
Q4. A 16-bit adder is built from four 4-bit CLA blocks with the block carries rippled. Using the standard model (G, P at 1; a block's carries 2 gate delays after its carry-in and its G, P; sum 1 gate delay later), when is S15 valid?
C4 at 3, C8 at 5, C12 at 7; inside the last block C15 at 9; S15 = P15 ⊕ C15 at 10 gate delays (C16 at 9).
Q5. An 8-bit ripple-carry adder uses full adders with carry delay 3 ns and sum delay 4 ns (both from Cin). What is the worst-case addition time?
C8 at 8 × 3 = 24 ns; S7 at 7 × 3 + 4 = 25 ns. Worst case: 25 ns.
Q6. What do the block generate and block propagate signals of a 4-bit CLA mean?
P* = P3P2P1P0 is 1 when a carry entering the block will pass all the way through it. G* = G3 + P3G2 + P3P2G1 + P3P2P1G0 is 1 when the block produces a carry out on its own. The block carry-out is G* + P*Cin, which lets a second level of look-ahead treat blocks like bits.
Q7. Why don't designers just build one 64-bit single-level CLA?
C64 would need a 65-input OR gate and AND gates with up to 65 inputs, and thousands of gates in total (64 × 65 / 2 = 2080 AND gates). Large fan-in gates are slow and big, and the wires would be long. Hierarchical look-ahead (or prefix adders) achieves O(log n) delay with small gates.
Summary
Ripple-carry adder: n chained full adders; simple and small, but the carry ripples: Cn at 2n and Sn−1 at 2n − 1 gate delays, O(n).
Carry look-ahead: Gi = AiBi, Pi = Ai ⊕ Bi, Ci+1 = Gi + PiCi, expanded into two-level expressions so all carries are computed in parallel. A 4-bit CLA has carries at 3 and sums at 4 gate delays.
Single-level look-ahead costs n(n + 1)/2 AND gates and fan-in up to n + 1, so practical adders use 4-bit blocks.
16-bit adder: rippled CLA blocks give C16 at 9, sums at 10; a second look-ahead level (P*, G*) gives C16 at 5, sums at 8. Our gate-level simulation confirmed all of these.
Next, Multiplexers: the data selector, which you will also find inside carry-select adders.