Combining gates

Switches and gates ended with a promise: any truth table can be built from AND, OR and NOT. This page keeps it. It starts with how bits count, turns a truth table into a circuit, then makes the circuit smaller, first with algebra and then with a picture that does the algebra for you, and ends with two circuits a processor uses everywhere. The running example is a job real chips do: lighting the right segments of a digit.

It leans on Switches and gates for the gates, their symbols and truth tables. The diagrams use the same colours: orange is 1, grey is 0.

1 · Counting with two digits

Before gates can do anything with numbers, numbers have to be made of bits. We count in tens: the digits 0 to 9, and each place in a number is worth ten times the place to its right. In 407, the 4 is in the hundreds place and the 7 in the ones: 4 × 100 + 0 × 10 + 7 × 1. Counting up, the ones digit runs 0 to 9, then rolls back to 0 and pushes a 1 into the tens, like a car’s odometer.

A switch only has two settings, so a computer counts with two digits, 0 and 1: binary. It works exactly the same way, except that each place is worth two times the place to its right. Instead of ones, tens, hundreds and thousands, the places are ones, twos, fours, eights, and so on, doubling each time. Each binary digit is one bit.

Click the bits to turn them on (1) and off (0): each one that’s on adds its place value, and the total is the number they make. Count up adds 1: watch the ones bit flip every time, the twos bit every second time, the fours every fourth, just like the odometer, rolling over to 0 after the biggest number. New target picks a number for you to make, and counts your clicks. Four bits make 0 to 15, sixteen numbers; eight bits, 0 to 255. Every extra bit doubles how many numbers there are.

A trick for making a target: start at the biggest place. If the target is at least that big, turn that bit on and take its value away; then do the same with what’s left, place by place. For 13: 8 fits (5 left), 4 fits (1 left), 2 doesn’t, 1 does: 1101.

2 · A job for gates: showing a digit

A 7-segment display, the digits on a microwave, a clock radio or an old calculator, draws every digit from seven bars, lettered a to g. Something has to decide which bars to light for each digit. That something is a circuit of gates, and it has seven outputs, one per segment.

Its input is a digit as four bits, as in section 1: the bits 1001 mean 8 + 1 = 9. Here the bits are named A (worth 8), B (4), C (2) and D (1).

Click the four bits. The table is the whole job: for each input, which of the seven segments light. It’s really seven truth tables side by side, one per segment, each with 16 rows. Inputs 10 to 15 aren’t digits, so for now they show nothing.

3 · Any truth table as a circuit

The display’s table says what each segment should do, but not how to build it. And it’s just one table: other jobs need others, with different inputs and outputs, and any pattern of 0s and 1s at all. So what’s needed is a method that works for every truth table, turning it into gates without any cleverness. There is one, and it’s simple, which is what this section is about. The circuits it makes are usually bigger than they need to be, so the sections after it are about making them smaller.

First, some shorthand, because circuits are about to be written out as formulas. A·B means A AND B, A + B means A OR B, and a bar, $\bar{A}$ , means NOT A. This is Boolean algebra, Boole’s algebra of true and false, and it reads like ordinary algebra with · for times and + for plus (with one change: 1 + 1 is 1, since “true or true” is just true).

One more thing before the recipe: gates can have more than two inputs. A three-input AND, A·B·C, is 1 only when all three inputs are 1; a three-input OR, A + B + C, is 1 when any of them is. Each is the same as two ordinary gates chained, (A·B)·C or (A + B) + C, so there’s nothing new in them, but they’re drawn as one symbol with more inputs, and the same goes for four, five or more.

Now the recipe. It works on one output at a time: a table with several output columns, like the display’s seven, is several truth tables side by side, and each gets its own circuit. So take a table with one output. Each row whose output is 1 can be picked out by one AND gate: for the row A = 0, B = 1, C = 1, that’s $\bar{A} \cdot B \cdot C$ , which is 1 on that row and no other. OR together one such AND for every row whose output is 1, and the result is 1 on exactly those rows. Each AND is a product (it multiplies, in the · sense), so the whole thing is a sum of products.

The output starts as majority: 1 when two or more of the three inputs are 1. Click any output in the table to change it, and the circuit is rebuilt: inputs across the top, each with its own line down and, beside it, a NOT gate making an inverted line; an AND per 1 in the table, tapping the lines it needs (a dot marks each tap; lines that cross without a dot aren’t connected); and an OR joining them. Click the inputs to follow a row through. Majority this way takes 8 gates: 3 NOTs, 4 ANDs and an OR.

The recipe always works, for any truth table of any size, which is the promise kept. But it’s wasteful. A function that’s 1 on half its rows needs an AND for each of them, and a 4-input table can need 16. (These pages count a gate as one gate however many inputs it has; real gates with many inputs cost more, so the smaller formulas below are even better than the counts suggest.)

4 · Simplifying with algebra

Boolean algebra has rules for rewriting a formula without changing what it does, and some rewrites need fewer gates. Three rules are worth knowing, and the first does most of the work.

An input that appears both ways drops out. Take two inputs, X and Y, and the formula $\bar{X} \cdot Y + X \cdot Y$ : “X is 0 and Y is 1, or X is 1 and Y is 1”. Check all four rows:

$X$	$Y$	$\bar{X} \cdot Y$	$X \cdot Y$	$\bar{X} \cdot Y + X \cdot Y$
0	0	0	0	0
0	1	1	0	1
1	0	0	0	0
1	1	0	1	1

The last column is just Y. X is always either 0 or 1, so one of the two terms passes Y through whichever it is, and X makes no difference: $\bar{X} \cdot Y + X \cdot Y = Y$ . Four gates (a NOT, two ANDs and an OR) become a plain wire.

Saying a thing twice changes nothing. $X + X = X$ . In this algebra + is OR, and “true or true” is just true: 1 + 1 = 1. So a term can be written out as many times as is useful, without changing what the formula does.

De Morgan’s laws, after Augustus De Morgan, who published them in 1847, move a NOT across an AND or an OR:

\overline{A \cdot B} = \bar{A} + \bar{B} \qquad\qquad \overline{A + B} = \bar{A} \cdot \bar{B}

“Not both” is the same as “one or other isn’t”; “neither” is the same as “both aren’t”. Majority doesn’t need them, but they connect back to NAND: the first is why a NAND with inverted inputs is an OR, as in making OR from NANDs.

Bigger terms. X and Y don’t have to be single inputs: either can stand for a whole term. In $\bar{A} \cdot B \cdot C + A \cdot B \cdot C$ , take $X = A$ and $Y = B \cdot C$ : it’s the first rule again, so it’s just $B \cdot C$ , “B and C are 1, and A can be either”. Two three-input ANDs become one two-input AND.

Majority. Its formula, straight from the truth table, has four terms:

\bar{A} \cdot B \cdot C + A \cdot \bar{B} \cdot C + A \cdot B \cdot \bar{C} + A \cdot B \cdot C

The last one, $A \cdot B \cdot C$ , differs from each of the other three in exactly one input. So it could merge with any of them by the first rule, but it’s only there once. The second rule fixes that: write $A \cdot B \cdot C$ three times, give each of the other terms a copy to pair with, and merge all three pairs.

Step through: the formula straight from the truth table; A·B·C written three times, in three pairs; each pair merged. Majority is “any two are 1”: B·C + A·C + A·B, 4 gates instead of 8. Click the inputs on any step: every step gives the same output, which is the point: each rule changes the formula, never what it does.

Algebra works, but you have to spot which rule to apply where, and it’s easy to stop before the formula is as small as it can be.

5 · Karnaugh maps

In 1953 Maurice Karnaugh, at Bell Labs, found a way to make the spotting visual. Arrange the truth table in a grid so that neighbouring squares differ in exactly one input. Then the rule from section 4, “two terms that differ in one input merge into one without it”, becomes: two neighbouring 1s can be circled together.

The trick is the order of the labels: 00, 01, 11, 10, not 00, 01, 10, 11. Each step changes one bit (a Gray code), and so does the step from the end back to the start. So the map wraps round: the right edge neighbours the left, and the bottom the top, as if it were drawn on a doughnut.

Groups must be rectangles of 1, 2, 4 or 8 squares (powers of two), all 1s. A group of 2 drops one input, a group of 4 drops two, and so on: the bigger the group, the smaller its AND. Cover every 1 with as few, as large groups as possible, and the groups are the formula.

Click a 1 to circle the biggest group it belongs to; click it again for the next group that includes it, and again to remove it. The formula and its gate count follow your groups. Majority’s three groups overlap at A·B·C, just as the algebra copied it. Try NOT C: a group that wraps round (one group of four, across the edges) and the four corners (one group, $\bar{B} \cdot \bar{D}$ : the corners all neighbour each other round the wrap). To make your own, choose “your own” and set clicking to change the squares’ values. Show a smallest answer fills in the fewest groups, found by trying every set of the biggest groups.

The map only offers the biggest groups each square can be part of (a smaller group inside one never helps), and choosing among them is the real skill. Programs do it the same way, step by step: Willard Quine and Edward McCluskey’s method (1952–56) finds every biggest group by merging terms that differ in one input, then picks the fewest that cover every 1. That’s what this page runs to check your answers. Maps stop being practical beyond 5 or 6 inputs, and exact minimisation gets very slow for many inputs, so the tools that design real chips use clever approximations instead.

6 · Don’t-cares

Back to the display. Inputs 10 to 15 will never arrive: the circuit only ever receives digits. So on those rows, the output doesn’t matter, and the designer can choose whatever makes the circuit smallest. They’re don’t-cares, marked × on the map, and they can join a group or be left out, whichever helps.

Pick a segment. The map has its 1s (the digits that light it) and, if Use the don’t-cares is ticked, ×s for 10 to 15; the groups are the smallest answer, and the circuit below is built from them. Segment e lights for 0, 2, 6 and 8: 9 gates from its truth table, 7 simplified, and with don’t-cares just $\bar{B} \cdot \bar{D} + C \cdot \bar{D}$ , 5 gates. All seven segments take 84 gates from their truth tables, 60 simplified, and 39 with don’t-cares. The display beside the map is driven by these simplified circuits; click the circuit’s inputs to change the digit. Every digit is still right. But try 10 to 15 with don’t-cares on: 13 comes out as a 5, 14 as a 6, and 11, 12 and 15 as 9s, whatever the groups happened to include.

A real display driver is exactly this kind of circuit, in one small chip (the 7447 and its relatives were the classic ones). And notice the trade: the don’t-cares saved gates by deciding, silently, what the display shows for inputs nobody expected. If one ever does arrive, by a fault or a bug, the result is whatever fell out of the simplification. Designers have to remember what they didn’t care about.

7 · Two building blocks: the decoder and the multiplexer

Some combinations of gates turn up so often they have names. Two of them are everywhere in a processor.

A decoder turns a number into “that line on”. Two input bits can say 0 to 3, and a 2-to-4 decoder has four outputs, exactly one of which is on: the one numbered by the inputs. A processor uses decoders to pick things by number: which memory chip an address belongs to, which register an instruction names.

A multiplexer (a mux) does the reverse kind of job: a number chooses which of several inputs gets through to the output, like a rotary switch worked by bits. A processor uses them wherever one of several values has to be chosen: which register feeds the adder, whether the next instruction comes from the next address or from a jump.

Click S1 and S0 (worth 2 and 1). In the decoder, each AND matches one of the four numbers, so exactly one output lights. The multiplexer is the same four ANDs, each with one data input added, ORed together: the selected AND passes its data input through, and the other three are held at 0. Click D0 to D3 and see that only the selected one makes any difference.

Both are sums of products, built straight from their truth tables, and neither can be simplified any further.

Summary

Binary counts with two digits: each place is worth twice the one to its right (1, 2, 4, 8, …), and each extra bit doubles how many numbers there are.
Write A·B for AND, A + B for OR, and $\bar{A}$ for NOT: Boolean algebra.
Any truth table becomes a circuit as a sum of products: one AND per row whose output is 1, ORed together. It always works, and is usually far bigger than it needs to be.
Simplifying keeps the function and drops gates. In algebra, the key rule is that two terms differing in one input merge without it ( $\bar{X} \cdot Y + X \cdot Y = Y$ ); De Morgan’s laws turn NOT-AND into OR-of-NOTs and back.
A Karnaugh map puts the truth table in Gray-code order, so merging becomes circling neighbouring 1s in groups of 1, 2, 4 or 8, round the edges too. Fewest, largest groups give the smallest sum of products.
Don’t-cares (inputs that never happen) can be grouped or not, whichever helps: the display’s seven segments shrink from 84 gates to 39. But the circuit still does something with those inputs.
A decoder turns a number into one line on; a multiplexer lets a number choose an input. A processor is full of both.