Digital Design / Module 1: Numbers and logic
2. Logic gates and truth tables
Connect each gate to the question it answers.
See it move
The idea
A gate answers a simple yes-or-no question about its inputs. Think of each gate as a question, and truth tables stop being something you memorise:
| Gate | Question it asks |
|---|---|
| AND | Are all inputs 1? |
| OR | Is any input 1? |
| XOR | Do the inputs differ? (for two inputs) |
| NOT | What is the opposite? |
NAND, NOR and XNOR are the same questions with the answer inverted.
Truth tables
A truth table lists the output for every input combination, so N inputs need 2^N rows. It is a complete description of any combinational block, and it grows quickly: a 32-input function would have over four billion rows. That is why we build large functions from small ones instead.
Universal gates
NAND alone can build every other function, and so can NOR. A NAND with its inputs tied together is an inverter. A NAND followed by an inverter is an AND. Real cell libraries still offer many gate types, because a dedicated cell is usually smaller and faster than a combination of NANDs.
Worked example: XOR from four NANDs
Let n1 = NAND(A,B), n2 = NAND(A,n1) and n3 = NAND(B,n1). The output is NAND(n2,n3). The animation above lets you check all four input combinations and watch each internal signal.
Common mistake
Assuming XOR with many inputs still means "exactly one input is high". A multi-input XOR tells you whether an odd number of inputs are high. That is why XOR is used for parity, and it is a common trick question in interviews.
Key ideas
- AND asks all, OR asks any, XOR asks different.
- NAND and NOR are each universal.
- A truth table with N inputs has 2^N rows.
Your exercise
Interview questions
coreHow many 2-input NANDs make an XOR?
Four.
coreWhy are NAND gates preferred over NOR in CMOS?
NOR has series PMOS, and PMOS is weaker, so it needs more area for the same drive.
basicHow many different Boolean functions of two inputs exist?
Sixteen. A 2-input truth table has 4 rows, and each row's output can independently be 0 or 1, so there are 2^4 = 16 possible tables. AND, OR, XOR, NAND, NOR and XNOR are six of them. The other ten are the two constants, A, B, their inversions, and four functions such as A·B' that treat the inputs unequally.
basicA 3-input XOR has all three inputs at 1. What is the output?
The output is 1. XOR of many inputs asks whether an odd number of inputs are high, and three is odd. Working it pairwise: 1 XOR 1 is 0, and 0 XOR 1 is 1. Reading XOR as 'exactly one input is high' only works for two inputs.
coreBuild a 2-input OR using only 2-input NAND gates. How many do you need?
Three. Use one NAND with both inputs tied to A to make A', and another to make B'. A third NAND of A' and B' gives (A'B')', which by De Morgan is A + B.
coreShow how NOR alone makes an inverter and a 2-input AND.
A NOR with both inputs tied to A gives (A + A)' = A', so it is an inverter. For AND, invert both inputs with two such NORs and feed them to a third NOR: (A' + B')' = AB. That is three NOR gates in total, the mirror image of building OR from NANDs.
coreA 5-input XOR's truth table has how many rows, and in how many of them is the output 1?
There are 2^5 = 32 rows. The output is 1 whenever an odd number of inputs are high, and exactly half of all patterns have odd parity, so 16 rows give 1. This is also why XOR does not simplify on a Karnaugh map: no two 1s are neighbours.
coreWhat does this line compute for two 4-bit buses, and why does it work?
wire [3:0] a, b; wire eq = &(a ~^ b);
It is an equality comparator. ~^ is bitwise XNOR, which gives 1 in each position where the bits match. The reduction AND & then asks whether every position matched, so eq is 1 only when a equals b in all four bits.
advancedAn 8-bit byte is 1101_0110. What even-parity bit is sent with it, and what does the receiver check?
wire [7:0] d = 8'b1101_0110; wire p_even = ^d; // parity bit sent with d
The byte has five 1s. For even parity the extra bit must make the total even, so it is 1, which is ^d computed by an 8-input XOR. The receiver XORs all nine bits; a result of 0 means the count is still even, and 1 means an odd number of bits flipped. Two flipped bits cancel and go undetected.
advancedCan you make a 3-input NAND by feeding one 2-input NAND's output into a second 2-input NAND with the third input?
No. NAND is not associative: NAND(NAND(A,B),C) is not the same as NAND(A,B,C). With A = B = 0 and C = 1, the chain gives NAND(1,1) = 0, but a true 3-input NAND gives 1. You need the AND of A and B first, so put an inverter (a NAND with tied inputs) after the first NAND. XOR, AND and OR chain safely because they are associative.