Half Adder and Full Adder

In the last article we saw that binary addition is one column repeated. In this one we build the column. One XOR and one AND make a half adder, which is about the smallest circuit that does arithmetic, and two half adders and an OR gate make a full adder, which is the cell every multi-bit adder is made from. I want to derive both from their truth tables rather than just present them, because the expressions fall out on their own once you are clear about what a carry is.

The half adder

A half adder adds two single bits $A$ and $B$ and produces a sum bit $S$ and a carry $C_{out}$. It is called “half” because it does half the job: it cannot accept a carry from a previous column. That makes it unusable on its own for multi-bit addition, but it is the piece we need first.

There are four input combinations. $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, and $1 + 1 = 2$, which in binary is $10$, so the sum bit is 0 and the carry is 1.

A	B	S	Cout
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

The $S$ column is 1 when exactly one input is 1, which is XOR. The $C_{out}$ column is 1 only when both are 1, which is AND.

$$S = A \oplus B \qquad C_{out} = A \cdot B$$

Two gates (Figure 1). XOR is sometimes described as addition modulo 2, and this is why: it is the sum bit with the carry thrown away. Whenever you see XOR in a circuit there is a fair chance addition is somewhere behind it.

Both outputs are one gate delay from the inputs. It does not get faster than that.

The full adder

The general column has three inputs, $A$, $B$ and a carry-in $C_{in}$. Three bits sum to at most 3, which is $11$ in binary, so the sum and carry always fit in two output bits.

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

Check a few rows: $0 + 1 + 1 = 2 = 10_2$, sum 0 and carry 1. $1 + 1 + 1 = 3 = 11_2$, sum 1 and carry 1.

The sum

Put the $S$ column on a 3-variable map with $C_{in}$ on the rows and $AB$ on the columns:

$$\begin{array}{c|cccc} S & AB=00 & AB=01 & AB=11 & AB=10 \\hline C_{in}=0 & 0 & 1 & 0 & 1 \ C_{in}=1 & 1 & 0 & 1 & 0 \end{array}$$

The 1s form a checkerboard, with no two adjacent, so nothing groups. A checkerboard on a map is the signature of XOR:

$$S = A \oplus B \oplus C_{in}$$

The sum bit is 1 when an odd number of inputs are 1, which is exactly what binary addition requires.

The carry

$$\begin{array}{c|cccc} C_{out} & AB=00 & AB=01 & AB=11 & AB=10 \\hline C_{in}=0 & 0 & 0 & 1 & 0 \ C_{in}=1 & 0 & 1 & 1 & 1 \end{array}$$

Three groups of two: the column $AB = 11$ gives $AB$; the bottom row at $AB = 01$ and $11$ gives $BC_{in}$; the bottom row at $AB = 11$ and $10$ gives $AC_{in}$.

$$C_{out} = AB + BC_{in} + AC_{in}$$

This is the majority function from Module 1: the carry is 1 when at least two of the three inputs are 1. It treats the three inputs completely symmetrically. In the carry-lookahead adder we will deliberately break that symmetry, treating $A$ and $B$ differently from $C_{in}$, to gain speed.

$$S = A \oplus B \oplus C_{in} \qquad C_{out} = AB + BC_{in} + AC_{in}$$

Two ways to build it

Two half adders and an OR

The sum expression suggests using half adders. The first one computes $A \oplus B$ and $AB$. Feed its sum into a second half adder along with $C_{in}$:

• First: $S_1 = A \oplus B$, $C_1 = AB$
• Second: $S = S_1 \oplus C_{in} = A \oplus B \oplus C_{in}$, and $C_2 = S_1 C_{in} = (A \oplus B) C_{in}$
• Carry out: $C_{out} = C_1 + C_2 = AB + (A \oplus B) C_{in}$

Does that match the majority form? Expand $(A \oplus B) C_{in} = A\overline{B}C_{in} + \overline{A}BC_{in}$, so $C_{out} = AB + A\overline{B}C_{in} + \overline{A}BC_{in}$. Both this and $AB + BC_{in} + AC_{in}$ cover exactly the minterms 3, 5, 6 and 7, so they are the same function. Figure 2 shows the circuit.

Gate count: two XOR, two AND, one OR, five gates.

Straight from the equations

Two XORs for the sum, three ANDs and a 3-input OR for the carry: six gates. The half-adder version is one gate smaller and reuses the XOR, so it is the usual choice.

Timing

Path	Gates	Delay
$A$ or $B$ to $S$	XOR, XOR	2
$C_{in}$ to $S$	XOR	1 (the second XOR only)
$A$ or $B$ to $C_{out}$	XOR, AND, OR	3
$C_{in}$ to $C_{out}$	AND, OR	2

In the half-adder implementation, $C_{in}$ enters at the second XOR and at the second AND, so its path to $C_{out}$ is two gates. In the direct implementation the carry is a two-level AND-OR and the $C_{in}$ to $C_{out}$ path is also two gates. It is a common mistake to assume every path through a full adder takes the same time. They do not, and when full adders are chained it is only the $C_{in}$ to $C_{out}$ path that matters, because that is the one that repeats.

Practice Exercise

Problem 1. Verify the full adder truth table row by row from the expressions.

Solution

A	B	Cin	$A \oplus B$	S	$AB$	$BC_{in}$	$AC_{in}$	Cout
0	0	0	0	0	0	0	0	0
0	0	1	0	1	0	0	0	0
0	1	0	1	1	0	0	0	0
0	1	1	1	0	0	1	0	1
1	0	0	1	1	0	0	0	0
1	0	1	1	0	0	0	1	1
1	1	0	0	0	1	0	0	1
1	1	1	0	1	1	1	1	1

All eight rows match.

Problem 2. Show that $C_{out} = AB + C_{in}(A \oplus B)$ is the same function as $AB + BC_{in} + AC_{in}$.

Solution

$AB$ covers minterms 6 and 7. $C_{in}(A \oplus B)$ is 1 when $C_{in} = 1$ and exactly one of $A$, $B$ is 1: minterms 3 and 5. Together, ${3, 5, 6, 7}$. The majority form covers the same four minterms, so the two are equal. The first form needs two ANDs and one OR and reuses the XOR already computed for the sum, which is why the half-adder construction is one gate smaller.

Problem 3. What can a half adder not do, and give an example where using one in place of a full adder gives the wrong answer.

Solution

It has no carry-in. Add $11_2 + 01_2$ (3 + 1). Bit 0: $1 + 1$ gives $S_0 = 0$ and a carry of 1. Bit 1 with a half adder: $1 + 0 = 1$, carry ignored, result $01_2 = 1$. Wrong. With a full adder at bit 1: $1 + 0 + 1$ gives $S_1 = 0$ and carry 1, result $100_2 = 4$. Every position except possibly the least significant needs a full adder.

In the next article we chain $N$ full adders together into the ripple-carry adder, the simplest multi-bit adder, and work out exactly how slow it is.