Before continuing, be sure you've read my previous article at How Computers “Think” – Binary Numbers. You will need to understand the concept of Binary Numbers to fully understand this article.
We know that computers "think" in terms of 1's and 0's, but how do they take all the 1's and 0's and do anything useful with them? The answer: logic gates. A logic gate is a device that takes one or two electrical signals called inputs, does something with those signals based on whether or not they are high or low voltage, and produces a high or low voltage result called an output. By the way, when it comes to electronics, logic gates are really, really small. The processors in modern day computers contain millions of them! So why are they called logic gates and what exactly do these logic gates do?
Back in 1854, a mathematician named George Boole wrote a book called An Investigation of the Laws of Thought, in which he described a form of mathematics that came to be known as Boolean algebra. In his book, he essentially used math to describe the basis of logical thought, expressing logic as a set of conditions and results with only two possible values: true and false, or 1 and 0 respectively. For the purposes of this discussion, we aren't going to start delving into a bunch of deep mathematical theories, but we will need to discuss a few very basic assertions about Boolean algebra. Afterward, we will see how these assertions are used by logic gates in computer processors.
The AND assertion states that, given two conditions, a desired outcome may be true if and only if both conditions are also true. The AND Logic Gate works the same way. It takes two input voltages and produces an output voltage. The output voltage is high if and only if the first input is high AND the second input is high.
To illustrate, I've created a demonstration applet below showing two light switches and a light bulb wired to an AND Logic Gate, representing the two inputs and an output respectively. If we assign a value of 1 for the state of a switch or bulb that is "on", and a value of 0 otherwise, then we can use the demonstration applet to create something the mathematicians call a Truth Table showing the four possible combinations of inputs and the resulting outputs. As can be seen from the Truth Table, the only output resulting in a value of 1 occurs when both inputs are also 1.
The OR assertion states that, given two conditions, a desired outcome may be true if either condition is also true.
As before, the OR Logic Gate works the same way. It takes two input voltages and produces an output voltage. But in this case, the output voltage is high if the first input is high OR the second input is high. Below is another demonstration applet to illustrate, with an accompanying truth table. As we can see, the light can be turned on by flipping either or both switches into the "on" position:
The XOR assertion (meaning Exclusive OR) states that, given two conditions, a desired outcome may be true if and only if both conditions are mutually exclusive (i.e., they are different from each other).
Again, the XOR Logic Gate works in the same manner as the previous two logic gates. It takes two input voltages and produces an output voltage. But in this case, the output voltage is high only if the first input is different from the second input. Below is another demonstration applet to illustrate, with an accompanying truth table. As we can see, the light can be turned on only when one of the two switches is "on" and the other is "off".
Now that we've discussed some basic logic gates, we can talk about doing something useful with them - like adding numbers together. Remember that computers can only think in terms of binary numbers, like 11012 (= 1310) and 01112 (= 710). Think for a second about how we add base 10 numbers together:
Base 10 Addition of 13 and 7 carry --> 1 13 + 07 20 Base 2 Addition of 13 and 7 carry --> 111 1101 (1310) + 0111 (710) 10100
We start with the right-most column of two digits and add them. If the result is greater then 10, then we write down the result of the ones place as our "sum" value, "carry" the extra ten to the next column to the left, and repeat the addition process for the next column to the left until we run out of columns to add.
Computers add numbers using the exact same process, only the numbers are in base 2. Adding binary numbers may look a bit foreign, but makes sense if you remember that 0 and 1 are the only numbers the computer can use. Looking at the right-most column, we are adding 1 + 1. The result of course is 2, which is 102. So, we write down the 0 as our "sum" value and "carry" the 1 to the next column to the left.
Now what if we just examine a single column of two digits to add together? In that respect, we have just two inputs, an output that is our "sum" value for the column and an output that is a "carry" value. Let's look more closely at the four possible combinations of inputs and outputs and compare them to the outputs of the XOR Logic Gate and the AND Logic Gate.
|A||B||A + B||A AND B||A XOR B|
Looking at the results of addition, we can immediately see that the XOR Logic Gate output exactly matches our "sum" value (right-most digit of A + B), while the AND Logic Gate output exactly matches our "carry" value (left-most digit of A + B)! If we combine the two into a circuit, we have what is called a "single-bit adder circuit"...well...almost.
In reality, adding just two bits together isn't very useful. But if we could chain together several single-bit adders so that the "carry" output of one adder provides an additional input to another adder, then we could add together larger binary numbers. Doing so would require our adder circuit to actually have three inputs (A + B + Cin) and two outputs (S + Cout).
As you can imagine though, trying to figure out what combination of logic gates are needed for even this simple task can become very complex, very quickly. I won't go further into the technical details of how to build a full adder, or why it works, beyond giving you the formulas and an image of the circuit diagram for you to explore.
Cout = ((A XOR B) AND Cin) OR (A AND B) S = (A XOR B) XOR C
Here is an example applet combining a series of four 1-bit adders of this nature by tying the "Carryout" output of one adder to the "Carryin" input of the next adder to form a complete 4-bit adder:
Computers can do some amazingly complex things. But at the root of it all, a computer processor is nothing more than a collection of logic gates wired together in a particular way to process binary numbers. If you would like to explore computer engineering and digital circuit design further, I would highly recommend the following books:
- Make: Electronics (Learning by Discovery)
- Make: More Electronics: Journey Deep Into the World of Logic Chips, Amplifiers, Sensors, and Randomicity
Both books are written by Charles Platt, and provide a fun and interesting beginner's guide to electronics and circuit design.