Proof of two half-adders = a full adder + OR of carry

Question

A half-adder can be used to get the sum and carry of two binary digits. For example:

\begin{align*} sum = ab \\ carry = a \oplus b \\ \end{align*}

And a full-adder is often described as "two half adders combined with an OR gate to combine their carry outputs".

Yet I don't really understand what that means. What would be an example of creating a full-adder from a half-adder in boolean/logical terms?

https://en.wikipedia.org/wiki/Adder_(electronics)#Half_adder

Answer 1

If I give you two 2-bit binary numbers, how do you add them?

We're going to use the normal elementary school algorithm:

• add the digits in the 1's place, possibly carry a 1
• add the digits in the 2's place and add the carried one from before, possibly carry a 1
• add the digits in the 4's place and add the carried one from before, possibly carry a 1
• ... etc.

A half adder essentially does the first step, but for all subsequent we need to add three bits---two digits, $d_1, d_2$, and one carry, $c$.

The way we're going to do that is as follows:

1. add $(d_1 + d_2)$ using a half-adder, and get the sum $s$ (note that this is the ones place, so the $1+1 = 0$ using the half adder).

2. add (s + c) using a half-adder, and get the ones place of that sum. This will be the sum (ie, ones place) of our full adder, as it is the ones place of $d_1+d_2+c$.

3. Now, we have to figure out the carry. It doesn't take too much though to see that we need to carry a 1 iff we need to carry a 1 in the addition $(d_1 + d_2)$ OR in the addition $(s + c)$ (just think about the circumstances in which you carry in the elementary school algorithm). Then, you just OR the outputs of the carrys of the half-adders to get the carry of the sum $d_1+d_2+c$.

There's a nice and pretty gif of a full adder in boolean/logical terms in the link you provided. Anything I could write out here would be far more confusing, and staring at that gif will give you a good idea what's going on.