So far we have used logic gates to build circuits that select and route signals. This time, let’s combine gates to build a circuit that does addition.
The calculator app on your phone handles a sum like 999,999 + 888,888 in an instant. Yet at its core, that calculator is also nothing more than a combination of the logic gates we have learned.
How do we usually add? Let’s calculate 179 + 287.
11 <-- (carry)
179
+ 287
-----
466
9 + 7 = 16, so write 6 and carry 1.1 + 7 + 8 = 16, so write 6 and carry 1.1 + 1 + 2 = 4.We work one digit at a time from the right, and each digit produces two things:
But computers only know 0 and 1. How do we carry this idea over to a world of 0s and 1s?
Computers write numbers in binary, which uses only the two digits 0 and 1. Each place is worth twice the one before it. Adding works the same way as in decimal. Let’s calculate 310 + 110 in binary.
11 <-- (carry)
11
+ 01
-----
100
The result, 1002, is 4 in decimal. Here too, each place produces a Sum and a Carry.
Let’s start with the simplest case, adding two one-digit binary numbers, and turn it into a circuit. There are four possible cases:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10
In the last case, Sum is 0 and Carry is 1. Looking at the truth table, Sum is 1 only when A and B differ, and Carry is 1 only when A and B are both 1.
| Sum | Carry | ||
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Carry is A ∧ B. Sum is “A or B is 1, but not both”, so it is
(A ∨ B) ∧ ¬(A ∧ B). Turn these expressions into gates and you have a
calculator for adding one-digit binary numbers.
This circuit is called a half adder. From now on, to keep things simple, we will wrap it into a single block labeled HALF ADDER.
A half adder only handles adding two one-digit binary numbers. In real addition, though, we also have to add the carry coming up from the place below. In the next post, let’s build a full adder that solves this.
Using three half adders, build a circuit that adds three one-digit binary numbers A, B, and C. Output the result (0~3) as two bits: the 2s place and the 1s place.