Block carry-lookahead

Also called: hierarchical carry-lookahead, multilevel carry-lookahead, group generate, group propagate, lookahead carry unit

A fast adder design that applies carry-lookahead within small blocks (often 4 bits) and then again between blocks, using group generate and propagate signals.

A fully expanded carry lookahead adder gets impractical for wide numbers: C64 would need 65 product terms, the longest with 65 inputs. Block carry-lookahead keeps most of the speed without giant gates by using lookahead in two or more levels.

Split the adder into blocks of, say, 4 bits. Inside each block, compute the carries with ordinary lookahead from that block's G and P signals.
Summarize each block with two signals, both computed from the block's own G's and P's.
A second-level lookahead unit treats the blocks exactly like bits: the carry into the next block is GG + PG · (carry into this block).

The two block signals for a 4-bit block:

Group generate GG = : the block produces a carry-out by itself.
Group propagate PG = : a carry entering the block passes all the way through.

Every gate stays small (at most 5 inputs for 4-bit blocks), and the delay grows with the number of levels, roughly the logarithm of the width, instead of linearly as in a ripple carry adder.

A simpler middle ground uses lookahead inside each block but lets the carry ripple from block to block. It's faster than pure ripple and smaller than a second lookahead level.

Worked example

Example

Carries between four 4-bit blocks

A 16-bit adder with C0 = 0. Suppose block 0 has GG = 1, blocks 1 and 2 have GG = 0 and PG = 1, and block 3 has GG = 0 and PG = 0.

1.
Into block 1: GG₀ + PG₀ · C0 = 1 + 0 = 1.
2.
Into block 2: GG₁ + PG₁ · 1 = 0 + 1 = 1.
3.
Into block 3: GG₂ + PG₂ · 1 = 0 + 1 = 1.
4.
Out of block 3: GG₃ + PG₃ · 1 = 0 + 0 = 0.
5.
The second level computes all four block carries in parallel, just as a 4-bit lookahead computes C1 to C4.

Common mistakes

Writing group propagate as an OR of the P's. Every position must propagate, so it's an AND.
Assuming full lookahead scales to any width. Gate size is the limit.
Thinking the group signals depend on the block's carry-in. They depend only on its A and B bits.

Practice Block carry-lookahead

Interactive questions with instant feedback and a worked solution for every wrong answer.

Adders and ALUs lesson full course

Why don't real 64-bit adders just use one fully expanded lookahead expression for every carry?

Learn it step by step

Block carry-lookahead is taught in Adders and ALUs.

Adders and ALUs →

All terms