Carry-Lookahead Adders

Compute carries from generate and propagate signals instead of waiting for them, and measure what that saves.

You Will Be Able To

  • Define generate and propagate, and write each carry from them.
  • Write the 4-bit lookahead equations.
  • Combine bits into block generate and block propagate.
  • Compare ripple, block and two-level lookahead adders by measured gate delays and cells.
Lesson
G4.6
Time
30 min
Runs on
Your browser
Check
5 questions

A 16-bit ripple-carry adder is small, but its worst carry crosses 16 stages. In the cell model of this lesson it needs 33 gate delays. A clock that ticks every 10 gate delays leaves no time for anything else.

16-bit adderCarry in crosses every bitWorst seenCells
Ripple carry323380
Lookahead for block carries (the lab)1315100
Two-level lookahead58118

Gate delays measured in Icarus, one time unit per cell of any fan-in. Worst seen covers directed changes and 3,000 seeded ones.

Generate and Propagate

Look at one bit position with inputs a and b. It generates a carry when both are 1: g = a·b. It propagates an incoming carry when exactly one is 1: p = a ⊕ b. When both are 0, it kills the carry.

So the carry out of bit i is c(i+1) = g(i) + p(i)·c(i). The sum is s(i) = p(i) ⊕ c(i). These are the two half adders of lesson G4.5.

a bgpWhat happens to a carry
0 000killed
0 101passed on
1 001passed on
1 110made here, whatever comes in

Each bit position does one of three things to the carry.

The 4-Bit Lookahead Equations

Substitute each carry into the next. Then every carry depends only on g, p and the carry in c0.

Read c3 term by term. Bit 2 makes a carry. Or bit 1 makes one and bit 2 passes it. Or bit 0 makes one and both pass it. Or c0 comes in and all three pass it.
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

Each carry is one AND level and one OR level after p and g. No carry waits for another.

Four Bits, Ripple Carry
Four Bits, Ripple Carryg0 · XORp0=0g1 · ANDgen0=1g2 · XORp1=1g3 · ANDgen1=0g4 · XORp2=1g5 · ANDgen2=0g6 · XORp3=1g7 · ANDgen3=0g8 · ANDt1=0g9 · ORc1=1g10 · XORs0=0g11 · ANDt2=1g12 · ORc2=1g13 · XORs1=0g14 · ANDt3=1g15 · ORc3=1g16 · XORs2=0g17 · ANDt4=1g18 · ORcout=1g19 · XORs3=0a0=1a1=1a2=1a3=1b0=1b1=0b2=0b3=0ci=0
a0=1 a1=1 a2=1 a3=1 b0=1 b1=0 b2=0 b3=0 ci=0
g0 · XORa0=1, b0=1 → p0=0
g1 · ANDa0=1, b0=1 → gen0=1
g2 · XORa1=1, b1=0 → p1=1
g3 · ANDa1=1, b1=0 → gen1=0
g4 · XORa2=1, b2=0 → p2=1
g5 · ANDa2=1, b2=0 → gen2=0
g6 · XORa3=1, b3=0 → p3=1
g7 · ANDa3=1, b3=0 → gen3=0
g8 · ANDp0=0, ci=0 → t1=0
g9 · ORgen0=1, t1=0 → c1=1
g10 · XORp0=0, ci=0 → s0=0
g11 · ANDp1=1, c1=1 → t2=1
g12 · ORgen1=0, t2=1 → c2=1
g13 · XORp1=1, c1=1 → s1=0
g14 · ANDp2=1, c2=1 → t3=1
g15 · ORgen2=0, t3=1 → c3=1
g16 · XORp2=1, c2=1 → s2=0
g17 · ANDp3=1, c3=1 → t4=1
g18 · ORgen3=0, t4=1 → cout=1
g19 · XORp3=1, c3=1 → s3=0
Read the connections
GateKindInputsOutput
g0XORa0, b0p0
g1ANDa0, b0gen0
g2XORa1, b1p1
g3ANDa1, b1gen1
g4XORa2, b2p2
g5ANDa2, b2gen2
g6XORa3, b3p3
g7ANDa3, b3gen3
g8ANDp0, cit1
g9ORgen0, t1c1
g10XORp0, cis0
g11ANDp1, c1t2
g12ORgen1, t2c2
g13XORp1, c1s1
g14ANDp2, c2t3
g15ORgen2, t3c3
g16XORp2, c2s2
g17ANDp3, c3t4
g18ORgen3, t4cout
g19XORp3, c3s3

Outputs: s3, s2, s1, s0, cout. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 24. Settled after 24 gate delays from t = 0.

Output values at each gate delay0123456789101112131415161718192021222324s3xxxxxxx111111111111111100s2xxxxx11111111111111110000s1xxx1111111111111111000000s0xx11111111111111110000000coutxxxxxxxx00000000000000001
Scroll horizontally ↔
Every computed frame
Times3s2s1s0cout
0xxxxx
1xxxxx
2xxx1x
3xx11x
4xx11x
5x111x
6x111x
71111x
811110
911110
1011110
1111110
1211110
1311110
1411110
1511110
1611110
1711110
1811100
1911000
2011000
2110000
2210000
2300000
2400001

  1. Step 18 · b becomes 0001 at time 16. Bit 0 now makes a carry. The ripple chain starts moving it up.
  2. Step 24 · Settled at time 24. 8 gate delays after the change: two per bit.

The ripple-adder preset: 1111 + 0000, then b = 0001 at time 16.

Four Bits, Lookahead
Four Bits, Lookaheadg0 · XORp0=0g1 · ANDgen0=1g2 · XORp1=1g3 · ANDgen1=0g4 · XORp2=1g5 · ANDgen2=0g6 · XORp3=1g7 · ANDgen3=0g8 · ANDt1_0=0g9 · ORc1=1g10 · XORs0=0g11 · ANDt2_1=1g12 · ANDt2_0=0g13 · ORc2=1g14 · XORs1=0g15 · ANDt3_2=0g16 · ANDt3_1=1g17 · ANDt3_0=0g18 · ORc3=1g19 · XORs2=0g20 · ANDt4_3=0g21 · ANDt4_2=0g22 · ANDt4_1=1g23 · ANDt4_0=0g24 · ORcout=1g25 · XORs3=0a0=1a1=1a2=1a3=1b0=1b1=0b2=0b3=0ci=0
a0=1 a1=1 a2=1 a3=1 b0=1 b1=0 b2=0 b3=0 ci=0
g0 · XORa0=1, b0=1 → p0=0
g1 · ANDa0=1, b0=1 → gen0=1
g2 · XORa1=1, b1=0 → p1=1
g3 · ANDa1=1, b1=0 → gen1=0
g4 · XORa2=1, b2=0 → p2=1
g5 · ANDa2=1, b2=0 → gen2=0
g6 · XORa3=1, b3=0 → p3=1
g7 · ANDa3=1, b3=0 → gen3=0
g8 · ANDp0=0, ci=0 → t1_0=0
g9 · ORgen0=1, t1_0=0 → c1=1
g10 · XORp0=0, ci=0 → s0=0
g11 · ANDp1=1, gen0=1 → t2_1=1
g12 · ANDp1=1, p0=0, ci=0 → t2_0=0
g13 · ORgen1=0, t2_1=1, t2_0=0 → c2=1
g14 · XORp1=1, c1=1 → s1=0
g15 · ANDp2=1, gen1=0 → t3_2=0
g16 · ANDp2=1, p1=1, gen0=1 → t3_1=1
g17 · ANDp2=1, p1=1, p0=0, ci=0 → t3_0=0
g18 · ORgen2=0, t3_2=0, t3_1=1, t3_0=0 → c3=1
g19 · XORp2=1, c2=1 → s2=0
g20 · ANDp3=1, gen2=0 → t4_3=0
g21 · ANDp3=1, p2=1, gen1=0 → t4_2=0
g22 · ANDp3=1, p2=1, p1=1, gen0=1 → t4_1=1
g23 · ANDp3=1, p2=1, p1=1, p0=0, ci=0 → t4_0=0
g24 · ORgen3=0, t4_3=0, t4_2=0, t4_1=1, t4_0=0 → cout=1
g25 · XORp3=1, c3=1 → s3=0
Read the connections
GateKindInputsOutput
g0XORa0, b0p0
g1ANDa0, b0gen0
g2XORa1, b1p1
g3ANDa1, b1gen1
g4XORa2, b2p2
g5ANDa2, b2gen2
g6XORa3, b3p3
g7ANDa3, b3gen3
g8ANDp0, cit1_0
g9ORgen0, t1_0c1
g10XORp0, cis0
g11ANDp1, gen0t2_1
g12ANDp1, p0, cit2_0
g13ORgen1, t2_1, t2_0c2
g14XORp1, c1s1
g15ANDp2, gen1t3_2
g16ANDp2, p1, gen0t3_1
g17ANDp2, p1, p0, cit3_0
g18ORgen2, t3_2, t3_1, t3_0c3
g19XORp2, c2s2
g20ANDp3, gen2t4_3
g21ANDp3, p2, gen1t4_2
g22ANDp3, p2, p1, gen0t4_1
g23ANDp3, p2, p1, p0, cit4_0
g24ORgen3, t4_3, t4_2, t4_1, t4_0cout
g25XORp3, c3s3

Outputs: s3, s2, s1, s0, cout. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 20. Settled after 20 gate delays from t = 0.

Output values at each gate delay01234567891011121314151617181920s3xxxx11111111111111110s2xxxx11111111111111110s1xxx111111111111111100s0xx1111111111111111000coutxxx000000000000000011
Scroll horizontally ↔
Every computed frame
Times3s2s1s0cout
0xxxxx
1xxxxx
2xxx1x
3xx110
411110
511110
611110
711110
811110
911110
1011110
1111110
1211110
1311110
1411110
1511110
1611110
1711110
1811100
1911001
2000001

  1. Step 18 · Two gate delays after the change. p0 and g0 change at 17. At 18 every carry term that uses them has switched.
  2. Step 20 · Settled at time 20. 4 gate delays after the change, half the ripple time. The cost is wider gates: an OR of five terms for the carry out.

The cla preset: the same inputs and the same change, with every carry written from p, g and the carry in.

Block Generate and Block Propagate

The same idea works for a group of bits. A 4-bit block propagates when every bit propagates: P = p3·p2·p1·p0. It generates when it makes a carry by itself: G = g3 + p3·g2 + p3·p2·g1 + p3·p2·p1·g0.

Then the block's carry out is G + P·cin: two cell delays after its carry in, whatever happens inside. The lab below keeps a ripple chain inside each block and uses this for the block carries.

A 16-bit Adder with Lookahead for Block CarriesFour 4-bit blocks. Each one computes P and G from its own bits. Its carry out is G + P times its carry in.
  • I/O
  • Datapath
  • Data
CallValueReturnWaiting
A 16-bit adder with lookahead for block carriesFour 4-bit blocks. Each one computes P and G from its own bits. Its carry out is G + P times its carry in. io ci carry in datapath Block 0 bits 3..0 datapath Block 1 bits 7..4 datapath Block 2 bits 11..8 datapath Block 3 bits 15..12 io co carry out cinc4c8c12c16
  1. datapath Block 0bits 3..0
    • c4 → Block 1
  2. datapath Block 1bits 7..4
    • c8 → Block 2
  3. datapath Block 2bits 11..8
    • c12 → Block 3
  4. datapath Block 3bits 15..12
    • c16 → co
  5. io cicarry in
    • cin → Block 0
  6. io cocarry out
  1. P and G first

    All four blocks compute P and G at the same time, from their own a and b. That takes three cell delays.

  2. Block carries

    A carry in now crosses each block in two cell delays, through G + P·cin, not through four bit stages.

    Follow the calls, values and waits
    1. data carry: Block 0 → Block 1
    2. data carry: Block 1 → Block 2
    3. data carry: Block 2 → Block 3
  3. The last block ripples

    Inside block 3 the carry still ripples to bit 15. That sets the lab's worst case, 15 gate delays.

Read the diagram as text
  • ci: carry in
  • Block 0: bits 3..0
  • Block 1: bits 7..4
  • Block 2: bits 11..8
  • Block 3: bits 15..12
  • co: carry out
  • ci → Block 0: cin
  • Block 0 → Block 1: c4
  • Block 1 → Block 2: c8
  • Block 2 → Block 3: c12
  • Block 3 → co: c16

The block carries still pass from block to block, but each step costs two cells instead of eight.

Two-Level Lookahead

The block carries can be looked ahead too. Treat each block as one big bit with its own P and G. Then write c4, c8, c12 and c16 with the same equations as c1 to c4. A second lookahead unit computes them all at once from the four (P, G) pairs and ci.

Inside each block the carries can also be written with lookahead, from the block's carry in. Then no carry waits for a chain. The order is p and g, block P and G, the block carries, the inner carries, and the sum.

In the cell model that is 8 gate delays, against 33 for ripple, at the cost of 118 cells against 80. Problem G4.6.2 asks you to build it.

Written asCellsLogic levels
Ripple carry8033
Lookahead for block carries8333
Two-level lookahead9229

Measured on this site's synthesis flow for these netlists, with each cell turned into an assign. Another way of writing the same adder gives other numbers.

Asked in interviews
  1. What are generate and propagate?

    For one bit, g = a·b makes a carry and p = a ⊕ b passes one on. The carry out is g + p·cin. For a block, G and P say the same about the whole group.

  2. Why is a lookahead adder faster than ripple?

    Each carry is computed directly from g, p and the carry in, in one AND level and one OR level. No carry waits for the one below it.

  3. What does lookahead cost?

    More and wider gates. The carry out of 4 bits already needs an OR of five terms and an AND of five inputs. Wide adders split into blocks and look ahead in two levels.

Try It

The carry in crosses all four blocks through their G + P·cin cells, then ripples inside block 3. That takes 13 gate delays. A change of a0 adds two more: p0, then the block G.

Make block4 a plain ripple block: replace the last two cells with OR2 obc (cout, g[3], t3); and an AND2 at3 (t3, p[3], c[3]);, and declare t3. Run, and compare the settle times with the ripple row of the table.

Count the cells: the bench prints 100, 25 per block. Seven per block compute P, G and the carry out, five more than a ripple block needs.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: ci rises, all bits propagate ffff + 0000 + 1 = 1_0000 settled after 13 a0 falls fffe + 0000 + 1 = 0_ffff settled after 15 a0 rises ffff + 0000 + 1 = 1_0000 settled after 15 carry stops in bit 8 00ff + 0001 + 0 = 0_0100 settled after 11 100 cells
Read included file: cells.sv
// cells.sv: the unit-delay cell library (read-only).
// Every cell takes 1 time unit, whatever its fan-in. Ports are (y, inputs...): output first.
// Each cell adds 1 to the bench's cell counter when the simulation starts.
module INV   (output wire y, input wire a);                 not #1 (y, a);               initial tb.cells++; endmodule
module AND2  (output wire y, input wire a, b);              and #1 (y, a, b);            initial tb.cells++; endmodule
module AND3  (output wire y, input wire a, b, c);           and #1 (y, a, b, c);         initial tb.cells++; endmodule
module AND4  (output wire y, input wire a, b, c, d);        and #1 (y, a, b, c, d);      initial tb.cells++; endmodule
module AND5  (output wire y, input wire a, b, c, d, e);     and #1 (y, a, b, c, d, e);   initial tb.cells++; endmodule
module OR2   (output wire y, input wire a, b);              or #1 (y, a, b);             initial tb.cells++; endmodule
module OR3   (output wire y, input wire a, b, c);           or #1 (y, a, b, c);          initial tb.cells++; endmodule
module OR4   (output wire y, input wire a, b, c, d);        or #1 (y, a, b, c, d);       initial tb.cells++; endmodule
module OR5   (output wire y, input wire a, b, c, d, e);     or #1 (y, a, b, c, d, e);    initial tb.cells++; endmodule
module NAND2 (output wire y, input wire a, b);              nand #1 (y, a, b);           initial tb.cells++; endmodule
module NOR2  (output wire y, input wire a, b);              nor #1 (y, a, b);            initial tb.cells++; endmodule
module XOR2  (output wire y, input wire a, b);              xor #1 (y, a, b);            initial tb.cells++; endmodule
module XNOR2 (output wire y, input wire a, b);              xnor #1 (y, a, b);           initial tb.cells++; endmodule
Read included file: tb.sv
// tb.sv: four input changes; for each, the sum and the gate delays until the outputs settle (read-only).
module tb;
  int cells;                       // every cell adds itself here
  logic [15:0] a, b;
  logic        ci;
  wire  [15:0] s;
  wire         co;
  time         t0, last;
  add16 dut (.a(a), .b(b), .ci(ci), .s(s), .co(co));
  always @(s or co) last = $time;
  task automatic change(input logic [15:0] x, y, input logic z, input string what);
    a = x; b = y; ci = z;
    t0 = $time; last = t0;
    #40;
    $display("%-28s %h + %h + %b = %b_%h  settled after %0d", what, x, y, z, co, s, last - t0);
  endtask
  initial begin
    a = 16'hFFFF; b = 16'h0000; ci = 1'b0;
    #40;
    change(16'hFFFF, 16'h0000, 1'b1, "ci rises, all bits propagate");
    change(16'hFFFE, 16'h0000, 1'b1, "a0 falls");
    change(16'hFFFF, 16'h0000, 1'b1, "a0 rises");
    change(16'h00FF, 16'h0001, 1'b0, "carry stops in bit 8");
    $display("%0d cells", cells);
  end
endmodule

Check Yourself

ConceptBits 3 to 0 have p = 1011 and g = 0100. What is the block propagate P?
ConceptIn the 4-bit lookahead equations, how many product terms does c4 have, and how many inputs has its widest AND?
ConceptWhy does the lab adder settle in 15 gate delays and not in 8?
ConceptA 16-bit ripple adder and a two-level lookahead adder are synthesized on this site. What does the Gates tab show?
Predict the outputPredict the exact line: the carry out of one bit, g + p·cin, for a = 1, b = 0, cin = 1.
module tb;
  logic a = 1, b = 0, cin = 1;
  initial $display("%b", (a & b) | ((a ^ b) & cin));
endmodule

Common Mistakes

Wrong Define p as a OR b in one place and as a XOR b in another.

Both work for the carry, but only the XOR gives the sum: s = p ⊕ c. An OR in the sum is wrong whenever a = b = 1.

Fix Use p = a ⊕ b everywhere, so the same signal serves the carry and the sum.

Wrong Write lookahead equations that still use the carry below.

c2 = g1 + p1·c1 is correct, but it waits for c1. The chain still ripples.

Fix Substitute until only g, p and the carry in remain: c2 = g1 + p1·g0 + p1·p0·c0.

Wrong Trust the Gates tab to compare adder architectures.

The synthesis flow rebuilds the carry logic. Adders with very different unit-delay times can come out with similar depths.

Fix Compare structures in a model that keeps them, such as the unit-delay cells of this lesson.

Wrong Read "worst seen" over random inputs as the true worst case.

A sample can miss the one change that sensitizes the longest path.

Fix Add directed changes that start a carry at bit 0 with every bit propagating, and reason about the longest path.

Remember

  • g = a·b generates a carry; p = a ⊕ b propagates one; c(i+1) = g(i) + p(i)·c(i).
  • Lookahead writes every carry from g, p and c0: one AND and one OR level.
  • A block has P = AND of its p and G = its own carry; its carry out is G + P·cin.
  • Measured for 16 bits: ripple 33, block lookahead 15, two-level lookahead 8 gate delays.
  • Synthesis restructures adders; compare architectures in a unit-delay model.

Practice

Report a problem with this page