AND, OR, NOT, NAND, NOR, XOR: the building blocks of digital logic, what's inside them, and why they take time.
Interactive·Logic Gate Playground
Pick a gate, flip inputs, and explore the full truth table. Watch the output glow when it's HIGH!
&AND
0
A
B
Y
0
0
0
0
1
0
1
0
0
1
1
1
The seven gates
A gate is a small circuit that takes one or more input bits and produces one output bit by a fixed rule. Every digital chip, however large, is built from these few rules.
> Loading the circuit…
All seven gates side by side, driven by the same two switches. Flip them and compare the lights.
With a = 1 and b = 1, which lights are on?
Find the two pairs of gates whose lights are always opposite.
Gate
Output is 1 when…
Written
Verilog
NOT
the input is 0
a'
~a
AND
all inputs are 1
a·b
a & b
OR
any input is 1
a + b
a | b
NAND
not all inputs are 1
(a·b)'
~(a & b)
NOR
no input is 1
(a + b)'
~(a | b)
XOR
an odd number of inputs are 1
a ⊕ b
a ^ b
XNOR
an even number of inputs are 1
(a ⊕ b)'
~(a ^ b)
TipIn a gate symbol, a small circle (a bubble) means "invert". NAND is an AND with a bubble on its output, and NOR is an OR with one.
XOR deserves a second look, because you'll use it often. With two inputs it answers "are these different?", which makes it a comparator. It is also a controlled inverter: a ⊕ 0 = a and a ⊕ 1 = a'. That's the trick the adder/subtractor used in Chapter 3.
What's inside a gate
Modern chips build gates from CMOS transistors, which come in two complementary types. A PMOS transistor conducts when its input is 0, and an NMOS transistor conducts when its input is 1. Each gate has a network of PMOS transistors that can connect the output up to the supply, and a mirror network of NMOS transistors that can connect it down to ground.
To see where those transistors sit in the silicon, here is a cross-section of an inverter. Turn it with the mouse or the Turn buttons.
> Loading the animation…
> Loading the animation…
Compare NAND and NOR above. NAND has its PMOS transistors in parallel and its NMOS in series. NOR has them the other way round. Series becomes parallel and vice versa, and you'll see the same swap again in De Morgan's theorem in the next chapter.
NoteThis is why NAND and NOR are the natural gates in CMOS. An AND gate is really a NAND followed by a NOT, so it costs two more transistors and is slower. Chapter 9 looks at this in detail.
One gate to build them all
NAND is universal: you can build any logic function using NAND gates alone. To prove it, it's enough to build NOT, AND and OR, since every truth table can be written with those three.
To get
Using NAND
Why it works
NOT a
NAND(a, a)
(a·a)' = a'
a AND b
NAND(NAND(a, b), NAND(a, b))
NOT of a NAND is an AND
a OR b
NAND(NAND(a, a), NAND(b, b))
(a'·b')' = a + b, by De Morgan
> Loading the circuit…
NOT, AND and OR, each built only from NAND gates.
Check all four input combinations against the truth tables above.
Count the gates: 1 for NOT, 2 for AND, 3 for OR.
NOR is universal in the same way, with the roles swapped: NOT takes 1 gate, OR takes 2 and AND takes 3.
How many 2-input NAND gates does F = ab + cd need?
Gates with more inputs
AND, OR, NAND and NOR extend naturally to more inputs: a 3-input AND is 1 only if all three inputs are. Since AND and OR are associative, you can also build wide gates by chaining narrow ones.
Be careful with XOR. A wide XOR doesn't mean "exactly one input is 1". It means an odd number of inputs are 1, so a ⊕ b ⊕ c is 1 when all three are 1. This is why XOR is the parity gate from Chapter 4.
Watch outNAND and NOR are not associative. NAND(NAND(a, b), c) is not a 3-input NAND of a, b and c, so you can't chain them the way you chain AND gates.
Practice
A 4-input XOR gate has inputs 1, 1, 1, 0. What's its output?
Gates take time
So far a gate's output has changed the instant its input does. In a real gate, charge has to move to change a voltage, so the output changes a little later. That's the propagation delay. In a modern chip it's measured in picoseconds, but it still decides how fast a chip can run: the clock must wait for the slowest path of gates to finish.
Delay also creates surprises. This circuit ANDs a signal with its own inverse. On paper a·a' is always 0, so the output should never turn on.
> Loading the circuit…
Slow motion is already on. The NOT gate takes time to react, so for a moment both inputs of the AND are 1.
Turn a on and watch y. It flashes for a moment, though the logic says it never should.
Turn a off. There's no flash this time, because the AND's input from a goes low first.
That short wrong pulse is a glitch. It's why every signal in a synchronous design is allowed to settle before a flip-flop samples it at the next clock edge. Chapter 17 explains how to find these hazards and remove them.
You can describe gates in Verilog in two ways. The first lists the gates, and the second writes the equation and leaves the choice of gates to the synthesis tool. Real projects nearly always use the second.
// Listing gates (structural)
nand n1 (y1, a, b);
xor x1 (y2, a, b);
// Writing the equation (dataflow)
assign y1 = ~(a & b);
assign y2 = a ^ b;
Note& and | work bit by bit on buses, while && and || treat each whole value as true or false. Use the single-character forms for logic.
Positive and negative logicGATE: fine to skip at first
Nothing forces high voltage to mean 1. In positive logic it does, and in negative logic high means 0. The same physical gate then performs a different function: swap 0 and 1 throughout the truth table of a positive-logic AND and you get a negative-logic OR. A positive NAND is a negative NOR, and a positive XOR is a negative XNOR.
Positive logic
Same gate in negative logic
AND
OR
OR
AND
NAND
NOR
NOR
NAND
XOR
XNOR
NOT
NOT
Practice · GATE-style
Using only 2-input NAND gates, which of these needs the most gates?