Half Adder and Full Adder

Addition as a logic problem

Adding two binary digits produces a sum and a carry. This is a combinational logic function: the inputs are the two operand bits, the outputs are the sum and carry bits. There are two standard building blocks.

Half adder

A half adder adds two single-bit inputs a and b, producing a sum bit s and a carry-out bit c. It does not accept a carry-in from a previous column.

a	b	s (sum)	c (carry)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

From the truth table:

$s = a \oplus b$

$c = a \cdot b$

The sum is the XOR of the inputs; the carry is their AND. The gate-level implementation requires one XOR gate and one AND gate.

Full adder

A full adder adds three bits: two operand bits a and b, plus a carry-in cin from the previous (less significant) column. It produces a sum s and carry-out cout.

a	b	cin	s	cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

The sum is the XOR of all three inputs:

$s = a \oplus b \oplus cin$

since XOR is associative. The carry-out is a majority function: it is 1 when at least two of the three inputs are 1.

$cout = a \cdot b + a \cdot cin + b \cdot cin$

An equivalent and more hardware-efficient expression:

$cout = a \cdot b + (a \oplus b) \cdot cin$

This formulation is useful because a ⊕ b is already computed for the sum, so only one additional AND and one OR are needed.

Building a full adder from half adders

A full adder can be constructed from two half adders and an OR gate:

1. First half adder: computes s1 = a ⊕ b and c1 = a · b.
2. Second half adder: takes s1 and cin, computes s = s1 ⊕ cin = a ⊕ b ⊕ cin and c2 = s1 · cin = (a ⊕ b) · cin.
3. OR gate: cout = c1 + c2 = a · b + (a ⊕ b) · cin.

This decomposition reveals why the expression a · b + (a ⊕ b) · cin is natural: c1 = a · b is the carry generated within this column, and c2 = (a ⊕ b) · cin is the carry propagated through from the previous column. These are exactly the generate and propagate signals used in carry lookahead adders.

Gate count

A full adder built from two half adders plus OR requires: 2 XOR, 3 AND, 1 OR (5 gates total, though XOR itself typically requires multiple primitive gates). For an n-bit ripple carry adder, the total gate count is proportional to n, and the worst-case delay is also proportional to n, limited by the carry chain.