Adders and Subtractors

Adders are the core combinational blocks of arithmetic. A half adder adds two bits; a full adder adds three bits (two operands and a carry-in). Chaining full adders yields a ripple-carry adder (RCA); carry-lookahead (CLA) computes the carries in parallel to cut the delay. Two's-complement subtraction is addition of the bitwise complement with carry-in 1, so one circuit with a mode line both adds and subtracts.

GATE asks for gate-level equations, gate and delay counts under a stated gate model, carry-lookahead expressions, and the overflow and carry flags of a result.

Inputs $a,b$; outputs $\textit{sum}=a\oplus b$, $\textit{carry}=ab$. One XOR and one AND.

Inputs $a,b,c_{\mathrm{in}}$; outputs

Equivalently $c_{\mathrm{out}} = ab + (a\oplus b)c_{\mathrm{in}}$ with generate $g=ab$ and propagate $p=a\oplus b$.

$s$ is the odd-parity function and $c_{\mathrm{out}}$ the majority function of the three inputs; the pair $(c_{\mathrm{out}}, s)$ is the 2-bit binary count of 1s among $a, b, c_{\mathrm{in}}$.

Two half adders and an OR. The first half adder gives $p = a \oplus b$ and $g = ab$; the second adds $c_{\mathrm{in}}$: $s = p \oplus c_{\mathrm{in}}$ and carry $p\,c_{\mathrm{in}}$. Then $c_{\mathrm{out}} = g + p\,c_{\mathrm{in}}$. The OR never sees two 1s, because $g = 1$ forces $p = 0$. Totals: 2 XOR, 2 AND, 1 OR. A full adder can also be built from 9 two-input NAND gates (the 4-NAND XOR used twice, with the shared NANDs reused for the carry).

A full subtractor computes $a - b - b_{\mathrm{in}}$: difference $D = a \oplus b \oplus b_{\mathrm{in}}$ (the same as the sum) and borrow out

The borrow is the full-adder carry with $a$ complemented. The half subtractor is $D = a \oplus b$, $b_{\mathrm{out}} = a'b$.

$n$ full adders; $c_0=0$ for addition; the carry out of stage $i$ is the carry into stage $i + 1$. Worst-case delay grows as $\Theta(n)$ because the carry must pass through every stage: adding $0111\cdots1 + 0000\cdots1$ propagates a carry from bit 0 to bit $n - 1$.

Define $g_i = a_i b_i$, $p_i = a_i \oplus b_i$ (XOR form). Then $c_{i+1} = g_i + p_i c_i$. Unrolling for a 4-bit block:

Every carry is a two-level AND-OR of the $g_i$, $p_i$ and $c_0$, so all four are available at the same time. The cost is fan-in: $c_4$ needs a 5-input AND and a 5-input OR. For a 4-bit block the lookahead unit uses $1 + 2 + 3 + 4 = 10$ AND gates and 4 OR gates.

Group generate and propagate. A 4-bit block also outputs

so that $c_4 = G + P c_0$. $G = 1$ means the block creates a carry by itself; $P = 1$ means it passes an incoming carry through. A second-level lookahead unit combines block $(G, P)$ pairs with the same equations, giving $O(\log n)$ delay for $n$ bits.

Two's-complement subtract $A-B$: feed $\overline{B}$ to the adder and set $c_0=1$. With a mode line $M$ (0 add, 1 subtract), each adder input is $b_i \oplus M$ and $c_0 = M$. The signed overflow flag is $V = c_n \oplus c_{n-1}$; the carry flag is $c_n$, and in subtraction $c_n = 0$ signals an unsigned borrow ($A < B$).

Gate-delay convention used in this note. Every two-input or multi-input AND, OR and XOR gate costs 1 unit; inputs $a_i, b_i, c_0$ arrive at time 0. Other delay models are also used (for example 2 units per carry stage); always rebuild the count from the model in the stem.

Ripple-carry. $p_i$ and $g_i$ are ready at 1. Stage $i$ computes $c_{i+1} = g_i + p_i c_i$ with an AND then an OR, so the carry advances 2 units per stage after the first: $c_1$ at 3, $c_2$ at 5, and in general

with $s_0$ at 2. For $n = 4$: $s_3$ at 8 and $c_4$ at 9. For $n = 16$: $s_{15}$ at 32 and $c_{16}$ at 33.

Carry-lookahead, 4 bits. $g_i, p_i$ at 1, every carry $c_1$ to $c_4$ at 3 (one AND level, one OR level), every sum at 4. The delay does not grow with the bit position inside the block.

16 bits from four 4-bit CLA blocks, carries rippling between blocks. Inside each block $G$ is ready at 3 and $P$ at 2. The block carry-outs are $c_4$ at 4, $c_8$ at 6, $c_{12}$ at 8 and $c_{16}$ at 10 (2 units per block). The last block computes $c_{15}$ from $c_{12}$ at 10, so $s_{15}$ is ready at 11. Compare 32 for the 16-bit ripple adder.

For signed two's complement, overflow $= c_n \oplus c_{n-1}$ (carry into sign XOR carry out of sign), as in Signed Number Representation.

Arrays are 0-indexed from the LSB; <- is assignment.

RIPPLE-ADD uses $n$ full adders and $\Theta(n)$ delay. A one-level CLA over $n$ bits uses $\Theta(n^2)$ AND gates of fan-in up to $n + 1$ for constant delay; a tree of 4-bit lookahead units uses $\Theta(n)$ gates and $\Theta(\log n)$ delay.

Unrolling $c_{i+1}=g_i + p_i c_i$ gives

with the convention $g_{-1} = c_0$. In words: there is a carry into position $k$ exactly when some position $j < k$ generates one and every position between $j$ and $k$ propagates it.

Propagate variants. Some texts use $p_i = a_i + b_i$ (OR) for the carry chain. The carry equation still holds, because the two definitions differ only when $a_i = b_i = 1$, and then $g_i = 1$ already. The sum, however, needs the XOR form: $s_i = (a_i \oplus b_i) \oplus c_i$, not $(a_i + b_i) \oplus c_i$.

Subtraction correctness. $A + \overline{B} + 1 = A + (2^n - 1 - B) + 1 = A - B + 2^n$, which is $A - B$ modulo $2^n$. The extra $2^n$ is the carry out: it is 1 exactly when $A \ge B$ as unsigned numbers.

Array multiplier sizing. A combinational multiplier for a $J$-bit multiplier and $K$-bit multiplicand forms $J \cdot K$ partial-product bits with AND gates and adds them with $J - 1$ adders of $K$ bits each, producing a $J + K$-bit product. For $K=4$ multiplicand bits and $J=3$ multiplier bits: 12 AND gates, two 4-bit adders, a 7-bit product ($15 \cdot 7 = 105 < 128$).

For $a=1,b=1,c_{\mathrm{in}}=1$: $s=1$, $c_{\mathrm{out}}=1$ (total 3).

From the LSB: bit 0 gives $s_0 = 1$, carry 0; bit 1 gives $s_1 = 1$, carry 0; bit 2 gives $s_2 = 0$, carry 1; bit 3 gives $s_3 = 1$, carry 0. The pattern is $1011$, which is 11 unsigned and correct; as signed 4-bit it is $-5$, and $V = c_4 \oplus c_3 = 0 \oplus 1 = 1$ flags the overflow of $5+6$.

For $A = 1011$, $B = 0110$, $c_0 = 0$: $g = A \wedge B = 0010$ and $p = A \oplus B = 1101$ (bit 3 on the left). Then $c_1 = g_0 = 0$; $c_2 = g_1 + p_1 g_0 = 1$; $c_3 = g_2 + p_2 g_1 + \cdots = 0 + 1\cdot 1 = 1$; $c_4 = g_3 + p_3 g_2 + p_3 p_2 g_1 + \cdots = 0 + 0 + 1\cdot 1\cdot 1 = 1$. Sums $s_i = p_i \oplus c_i$ give $0001$ with $c_4 = 1$: $11 + 6 = 17 = 1\,0001_2$. Group signals: $P = p_3p_2p_1p_0 = 0$ and $G = 1$.

With the 1-unit gate model above, a 16-bit RCA needs 33 units for $c_{16}$ and 32 for $s_{15}$. Four 4-bit CLA blocks with rippling block carries give $s_{15}$ at 11. A single 16-bit two-level lookahead would be faster still (all carries at 3) but needs a 17-input AND and OR for $c_{16}$, which is why hierarchical lookahead is used. Answers claiming "CLA is always two gate delays for any $n$" ignore fan-in.

Add 4-bit BCD digits as binary. If the sum exceeds 9 or the 4-bit addition carries out, add $0110$ and produce a decimal carry. Example: $0110+0101=1011$ (11); adding $0110$ gives $1\,0001$: digit 1 with a decimal carry, that is $0001\,0001_{\text{BCD}} = 11$. Details are in the Binary Codes note.

Common misconceptions.