Chapter 14 of 32

Ripple-Carry & Carry Look-Ahead Adders

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.