What you will be able to do. By the end of this chapter you will know the seven basic logic gates, read and write their truth tables and Boolean expressions, and have built a small circuit out of gates yourself. You will also see why engineers describe circuits in a language called Verilog, and read your first piece of it. Finally, you will find out what a gate is physically made of, and why almost every chip today is built in a technology called CMOS. You need no background in electronics or programming.
Digital electronics is all around you. Your phone, laptop and television are the obvious examples, but there is also a digital chip in the washing machine, the microwave oven, the car and the bank card in your wallet.
You have probably also heard that all of it works on 1s and 0s. That is true. Every photo, song and message on your phone is stored as a very long list of 1s and 0s, and every calculation the phone makes is a calculation on 1s and 0s.
What is rarely explained is what a 1 or a 0 actually is. There are no tiny numbers written inside a chip. A chip is full of wires, and at any moment each wire is in one of two states: it is at a high voltage or at a low voltage, called HIGH and LOW for short. You can think of it as electricity being present on the wire or absent. A 1 is simply another name for HIGH, and a 0 is another name for LOW. 1 and 0 are digits, and that is where the word digital comes from: a digital device handles everything as digits.
Why only two states, when we ourselves count with ten digits? Because two are easy to tell apart. You can see from across a room whether a lamp is on or off. Telling whether a dimmer is set to 6 or to 7 out of 10 is much harder, and a single flicker would fool you. A chip that only has to tell HIGH from LOW keeps getting the right answer even when its signals are not perfectly steady.
There is a word for anything that has exactly two possible values, with nothing in between: binary. It is an ordinary English word, and it begins with bi, meaning two, as in bicycle.
A light switch is binary: it is on or it is off. A question that can only be answered yes or no is binary. A coin toss is binary.
Every pair below is a binary pair. They are different words for the same idea: one of two values.
| One value | The other value |
|---|---|
| 1 | 0 |
| YES | NO |
| ON | OFF |
| HIGH | LOW |
| TRUE | FALSE |
| OPEN | SHUT |
So when people say that computers work on 1s and 0s, they mean that computers work on binary values. A modern chip contains millions, often billions, of wires, each one HIGH or LOW, and everything the chip does comes from combining them.
The parts that do the combining are called gates. To see what a gate does, start with the kind of gate you can walk through.
A garden gate is binary: it is OPEN or it is SHUT. You want to walk to a garden, and whether you get in is binary too: you get in or you do not. So a gate takes binary information (is it open?) and produces binary information (do you get in?).
It gets interesting with two gates, because there are two ways to arrange them.
Here the path passes through gate A and then gate B.
You reach the garden only when gate A and gate B are both OPEN. One SHUT gate is enough to stop you. Each gate can be in two states, so there are four situations:
| Gate A | Gate B | Do you get in? |
|---|---|---|
| SHUT | SHUT | NO |
| SHUT | OPEN | NO |
| OPEN | SHUT | NO |
| OPEN | OPEN | YES |
Now the wall has two gates next to each other, and either one leads to the garden.
You reach the garden when gate A or gate B is OPEN. Both OPEN works too. You are stuck only when both are SHUT.
| Gate A | Gate B | Do you get in? |
|---|---|---|
| SHUT | SHUT | NO |
| SHUT | OPEN | YES |
| OPEN | SHUT | YES |
| OPEN | OPEN | YES |
The gates are the same in both gardens. Only the arrangement changed, and that changed the rule for getting in.
Look at how you worked out the answer in each garden. You took statements that are either true or false, such as “gate A is open”, and joined them with the word and or the word or to decide whether another statement, “I get in”, is true.
Reasoning with true-or-false statements joined by and, or and not is called logic. An electronic part that does this job on electrical signals is therefore called a logic gate. A chip contains no gardens: its gates are made from microscopic switches called transistors, and what passes through them is electricity. But the rules are exactly the ones you just used.
OPEN and SHUT suit a garden, ON and OFF suit a lamp, HIGH and LOW suit a voltage. Engineers use one pair for all of them: 1 and 0.
| Written as 1 | Written as 0 |
|---|---|
| OPEN | SHUT |
| YES | NO |
| ON | OFF |
| HIGH | LOW |
| TRUE | FALSE |
This is easier for three reasons:
A single 1-or-0 value is called a bit.
The values going into a gate are its inputs. The value coming out is its output. In the garden, the inputs were the two gates and the output was whether you got in.
This course names them the same way every time:
These names are only a convention, which means an agreed habit. A gate behaves the same whatever its wires are called, and other books use other letters. Keeping to one set of names means that every truth table, formula and diagram in this course can be read the same way.
AND and OR each join two statements. The third word of logic, not, works on a single statement: it turns the statement into its opposite. This is called negation.
Take the statement “the door is locked”. Its negation is “the door is not locked”. Whenever the first statement is true, the second is false, and whenever the first is false, the second is true. The two are never true together, and never false together.
| The door is locked | The door is not locked |
|---|---|
| TRUE | FALSE |
| FALSE | TRUE |
A gate that does this to a signal is called a NOT gate, or an inverter. It has only one input, A, and one output, Y, and the output is always the opposite of the input. Written with 1 and 0: it turns a 1 into a 0 and a 0 into a 1.
Take the table for two gates in a row and write 1 for OPEN and YES, 0 for SHUT and NO. Use the names from the last section: A and B for the inputs, Y for the output. You get this:
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
A table like this is called a truth table. It has one row for every possible combination of inputs, and it gives the output for each row. A truth table is the complete description of a gate: nothing else is needed to know what it does.
The rows are always written in the same order: 00, 01, 10, 11. Keeping to one order makes two truth tables easy to compare, and makes it hard to forget a row. Two inputs give four rows; three inputs would give eight.
Here are the truth tables of the other two gates. OR, from the garden with two gates side by side:
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
And NOT, which has one input and therefore only two rows:
| A | Y |
|---|---|
| 0 | 1 |
| 1 | 0 |
Below are an AND, an OR and a NOT gate that you can operate. In each one:
Go through all the rows of each truth table by hand and see that the lamp agrees.
The AND symbol has a flat back and a round front, like the letter D.
The OR symbol has a curved back and a pointed front.
The NOT symbol is a triangle with a small circle at its tip. Remember the small circle: wherever it appears on a symbol, it means “inverted”.
A truth table says everything about a gate, but it takes space. There is a shorter way to write what a gate does, as a small formula. It is called Boolean notation, after George Boole, who worked out the algebra of true and false in the 1800s.
AND is written with a dot, like multiplication. Read it as “Y equals A and B”. The dot is often left out, so you will also see it written AB.
Y = A \cdot BOR is written with a plus sign. Read it as “Y equals A or B”.
Y = A + BNOT is written with a bar over the name. Read it as “Y equals not A”, or “A bar”.
Y = \overline{A}A bar over a letter is slow to write by hand, and a computer keyboard has no key for it. So, for ease of writing, NOT A is also written A′, read “A prime”. The small mark after the letter is quick to add with a pen, and on a computer you can type it with the apostrophe key, as A'.
A′ and A with a bar over it mean exactly the same thing. From the next chapter on, this course uses the prime in sentences and tables, and keeps the bar for equations that stand on their own line, like the one above.
Be careful with the plus sign. In Boolean notation + means OR, not addition. The last row of the OR truth table says 1 + 1 = 1, which is correct for OR and wrong for arithmetic. The dot is safer: A · B gives the same answer as multiplying A by B, as you can check against the AND truth table.
Two more gates come from putting a NOT after a gate you already know.
NAND is short for NOT AND: an AND gate followed by a NOT. Its output is the opposite of AND in every row, so it is 0 only when both inputs are 1.
| A | B | Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
In Boolean notation the bar goes over the whole AND:
Y = \overline{A \cdot B}The NAND symbol is the AND symbol with the small “inverted” circle on its output.
NOR is short for NOT OR: an OR gate followed by a NOT. Its output is 1 only when both inputs are 0.
| A | B | Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Y = \overline{A + B}The NOR symbol is the OR symbol with the small circle on its output.
In everyday English “or” often means one or the other but not both: “tea or coffee?”. The OR gate is not like that, because it also gives 1 when both inputs are 1. The gate that matches the everyday meaning is the exclusive OR, written XOR. You will also see it written EX-OR.
Its output is 1 when exactly one input is 1. Compare it with OR: only the last row differs.
| A | B | Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Another way to read the table: Y is 1 when the two inputs are different. In Boolean notation XOR has its own sign, a plus in a circle:
Y = A \oplus BThe XOR symbol is the OR symbol with a second curved line across its back.
XNOR (also written EX-NOR) is an XOR followed by a NOT. Its output is 1 when the two inputs are the same, which makes it a one-bit equality checker.
| A | B | Y |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Y = \overline{A \oplus B}The XNOR symbol is the XOR symbol with the small circle on its output.
You have operated seven gates. Now build one. The canvas below has two switches and a lamp, and nothing between them. Using only AND, OR and NOT gates, make a circuit that behaves like an XOR.
Start from the truth table. Y must be 1 in two rows:
Y is 1 when the first or the second is true. Written in Boolean notation:
Y = A \cdot \overline{B} + \overline{A} \cdot BCount the operations in that expression: two NOTs, two ANDs and one OR. That is your parts list.
How to use the canvas:
When you think it is right, press Check.
Give it a real try first; the answer is below. This circuit is complete, so you can flip A and B and follow the green and red wires to see why it works. The upper AND gate detects “A and not B”, the lower one detects “not A and B”, and the OR gate lights the lamp when either of them fires.
Now make an XNOR, again from AND, OR and NOT only. You know that an XNOR is an XOR followed by a NOT, so one way is to build your XOR again and add one more gate at the end.
If you want a different route, read the XNOR truth table the way you read the XOR one: Y is 1 when both inputs are 1, or when both are 0.
Y = A \cdot B + \overline{A} \cdot \overline{B}This is the XOR from before with a NOT gate added before the lamp.
Think about what that took. For one small function of two inputs you placed five gates, dragged them into position and connected nine wires, and one wire in the wrong place meant hunting for the mistake.
A real chip has millions of gates. Nobody places them by hand. Engineers describe the circuit in text, and software works out the gates and the wires. A language for describing circuits is called a hardware description language. The one this course teaches is Verilog.
Here is the circuit you just built, as Verilog. You are only reading it for now; you will write and run your own soon.
module my_xor(
input a,
input b,
output y
);
assign y = (a & ~b) | (~a & b);
endmodule
Compare it with your canvas, part by part:
module my_xor( ... ); starts a module. A module is Verilog's word for a circuit with a name. Think of it as the canvas with a label on it: a box with wires going in and wires coming out. endmodule closes the box.input a and input b are the wires going in. On the canvas they were the switches A and B.output y is the wire coming out. On the canvas it was the lamp Y.a, b and y are A, B and Y. Verilog code is usually written in lower case, and Verilog treats a and A as two different names, so the code must use the same spelling throughout.assign y = (a & ~b) | (~a & b); is everything you wired between them: all five gates and all nine wires, in one line.That line is the Boolean expression you built from, written with symbols that exist on a keyboard:
| Gate | Boolean notation | Verilog |
|---|---|---|
| AND | A · B | a & b |
| OR | A + B | a | b |
| NOT | A with a bar over it | ~a |
| XOR | A ⊕ B | a ^ b |
One idea to hold on to: assign is not an instruction that runs once. It describes a permanent connection, like the wires on the canvas. Whenever a or b changes, y follows at once.
The table has a fourth row. Verilog has an operator for XOR itself, so the whole circuit can be written even more briefly:
module my_xor(
input a,
input b,
output y
);
assign y = a ^ b;
endmodule
Both versions describe the same truth table, so they are the same circuit as far as anyone using it can tell.
Wiring was one tedious job. Testing was the other. To be sure a circuit was right you had to click the switches through every combination and compare the lamp with the truth table by eye. Four rows is bearable. A circuit with ten inputs has 1,024 rows.
So engineers write a second piece of Verilog whose only job is to flip the switches. It is called a testbench. Here is one for the XOR module:
`timescale 1ns/1ps
module TB;
reg a, b; // the two switches
wire y; // the lamp
my_xor dut(.a(a), .b(b), .y(y)); // the circuit being tested
initial begin
$dumpfile("dump.vcd"); $dumpvars(0, TB);
a = 0; b = 0; // row 1 of the truth table
#10 a = 0; b = 1; // wait 10 ns, then row 2
#10 a = 1; b = 0; // wait 10 ns, then row 3
#10 a = 1; b = 1; // wait 10 ns, then row 4
#10 $finish; // wait 10 ns, then stop
end
endmodule
You do not need to understand every line yet. Read only the four lines in the middle: they set a and b to each row of the truth table in turn. #10 means βwait 10 nanosecondsβ, so each row is held for 10 nanoseconds (ns) before the next one starts. That is the clicking you did by hand, written down once so that it can be repeated exactly, any number of times.
A program called a simulator runs the testbench against the module and records the value of every wire as time passes. The recording is drawn as a waveform. This is the waveform for the XOR module and the testbench above:
How to read it:
a, b and y.Now read y: low, high, high, low. That is the Y column of the XOR truth table, 0 1 1 0. The waveform and the truth table say the same thing; the waveform also shows when each value happened. Hardware engineers spend much of their working day reading waveforms, and from here on so will you.
In this chapter a logic gate has been a garden gate, a symbol on a canvas and a line of Verilog. None of these is what sits inside your phone. This last section looks at what a gate is physically made of. You can design circuits without knowing it, but it explains why chips are built the way they are.
Begin with something that is easy to miss. The two garden gates in a row were not a picture of an AND gate. They were an AND gate: a working one, made of wood and hinges. A logic gate is defined by its truth table, and anything that behaves according to that table is that gate. To build one you need only two things:
In the garden, the switch was a gate across a path. Many other things can do the same job.
Replace the paths with pipes and the garden gates with valves. A valve is a tap: it opens or shuts a pipe just as a gate opens or shuts a path. Let water coming out of a pipe stand for 1, and no water stand for 0.
The pipes do the work of wires: they carry a 1 or a 0 from one gate to the next. If each valve is opened by the push of the water in another pipe, instead of by a hand, then the output of one gate can operate the next, and gates can be joined into circuits of any size. This is not only a thought experiment. Engineers have built working logic circuits from moving water and air, a technique called fluidics.
Light can carry binary values as well. Light on is 1, light off is 0, and a thin glass fibre guides light the way a wire guides electricity. Light is excellent at carrying information: the long-distance links of the internet are glass fibres. The difficulty is the switch. Two beams of light pass straight through each other and neither is changed, so making one beam turn another on and off takes special materials and very strong light. Optical logic gates have been built in research laboratories, but they are still far larger and far more expensive than electronic ones.
Almost every logic gate ever made is electronic. In an electronic gate, the two states are the high and low voltages you read about at the start of this chapter, and the switch is the transistor. Electronics beat water, light and every other method on several counts at once:
A transistor has three terminals. Two of them are the ends of a path that electric current can flow along. The third is the control terminal: the voltage on it decides whether the path conducts or is blocked. A transistor that conducts is said to be on, and one that blocks is off.
So a transistor is a switch that is worked by electricity instead of by a finger. That is exactly what a gate needs, because the output of one gate can then work the switches inside the next. The transistor is the valve in the water circuit and the gate across the garden path.
Every chip also has two special wires that reach all of its gates. The supply is held at the high voltage: 5 volts in many older chips, about 1 volt in modern ones. Ground is held at 0 volts. A gate produces a 1 by connecting its output to the supply, and a 0 by connecting its output to ground.
What has changed over the years is the way transistors are arranged to do this. Each arrangement is called a logic family, and three of them tell the story.
Resistor-transistor logic, or RTL, was the first logic family to be made as chips, in the early 1960s. It uses one more part, the resistor, which lets current through but limits how much.
The first drawing shows how a NOT gate works in RTL, with the transistor drawn as a plain switch. The output is joined to the supply through a resistor, and to ground through a transistor. The input is the control terminal of the transistor. (A real RTL gate has one more resistor at each input, to limit the current flowing into the transistor. It is left out of this drawing and appears in the next one.)
The switch is a simplification. The next drawing shows the actual circuit, and to read it you need three symbols:
It is the circuit you have just seen, with the resistor at the input now shown: two resistors and one transistor make the whole gate. Early RTL chips ran from a supply of 3.6 volts. A transistor of this kind is called a bipolar transistor.
Add a second transistor beside the first, with an input of its own, and the output is pulled down to 0 when A or B is 1. That is a NOR gate, and it is the gate that RTL makes most easily. The logic of the computer that guided the Apollo spacecraft to the Moon was built entirely from one kind of RTL gate, a three-input NOR, repeated thousands of times.
Pros
Cons
Transistor-transistor logic, or TTL, followed a few years later. It cured the worst faults of RTL by spending more transistors on each gate. The resistors at the inputs gave way to a transistor. At the output, the single resistor that pulled the output up gave way to a pair of transistors: one switches on to connect the output to the supply, and the other switches on to connect it to ground. The output is therefore driven firmly in both directions, instead of drifting upwards through a resistor.
The drawing shows the actual circuit of a standard TTL NOT gate, the one inside the chip numbered 7404. It has four bipolar transistors, four resistors and a diode. A diode, drawn as a triangle against a bar, lets current flow in one direction only: the way the triangle points.
You do not need to follow every wire. The outline is this:
So an input of 1 switches on Q2 and Q4, and the output is 0. An input of 0 leaves Q3 on, and the output is 1. That is a NOT gate. Give Q1 a second emitter, as a second input, and the same circuit becomes a NAND gate.
The gate that TTL makes most easily is the NAND. The best-known TTL chips are the 7400 series from Texas Instruments. The chip numbered 7400 itself contains four two-input NAND gates, and others in the series contain larger ready-made circuits. In the 1970s, engineers built entire computers by wiring hundreds of such chips together on circuit boards. TTL chips run from a 5-volt supply, which made 5 volts the usual supply voltage in electronics for decades.
Pros
Cons
CMOS is short for complementary metal-oxide-semiconductor, and is pronounced “see-moss”. It was invented in 1963, and it uses a different kind of transistor, called the MOSFET.
The bipolar transistors in RTL and TTL stay on only while a small current keeps flowing into their control terminal. In a MOSFET, the control terminal is separated from the rest of the transistor by a very thin layer of insulator, a material that does not conduct. (This layer is the “oxide” in the name.) No current flows through it, so the voltage alone does the switching. The control terminal of a MOSFET is itself called its gate. Do not confuse it with a logic gate: it is one terminal of one transistor.
MOSFETs come in two types that behave in opposite ways, and that is what “complementary” means:
A CMOS NOT gate uses one of each, as the drawing shows. The pMOS transistor sits between the supply and the output, the nMOS transistor sits between the output and ground, and the input controls both.
The actual circuit is the same drawing with each switch replaced by the symbol for a MOSFET. In that symbol, the line standing apart on the left is the control terminal, and the gap beside it stands for the insulating layer. The small circle again marks the pMOS transistor.
Notice what never happens. Whichever value the input has, one of the two transistors is off, so there is no path from the supply to ground. Once the output has settled at its value, almost no current flows. A CMOS gate uses power mainly at the moments when its output changes.
Larger gates follow the garden. In a CMOS NAND gate, two nMOS transistors sit in a row between the output and ground, so the output is pulled down to 0 only when A and B are 1, like the two gates in a row. Its two pMOS transistors sit side by side between the supply and the output, so the output is pulled up to 1 when A or B is 0, like the two gates side by side. That is a complete gate in four transistors, with no resistors. An AND gate is made by adding a NOT gate after the NAND, so inside a chip a NAND is the cheaper gate of the two.
Pros
Cons
The first advantage decided the matter. The number of gates that fit on a chip is limited by heat as much as by space, and a gate that uses almost no power while it waits allows millions of gates on one chip. Shrinking then solved the speed problem: by the 1980s CMOS had caught up with TTL, and it has become faster with every generation since.
Today almost every chip in the world is built in CMOS: the processor and the memory in your phone and laptop, the chip in your bank card, and even the sensor in your camera. When this course says that a gate is built from transistors, it means CMOS.
| Family | Appeared | Speed | Power while waiting | Fits on one chip |
|---|---|---|---|---|
| RTL | early 1960s | slow | high | a few gates |
| TTL | mid-1960s | fast for its time | high | a few gates to a few hundred |
| CMOS | late 1960s | slow at first, very fast today | almost none | billions of transistors |
module is a named circuit, assign describes a permanent connection, a testbench drives the inputs, and a waveform shows every wire over time.All six two-input gates in one table. Each column is one row of a truth table, written as A B:
| Gate | 0 0 | 0 1 | 1 0 | 1 1 | Y is 1 when |
|---|---|---|---|---|---|
| AND | 0 | 0 | 0 | 1 | both inputs are 1 |
| OR | 0 | 1 | 1 | 1 | at least one input is 1 |
| NAND | 1 | 1 | 1 | 0 | not both inputs are 1 |
| NOR | 1 | 0 | 0 | 0 | both inputs are 0 |
| XOR | 0 | 1 | 1 | 0 | the inputs are different |
| XNOR | 1 | 0 | 0 | 1 | the inputs are the same |
The seventh gate, NOT, has one input and simply inverts it.
If you used the “stuck” answers, go back and build the XOR again without looking. Then try the XNOR by the second route, using the expression with two AND gates. Being able to go from a truth table to gates is the skill the rest of this course builds on.