Adders — Generate, Propagate & Trees

Ground-up guide to CMOS circuit design — transistors, gates, delay, power, memory, datapath and test

Adders Deserve a Deep Look

Addition shows up everywhere in a chip. It is inside counters, address math, and multipliers. So a fast, small adder pays off many times over. This chapter goes deeper than the basics. It explains generate and propagate, the lookahead idea, and tree adders, all in plain words with numbers.

The Full Adder, Restated

A full adder takes three inputs: bit A, bit B, and a carry-in. It makes two outputs: a sum bit and a carryout.

• Sum is 1 when an odd number of the three inputs are 1.
• Carry-out is 1 when two or more inputs are 1. Chain N full adders and the carry ripples along. This is the ripple-carry adder. Simple, small, but slow. The carry must walk through all N stages.

Generate and Propagate: the Key Idea

Fast adders rest on two per-bit signals. They describe what each bit position does to a carry.

• Generate (G): this bit makes a carry on its own. That happens when A and B are both 1. So G = A AND B.
• Propagate (P): this bit passes an incoming carry through. That happens when A or B is 1. So P = A OR B (or A XOR B in some forms). With G and P, the carry-out of a bit is: Cout = G OR (P AND Cin). In words: a carry leaves a bit if the bit generated one, or if it propagated the carry that came in. Signal Definition Meaning Generate G A AND B this bit makes a carry Propagate P A OR B this bit passes a carry Carry-out G OR (P AND Cin) leaves if made or passed This is the whole foundation. Every fast adder is a clever way to compute these carries quickly.

Carry-Lookahead: Compute Carries in Parallel

In ripple-carry, each carry waits for the one before it. Carry-lookahead breaks that wait. It expands the carry formula so each carry depends only on the G and P signals, not on the previous carry. For example, the carry into bit 2 can be written directly from G0, P0, G1, P1, and the first carry-in. No waiting. All carries can be computed at once, in parallel. The cost is more logic. The gates that compute these expanded carries get large for wide adders. So pure lookahead is used in small blocks, then blocks are combined.

Worked example — lookahead vs ripple

Say each carry stage adds 0.10 ns in ripple form. An 8-bit ripple adder's carry path is about 8 × 0.10 = 0.80 ns. A lookahead version computes the carries in roughly 2 to 3 gate levels, say 0.30 ns. That is more than 2× faster for 8 bits, and the gap grows with width.

For wide adders, the best structures arrange the carry logic as a balanced tree. These are called prefix adders. They combine G and P signals in pairs, then groups, then larger groups, like a tournament bracket. The depth of the tree is about log2 of the bit width. So a 32-bit adder has a carry depth of about 5 levels, not 32. This is the fastest common adder style.

Worked example — tree depth

Compare carry depth for a 32-bit adder.

ripple:  ~32 carry stages
tree:    log2(32) = 5 levels

The tree path is about 6× shorter. At 0.10 ns per level, that is roughly 0.50 ns versus 3.2 ns. That is why high-speed processors use tree adders, despite their larger area and wiring.

Carry-Select: Precompute Both Ways

Another fast trick is carry-select. Split the adder into blocks. For each block, compute two results at once: one assuming carry-in is 0, one assuming carry-in is 1. When the real carry arrives, a mux picks the correct result. This hides the carry wait behind parallel work. It trades area (two adders per block) for speed. It is a good middle ground between ripple and full tree.

Worked example — carry-select blocks

A 16-bit adder split into four 4-bit blocks. Each block computes both carry cases in parallel. The real carry then ripples only block to block (4 hops), and each hop is just a mux. So the carry path shrinks from 16 bit-stages to about 4 block-muxes. Faster, at the cost of nearly double the adder logic per block.

Choosing an Adder

The choice is the usual three-way trade.

Real designs often mix styles. A common pattern: lookahead within small blocks, then a tree or select across blocks. Synthesis tools pick the structure from the timing and area constraints you give.

Subtraction and Two's Complement (Brief)

Subtraction reuses the adder. To compute A − B, invert B and add 1. The "add 1" is done by setting the first carry-in to 1. So one adder handles both add and subtract, with a control bit that inverts B and sets the carry-in. This is why an ALU's add/subtract share most of their hardware.

Interview Q&A

bit makes its own carry. Propagate (P = A OR B) means a bit passes an incoming carry. With them, each carry-out is G OR (P AND carry-in). Fast adders use G and P to compute carries in parallel instead of rippling.

depends only on the G and P signals, not on the previous carry. All carries can then be computed in parallel in a few gate levels, removing the bit-by-bit ripple wait. The cost is more, larger gates.

balanced tree, giving a carry depth of about log2 of the bit width instead of N. For 32 bits that is ~5 levels versus ~32, so the carry path is several times shorter. The cost is more area and wiring.

result twice in parallel — once for carry-in 0 and once for carry-in 1. When the real carry arrives, a mux selects the right precomputed result. It trades extra area for a shorter carry path.

done by setting the first carry-in to 1. A control bit selects invert-and-carry-in for subtract or passthrough for add, so add and subtract share almost all the hardware.

smallest but slow; prefix/tree is fastest but largest; carry-select and small lookahead sit in between. Many designs mix styles (lookahead within blocks, tree across blocks), and synthesis picks based on constraints.

Key Takeaways

• Fast adders are built on generate (G = A·B) and propagate (P = A+B); carry-out = G OR (P AND carry-in).
• Carry-lookahead computes carries in parallel; prefix/tree adders give log-depth carry (~5 levels for 32 bits).
• Carry-select precomputes both carry cases per block and muxes the answer — area for speed.
• The choice is the speed vs area vs power trade; real designs mix styles and let synthesis decide.
• The same adder does subtraction by inverting B and setting carry-in to 1 (two's complement).