One Gate

A transistor has three connections. They are the source, the drain and the gate. Electrons can move from the source to the drain. The gate controls this movement.

The gate does not touch the silicon. A very thin layer of glass is between them. Glass is an insulator. Thus, no current flows into the gate.

When you put a voltage on the gate, the gate makes an electric field. The field goes through the glass. It pulls electrons up below the glass. These electrons make a path between the source and the drain. This path is the channel. Now the switch is closed.

When you remove the voltage, the electrons move away. The channel disappears. The switch is open.

A chip uses two types of transistor:

The two types work as a pair. Engineers call this CMOS (complementary metal-oxide-semiconductor).

NAND means "not AND". The output is 0 only when A is 1 and B is 1. For all other inputs, the output is 1.

Look at the top half of the figure. Two P switches connect OUT to the supply. They are side by side (in parallel). One closed P switch is sufficient to make OUT 1.

Look at the bottom half. Two N switches connect OUT to ground. They are one after the other (in series). Both N switches must close to make OUT 0.

When one half connects, the other half disconnects. Thus, no current flows from the supply to ground.

From this step, the guide shows each NAND gate as one symbol. Each symbol is the four switches from step 2.

A NOT gate changes 1 to 0 and 0 to 1. To make a NOT gate, connect the two inputs of a NAND gate together.

If A is 1, both NAND inputs are 1. Thus, the output is 0. If A is 0, both NAND inputs are 0. Thus, the output is 1.

A NAND gate gives the opposite of AND. Thus, put a NOT gate after the NAND gate. The NOT gate cancels the "not" in NAND.

This circuit uses two NAND gates. The second gate is the NOT gate from step 3.

Put a NOT gate on each input. Then connect the two NOT outputs to a NAND gate.

Why does this work? A NAND gate gives 0 only when both of its inputs are 1. Here, both NAND inputs are 1 only when A is 0 and B is 0. Thus, the output is 0 only when A and B are both 0. That is OR.

Mathematicians call this rule De Morgan's law.

XOR means "exclusive OR". It gives 0 when the two inputs are the same.

Gate 1 calculates A NAND B. Gate 2 compares this result with A. Gate 3 compares it with B. Gate 4 combines the two results.

XOR is necessary for addition. The next step shows why.

In decimal, each column can hold ten digits: 0 to 9. When a column goes past 9, it goes back to 0. Then you carry 1 to the next column. Thus, each column is worth ten times the column to its right: 1, 10, 100, 1000.

In binary, each column can hold only two digits: 0 and 1. When a column goes past 1, it goes back to 0. Then you carry 1 to the next column. Thus, each column is worth two times the column to its right: 1, 2, 4, 8, 16.

To read a binary number, add the values of the columns that have a 1. For example, 10110 is 16 + 4 + 2 = 22.

Look at one column of a binary addition. It adds bit A and bit B. Each bit is 0 or 1, so there are only four cases. Click a case to send it into the circuit.

Each case gives two digits. The right digit is the sum. You write it in this column. The left digit is the carry. It goes to the next column on the left.

Now compare the four cases with the gates from the earlier steps:

The sum digits are 0, 1, 1, 0. That is the truth table of XOR. The carry digits are 0, 0, 0, 1. That is the truth table of AND. The gates do not know arithmetic. Their truth tables are the same as the addition table. That is sufficient.

In the circuit, gates 1 to 4 are the XOR from step 6. Gate 5 is a NOT. It takes the output of gate 1, which is A NAND B. NOT (A NAND B) is A AND B. That is the carry. This circuit is a half adder.

It is a "half" adder because it cannot accept a carry from the column to its right. The next step solves this problem.

A half adder has only two inputs. But each column after the first one must add three bits: A, B and the carry in. Thus, a full adder has three inputs.

The full adder does the work in three parts:

• Half adder 1 adds A and B. It gives sum 1 and carry 1.
• Half adder 2 adds sum 1 and the carry in. It gives the final sum and carry 2.
• The OR gate combines carry 1 and carry 2 into one carry out.

Why is an OR gate sufficient? Why do the two carries not add together? Look at the Carry 1 and Carry 2 columns of the table. They are never both 1.

If carry 1 is 1, then A and B are both 1. Thus, sum 1 is 0. Half adder 2 then adds 0 and the carry in. That addition cannot make a carry. Thus, a maximum of one carry is 1, and "one or the other" is the correct answer.

When you add numbers on paper, you start at the right column. If a column is more than 9, you write the right digit and carry 1 to the top of the next column.

Binary addition is the same. But a binary column is full at 2, not at 10. And each column after the first one adds three bits: A, B and the carry from the column to its right.

Three bits can be at most 1 + 1 + 1 = 3. In binary, 3 is 11. Thus, the column writes 1 and carries 1. The carry is never more than 1.

Each box in the next figure is one full adder from step 9. Four full adders are in a line. The carry out of each column goes into the carry in of the column to its left.

In this adder, the carry goes through each full adder, one after the other. Engineers call this a ripple-carry adder.

A 4-bit number has 16 values: 0 to 15. When a 4-bit result goes past 15, it goes back to 0. The carry out is lost. Thus, in 4 bits, 16 is the same as 0.

This gives a trick. To subtract 3, add 16 − 3 = 13. For example, 5 + 13 = 18. Four bits keep 18 − 16 = 2. And 5 − 3 = 2.

The adder makes 16 − B easily. Flip each bit of B, then add 1. For example, 3 is 0011. Flipped, it is 1100. That is 12. And 12 + 1 = 13.

An XOR gate can flip a bit on command. Look at its truth table: when one input is 1, the output is the opposite of the other input. When that input is 0, the other input goes through unchanged. Thus, one control wire, SUB, goes to an XOR gate on each bit of B. The same wire is the carry in of the adder. That is the "add 1".

The machine at the end of this page has a "Subtract 1" instruction. It is this circuit with B = 1.

A number is zero when all its bits are 0. Thus, the question is: is any bit 1?

An OR gate answers this question for two bits. More OR gates answer it for more bits. Connect them in a tree. Then a NOT gate inverts the answer. The output is ZERO.

Each OR gate is three NANDs (step 5). Each NOT gate is one NAND. Thus, this 4-bit test is ten NAND gates.

The machine at the end of this page has the instruction "JZ: if the register is 0, go to another address". The zero test is the "if".

A multiplexer has two data inputs, A and B, and one select input, S. When S is 0, the output is A. When S is 1, the output is B. It is like an "if" statement in a program: if S then B, else A.

Gate 1 makes NOT S. Gate 2 lets A through only when NOT S is 1. Gate 3 lets B through only when S is 1. Gate 4 combines the two results. Only one of them can be active.

For a number with many bits, put one multiplexer on each bit. The same S controls all of them. A CPU uses multiplexers everywhere: to select a register, to select the result of an operation, and to select the next address.

The machine at the end of this page has four registers, R0 to R3. An instruction such as "INC R2" must find register 2. A decoder does this.

Two address bits can make four numbers: 00, 01, 10 and 11. The decoder has one output line for each number. Each line is an AND gate that looks for its own pattern. Line 2 looks for "2s bit is 1 and 1s bit is 0".

The two NOT gates make the opposite of each address bit. The four vertical wires carry A and NOT A for each bit. Each AND gate connects to one wire of each pair.

Memory chips use very large decoders. A chip with 30 address bits has 2³⁰ lines, one for each location.

Until now, each output changes when its inputs change. The circuits cannot keep a value. They have no memory.

To make memory, use feedback. Connect the output of a gate back to the input of a different gate.

In the figure, the output of gate 1 goes into gate 2. The output of gate 2 goes back into gate 1. The two gates hold each other in position. This circuit is an SR latch. It keeps one bit.

The registers and the fast cache memory in a CPU keep their bits with loops like this one.

The SR latch has two problems. You must push SET or RESET to change it. And when you push both, the result is not known.

The D latch fixes both problems. It adds two gates in front of the SR latch. When SAVE is 1, gate 1 or gate 2 makes a SET or a RESET from D. They can never make both, because one gets D and the other gets NOT D. When SAVE is 0, both gates give 1. Then the latch keeps its value.

A D latch copies D for all of the time that SAVE is 1. In a CPU that is a problem. While SAVE is 1, a changed output can go through the gates and come back to D. Then the value changes again, and again.

The solution is two latches in a row, with opposite SAVE signals. The clock goes to latch 2 directly and to latch 1 through a NOT gate. Thus, one latch is always closed.

• While the clock is 0, latch 1 copies D. Latch 2 is closed.
• When the clock goes to 1, latch 1 closes with the value it has. Latch 2 opens and copies that value to Q.

Thus, Q changes only when the clock goes from 0 to 1. Engineers call this an edge-triggered flip-flop.

A CPU has millions of memory bits. The signals through the gates do not all arrive at the same time. While a signal moves through the gates, the outputs can change many times.

Thus, the memory must wait. It must save a value only when all the gates are stable.

The clock is a square wave. It goes from 0 to 1 and back to 0. A modern CPU clock does this billions of times each second.

The flip-flop from step 17 looks at its input D at only one moment: when the clock goes from 0 to 1. This moment is the rising edge. Connect the same clock to all the flip-flops. Then all the memory changes at the same time, after the gates are stable.

The memory loop in step 15 has two gates. A signal goes around the loop and comes back the same. Thus, the loop is stable.

Make a loop with three NOT gates. Now the signal comes back inverted. The first gate must change. That change goes around the loop and comes back inverted again. The loop never becomes stable. It makes a square wave: a clock.

A program is a list of instructions in memory. Each instruction has an address. The program counter (PC) keeps the address of the instruction to do.

The PC is a register: four flip-flops, one for each bit. At each rising edge of the clock, the flip-flops save a new address. Two parts calculate that address:

• An add-1 unit calculates PC + 1. This is the adder from step 10 with B = 1.
• A multiplexer selects PC + 1 or a jump address. The JUMP signal is its select input.

Usually JUMP is 0 and the PC counts up: 0, 1, 2, 3. When JUMP is 1, the PC goes to a different address. That is how a program makes a loop or skips a part.

In the machine, the instruction decides the JUMP signal. For JMP, JUMP is always 1. For JZ, JUMP comes from the zero test.

This machine has four registers, R0 to R3. Each register is eight flip-flops. Thus, each register keeps a number from 0 to 255. The program is in memory. Each line of the program has an address.

The machine knows only five instructions:

The program counter (PC) keeps the address of the instruction to do. The machine does these four steps again and again:

• Fetch: read the instruction at the address in the PC.
• Decode: find which operation the instruction must do.
• Execute: do the operation.
• Next: put the next address into the PC. Usually, this is PC + 1.

A jump is not a special operation. It only puts a different number into the PC.

You know every part of this machine. Each register is eight flip-flops. Add 1 and subtract 1 are the adder and its subtract trick. The zero test is step 12. A decoder selects the register. The program counter and its multiplexer do the jumps.

A system is Turing complete when it can do all the calculations that a computer can do. It must have sufficient time and memory. It needs three things:

• Memory that it can read and change.
• A conditional jump: an operation that goes to one place or a different place, related to a value.
• A method to do the same steps again (a loop).

This machine has all three. The registers are the memory. JZ is the conditional jump. JMP makes a loop.

In 1961, the mathematician Marvin Minsky proved a related fact. A machine with only add 1, subtract 1, a zero test and two registers is Turing complete. The registers must have no upper limit.

This demo stops at 255. A true Turing complete machine needs memory with no limit. Real computers also have limits, but their limits are very large.

Minecraft redstone, Magic: The Gathering and PowerPoint animations are Turing complete for the same reason. They can branch, and they can remember.

Connect the output Q of each flip-flop to the input D of the next flip-flop. All of them get the same clock. At each rising edge, each flip-flop saves the value of its left neighbor. Thus, the pattern moves one place to the right.

The flip-flops save at the same moment, so each one saves the old value of its neighbor. The edge-triggered flip-flop from step 17 makes this possible. With D latches, one bit would go through all of them at once.

Shift registers have many uses:

• A USB cable or a network cable sends one bit after the other. A shift register collects the bits into bytes again.
• A shift to the right divides a number by 2. A shift to the left multiplies it by 2.
• LED chasers and scanners move a light along a row of LEDs.

A computer cannot easily make true random numbers. All its circuits do the same thing each time. But it can make numbers that look random.

Take a 4-bit shift register. Do not feed IN from outside. Instead, connect FF3 and FF4 to an XOR gate, and connect the XOR output to IN. Engineers call this a linear-feedback shift register (LFSR).

This LFSR goes through all 15 values from 1 to 15 in a mixed order. Then it starts the same list again. It never shows 0. If all bits are 0, the XOR gives 0, and the register stays at 0 for all time.

LFSRs are everywhere. The noise sound of the NES game console comes from a 15-bit LFSR. Wi-Fi and GPS use them to mix their signals.

The display on a clock or a microwave has seven segments: a to g. Each segment is one lamp. A circuit must decide, for each 4-bit input, which segments are on.

Each segment has its own truth table with 16 rows. A simple method makes any truth table. First, use a decoder (step 14) with 16 lines: one line for each input value. Then, for each output, connect an OR gate to the lines where the output must be 1.

Engineers then make the circuit smaller, but this method shows an important fact: NAND gates can make any truth table.

A traffic light at a crossroad has four states. A 2-bit register keeps the state: 00, 01, 10 or 11. A counter is the timer.

At each tick, logic gates calculate the next state from three things: the current state, the timer, and a sensor in the road. If no car waits on the East–West road, the North–South light stays green.

This is a state machine. The program counter and the machine in this guide are state machines too. They have more states and more inputs.