Content

Karnaugh Maps

We have already seen two methods for simplifying switching circuits. These are manipulation using the properties of Boolean algebra and the function approach that reduces the problem down to looking at values of the function at specific points. (Of course these two methods can be used together.) Karnaugh maps
(see https://en.wikipedia.org/wiki/Karnaugh_map and
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html#KMapsIntro)
are a third method that is more efficient than the function approach and which are often used for relatively small numbers of switches (or propositions). Once the number of switches gets past a certain point, however, computer algorithms need to come into play.

Example of a Karnaugh Map: The switching circuit for Voting for Three (see Q3) can be rewritten as

Table 9: Voting for three

$x$	$y$	$z$	Light
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

The Karnaugh map (K-map) of this is presented below. It contains all the information of the original table but that information is represented differently. The result is a decrease in the number of cells that need to be considered.

Table 10: an example of a K-map

$x$	$yz$
		00	01	11	10
	0	0	0	1	1
	1	0	1	1	1

Note:

• The entries 00, 01 etc. along the top of Table 10 represent the values of $y$ and $z$ together. So the entry in column 4 row 2 is the value for $x = 1, y = 1, z = 0$.
• The headings of the columns differ by 1 in each place as you move from left to right. (The same is true for rows regardless of how many rows there are.)
• The headings increase in an unnatural way in that they do not increase in the way that binary numbers would. However, this enables a term and its complement to be next to each other and so reductions of the form $w + w'$ are easier to spot and combine.
• K-maps can be produced for any number of switches or propositions. It is probably more efficient to divide the numbers so that about half are along the top and the rest down the side.

Now the entry in Table 10 in column 2 row 2, represent the value of $xy'z$ and the entry in column 3 row 2 represent $xyz$. But as these have both got a value of 1 (and in the disjunctive normal form) they give $xy'z + xyz$ which simplifies to $xz$. This always happens when two ones are next to each other in a K-map. From Table 10 above we can see that we could have combined $xyz$ with $xyz'$ to get $xy$. This happens whenever there are two adjacent ones in the same row or column. So working with columns the third column of Table 10 shows that $x'yz + xyz = yz$. As a result the switching circuit can be simplified to $xz + xy + yz$.

For groups of 1s that have area that is a power of 2, more substantial savings can be made in the simplification process

(see https://en.wikipedia.org/wiki/Karnaugh_map#Solution).

Next page - Answers to switching circuits