Fast Carry Generation: Summary

Comparing adder architectures

Architecture	Delay (carry)	Gate count	Notes
Ripple carry	O(n)	O(n)	Simple, minimal hardware, slow for large n
Carry lookahead	O(1) per block	O(n²)	Fastest fully parallel design, high fan-in limits
Block lookahead	O(n/k)	O(n)	k-bit CLA blocks with ripple between blocks
Tree / prefix	O(log n)	O(n log n)	Used in modern high-performance processors

The fundamental trade-off is area versus speed. For the Part IA syllabus, the ripple carry and the block-based carry lookahead are the expected architectures to understand.

Carry kill, propagate, generate: complete picture

For completeness, every pair of inputs $(a_i, b_i)$ defines exactly one of three functions:

• $g_i = a_i \cdot b_i$ (generate: $c_{i+1} = 1$ unconditionally)
• $p_i = a_i \oplus b_i$ (propagate: $c_{i+1} = c_i$)
• $k_i = \bar{a}_i \cdot \bar{b}_i$ (kill: $c_{i+1} = 0$ unconditionally)

Carry out is always zero: this is a carry kill. The carry chain ends.

Carry out equals carry in: this is a carry propagate. The carry passes through.

Carry out is always one: this is a carry generate. A new carry begins (or continues).

With these definitions, a fast carry generator is simply a circuit that evaluates $c_{i+1} = g_i + p_i \cdot c_i$ for all i simultaneously. The unrolled equations shown in the previous note are the direct SOP expressions for each $c_i$.

Block carry lookahead

In practice, a 4-bit carry lookahead block computes c1, c2, c3, c4 from (a0,b0)...(a3,b3) and c0. It also outputs:

• Block generate G = g3 + p3·g2 + p3·p2·g1 + p3·p2·p1·g0
• Block propagate P = p3 · p2 · p1 · p0

These feed the next-level carry generator. For a 16-bit adder: four 4-bit CLA blocks, plus one carry generator that computes carries between blocks using G and P from each block. The total delay is roughly 3 + 3 + 3 = 9 gate delays, compared to 16 × 2 = 32 for ripple.

The XOR-based sum revisited

The expression $s_i = a_i \oplus b_i \oplus c_i = p_i \oplus c_i$ is the same for both ripple carry and carry lookahead adders; only the way $c_i$ is generated differs. This separation is key: the carry generation logic can be optimised independently from the sum generation.

Connection to the ALU

In the processor architecture section, the ALU’s adder uses these same principles. An ALU that performs both addition and subtraction typically uses a carry lookahead adder with an extra control: setting c0 = 1 and XORing the $b_i$ inputs with the subtract control signal implements two’s complement subtraction (A + ~B + 1 for subtract, or A + B + 0 for add).

The fast carry generation concepts are also used in the BEQZ branch logic within the processor: testing whether a register equals zero requires a fast OR (or NOR) tree over all bits, which is structurally similar to a carry tree.