Logic gates and digital building blocks
Introduced| English | Meaning |
|---|---|
| OR/ɔː/ | OR |
| AND/ænd/ | AND |
| NOT/nɒt/ | NOT |
| XOR | XOR |
| NAND | NAND |
| universal | universal |
| half adder/hɑːf ˈædə/ | A logic circuit that adds two single binary digits and produces a sum bit and a carry bit. |
| full adder/fʊl ˈædə/ | A circuit that adds two bits and a carry-in, giving a sum bit and a carry-out. |
| ripple-carry adder/ˈrɪpl ˈkæri ˈædə/ | ripple-carry adder |
| multiplexer/ˈmʌltɪpleksə/ | A circuit that chooses one of several inputs and passes it to its output. |
| boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | boolean algebra |
Billions of tiny switches
- A phone adds two numbers in well under a nanosecond. Inside, there is no arithmetic, only switches that are on or off.
- A few kinds of switch pattern, called gates, are enough to build every circuit in a computer. This lesson builds an adder and a selector from them.
The basic gates
- AND 与门 gives 1 only when both inputs are 1; OR 或门 gives 1 when at least one is 1; NOT 非门 flips its input. XOR 异或 gives 1 when the inputs differ.
- NAND 与非门 (NOT-AND) is universal 通用的: every other gate, and so every circuit, can be built from NAND gates alone.
Any logic circuit can be built using only NAND gates.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
NAND is universal. For example, NOT a is a NAND a, and AND is a NAND followed by a NOT.
How many rows does the full truth table of a 3-input gate have?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Each input is 0 or 1, so there are 2^3 = 8 rows.
The half adder
- A half adder 半加器 adds two bits. Sum $= a \oplus b$ (XOR), carry $= ab$ (AND).
- Check the hard row: $1 + 1 = 10_2$, so sum 0 and carry 1. Two gates give correct arithmetic.
In a half adder, the sum bit is —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
1 + 1 = 10: sum 0, carry 1. XOR gives the sum and AND gives the carry.
Full adders in a chain
- A full adder 全加器 also takes a carry in from the column to its right. It is two half adders plus an OR gate.
- Chain $n$ full adders and you get a ripple-carry adder 行波进位加法器. Each carry must wait for the one before it, so the delay grows with $n$.
A 4-bit ripple-carry adder adds 0110 and 0111. What is the result in decimal?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
6 + 7 = 13 = 1101 in binary, which still fits in 4 bits.
The multiplexer
- A multiplexer 多路选择器 uses a select line to pick one input: out $= \bar{s}a + sb$. When $s = 0$, $a$ passes; when $s = 1$, $b$ passes.
- A 4-to-1 mux is three 2-to-1 stages. Choosing among $2^k$ inputs needs $k$ select bits, so a 32-to-1 mux has 5 levels.
A 2-to-1 multiplexer has a = 0, b = 1 and select s = 1. What is the output?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
out = (NOT s)·a + s·b = 0·0 + 1·1 = 1. The select line picks b.
How many select bits does a 16-to-1 multiplexer need?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
2^4 = 16, so 4 select bits name one of 16 inputs.
Boolean algebra makes circuits smaller
- Boolean algebra 布尔代数 has identities such as $x + x = x$, $x \cdot x = x$ and $x + \bar{x} = 1$. Two expressions with the same truth table can be collapsed into the simpler one.
- Example: $ab + a\bar{b} = a(b + \bar{b}) = a$, so three gates become a plain wire. Fewer gates use less power and add less delay, and gate delay is what limits the clock speed.
ab + a(NOT b) simplifies to —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ab + a(NOT b) = a(b + NOT b) = a · 1 = a. Three gates become a wire.
Match each expression to what it is.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Each building block is a short boolean expression.
Worked example: 0101 + 0011
- Right to left: $1 + 1 = 0$ carry 1; $0 + 1 + 1 = 0$ carry 1; $1 + 0 + 1 = 0$ carry 1; $0 + 0 + 1 = 1$.
- Result $1000_2 = 8$, and $5 + 3 = 8$. The carry rippled through three columns before the answer was ready.
Three common slips
- Writing OR for XOR. They differ on the $1 + 1$ row: OR gives 1, XOR gives 0.
- Treating gates as instant. Every gate adds delay, and a ripple adder adds it once per bit.
- Counting select lines wrongly. 8 inputs need 3 select bits, not 8.
Recap
- AND, OR, NOT, XOR; NAND alone can build anything.
- Half adder: sum XOR, carry AND; full adders chain into a ripple-carry adder whose delay grows with width.
- Mux: out $= \bar{s}a + sb$; boolean identities remove gates, power and delay.