Logic from switches

Chapter 28 ended with a question: how does a piece of silicon add two bits? There are only four cases: $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$ and $1 + 1 = 10_2$, which is two written in binary. To make every answer two bits long, we write a leading zero.

Take the answer apart bit by bit. The low bit is 1 when exactly one of the two bits is 1, and the high bit is 1 when both are. The high bit is the “and” from Chapter 3, “this and that too”; the low bit is “one or the other, but not both,” the exclusive or. For bits, Python writes them as a & b and a ^ b, and the cell above bears this out: to add two bits is to compute two logical functions.

A machine that adds, then, needs something that computes logic with electricity. That is what we are going to build: first out of relays, which click, then out of transistors, which make no sound. Then, in the workshop, you will get a box of parts that are all of one kind and build everything else from them: NOT, AND, OR, exclusive OR, an adder. Each level you pass puts a new part in the box, and into Iskra-8 along with it. Iskra-8 is the teaching computer we assemble in Chapters 29–31 and switch on in Chapter 32.

A switch pressed by a current

In Chapter 3 a condition already turned into a circuit: and put switches one after another, or put them side by side, and the lamp lit up when the expression was true. But there a person pressed the switches. For a circuit to compute on its own, it needs a switch worked by another current.

Such a switch was invented back in the days of the telegraph, and it is called a relay. It has a coil wound around an iron core, a movable iron armature on a spring and a pair of contacts. Send current through the coil, and the core becomes a magnet and pulls in the armature, which flips the contacts with a click. Switch the current off, and the spring pulls the armature back. Contacts come in two kinds: normally open ones close while the coil carries current, and normally closed ones do the opposite and open.

The widget has four circuits, not counting the chain. Two normally open contacts in a row make AND: the lamp lights only when both armatures are pulled in. Two side by side make OR. A normally closed contact is NOT: the lamp stays lit as long as the coil carries no current. And two normally closed contacts side by side give NOT (A AND B): the lamp goes out only when both buttons are pressed. Remember this last circuit, because it is about to become the hero of the chapter.

The switches in Chapter 3 could already do AND and OR. A relay has a more valuable property: its output can drive the coil of another relay. A switch worked by a finger can’t join such a chain, but a relay can: its own contacts switch on the current that presses the next switch. Turn on “chain” mode and listen: the clicks run from relay to relay like a baton in a relay race. Such a race gives you logic of any depth, since the answer of one condition becomes the input of the next. You can hear the price, too: each link clicks a little later than the one before it. In Chapter 30 this delay becomes the main worry of anyone who designs adders.

Cambridge, 1937. A master’s thesis

In November of the same year, 1937, and independently of Shannon, the Bell Labs researcher George Stibitz built a one-bit binary adder on his kitchen table out of scrap relays, two flashlight bulbs and switches cut from a tobacco can. The machine was later nicknamed the Model K, for “kitchen.” Two people arrived at the same idea in the same year: the relays that connect telephone lines can also count.

Shannon gave us the language this chapter speaks. A circuit can be written as a formula, a formula can be drawn as a circuit, and formulas can be transformed by the rules of algebra. We will come back to the algebra itself after the workshop. First, we replace the clicking relay with the part your computer is made of.

The transistor: a relay with no moving parts

The relay has three problems. The armature needs a few milliseconds to fly across to the contact. The relay itself is the size of a thimble or bigger. And it wears out: the contacts burn and the springs weaken. A computer made of relays is possible, and such machines were built in the 1940s, but it fills a room and adds numbers a few times a second at best.

In December 1947, at the same Bell Labs, John Bardeen and Walter Brattain demonstrated the first working transistor, and their boss, William Shockley, soon came up with an improved design. The transistor in a modern processor is built differently from that first one, but the idea is the relay’s: a control terminal opens or closes a path for current. Engineers call this terminal the gate, a word that has nothing to do with the logic gates coming up in a moment. And nothing moves: the path opens inside the crystal when the voltage on the gate changes the properties of the silicon beneath it. Such a switch flips in a fraction of a nanosecond, and tens of billions of them fit on a single chip.

Transistors come in two kinds. An n-type transistor conducts when its gate has a 1 (a high voltage), a p-type one when it has a 0. Nearly all digital circuits today are built from pairs of both kinds, a technology called CMOS. Here is how CMOS builds the gate we met last in the relay widget, NOT (A AND B).

The lower chain connects the output to ground only when both n-transistors are open, that is, when $A = 1$ and $B = 1$. In every other case at least one p-transistor at the top is open and pulls the output up to the supply. The result is NOT (A AND B), and it costs four transistors. Plain A AND B can’t be built this way: a CMOS circuit with a single layer of transistors always inverts the signal. To get AND, you add two more transistors, an inverter, to the four. That is why in the world of CMOS the NAND gate is a simple, cheap part, and AND is a composite one.

Gates

A circuit that takes several bits and puts out one bit by a fixed rule is called a logic gate. A gate’s rule is its truth table, the kind you saw in Chapter 3, with 1 and 0 now standing in for True and False. On circuit diagrams gates are drawn as symbols, and there is more than one way to draw them. The widget uses the American “distinctive shapes” of IEEE Std 91, while the international standard IEC 60617 draws the same gates as rectangles with a sign inside: “&” for AND, “≥1” for OR.

How many two-input gates are there altogether? The table has four rows, and in each the output is 0 or 1, so there are $2^4 = 16$ different tables. Here they all are.

Sixteen, and each has a name, though not all of them are useful: “always 0” and “copy of a” hardly deserve to be called gates. With three inputs the table has eight rows, and there are $2^8 = 256$ tables; with $n$ inputs, $2^{2^n}$. At five inputs that is already more than four billion. Keeping a part in stock for every function is out of the question. We need a small set from which any function can be assembled, and in the workshop that set will shrink to a single part.

The workshop: everything from NAND

The parts in the workshop’s box are all of one kind, NAND, short for NOT-AND: it puts out 0 only when both inputs are 1, and 1 in every other case. It is the four-transistor circuit you were clicking a moment ago. Each level asks you to build a new part: inputs on the left, outputs on the right, your circuit in between. A level you pass puts the part you built into the box, and later levels can use it ready-made.

Here is how the bench works. The “+ NAND” button puts down a new gate, which you can drag around. To lay a wire, tap an output (the circle to the right of a part, or of an input on the left edge) and then an input of another part; you can also drag a finger from one to the other. Tapping an input that already has a wire removes the wire, and to get rid of a part you don’t need, tap the part itself and then “delete part.” The switches on the left flip the inputs, and light runs along every wire that carries a 1. Under the bench is the truth table: each row shows what is wanted and what your circuit gives, with mistakes in red. Tapping a row sets its inputs. When all the rows match, the level is passed.

Level 1. Flip the signal

The first part is NOT: A at the input, $\overline{A}$ at the output. NAND has two inputs, and we have one signal. What happens if we feed it to both?

When both inputs carry the same value, only two rows of the NAND table remain: 0 and 0 give 1, and 1 and 1 give 0. That is NOT. One gate was enough, and you can’t do it with fewer.

Level 2. AND

Now the box has a NOT in it. NAND is an AND with its answer flipped. How do you flip it back?

Two inversions in a row cancel each other, so AND is a NAND followed by a NOT. Inside there are two NAND gates.

Level 3. OR

This one takes some thought. “A or B” is false in one case only: when both are false. So “A or B” means “it is not true that A is false and B is false.” Translate this sentence into parts, word by word.

“A is false” is $\overline{A}$, and “it is not true that… and…” is NAND. So $A + B = \mathrm{NAND}(\overline{A}, \overline{B})$: a NOT in front of each input of one NAND, three gates in all. That was De Morgan’s law from Chapter 3, and before long it will get a proof.

Level 4. One or the other

The last part of the first tier is the exclusive or, XOR: 1 when the inputs differ. It is the low bit of the sum from the start of the chapter. Building it from ready-made AND, OR and NOT is easy, for example as “(A OR B) AND NOT (A AND B).” Count how many NANDs end up inside, and then try to get it down to four.

How to do it with four NANDs

Let $n = \mathrm{NAND}(A, B)$. It is 0 only when $A = B = 1$. Now take $\mathrm{NAND}(A, n)$. If $A = 0$, it is 1. If $A = 1$, then $n = \overline{B}$, and $\mathrm{NAND}(1, \overline{B}) = B$. A zero comes out only when $A = 1$, $B = 0$, so $\mathrm{NAND}(A, n) = \overline{A \cdot \overline{B}}$. Symmetrically, $\mathrm{NAND}(B, n) = \overline{\overline{A} \cdot B}$. One more NAND of these two gives, by De Morgan’s law, $A\overline{B} + \overline{A}B$, which is “one or the other.” The saving comes from using gate $n$ twice: one output can feed as many inputs as you like.

Everything you have built can be checked in code. Below are the same four parts in Python: functions that know nothing but nand, and a counter of how many times it gets called per evaluation.

The columns match the tables from the cell with the sixteen gates, and the counts match the workshop records: 2, 3 and 4. An exhaustive computer search confirms that none of the three can be built with fewer.

An algebra you can check by brute force

Shannon wrote circuits as formulas, and so will we. Here is the notation. AND is written as multiplication, $ab$ or $a \cdot b$; OR as addition, $a + b$; NOT as a bar on top, $\overline{a}$. The variables take only the values 0 and 1, and $1 + 1$ is 1 here: “true or true” is true. This system is called Boolean algebra, after George Boole, who wrote logic down as equations in 1854.

Most laws of Boolean algebra look like the ones from school, but not all. Each law comes in two versions, one for AND and one for OR.

The second distributive law looks odd: OR spreads over AND, as if $2 + 3 \cdot 4$ were equal to $(2 + 3)(2 + 4)$. You can’t do that with numbers, but you can with bits. The last row holds De Morgan’s laws, named after the London mathematician Augustus De Morgan, who corresponded with Boole. The negation moves inside the parentheses and on its way turns AND into OR and OR into AND.

In school algebra an identity is proved by manipulating symbols, because you can’t substitute every number. Here there are only two values, and an identity in three variables needs checking on only eight combinations. Such a check of every case is a complete proof, and a computer can do it for you.

The last line is a common mistake: the negation went inside the parentheses, but nobody swapped AND for OR. Checking every case turns up a counterexample at once.

The laws in everyday code

Boolean algebra comes in handy well beyond processor design. The condition if not (age < 18 or not has_ticket): is hard going: “if it is not true that the person is under eighteen or has no ticket.” By De Morgan’s law the negation moves inside, the OR becomes AND, and the double NOT disappears: if age >= 18 and has_ticket:. The meaning is the same, and you can read it the first time through. Another example: if is_admin or (is_admin and is_owner): shrinks by the absorption law to if is_admin:.

Which condition is equivalent to not (x > 0 and y > 0)?

x <= 0 or y <= 0 x <= 0 and y <= 0 x < 0 or y < 0

By De Morgan, “not (A and B)” = “not A or not B”, and “not (x > 0)” = “x <= 0”. Both traps turn up in programs all the time: forgetting to swap “and” for “or,” and forgetting the equality at the boundary.

Why one NAND is enough for everything

The workshop promised that anything can be built from NAND. Four levels don’t prove it: there might be a function that no arrangement of NANDs can produce. We will prove that no such function exists.

The formula from step 1, a sum of products with one product for each 1 in the table, is called the disjunctive normal form. The proof has a strong consequence. Any circuit without memory (an adder, a comparator, a processor’s instruction decoder) can in principle be assembled from a single kind of part. We get to memory in Chapter 31, and it, too, will turn out to be made of NAND.

What about AND and OR alone, without NOT? Can they build anything?

Yes, if you use enough of them No, some things are out of reach

No. Feed zeros to every input of such a circuit. An AND or an OR gate with zeros at its inputs puts out a zero, so the zeros travel all the way to the output. But NOT has to answer a zero with a one. Circuits of AND and OR are called monotone: switching an input on can light up their output but never put it out. NAND is different because it already has an inversion inside.

The proof is also a recipe: a truth table turns straight into a circuit. The widget below follows the recipe for any function of two, three or four inputs. You can click the cells of the output column or type an expression in Python.

The Karnaugh map: simplifying by eye

The formula from the proof is correct but wasteful. Take the majority function of three inputs: it is 1 when at least two of the inputs are 1. Its table has four rows with a 1 (011, 101, 110 and 111), so the recipe gives four products of three factors each:

$$\mathrm{maj}(a, b, c) = \overline{a}bc + a\overline{b}c + ab\overline{c} + abc.$$

The first and the last terms differ only in the factor $a$. By the distributive law, $\overline{a}bc + abc = (\overline{a} + a)bc = bc$: a variable that appears in a pair once with a bar and once without drops out. The term $abc$ can pair up with the second and the third terms too, since by the idempotence law it may be written three times. We get

$$\mathrm{maj}(a, b, c) = bc + ac + ab$$

with three products of two factors instead of four of three. The question is how to find such pairs quickly. In 1953 Maurice Karnaugh, an engineer at Bell Labs, proposed drawing the truth table as a rectangle instead of a column, building on a similar diagram that Edward Veitch had published in 1952. The rows and columns of a Karnaugh map are labeled in the order 00, 01, 11, 10 rather than 00, 01, 10, 11. In this order any two neighboring cells differ in one input only, and cells on opposite edges count as neighbors too, as if the map were rolled into a tube.

From here on, the eye does the work. Two neighboring 1s merge into a product with one input gone; four 1s forming a rectangle merge into one with two inputs gone. Cover all the 1s with as few rectangles of 1, 2, 4 or 8 cells as you can, each as large as you can, and every rectangle gives one term. Pick the “majority” example in the widget above: its 1s are covered by three groups of two cells. Then pick “parity.” Its 1s form a checkerboard, no two of them merge, and there is nothing to simplify. For a two-level circuit parity is the most awkward function there is, and we are about to need it: the low bit of the sum of three bits is their parity. That is why adders compute it with a chain of XORs.

A Karnaugh map works up to four or five inputs, while a processor has thousands of functions of dozens of inputs. Those are simplified by circuit synthesis programs. They do the same thing, looking for what can be merged, only without a map and on an enormous scale. Finding the shortest formula is hard in general, so the programs settle for a good one that may not be the best. What “hard” means in the strict sense we will find out in Chapter 57.

The adder

Back to adding two bits, where the chapter began. Now we can build it: the low bit is XOR and the high bit is AND. This part is called a half adder.

Level 5. The half adder

The half adder does only half the job. In column addition, every column except the rightmost adds three bits: two from the numbers and the carry that came in from the right. Here is 6 plus 7, that is, $0110_2 + 0111_2$:

The answer is $1101_2 = 13$. In column 1 the two 1s give 0 and a carry; in column 2 two 1s and the carry give 1 and another carry. A part that adds three bits and puts out a sum and a carry is called a full adder. Its sum bit is the parity of its three inputs, $a \oplus b \oplus c$ (the symbol $\oplus$ stands for XOR), and its carry is the majority function from the section on Karnaugh maps: a carry appears when at least two of the inputs are 1. The easiest way to build one is from two half adders. The first adds $a$ and $b$, the second adds the incoming carry to their sum, and an OR combines the two carries. Both carries can’t happen at once; think about why.

Level 6. The full adder

The same assembly can be checked in code. The assertion in the cell tests what an adder is built for in the first place: the carry is worth two, the sum is worth one, and together they make $a + b + c$.

Level 7. The switchman

The last part doesn’t add; it chooses, like a railroad switchman deciding which of two tracks gets onto the main line. A multiplexer takes two signals, A and B, and a control bit S. When $S = 0$, A goes to the output; when $S = 1$, B does. It is a conditional statement made of wires: a if s == 0 else b without any if. As a formula, $y = \overline{s}a + sb$: of the two terms, one is always open, and it lets its input through.

Both of the next chapters will need the switchman. In Chapter 30 eight-bit multiplexers will choose which result (of the addition, the subtraction or the AND) goes into Iskra-8’s register. In Chapter 31 a circuit of the same kind will take an eight-bit address and pick one memory cell out of 256.

The box now holds NOT, AND, OR, XOR, a half adder, a full adder and a multiplexer, and inside every one of them there is nothing but NAND. These are the first parts of Iskra-8. Its processor will add eight-bit numbers, and so far we have an adder for a single bit with a carry.

Tasks

Four tasks in Python, with bits as the integers 0 and 1. Each comes with a limit on what you may use: the checker reads your code and won’t let anything forbidden through. The program has to stay a circuit, only one written in Python.

The box still holds nothing but nand. Write nor(a, b) (NOT-OR: 1 only when both inputs are 0), xnor(a, b) (equality: 1 when the inputs are the same) and implies(a, b) (“if a, then b”: 0 only when $a = 1$, $b = 0$). Inside the functions there may be only calls to nand and to your own functions: no operators, no if, no comparisons. And there is a budget: per evaluation, nor may call nand at most four times, xnor at most five times, and implies at most twice.

Bring in helpers from the workshop: not_(a) is one NAND, or_(a, b) is three. Then NOR is NOT of OR, which makes four.

Equality is XOR inverted. XOR from four NANDs is worked out under level 4 of the workshop; add one NOT, and that makes five.

“If a, then b” is false in a single row: $a = 1$, $b = 0$. NAND is also false in a single row, when both of its inputs are 1. What should go into its inputs to make that row $a = 1$, $b = 0$?

Implication is a NAND with its second input inverted: it gives 0 only when $a = 1$ and $\overline{b} = 1$. A computer search through all circuits shows that the budgets in the statement are the exact minimums: NOR can’t be built from fewer than four NANDs, and equality from fewer than five. In a box full of NORs, of course, NOR is a single gate, and NAND costs four: the two universal gates are mirror images of each other.

Write full_adder(a, b, c), which returns the pair (s, carry), the sum and the carry, so that $a + b + c = 2 \cdot carry + s$. Then write the mirror-image part for column subtraction: full_subtractor(a, b, borrow) returns (d, borrow_out), the difference and the borrow from the next column, so that $a - b - borrow = d - 2 \cdot borrow\_out$. For example, in $0 - 1 - 0$ we borrow a two from the neighbor, and $2 - 1 = 1$, so full_subtractor(0, 1, 0) equals (1, 1). You may use only the bitwise operations &, | and ^: no +, no -, no comparisons, no if.

The adder is in the chapter. For the subtractor, write out the eight-row table: for each triple, work out $a - b - borrow$ and find d and borrow_out. For example, $0 - 1 - 1 = -2 = 0 - 2 \cdot 1$.

The d column will match the adder’s sum column. Enter the borrow column into the “function → table → circuit” widget: the Karnaugh map will find three groups of two cells.

A borrow happens when there are more 1s to take away ($b$ and $borrow$) than $a$ can supply. Compare it with the adder’s carry (the majority function): what changes if you invert $a$? NOT for a bit, without a minus sign, is a ^ 1.

The difference is built the same way as the sum: it is the parity of three bits. And the borrow is the majority of $\overline{a}$, $b$ and $borrow$, the same function as the carry with $a$ inverted. So a subtractor is an adder with one NOT. In Chapter 30 it will turn out that a processor doesn’t need a separate subtractor at all: thanks to two’s complement, the adder itself does the subtracting.

Write mux(s, a, b): when $s = 0$ it returns a, and when $s = 1$ it returns b. No if, no comparisons, no arithmetic, no indexing and no and/or/not; only &, |, ^, ~ and shifts. The catch is that a and b aren’t necessarily bits. A switchman in a processor switches eight wires at once, so mux must work for bytes from 0 to 255 too (while s is always 0 or 1). Then build mux4(s1, s0, a, b, c, d): the address $s_1 s_0$ = 00, 01, 10, 11 selects a, b, c or d. Inside mux4 there may be only three calls to mux.

For bits the formula $y = \overline{s}a + sb$ works. Try it on a byte: when $s = 1$, the expression s & b keeps only the lowest bit of b. You need a mask, eight copies of the bit s: 0b11111111 when $s = 1$ and zero when $s = 0$.

The mask can be built up by shifting: m = s | (s << 1) gives two bits, m | (m << 2) four, and once more makes eight. Then (a & ~m) | (b & m): where the mask has ones, b gets through, and where it has zeros, a does.

In mux4 the low bit of the address chooses within the pairs (a or b, c or d), and the high bit chooses between the pairs.

In hardware the mask is eight wires carrying one control bit: the select signal is amplified and fed to eight identical switchmen at once, one per bit. mux4 is a little tree, with two switchmen on the lower level and one on top. For 256 inputs you need eight levels, and that is how an eight-bit address selects a memory cell, the subject of Chapter 31.

Critical units, in flight computers or at nuclear power plants, are sometimes tripled: three identical units compute the same thing, and a voting circuit puts out whatever at least two of them said. If one unit breaks, the other two outvote it. Write that voting circuit: majority(a, b, c) returns 1 when at least two of the inputs are 1, using bitwise operations only, with no +, no comparisons and no if. Then a council of five: majority5(a, b, c, d, e), built only from calls to majority. It may contain no operators, but you may pass the constants 0 and 1 to majority.

For three inputs the formula comes from the section on Karnaugh maps: $ab + bc + ac$.

Find out what majority(x, y, 0) and majority(x, y, 1) do. With these two “parts” you can build the council of five by the recipe from the universality proof: OR over all the triples out of five, AND inside each triple.

The recipe makes for a long solution. Here is a shorter route. First let three of them vote: m = majority(a, b, c). If $d$ and $e$ disagree, their votes cancel out and the three decide. If they agree, they need one more ally among the three: when $d = e = 1$, at least one 1 among $a$, $b$, $c$; when $d = e = 0$, at least one 0. This can be written with four calls.

Four calls is the minimum; a search through all circuits confirms it. Why it works becomes clear case by case, once you remember that $\mathrm{maj}(1, x, y) = x + y$ and $\mathrm{maj}(0, x, y) = xy$. When $d = e = 1$, the output turns into $a + b + c$: two votes in favor need only one more from the three. When $d = e = 0$, it turns into $abc$: all three are needed. When $d \ne e$, the votes of $d$ and $e$ cancel out, and substitution shows that the output equals $m$, the verdict of the three. The surest check is the same as for the laws of Boolean algebra: go through all 32 rows. We have met the majority function before. It is the carry of the full adder: a carry appears when at least two of the three addends vote for it.

What next

The workshop is finished. Everything else came out of a part that can only do NOT-AND, and the proof promises that any other logic will come out of it too. The most valuable thing in the box is the full adder, which adds three bits: one bit from each number and a carry.

But Iskra-8’s registers are eight bits wide. The instruction ADD R0, R1 has to add numbers from 0 to 255, SUB has to subtract, and both must report whether there was a carry and whether the result came out zero. There is no subtractor in the box. And if you put eight adders in a row, the carry will run from column to column like the clicks along a chain of relays. How to cope with that is the business of the assembly shop in Chapter 30. There, too, the quality control department will work out how, in 1994, a mistake in five cells of a table cost Intel 475 million dollars.