Switches and gates

A computer is made of switches. The one in your pocket has billions of them, each either on or off, each flipping millions of times a second. This page starts with one switch you click yourself, and builds up to the logic gates that every part of a computer is made from: switches that work other switches, then switches with no moving parts, then the handful of ways of wiring them that everything else is built on.

The diagrams use one colour code throughout: an orange wire is connected to the battery’s + side (the supply), a grey one isn’t, and a dashed one is connected to nothing at all. Everything you can click has a pointer cursor, and works from the keyboard too (Tab, then Space).

1 · A switch is a bit

A battery pushes current round a loop of wire. Put a lamp in the loop and it lights; put a switch in the loop and it lights only while the switch is closed. That’s already a useful idea: the switch is either open or closed, the lamp either off or on. Call those 0 and 1. A thing that can only be one of two values is a bit (binary digit), and every number, letter, picture and sound a computer handles is made of them.

With two switches, it matters how they’re wired. One after the other (in series), current has to get through both. Side by side (in parallel), it can take either path.

Click the switches A and B (closed is 1). In series, the lamp lights only when A and B are both closed; side by side, it lights when A or B (or both) is closed. Each table fills in as you try its combinations: a truth table, the list of what a circuit does for every combination of its inputs. Two inputs have 4 combinations; three would have 8, and each extra input doubles it.

Those two circuits are AND and OR, the same words you’d use: “the lamp lights if A and B are closed”. In 1854 George Boole worked out an algebra for true and false, with AND, OR and NOT as its operations, as a mathematics of logic. In 1937 a 21-year-old student, Claude Shannon, showed in his master’s thesis that circuits of switches do Boole’s algebra, and so any logical statement can be built as a circuit. (The same Shannon later founded information theory: see the Shannon limit on the signal-processing site.)

2 · Switches that work switches

There’s a problem. A computer has to make decisions in long chains, the result of one step deciding the next, and the switches above need a hand to work them. We need a switch that can be flipped by electricity, so one circuit’s output can work the next circuit’s switch.

The first such switch was the relay, invented in the 1830s for the telegraph, to pass a weak signal on down the next stretch of line. Current through a coil of wire makes it a magnet, which pulls a springy metal contact across; with the current gone, the spring pulls it back. A changeover contact has two sides: the normally closed one, connected while the coil is off, and the normally open one, connected while it’s on.

The relay figures below click as their contacts move, as real ones do. If you’d rather they didn’t, untick Sound before you start.

Click the switch S to energise the coil. The normally open contact gives the same as S: its lamp lights when S is closed. The normally closed contact gives the opposite: its lamp lights when S is open. That’s NOT, the third of Boole’s operations. Slow it down to watch the contact leave one side before it reaches the other.

And now one relay can work the next:

Close S, and each relay pulls in its contact, which energises the next relay’s coil. This page’s relays take 5 ms to pull in and 3 ms to let go (typical of a small modern relay), so the lamp lights 4 × 5 ms = 20 ms after S closes: 2.0 s in the figure, at 100× slower. Open S, and they let go one by one.

Telephone exchanges were built from relays, millions of them, switching calls for most of the twentieth century. In 1941 Konrad Zuse in Berlin finished the Z3, a programmable computer of about 2,600 relays. It worked, but slowly: an addition took most of a second, because every step waited for contacts to move, and every contact wore out eventually.

3 · A switch with no moving parts

The transistor, invented at Bell Labs in 1947, does a relay’s job with nothing that moves. The kind every modern chip is made of is the MOSFET (metal–oxide–semiconductor field-effect transistor, from 1959). How it works inside is a story for physics; here it’s enough to know the rule. A MOSFET has three wires. Two are the ends of its channel, which either conducts or doesn’t, like a switch’s contacts. The third, confusingly also called the gate (it has nothing to do with the logic gates later on), is like the relay’s coil: the voltage on it decides whether the channel conducts.

Voltage is how hard the supply pushes. Here it’s given as a share of the supply: 0% is the − side (ground), 100% is the full + side. There are two kinds of MOSFET, mirror images of each other.

Slide the gate voltage. The n-type conducts when its gate is high (near the supply), lighting the lamp above it; the p-type conducts when its gate is low (near ground). Neither conducts with its gate within 25% of its own side (the threshold), and in between they’re partly on: in this page’s simple model, a transistor conducts in proportion to how far past its threshold the gate is. The channel lights up as it conducts.

A transistor in a chip is far smaller than any relay (parts of a modern one are only a few atoms thick) and switches in trillionths of a second. That’s what made computers small, fast and cheap.

4 · CMOS: the inverter

Pair one of each kind, gates joined, and you get the simplest and most important circuit in a chip. The p-type connects the output to the supply (it pulls up); the n-type connects it to ground (it pulls down). The same input turns one on and the other off, so the output is always the opposite of the input: NOT, called an inverter. This pairing is CMOS (complementary MOS, from 1963), and nearly every chip made today is built from it.

Click the input (or slide it). At 0 the p-type is on and the n-type off, so the output is connected to the supply: 1. At 1 it’s the other way round. Either way, one transistor is always off, so no current flows through from supply to ground: an idle CMOS gate uses almost no power. Current flows only while the input is in between, between 25% and 75% of the supply, when both are partly on; in this model it peaks at 11% of what a fully-on transistor would carry, with the input at 50%. The output flips quickly: it stays above 90% until the input reaches 46%, and is below 10% from 54%.

So a CMOS gate uses energy only when it switches: that brief current, and more than that, the charge it takes to fill and empty the wires and the next gates’ inputs every time a signal changes. That’s why a processor running flat out gets hot, and one waiting for you to type barely gets warm. (In the smallest modern transistors, some current leaks through even when they’re off, so idle isn’t quite free.)

5 · NAND and NOR

Two inputs need two pull-ups and two pull-downs. Arrange the pull-downs one above the other, so the output is pulled down only when both inputs are high, and the pull-ups side by side, so it’s pulled up when either input is low. The output is 0 only when A and B are both 1: that’s NOT AND, called NAND. Swap the arrangements over and you get NOT OR: NOR.

Click the inputs A and B, and pick NAND or NOR. Each transistor’s gate is labelled with the input that drives it. For every combination, exactly one of the two paths is complete, so the output is always connected to either the supply or ground, never both and never neither. Both gates take 4 transistors. (The levels here, and the truth table, are worked out from the transistors alone, by following which wires each conducting channel connects.)

Notice what CMOS gives you for free: an inverted answer. A plain AND has to be a NAND followed by an inverter, 6 transistors instead of 4. So in a chip, NAND and NOR are the natural gates, and AND and OR cost extra.

6 · Gates as symbols

From here on we stop drawing transistors. Each kind of gate gets a symbol, and a diagram of symbols says what a circuit does without saying how it’s built. Besides AND, OR and NOT (and their inverted twins), there’s one more that turns up everywhere: XOR, exclusive or, which is 1 when its inputs differ: one or the other, but not both. A small circle on a symbol’s output means “inverted”.

Six gates sharing the same two inputs. Click A and B: the table shows every gate’s output for every combination, with the current one highlighted. Where a wire crosses another without a dot, they aren’t connected; a dot marks a join.

7 · NAND makes everything (and so does NOR)

Here’s a surprise: you don’t need all of these. NAND alone can make every one of them, and so can NOR alone. Tie a NAND’s two inputs together, and it’s an inverter (NOT A AND A is NOT A). Put an inverter after a NAND and it’s AND. Invert both inputs first and it’s OR. Once you have NOT, AND and OR you can make anything, because any truth table can be written as an OR of ANDs (one AND for each row whose output is 1, of the inputs or their inverses). A gate that can make all the others is called universal.

NOT, AND, OR and XOR, each built from one kind of gate. Pick which, and click the inputs to follow the levels through. From NAND gates they take 1, 2, 3 and 4 gates; from NOR gates, 1, 3, 2 and 5. Each is the fewest possible: the puzzle below finds that by trying every circuit.

Henry Sheffer showed NAND’s universality in 1913 (Charles Sanders Peirce had noticed it in the 1880s, but never published). It’s not just a curiosity. A chip designer can work with a few well-tuned cells, and some famous machines used one gate only: the Apollo Guidance Computer, which flew to the Moon, was built entirely of NOR gates, about 2,800 chips each holding two of them.

Now try it yourself:

Wire up to five gates (G1 to G5) from the drop-downs: each gate’s two inputs can come from A, B or any gate before it, and output picks which gate is the answer. Only the gates the output depends on are drawn. The table compares yours with the target, row by row, and fewest possible is the smallest number of these gates that can do it, found by trying every circuit. Click A and B to follow the levels. Try OR from NANDs (3 gates), then XOR (4), then switch to NOR gates.

8 · How many, how fast

A CMOS NAND gate is 4 transistors. An adder for two 8-bit numbers is a few dozen gates. The 6502, the processor in the Apple II (and, in close variants, the Commodore 64 and the NES), and the one this series builds towards, has about 3,500 transistors. A modern laptop or phone processor has tens of billions.

And every gate takes a little time to switch. A relay takes milliseconds; a gate in a modern chip, a few picoseconds (trillionths of a second): roughly a billion times faster. But the delays still add up. When one gate’s output feeds the next, and that one’s the next, the answer at the end of a long chain arrives last, just as the lamp at the end of the relay chain did. How long the longest chain is decides how fast a processor can run, and it’s the first problem waiting when gates are put to work adding numbers.

Summary

A switch holds a bit: 0 or 1. Two switches in series make AND, in parallel, OR; a truth table lists a circuit’s output for every combination of inputs.
A computer needs switches worked by electricity, so one circuit can drive the next. Relays did it with moving contacts (and their normally closed contact gives NOT); transistors do it with none.
A MOSFET’s gate voltage decides whether its channel conducts: an n-type when the gate is high, a p-type when it’s low.
CMOS pairs them: one pulls the output up, the other down, and one is always off, so an idle gate draws almost no current. The simplest is the inverter; with two inputs, NAND and NOR take 4 transistors, while AND and OR take 6.
NAND alone can make every other gate, and so can NOR: they’re universal.
Every gate takes time to switch, and chains of gates add up: the longest chain sets a processor’s speed.