Karnaugh Maps – Introduction

This video is an introduction to Karnaugh maps. It assumes that you're already familiar with logic gates like AND, OR and NOT, and how these gates can be combined to produce more complex circuits. You should know about truth tables and how these can be used to describe the behaviour of logic circuits in terms of inputs and outputs. It's also assumed that you're familiar with some Boolean algebra, specifically how various rules can be used to simplify Boolean expressions, and therefore the role of Boolean algebra in circuit design. So what is a Karnaugh map, or a K-map as they're sometimes known? It's a special form of truth table which enables easier pattern recognition than a truth table does. It's a pictorial method of simplifying Boolean expressions. Good for circuit designs with up to four variables, that's four inputs. So let's look at an example. Here's a simple truth table with two inputs, or shall we say two variables. You should recognise this as the truth table of an OR gate. Column F contains the output value for each combination of input values A and B. Strictly speaking, this is the truth table for any combination of logic gates that behave in the same way as an OR gate. So we could say that this is the truth table of an OR function. That's why we've called the output column F. To construct the corresponding K-map, we draw a grid with one square for each row in the truth table. The possible input values for A are used as column headings across the top, and those for B as row labels down the left-hand side. These input values will act like coordinates for the output values. Now we can populate the K-map. We can see from the truth table that when A is 0 and B is 0, the output is 0. When A is 0 and B is 1, the output is 1. When A is 1 and B is 0, the output is 1. And when A is 1 and B is 1, the output is 1. Our K-map is ready for use. We'll see this particular one again later. Now let's talk about how a K-map can be used to derive the simplest possible Boolean expression. Here's another, different truth table, again with two variables A and B, but the outputs in column F are different this time. The corresponding K-map looks like this. To derive the simplest Boolean expression from the K-map, we're looking for the largest possible grouping of 1s. An expression can then be derived by inspecting this group. Here we can see that whenever there is a 1 in the group, the value of input A is 1. We can also see that the topmost 1 in the group corresponds to a value of 0 for input B, but the other 1 in the group corresponds to a value of 1 for input B. This means that the output is independent of the input value B, which makes B a redundant input. This grouping can therefore be expressed simply as A. The output of this function is A. Here's another example with two inputs. We've seen this one before. It's the truth table for an OR gate. But let's see how we can derive the Boolean expression by inspecting the K-map. Here's the corresponding K-map. A single group cannot be L-shaped, so what we have here are two overlapping groups of 1s. The 1s in the vertical group always match the input value A. The vertical grouping can therefore be expressed simply as A. The 1s in the horizontal group always match the input value B, so the horizontal grouping can be expressed as B. Hence, this K-map represents the expression A OR B. It is indeed the OR function. In this truth table, the output is always 1, regardless of the inputs. Here's the K-map, which matches this truth table. We can create one large group of 1s here. Clearly, the output is independent of all of the inputs. It is always 1. So the Boolean expression for this circuit is simply 1. Let's consider one more example with two variables. Here's the K-map, which matches this truth table. We have two groups here. The 1s in the vertical group are always the opposite of input A, so they are related to it. This group represents NOT A. The 1s in the horizontal group are always the opposite of input B, so this group represents NOT B. Hence, this particular K-map represents the function NOT A OR NOT B. You may have already recognised that this is the truth table of a NAND gate. Now let's look at some Karnaugh maps for functions which have three variables. This truth table has three inputs, or to put it another way, three variables. To construct a three-variable Karnaugh map, we could start by placing possible input values for one of them, in this example, A, in the column headings like this. Now we can have one row for each combination of values for the inputs B and C, starting with B equals 0 and C equals 0, then B equals 0 and C equals 1, now B equals 1 and C equals 1, and finally B equals 1 and C equals 0. We now have all of the possible combinations of inputs B and C included. You can see that as you scan down the row labels, each pair of input values for B and C differs from the next or the previous pair by only one bit. These are not sequential binary numbers. This is quite deliberate. Indeed, it's an essential aspect of the construction of a K-map with three or more variables. OK, now we can transfer data from the truth table to the K-map by using the input values as coordinates for the placement of output values. The K-map is now fully populated and ready for use. When we look for the largest possible groups of ones, we can see two overlapping groups here. There are some rules we must obey when it comes to grouping. One of these is that a group must be a horizontal or a vertical rectangle, or a square. More about these rules later. Suffice to say for now, we've obeyed them. Upon inspection, we can see that the tall vertical block of ones always matches the input value of A. So this expression includes A. And if you look carefully, you can see that the other block of ones always matches the input value B. Hence, this K-map represents the expression A or B. We could have constructed a different looking K-map from the same truth table. Both of these K-maps contain exactly the same information, but one of them is turned through 90 degrees. We've also combined the input values differently in the alternative version. This time, the input values for A and B are paired up, and are now acting as row headings. Again, you can see that as you scan across these row headings, each pair of input values differs from the next or the previous pair by only one bit. Looking for the largest possible group of ones, the uninitiated might decide that this is a candidate. But this breaks one of the rules. A group cannot contain six ones. It can only contain one, two, four, or eight ones, or to put it more generally, two to the power n ones. But we can have two overlapping groups of four. This is correct. Upon inspection, the ones in the group on the left always match the input value B. And the ones in the group on the right always match the input value A. So we arrive at B or A. The horizontally arranged version of the same K-map that we saw before has given us essentially the same result. From the vertically arranged version, we arrived at the expression A or B. And in case you were wondering, if we had created two groups like this, we would still arrive at the same conclusion, that this K-map represents the expression B or A. And two groups like this would yield the same result. But it's always best to create groups as large as possible. Here's a different example. Let's see what we can make of it. We have two groups of ones that obey the rules we've looked at so far. The ones in the long horizontal group are always the opposite of C. That is, they are not C. And the ones in the square block always match the value of input A. Hence, we have the expression not C or A. This example illustrates something we haven't seen yet. We have a small group of ones here. We can see that these ones correspond to an input value of 1 for A. And they also correspond to an input value of 1 for B. So this K-map represents the function A and B. Notice that when we're describing a single group of ones that's dependent on different input values, we use the AND operator to describe the relationship between the inputs. On the other hand, we've already seen that we use the OR operator to describe the relationship between different inputs in different groups of ones. This example illustrates a new rule for grouping ones together. We have a single group of four ones that wraps around the table. Imagine the table has been rolled up into a tube so that the top and bottom rows are now adjacent to each other. This type of group is allowed. We can see that where there are ones, sometimes A is 0 and sometimes it's 1. So the output of the circuit that this K-map represents is independent of A. Also, where there are ones, sometimes B is 0 and sometimes it's 1. So the output of the circuit that this K-map represents is also independent of B. But where there are ones, the value of C is always 0, the opposite of the output. So this K-map represents the function NOT C. Here's another example. Here we have another group of ones that wrap around the table. Where there are ones, A is always 1. And where there are ones, the value of C is always 0. But the output is independent of B. Remember, because of the table wrapping rule, there is only one group of ones here, so this K-map represents A and NOT C. To finish then, here's a summary of the rules for identifying groups in a K-map. A group must only contain ones, no zeros. A group can only be horizontal or vertical, not diagonal. A group must contain 2 to the power n ones, for example 1, 2, 4, 8. Each group should be as large as possible. Groups can overlap, and groups can wrap around a table. Every one must be in at least one group. And finally, there should be as few groups as possible.