The not-so-deadly Adder
Let's recall the XOR gate. It has an output that is 1 only if one input or the other is 1, but not both. Another way to think about it is that it's 1 only when there an odd number of inputs are 1's—it's 0 if the inputs are even. That property of XOR means little gate can be used to make a simple adder. If we want to add two inputs, called A and B, we could say the sum of those would be S = A
B.
You bet! By the late 1800s the U.S. census data became too massive to tabulate by hand. So much so that the 1880 census took seven years to complete. But then Herman Hollerith invented his tabulating machine which allowed the 1890 census to be completed in a single year! (Though he used a series of toothed wheels to count because electronic logic gates had yet to be invented.)
We can check if this is true simply by looking at all the possibilities:
- 0+0=0 —good
- 0+1=1 —right
- 1+0=1 —ok
- 1+1=10 —Almost! (Remember that two is written "10" in in binary.)
So XOR works for the right bit but we see that we really need a two wire output to add two inputs. If both inputs were 1, this extra output wire, which we'll call Cout, should also be 1. So we can write Cout = AB (that's A AND B). Below is the design where we keep the XOR for S and add in the AND gate for Cout.
This is called a half adder. Wow, that was pretty easy!
Full Adder
A full adder can take three inputs. Below is a truth table for adding three inputs. You'll notice only the top half of the table could be calculated by the half adder (when the C input is zero).
| A | B | C | Cout S |
|---|---|---|---|
| 0 | 0 | 0 | 0 0 |
| 1 | 0 | 0 | 0 1 |
| 0 | 1 | 0 | 0 1 |
| 1 | 1 | 0 | 1 0 |
| 0 | 0 | 1 | 0 1 |
| 1 | 0 | 1 | 1 0 |
| 0 | 1 | 1 | 1 0 |
| 1 | 1 | 1 | 1 1 |
Below is the somewhat more complicated design for a full adder. Take some time to see what it's doing and you'll get it. Focus on one gate at a time and click on the inputs.
Notice that S is 1 only when there are an odd number of inputs that are 1. So we used two of our handy XORs to that: S = (AB) C.
Now see that Cout is 1 when at least two inputs are 1's. So this design breaks that down into two cases: 1) when one of A or B is 1 and also C is 1; 2) when both A and B are 1. This means Cout = ((AB)C) + (AB).
That's way too much to draw every time we want to put an adder in our design, so we can draw it thusly:
Phew! Not quite as simple but you made it. Now let's use this bad boy.
Add it all up
What good is a computer that can only add up to three? Back to grade school: How do you go about adding numbers such as 109 and 092? First you add the numbers on the right. So 9+2 gives 1 and we carry 1 into the tens column. So then we have the carried 1 plus 9 + 0 which gives 0, and carry 1 to the hundreds. Then 1 + 1 = 2. So our number is 201!
That was hard work I know, but we'll use that technique for our computer as well. You notice we had an output marked Cout and an input marked Cin. Those will be our carry numbers. Below is a design that will add, not 109 + 092, but A2A1A0 + B2B1B0.
Or the shorthand:
That's it. Now we know how to make an adder. These simple creatures may be small, but they pack a mighty bite--No computer could exist without them.
Next Up: Multiplexers »