Adding with switches
Tonight's idea
A chip is made of switches. Each wire carries a bit: 1 (on) or 0 (off). A gate takes bits in and sends one bit out. AND gives 1 only when both inputs are 1. OR gives 1 when at least one is. NOT flips its single input. These are grade 8's truth tables, with 1 for true.
Now add two bits. The hard case is \(1 + 1 = 2\), which in binary is 10: write 0, carry 1. So the answer needs two bits, a carry \(C\) and a sum \(S\).
| \(A\) | \(B\) | \(A\) AND \(B\) | \(A\) OR \(B\) | \(A + B\) | \(C\) | \(S\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 2 | 1 | 0 |
\(C\) matches AND: you carry only when both bits are 1. \(S\) is nearly OR, but it must be 0 in the last row. It is 1 when exactly one input is 1. That rule is XOR, short for "exclusive or".
A half adder adds two bits: \(S = A \text{ XOR } B\) and \(C = A \text{ AND } B\).
Watch one: XOR from AND, OR and NOT
\(S\) should be 1 when \(A\) OR \(B\) is 1, but not when \(A\) AND \(B\) is 1:
\[S = (A \text{ OR } B) \text{ AND } \big(\text{NOT } (A \text{ AND } B)\big).\]Trace \(A = 1\), \(B = 1\). OR gives 1. The lower AND gives 1, so NOT gives 0. The last AND sees 1 and 0, so \(S = 0\). The carry is the lower AND's output, \(C = 1\). Together: 10, which is two. The carry is free, because \(A\) AND \(B\) was already in the circuit.
Flip the inputs and watch every gate (the demo draws XOR as a single box): mathdetours.com/demos/gates.html.
Your turn
- Write the four-row truth table for NOT (\(A\) AND \(B\)), and for (NOT \(A\)) OR (NOT \(B\)). What do you notice?
- (a) Trace \(A = 1\), \(B = 0\) through the figure. Give the output of each gate, then \(S\) and \(C\). (b) Someone uses a plain OR for the sum bit instead of XOR. For which inputs is the adder wrong, and what does it say \(1 + 1\) is?
- A column of a long addition has three bits: \(A\), \(B\) and a carry in, \(K\). A full adder adds them with two half adders. The first adds \(A\) and \(B\), giving \(S_1\) and \(C_1\). The second adds \(S_1\) and \(K\), giving \(S\) and \(C_2\). The carry out is \(C_1\) OR \(C_2\). Find \(S\) and the carry out when \(A, B, K\) are (a) 1, 1, 1; (b) 1, 0, 1. Check against ordinary addition.
- (a) In the full adder, can \(C_1\) and \(C_2\) both be 1? Explain without listing all eight cases. (b) The half adder in the figure uses 4 gates. How many does a full adder use? How many to add two 8-bit numbers (one half adder, then seven full adders)?
Stretch: one gate to build them all
A NAND gate is AND followed by NOT. Using NAND gates and nothing else, build NOT, then AND, then OR. (Hint: both inputs of a gate may carry the same bit.) So a whole computer can be made from one kind of gate.
Answers
- For \(A, B = 00, 01, 10, 11\) both columns read 1, 1, 1, 0. They are the same gate. "Not both are 1" says the same thing as "at least one of them is 0".
- (a) OR gives 1. The lower AND gives 0, so NOT gives 1. The last AND sees 1 and 1 and gives 1. So \(S = 1\), \(C = 0\): the answer 01, which is one. (b) OR and XOR differ only when \(A = B = 1\). There the faulty adder gives \(C = 1\), \(S = 1\), which reads 11: it claims \(1 + 1 = 3\).
- (a) \(1 + 1\): \(S_1 = 0\), \(C_1 = 1\). Then \(0 + 1\): \(S = 1\), \(C_2 = 0\). Carry out \(1 \text{ OR } 0 = 1\). Answer 11, three. (b) \(1 + 0\): \(S_1 = 1\), \(C_1 = 0\). Then \(1 + 1\): \(S = 0\), \(C_2 = 1\). Carry out 1. Answer 10, two. Both agree with ordinary addition.
- (a) No. \(C_1 = 1\) needs \(A = B = 1\), and then \(S_1 = 0\). But \(C_2 = S_1 \text{ AND } K\), which is 0 whenever \(S_1 = 0\). This fits the arithmetic: three bits add to at most 3, which is 11, so one carry is always enough. (b) A full adder has \(4 + 4 + 1 = 9\) gates. The 8-bit adder has \(4 + 7 \times 9 = 67\).
Stretch. Feed the same bit into both inputs: \(A\) NAND \(A\) is NOT \(A\). AND is NAND followed by that NOT: \((A \text{ NAND } B) \text{ NAND } (A \text{ NAND } B)\). For OR, use exercise 1 backwards: \((\text{NOT } A) \text{ NAND } (\text{NOT } B)\) is 0 only when both inputs are 0, which is \(A\) OR \(B\). In NAND gates: \((A \text{ NAND } A) \text{ NAND } (B \text{ NAND } B)\). That is 1, 2 and 3 gates.