Arithmetic Circuits: Adders and Multipliers

The simplest arithmetic building block is the half adder, which adds two individual bits and produces a sum (the XOR of the inputs) and a carry (the AND of the inputs). Since chaining multiple bit positions also requires accounting for a carry coming in from the previous position, in practice one uses the full adder, which combines three inputs (the two bits A and B to be added, plus the carry-in C_in from the previous position) into a sum and a carry-out C_out. A full adder can be built from two half adders plus an additional OR gate, and typically requires about 20 to 28 transistors in a standard CMOS cell.

The Boolean equation C_out = (A AND B) OR (C_in AND (A XOR B)) can be read intuitively as a majority vote: C_out becomes 1 exactly when at least two of the three inputs (A, B, C_in) are 1 – regardless of which two they are. For A=1, B=1, C_in=0, for instance, A AND B alone already produces the carry; for A=1, B=0, C_in=1, A and B differ (A XOR B = 1), and C_in AND (A XOR B) produces it instead. The sum, by contrast, is 1 when an odd number of the three inputs is 1 (1 or 3 out of 3) – exactly the behavior of a three-input XOR.

Chaining several full adders together, with the carry output of each stage feeding the carry input of the next higher stage, produces the simplest multi-bit adder: the carry-ripple adder.

In a carry-ripple adder, the carry must "ripple" sequentially through every bit position (hence the name) before the final result is available. A concrete example illustrates this: in the 4-bit addition 0111 + 0001, position 0 first produces C_out,0=1 (since A₀=B₀=1); this carry must arrive at position 1 before Sum₁ and C_out,1 are determined there, which in turn must arrive at position 2, and so on – only once the carry has propagated through all four stages is the correct final result, 1000, fully available. In a 32-bit adder, the carry signal in the worst case propagates through all 32 full-adder stages one after another, so the delay grows linearly with the bit width.

The carry-lookahead adder solves this problem by precomputing, for every bit position i, two auxiliary signals: generate G_i = A_i AND B_i (a carry is always generated here, regardless of the incoming carry) and propagate P_i = A_i XOR B_i (an incoming carry would be passed through). From these, every carry can be expressed directly as a sum of product terms, for example C₁ = G₀ + P₀C₀, C₂ = G₁ + P₁G₀ + P₁P₀C₀, C₃ = G₂ + P₂G₁ + P₂P₁G₀ + P₂P₁P₀C₀ – so each carry depends only on the input bits themselves, no longer on a sequentially computed predecessor carry, and can be computed in parallel for all positions with a fixed, small gate delay. Because the number of AND-gate inputs (fan-in) grows with each additional bit position, real lookahead adders are usually built in blocks of 4 bits, with the block carries combined at a second lookahead level to keep the fan-in bounded – a trade-off that explains the logarithmic rather than constant delay, but at the cost of significantly more area and wiring overhead, as seen in many areas of digital circuit design.