Chapter 8. Circuits: Simplifying

Logic gates are physical devices, built using transistors. At the heart of the computer is the central processing unit (CPU), which includes millions of transistors.

The designers of the CPU worry about two factors in their circuits: space and speed. The space factor relates to the fact that each transistor takes up space, and the chip containing the transistors is limited in size, so the number of transistors that fit onto a chip is limited by current technology. Since CPU designers want to fit many features onto the chip, they try to build their circuits with as few transistors as possible to accomplish the tasks needed. To reduce the number of transistors, they try to create circuits with few logic gates.

The second factor, speed, relates to the fact that transistors take time to operate. Since the designers want the CPU to work as quickly as possible, they work to minimize the circuit depth, which is the maximum distance from any input through the circuit to an output. Consider, for example, the two dotted lines in the following circuit, which indicate two different paths from an input to an output in the circuit.

The dotted path starting at x goes through three gates (an OR gate, then a NOT gate, then another OR gate), while the dotted path starting at y goes through only two gates (an AND gate and an OR gate). There are two other paths, too, but none of the paths go through more than three gates. Thus, we would say that this circuit's depth is 3, and this is a rough measure of the circuit's efficiency: Computing an output with this circuit takes about three times the amount of time it takes a single gate to do its work.

The sum of products technique that we saw last time for converting a Boolean function into a circuit isn't too bad using these criteria. In terms of speed, the resulting circuit's depth is just 3 — or perhaps slightly more if you insist (as circuit designers will) that each AND and OR gate has just two inputs. But it does less well than we might hope in terms of space.

We'll now turn to investigating a technique for deriving smaller circuits for a truth table, without making any compromises in terms of depth.

8.1. Karnaugh maps

For Boolean functions with four or fewer inputs, the Karnaugh map is a particularly convenient way to find the smallest possible sum-of-products expression. It is a simple process: We convert the truth table to a matrix as we'll see later, then we determine how best to cover the 1's in the matrix with a set of rectangles; each rectangle will correspond to a term in our sum of products expression.

Let us start with the truth table we saw earlier, when we derived Figure 7.4.

xyzout
0000
0011
0101
0110
1000
1010
1101
1111

Since there are eight rows to this table, we will convert it into a 2×4 matrix. (If there were 4 rows, it would be a 2×2 matrix. And if there were 16 rows, it would be a 4×4 matrix.) One of the variables will be represented along the vertical axis, and the other two variables along the horizontal axis. Note how the variable combinations along the horizontal axis do not go in the traditional order of 00-01-10-11, but instead 00-01-11-10. This is important for the Karnaugh map technique to work.

Having created that matrix, we now fill it by copying the corresponding output values into the appropriate row. The truth table's last row, for example, maps to the second row (since x is 1 in that row) and the third column (since y and z are both 1 in that row). The output in the truth table's last row is a 1, so we place a 1 at that location.

Now we look for the smallest set of rectangular regions that cover all 1's in our table but no 0's. The height and width of each rectangle must be a power of two (so the possibilities are 1×1, 1×2, 1×4, 2×1, 2×2, 2×4, 4×1, 4×2, and 4×4). In our example, we can cover all the 1's using just three rectangles.

Each of the regions will correspond to a term in our sum of products expression. The pink regions at far right, for instance, under the 10 column, corresponds to the term where y is 1 and z is 0, but x could be either 0 or 1. The corresponding term, then, would be y z. Putting together the terms from the three regions together, we arrive at:

x y z + y z + x y

This can be translated into the circuit of Figure 8.1. Notice how this circuit has only 7 gates in comparison to the 10 gates of Figure 7.4.

Figure 8.1: A simplified circuit equivalent to Figure 7.4

8.2. A more complex Karnaugh map

Another example will illustrate some additional features of a Karnaugh map. This time, we will work from a truth table over four inputs.

wxyzout
00001
00010
00101
00110
01001
01010
01101
01110
   
wxyzout
10001
10010
10101
10111
11000
11010
11101
11111

Since we have 16 rows in this table, we'll start with a 4×4 matrix. Each row will represent a combination of values for the first two variables' values, and each column will represent a combination of the last two variables' values.

In determining the regions, we introduce a new rule: Regions can wrap around the edges of the matrix. (This rule applies for three-input functions, too. It just didn't happen to appear in our previous example.) Using this fact, we can cover the 1's using just three rectangles.

The simplest region (drawn in yellow) is in the lower right; it corresponds to the term w y. The upper 2×2 region (drawn in pink) wraps from the last column around to first column; it corresponds to the term w z. There is another region (draw in blue) that wraps between columns and also between rows, so it covers all four corners of the matrix; it corresponds to the term x z. . Putting these three terms together, we arrive at our simplified Boolean expression:

w y + w z + x z

Notice that when you draw your rectangles, you want to use as few as possible: Each rectangle will correspond to an additional AND gate. In our above example, we omitted a possible rectangle that covers the last column, because it wouldn't cover any 1's that weren't already covered.

Moreover, you want each rectangle to cover as many 1's as possible, even if it isn't necessary, because larger rectangles lead to terms containing fewer variables. In our earlier example, we could have drawn the upper pink rectangle as a 1×2 rectangle in the second row only. But then the second terms would have been w x z, which has one more variable in it than we used previously.

8.3. More logic gates and universality

Until now, we've dealt only with AND, OR, and NOT gates. Circuit designers often work with four other gates: NAND (not and), NOR (not or), XOR (exclusive or), and XNOR (not exclusive or). The NAND, NOR, and XNOR gates work simply as an AND/OR/XOR gate with a NOT gate after it — and they are drawn as an AND/OR/XOR gate with a small circle at its output. The XOR gate emits 1 when one or the other of its inputs is 1, but not when both are; that is, the case of two 1 inputs is excluded from the situation when the gate emits a 1. Figure 8.2 depicts the appearance of these gates and the truth table summaries.

Figure 8.2: More logic gates.

(a) NAND gate (b) NOR gate (c) XOR gate (d) XNOR gate
abo
001
011
101
110
abo
001
010
100
110
abo
000
011
101
110
abo
001
010
100
111

We haven't looked at these gates previously because they can all be built using AND, OR, and NOT gates. In fact, we've seen that every truth table has a circuit of AND, OR, and NOT gates that corresponds to it — we simply derive the sum of products expression (which has only AND, OR, and NOT operations) and then build the corresponding circuit. Because of this property, we call the combination of AND, OR, and NOT universal.

Somewhat more surprising is that the NAND gate alone is universal. To convince ourselves of this, we have only to show that AND, OR, and NOT can all be built using NAND gates alone. Figure 8.3 demonstrates the NAND-gate circuit corresponding to each of AND, OR, and NOT.

Figure 8.3: Building NOT, AND, and OR using NAND gates.

Because this is possible, we can build any circuit corresponding to any truth table using simply NAND gates. (The same holds for NOR gates.)