1 Times Daily: Day 5 - 1 + 1 makes 10

< Day 4 Day 6 >
This post is part of a series I hope to publish regularly called "1 Times Daily." The idea is simple: that almost anyone can learn about computer science. I'm going to try to boil CS down to its core and present that in a way that nearly everyone can understand. I'll do my best to write from a "general audience" perspective, and we'll see if anyone bothers to read!

Day 5: Computers use logic to do arithmetic.

A mathematical formula should never be "owned" by anybody! Mathematics belong to God.

-Donald Knuth

Computers use logic to do arithmetic. Because we've already claimed that computers use yes/no values at their lowest level, and that they use logic to manipulate yes/no values, today's key point should come at no surprise. What I'd like to walk through today is the process of adding numbers using logic, which is precisely what computers must do. You've probably already noticed that this blog post is considerably longer than the previous posts, but that's only because we're taking things step-by-step. Hang in there!

Let's start by developing a simple adding circuit. The circuit takes three bits as input, which are two single-digit binary numbers and one "carry bit" as from a previous column of adding. The circuit then outputs two bits - a sum and a carry bit, which could be used to continue to the next column. Below is the truth table for our adder (yet another chance to brush up on your binary math skills!):

A	B	C	CO	O
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Now we need to develop logic formulae for each of our two output bits. One straightforward approach to developing a formula from a truth table is called the "sum of products." First, we let adding map to an OR operation and multiplying to an AND operation, so that "A OR B" can be written as:

A + B

And "A AND B" written as:

AB

As we'll see, this notation can help us enforce the rules of logic by mapping them to the rules of math. The input and output labels, as in math, are called variables. As another convention, we indicate the "complement" of a variable with an apostrophe ('), pronounced "prime." If we write the formulae for CO and O with these conventions, we get:

CO = A'BC + AB'C + ABC' + ABC

O = A'B'C + A'BC' + AB'C' + ABC

We have basically ANDed together the inputs which create a True output for each bit, and ORed those groups together. We could immediately build a logic circuit from these formulae, but this would require a 27 logic gates! If we can simplify the formulae first, we can implement them with fewer gates. Thanks to our notation, simplifying starts by following the rules of algebra. Let's do some rearranging to set things up:

CO =     A'BC + AB'C + ABC' + ABC =>

CO =     C(A'B + AB') + AB(C' + C) 

All we've done is to "regroup" the logic's AND and OR. At this point, we need some logic-specific rules to advance. First, look at the (C' + C) part of the expression. This expression means "C OR NOT C". If a gate should output True under C and NOT C, then it should output True all the time! So we can replace the expression with True:

CO =     C(A'B + AB') + AB(True) 

But the True also doesn't affect the AB expression, either, as ANDing with True has no effect. So we can further reduce the expression by dropping the True:

CO =     C(A'B + AB') + AB

Now we'd like to reduce the left-hand expression. To do this, we need to notice that the expression A'B + AB' looks like a special logic gate that we discussed in the previous post. Remember this?

A	B	A XOR B
F	F	F
F	T	T
T	F	T
T	T	F

The XOR gate is true in the same two cases that we need in our expression. So we can reduce CO to:

CO =     C(A XOR B) + AB

We can't reduce the CO expression any further, so it's time to move on to the main output bit, O. We'll start just as we did with the CO bit, by rearranging with some grouping:

O =    A'B'C + A'BC' + AB'C' + ABC =>

O =    C(A'B' + AB) + C'(A'B + AB')

The right-hand expression once again contains an XOR-like component, allowing us to reduce as follows:

O =    C(A'B' + AB) + C'(A XOR B)

The left-hand expression is a little more difficult to see immediately, but we can notice that its truth values are the exact OPPOSITE of an XOR gate. We could write this as A XNOR B (indicating the use of a special gate with inverted XOR output), but for our purposes here, let's use XOR then invert the output separately, as follows:

O =    C(A XOR B)' + C'(A XOR B)

From this form, we can actually perform one more major reduction. This reduction is much easier to see if we treat the expression A XOR B as a single expression. Say F = A XOR B, then we can write our expression as:

O =    CF' + C'F

Now we can see much easier that C and F are being XORed as well! So we have:

O =    C XOR F

And we can substitute back in for F to get:

O =    C XOR (A XOR B)

So our output bits have been reduced to:

O =    C XOR (A XOR B)

CO = C(A XOR B) + AB

Amazingly, we now only need 5 gates to implement our adder instead of the original 27! Here's the logic diagram of the full adder, from Wikipedia. The structure follows our formulae exactly (with some different variable names):

If we consider our one-bit adder as a single component, we can chain together these adders in what's referred to as a "ripple carry adder", which can add as many bits as we want. Here's a 4-bit ripple carry adder:

As you can tell, the Wikipedia page on Adders is quite good. You can go there for much more information on how adders are commonly implemented in much faster ways. But for our purposes in this series, I've hopefully convinced you that computers can do mathematics with logic gates. From this point forward, I won't waste any more time drilling lower into the computer, but you can look into the ways that computers represent negative numbers, multiply numbers, and do many other things. I'll focus on getting back up to cool things like programming.