Logic gates
Computers are built from logic gates.
Now, you might think that computers are built from transistors. But that’s not strictly true. Most current computers happen to be built from transistors. However, the very first computers were built from electromechanical relays, and after that they were built from thermionic emission valves (AKA vacuum tubes). And today, yes, they’re build from transistors.
People tend to think of computers as being these sophisticated, highly refined black box machines that mortal minds could never possibly comprehend. In fact, there’s no reason why you can’t have purely mechanical computers. You could make a working computer out of lego — but only if you can figure out how to make logic gates out of lego.
Because that’s the thing, see? Computers are made out of logic gates, and logic gates are (currently) made out of transistors (but used to be made of valves or relays). Anything you can make logic gates out of, you can make computers out of.
Types of logic gates
So what are logic gates, then?
Logic gates deal with digital signals. For the sake of explanation, these are signals where every wire is either “on” or “off”; there is no “in-between” state. For brevity, we use the symbol 1 to denote on, and 0 to denote off.
Note that I’m talking about wires and signals; there’s no reason you couldn’t have some sort of steam-powered computer. In such a machine, you’d have steam pipes instead of wires. 1 would mean high pressure in the pipe, and 0 would mean low pressure. And logic gates would work just the same way. But to keep things simple, let’s just stick to electricity.
Abstractly, a logic gate has several input wires going into it, and a single output wire coming out of it. The exact behavior of a logic gate can be described by a truth table, which basically shows every possible combination of inputs and what output the logic gate would produce if you gave it those inputs.
The NOT gate
The simplest possible logic gate is the NOT gate. [No it isn’t. But let’s pretend it is.] The schematic symbol for it looks like this:
It has a single input, and its output is simply the opposite of its input. That is, if the input is on, the output is off, and vice versa. We can write that in a little table like so:
| Input | Output |
|---|---|
| 0 | 1 |
| 1 | 0 |
This is the truth table of a NOT gate.
The AND gate
Another common type of logic gate is the AND gate. Its symbol looks like this:
This type of gate has a minimum of 2 inputs. Suppose we label the inputs X and Y (it doesn’t matter which is which, as you’ll see). The output of the AND gate turns on according to the following rule: The output is on if X is on and Y is on. This is where the name comes from. We can write that as a truth table:
| X input | Y input | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
It’s actually possible to have an AND gate with more than 2 inputs; in that case, the output turns on only if all the inputs are simultaneously on. Arguably the AND gate should have been named the ALL gate… but there we are.
The OR gate
Given what the AND gate does, you probably already have an idea what the OR gate does.
Again, like an AND gate, an OR gate has a minimum of 2 inputs (and no maximum number). It operates according to a simple rule: The output turns on if input X or input Y is on. Hence the name.
| X input | Y input | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
If an OR gate has more than 2 inputs, the general rule is that its output turns on if any input is on. (Again, it might be better if they named it the ANY gate, but still.)
The XOR gate
Actually “the” OR gate I mentioned above is one of two possible OR gates. The one above is the “normal” one; the one people usually mean. To be technical, it is the inclusive OR gate. There is also an exclusive OR gate, often abbreviated as XOR gate.
The inclusive-OR and exclusive-OR gates are nearly identical; the only difference is what they do when both inputs are on at the same time. (I.e., the last row of the truth table.) The inclusive-OR gate includes this state; i.e., the output turns on when both inputs are on. Its rule is: turn on if X is on or Y is on or both. The exclusive-OR gate excludes this state; it turns off if both inputs are on. It’s rule is: turn on if X is on or Y is on but not both.
The symbol for the exclusive-OR gate is very similar to the inclusive-OR gate, but with an extra bar across the inputs:
As explained, the truth table is nearly identical; only the last row is different.
| X input | Y input | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Gate properties
So far we’ve got the NOT gate, AND gate and OR gate. Let’s take a closer look at the properties of these gates.
AND blocking
Take a closer look at the truth table for the AND gate. Notice that if the X input is 0, then the output is always 0.
| X input | Y input | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
If X=0, then Y is basically ignored, and can have no effect on anything. But look: if X=1, then the output is basically equal to Y. So, as well as seeing the AND gate as a thing that takes two inputs, you could also see it as a thing that takes an input signal (the Y input) and passes it along unchanged if the X input is on, and blocks the signal completely if the X input is off.
OR blocking
If you look at it, you can actually do the same trick with an OR gate. Take another look at the truth table:
| X input | Y input | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
If X=0, then output=Y. However, if X=1, then the output is always 1. So if X=0, then Y passes through unchanged, but if X=1 then Y is blocked and we get only 1s.
So an AND gate can block a signal and replace it with 0s, whereas an OR gate can block a signal and replace it with 1s.
Gate duality
In fact, it turns out the AND and OR gates are kind of opposites of each other. The AND gate is usually off, and only turns on if all inputs are on at the same time. Well, if you think about it, an OR gate is usually on, and only turns off if all its inputs are off at the same time.
In fact, if you take an AND gate and invert all of its inputs and outputs, the combined circuit behaves exactly like an OR gate! And if you take an OR gate and invert all its ins and outs, it behaves as an AND gate! So they really are mirror image gates.
XOR flipping
The XOR gate is the most complicated of all the logic gates so far. In fact, it takes several simpler logic gates to build a single XOR gate, as we shall see shortly.
For the moment, let’s just look at the properties of the XOR gate itself.
| X input | Y input | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
One of the first things you might notice is that if both inputs are the same, the output is 0. So if X=Y=0, we get 0, but also if X=Y=1 we get 0. But if the inputs are different, we get 1. So the XOR can be used as a kind of “compare signals” gate.
We can also do the trick we did earlier of fixing one input and looking at how the output is related to the non-fixed input. Looking at the truth table, we see that if X=0 then output=Y. So, similar to a normal OR gate. But now look what happens if X=1; in that case, the output is the opposite of Y! In other words, Y gets inverted.
So the XOR gate can invert or not invert one signal based on the other input. That’s interesting.
Building an XOR gate
Suppose we want to build an XOR gate. We can do that using the other, simpler gates we’ve met so far. Let’s start with a normal inclusive-OR gate, since that does nearly the exact thing we want:
We want to do something different if both inputs are on at the same time. To detect that state, we can add an AND gate, taking the same inputs as our OR gate:
Now, we want to allow the output of the OR gate through unchanged if both inputs are not on, so we want the opposite of the AND gate’s output:
Finally, we can use the 0-blocking behavior of an AND gate as the final stage:
Most of the time, both inputs aren’t on simultaneously, so the bottom AND gate outputs 0, which the NOT gate turns into 1. So, most of the time, the bottom input to the final AND gate is 1, meaning that the output equals the other input — the one from the OR gate. So, most of the time, this circuit just outputs whatever the inclusive OR gate outputs.
However, if both inputs are on simultaneously, then the first AND gate outputs 1, the NOT gate converts that to 0, and the final AND gate therefore outputs 0. This is the behavior we want.
As you can see, an XOR gate is made up of four simpler logic gates. (There are other ways of implementing it, but this is perhaps the easiest one to understand.)
Building a multiplexer
Basic device
Let’s build something else. Suppose we have two signals comming in, and we want to select which one of them to output. Here’s one way to do that:
If both Select-A and Select-B are zero, then each of the AND gates outputs only zeros. However, if Select-A is turned on, then the top AND gate now passes through whatever A is, unchanged. That signal then reaches the OR gate. Since the other signal (from the other AND gate) is zero, the OR gate allows A through to the output. In other words, if Select A=1 and Select B=0, then Out=A.
By a similar chain of reasoning, if Select A=0 and Select B=1, then Out=B.
In this way, the device above allows us to connect either A or B to the output, depending on what we set the two Select signals to be. (Note that if we turn both Select signals off, Out=0, and if we turn both Select signals on, we get A OR B as the output — in other words, the output will be garbled.)
This device is called a multiplexer. There are various types that can be built. The above is a “2 to 1 multiplexer”, because 2 signals go in (A and B) but only 1 comes out. You can also build a multiplexer with more than 2 inputs, and also multiplexers that produce multiple outputs.
Fewer control inputs
Notice that since there are only 2 inputs, and a signal has one of two possible states (on or off), we could actually change our design to have only a single Select input, under the convention that Select=0 outputs A, while Select=1 outputs B. To do that, we can just connect Select to what used to be Select-B, and connect Select through a NOT gate to Select-A:
Now we only have one Select wire, and it’s impossible to select neither or select both. The output is always equal to one or other of the inputs.
Since it crops up a lot, the multiplexer has its own symbol too:
Bigger multiplexers
By cascading several 2-to-1 multiplexers, we can build a 4-to-1 multiplexer:
Notice how this now has two Select inputs. The first one selects whether we want A/C or B/D. The second one selects whether we want A/B or C/D. We can build a truth table explaining what this does:
| Select 1 | Select 2 | Output |
|---|---|---|
| 0 | 0 | A |
| 1 | 0 | B |
| 0 | 1 | C |
| 1 | 1 | D |
We can also use multiple multiplexers to multiplex signals that take several wires:
In this scheme, the 3 outputs are either connected to the 3 A-inputs (if Select=0) or the 3 B-inputs (if Select=1).