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 adder | Carry in crosses every bit | Worst seen | Cells |
|---|---|---|---|
| Ripple carry | 32 | 33 | 80 |
| Lookahead for block carries (the lab) | 13 | 15 | 100 |
| Two-level lookahead | 5 | 8 | 118 |
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 b | g | p | What happens to a carry |
|---|---|---|---|
| 0 0 | 0 | 0 | killed |
| 0 1 | 0 | 1 | passed on |
| 1 0 | 0 | 1 | passed on |
| 1 1 | 1 | 0 | made 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.
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·c0Each carry is one AND level and one OR level after p and g. No carry waits for another.
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.
- I/O
- Datapath
- Data
- 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.
- 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
- data carry: Block 0 → Block 1
- data carry: Block 1 → Block 2
- data carry: Block 2 → Block 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 as | Cells | Logic levels |
|---|---|---|
| Ripple carry | 80 | 33 |
| Lookahead for block carries | 83 | 33 |
| Two-level lookahead | 92 | 29 |
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
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.
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.
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.
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 cellsRead 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
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.