Chapter Fourteen

Adding with Logic Gates

Addition is the most basic of arithmetic operations, so if we want to build a computer (and that is my not-so-hidden agenda in this book), we must first know how to build something that adds two numbers together. When you come right down to it, addition is just about the only thing that computers do. If we can build something that adds, we’re well on our way to building something that uses addition to also subtract, multiply, divide, calculate mortgage payments, guide rockets to Mars, play chess, and use social media to share our latest dance moves, kitchen feats, or pet antics.

The adding machine that we’ll build in this chapter will be big, clunky, slow, and noisy, at least compared to the calculators and computers of modern life. What’s most interesting is that we’re going to build this adding machine entirely out of simple electrical devices that we’ve learned about in previous chapters—switches, lightbulbs, wires, a battery, and relays that have been prewired into various logic gates. These components were all available prior to the 20th century. And what’s really nice is that we don’t have to actually build anything in our living rooms; instead, we can build this adding machine on paper and in our minds.

This adding machine will work entirely with binary numbers and will lack some modern amenities. You won’t be able to use a keyboard to type in the numbers you want to add; instead you’ll use a row of switches. Rather than a numeric display to show the results, this adding machine will have a row of lightbulbs.

But this machine will definitely add two numbers together, and it will do so in a way that’s very much like the way that computers add numbers.

Adding binary numbers is a lot like adding decimal numbers. When you want to add two decimal numbers such as 245 and 673, you break the problem into simpler steps. Each step requires only that you add a pair of decimal digits. In this example, you begin with 5 plus 3. The problem goes a lot faster if you memorized an addition table sometime during your life.

The big advantage of binary numbers over decimal is the simplicity of the addition table:

If you actually grew up with a community of dolphins and memorized this table in dolphin school, you might have squeaked and whistled aloud:

0 plus 0 equals 0.

0 plus 1 equals 1.

1 plus 0 equals 1.

1 plus 1 equals 0, carry the 1.

You can rewrite the addition table with leading zeros so that each result is a 2-bit value:

Viewed like this, adding a pair of binary numbers results in two bits, which are called the sum bit and the carry bit (as in “1 plus 1 equals 0, carry the 1”). Now we can divide the binary addition table into two tables, the first one for the sum bit:

And the second one for the carry bit:

It’s convenient to look at binary addition in this way because our adding machine will do sums and carries separately. Building a binary adding machine requires that we design a circuit that performs these operations. Working solely in binary simplifies the problem immensely because all the parts of a circuit—switches, lightbulbs, and wires—can be binary digits.

As in decimal addition, we add two binary numbers column by column, beginning with the least significant bit in the rightmost column:

Notice that when we add the third column from the right, a 1 is carried over to the next column. This happens again in the sixth, seventh, and eighth columns from the right.

What size binary numbers do we want to add? Since we’re building our adding machine only in our minds, we could build one to add very long numbers. But let’s be reasonable and decide to add binary numbers up to 8 bits long, or 1 byte. That is, we want to add binary numbers that can range from 00000000 to 11111111. Those values range from hexadecimal 00h to FFh, or decimal 0 to 255. The sum of two 8-bit numbers can be as high as 510 in decimal, or 1FEh in hexadecimal, or 111111110 in binary.

The control panel for our binary adding machine can look like this:

This panel has two rows of eight switches. This collection of switches is the input device, and we’ll use it to “key in” the two 8-bit numbers. In this input device, a switch is off (down) for 0 and on (up) for 1, just like the wall switches in your home. As usual, the least significant bit is on the right, and the most significant bit is on the left. The output device at the bottom is a row of nine lightbulbs. These bulbs will indicate the answer. An unlit bulb is a 0, and a lit bulb is a 1. Nine bulbs are needed because the sum of the two 8-bit numbers can be a 9-bit number. That bulb on the far left will light up only if the sum is greater than decimal 255.

The rest of the adding machine will consist of logic gates wired together in various ways. The switches will trigger the relays in the logic gates, which will then turn on the correct lights. For example, if we want to add 01100101 and 10110110 (the two numbers shown in the preceding example), we throw the appropriate switches as shown here:

The bulbs light up to indicate the answer of 100011011. (Well, let’s hope so, anyway. We haven’t built it yet!)

I mentioned in a previous chapter that I’ll be using lots of relays in this book. The 8-bit adding machine we’re building in this chapter requires no fewer than 144 relays—18 for each of the eight pairs of bits we’re adding together. If I showed you the completed circuit in its entirety, you’d definitely freak. There’s no way that anyone could make sense of 144 relays wired together in strange ways. Instead, I’ll approach this problem in simpler incremental steps.

Maybe you saw right away a connection between logic gates and binary addition when you looked at the table of the carry bit that results from adding two 1-bit numbers together:

You might have realized that this was identical to the logical operation known as AND, and the output of an AND gate shown in Chapter 8:

Or like this if the two inputs are labeled:

Rather than draw a bunch of relays, electrical engineers symbolize an AND gate like this:

The inputs at the left are labeled A and B for the two bits being added. The AND gate output at the right is the carry bit for the addition of these two binary digits.

Aha! We’re definitely making progress. A somewhat more difficult task is persuading some relays to behave like this:

This is the other half of the problem in adding a pair of binary digits. The sum bit turns out to be not quite as straightforward as the carry bit, but we’ll get there.

The first thing to realize is that the OR logical operation is close to what we want except for the case in the lower-right corner:

You might recall from Chapter 8 that the OR gate is symbolized like this:

Also similar to what we want is the NAND (or Not AND) logical operation, which has an output the opposite of the AND gate. This is the same as the sum of two one-bit numbers except for the case in the upper-left corner:

Here’s how the NAND gate is represented:

It’s the same as an AND gate except with a little circle on the right symbolizing that the output is the opposite of the AND.

Let’s connect both an OR gate and a NAND gate to the same inputs. As usual, the small dots show where wires are connected; otherwise, they just overlap:

The following table summarizes the outputs of these OR and NAND gates and compares that to what we want for the adding machine:

Notice that what we want is 1 only if the output from the OR gate and the NAND gate are both 1. This suggests that these two outputs can be an input to an AND gate:

Notice that there are still only two inputs and one output in this entire circuit. The two inputs go into both the OR gate and the NAND gate. The outputs from the OR and NAND gates go into the AND gate, and that gives us exactly what we want:

There’s actually a name for what this circuit does. It’s called the Exclusive OR gate or, more briefly, the XOR gate. Some people pronounce it “eks or” and others spell it out: X O R. It’s called the Exclusive OR gate because the output is 1 if the A input is 1 or the B input is 1, but not both. So instead of drawing an OR gate, a NAND gate, and an AND gate as shown earlier, we can use the symbol that electrical engineers use for the XOR gate:

It looks very much like the OR gate except that it has another curved line at the input side. The behavior of the XOR gate is shown here:

The XOR gate is the final logic gate I’ll describe in detail in this book. (Yet another gate sometimes shows up in electrical engineering. It’s called the coincidence gate or equivalence gate because the output is 1 only if the two inputs are the same. The coincidence gate has an output opposite the XOR gate, so its symbol is the same as that of the XOR gate but with a little circle at the output end.)

Let’s review what we know so far. Adding two binary numbers produces a sum bit and a carry bit:

You can use the following two logic gates to get these results:

The sum of two binary numbers is given by the output of an XOR gate, and the carry bit is given by the output of an AND gate. So we can combine an AND gate and an XOR gate to add two binary digits called A and B:

Keep in mind that this is more complex than it looks! The XOR gate is actually a combination of an OR gate, a NAND gate, and an AND gate, and each of those gates consists of two relays. But it becomes easier to understand if a lot of the details are hidden. This process is sometimes called encapsulation: A complex assemblage of stuff is hidden away in a simpler package. At any time we can unwrap that package if we want to see all the details, but it’s not necessary.

Here’s another encapsulation: Instead of drawing and redrawing an AND gate and an XOR gate, you can simply represent the entire circuit with a box like this, called a half adder:

The S and CO labels stand for Sum and Carry Out. Sometimes a box like this is called a black box. A particular combination of inputs results in particular outputs, but the implementation is hidden. But since we know what goes on inside the half adder, it’s more correctly termed a clear box.

This box is labeled Half Adder for a reason. Certainly it adds two binary digits and gives you a sum bit and a carry bit. But for binary numbers greater than 1 bit, the half adder is inadequate for anything except adding the two least significant bits. It fails to add in a possible carry bit from a previous 1-bit addition. For example, suppose we’re adding two binary numbers like these:

We can use the half adder only for the addition of the rightmost column: 1 plus 1 equals 0, carry the 1. For the second column from the right, we really need to add three binary numbers because of the carry. And that goes for all subsequent columns. Each subsequent addition of two binary numbers must include the carry bit from the previous column.

To add three binary numbers, we need two half adders and an OR gate, wired this way:

It might not be quite clear why this works. Begin with the A and B inputs to the first half adder at the left. The output is a sum and a carry. That sum must be added to the carry from the previous column, called a Carry In. That Carry In and the Sum from the first half adder are inputs to the second half adder. The sum from the second half adder is the final sum. The two Carry Outs from the half adders are inputs to an OR gate. You might think another half adder is called for here, and that would certainly work. But if you go through all the possibilities, you’ll find that the Carry Outs from the two half adders are never both equal to 1. The OR gate is sufficient for adding them because the OR gate is the same as the XOR gate if the inputs are never both 1.

Instead of drawing and redrawing that diagram, we can just call it a full adder:

The following table summarizes all the possible combinations of inputs to the full adder and the resultant outputs:

I said early on in this chapter that we would need 144 relays for our binary adder. Here’s how I figured that out: Each AND, OR, and NAND gate requires two relays. So an XOR gate comprises six relays. A half adder is an XOR gate and an AND gate, so a half adder requires eight relays. Each full adder is two half adders and an OR gate, or 18 relays. We need eight full adders for our 8-bit adding machine. That’s 144 relays.

Recall our original control panel with the switches and lightbulbs:

We can now start wiring these switches and lightbulbs to eight full adders.

Start with the least significant bit: First connect the two rightmost switches and the rightmost lightbulb to a full adder:

When you begin adding two binary numbers, the first rightmost column of digits that you add is different. It’s different because every subsequent column might include a carry bit from the previous column. The first column doesn’t include a carry bit, which is why the carry input to the full adder is connected to ground. That means a 0 bit. The addition of the first pair of binary digits could, of course, result in a carry bit. That carry output is an input to the next column.

For the next two digits and the next lightbulb, you use a full adder wired this way:

The carry output from the first full adder is an input to this second full adder. Each subsequent column of digits is wired the same way. Each carry output from one column is a carry input to the next column.

Finally the eighth and last pair of switches (those at the far left of the control panel) are wired to the last full adder:

Here the final carry output goes to the ninth lightbulb.

We’re done.

Here’s another way to look at this assemblage of eight full adders, with each Carry Out serving as input to the next Carry In:

The order of these full adders is the same as the order of the switches and lightbulbs on the control panel: The least significant bit is on the right, and the most significant bit is on the left, just as numbers are normally written. Notice how each Carry Out circles around to become the Carry In for the next significant bit. The first Carry In is set to ground (to mean a 0 bit), while the final Carry Out lights up a ninth bulb.

Here’s the complete 8-bit adder encapsulated in one box. The inputs are labeled A₀ through A₇ and B₀ through B₇. The outputs are labeled S₀ through S₇ (for sum):

This is a common way to label the separate bits of a multibit number. The bits A₀, B₀, and S₀ are the least significant, or rightmost, bits. The bits A₇, B₇, and S₇ are the most significant, or leftmost, bits. For example, here’s how these subscripted letters would apply to the binary number 01101001:

The subscripts start at 0 and get higher for more significant digits because they correspond to the exponents of powers of two:

If you multiply each power of two by the digit below it and add them all up, you’ll get the decimal equivalent of 01101001, which is 64 + 32 + 8 + 1, or 105.

Another way an 8-bit adder might be drawn is like this:

The double-line arrows have an 8 inside to indicate that each represents a group of eight separate signals. These are 1-byte data paths. They are also labeled A₇ ...A₀, B₇ ...B₀, and S₇ ...S₀ to indicate 8-bit numbers.

Once you build one 8-bit adder, you can build another. It then becomes easy to cascade them to add two 16-bit numbers:

The two 16-bit input values are separated into two bytes, called low byte and high byte. The Carry Out of the adder on the right is connected to the Carry In of the adder on the left. The adder on the left has as input the most significant eight digits of the two numbers to be added and creates as output the most significant eight digits of the result.

And now you might ask, “Is this really the way that computers add numbers together?”

Excellent question!