Karnaugh Maps
February 11, 2021There are some seriously neat ideas that underly Karnaugh maps.
Their purpose is to solve the following problem: given a truth table, can you find a boolean function with the same inputs and outputs as the table? And furthermore, can you find the simplest possible function to do that?
For example, given the table
| A | B | C | Out |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
We want a function that takes three inputs, A, B, and C, and outputs what's in the Out column. How can we find that function?
The first observation to make is that a boolean function can only output a 0 or a 1. One way to express any boolean function, then, is to explicitly list what combinations of its inputs will result in a 1. In our case, A, B, and C are those inputs, so we can just list what A, B, and C values we want to output a 1.
For example, if you give me (0, 0, 0) for inputs to the table above, we can see from the first row that the output is a 1. (0, 1, 1) and (1, 0, 0) are the other inputs that result in a 1 as well, as seen in the fourth and fifth rows of the truth table. So one way to write this function out is to say: "If you give me (0, 0, 0) or (0, 1, 1) or (1, 0, 0), then the function is true."
Now our job is to convert those words into a boolean function. How can we write a function that knows if you gave it (0, 0, 0) or (0, 1, 1) or (1, 0, 0)? As humans we can just look at whatever input we're given and see if it matches, but circuits don't have eyes (and we care about Karnaugh maps for building circuits), so we need to be able to write out a mathematical expression to do this.
(I use the following notation for the algebra, we'll need it in a second: AB means A AND B, A'B means NOT A AND B, and A + C' means A OR NOT C)
Let's start with just one of those inputs. What is a function that evaluates to true if and only if it was passed in, say, (1, 0, 0)? If we were to write that in a programming language, we could express this as A == 1 && B == 0 && C == 0 We can be a little more concise if we express it as a boolean algebra statement. A == 1 is equivalent to just saying A. If A is equal to 1 the expression evaluates to 1, and if A is 0 the expression evaluates to 0. Similarly, B == 0 is the same as writing B', for the opposite reason. If B is 1 it evalutes to 0, and if B is 0 it evaluates to 1.
So to express the function that evaluates to true if and only if it was passed (1, 0, 0), we need only write AB'C'. This expression can only possibly be true for the inputs (1, 0, 0).
Expressions like these are called minterms. A minterm is just the jargony name for the concept we were just thinking about: an expression that evaluates to true for exactly one input.
If we string a bunch of minterms together, joined by ORs, we can create the very function we wanted earlier. Because each minterm evaluates to true for exactly one input, ORing together multiple minterms allows us to create functions that evaluate to true if the input matches any of the minterms that make up the function.
For example, if we take the minterms for each of the 3 inputs we were thinking about earlier, we get A'B'C' + A'BC + AB'C'. So if the input satisfies any of the 3 minterm expressions, the whole function will result in a 1.
And that is a perfectly comprehensive way to write out that table as a function. The function can only output 1s or 0s. If we just list all of the ways it should output a 1, then we're done. All other inputs will be a 0, and we get the correct function. Once we've done that listing out, the function is then said to be in its canonical disjunctive normal form.
I think the idea of writing functions out in that way is spectacularly clever. I don't think I would have come up with it. Let's recap the idea:
- A boolean function can only output either a 0 or a 1
- If you just list out the possible inputs that produce a 1, you can turn any truth table into a function by just checking if the input to a function is among that list of inputs that should output a 1
-
The way that we actually do that checking is by taking each input and creating a boolean expression that
uniquely
evaluates to true for only those inputs
- So if the input is (1, 0, 1), then you convert that to AB'C, which will only ever be true if A and C are 1, and B is 0
- It is absolutely impossible to make AB'C output 1 for anything other than that one specific input
- Once you take all of those expressions, ORing them together creates a statement that evaluates to true if and only if the function's input that you give it is within that list of inputs that should output a 1.
That's all super neat. The final level on top of that is that listing every single input that maps to a 1 can get pretty tedious, and if you are building a circuit to match that function, you could be using a ton of gates to compute all of those minterm expressions.
It's possible that following that method could produce a circuit, or function, that is unnecessarily large. For example, let's look at another table. When we create the function to match this table we will see that it is needlessly complex.
| A | B | C | Out |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
After we do the "enumerate all inputs that should output 1" method, we get the following function: A'B'C + A'BC + AB'C + ABC.
You can factor out the C in that expression to get C(A'B' + A'B + AB' + AB). That parenthetical expression will always be true. One way to justify that is to observe that no matter what A or B are, one of those terms in the parenthesis will be a 1, and because all the terms are OR'd together, the whole parenthetical expression will evaluate to true. C AND True evaluates to C, so we could have just written that instead. No long list of terms required. However, to figure that out, we needed to write out all the minterms and do some algebra to manipulate the function before spotting that it can be reduced. A Karnaugh map will help us automate the process we just did. Instead of doing the two step process of making that normal form function and then algebraically reducing the function down, we can use a Karnaugh map to skip straight to a reduced function.
Let's draw out a Karnaugh map first and then explain it.
We start by making a table with the same number of cells as rows in the truth table. Eventually, each row from the truth table will get its own cell in the Karnaugh map.
(If you have an even number of inputs, the table will be square, if you have an odd number of inputs, you make a rectangle that is as close to a square as possible)
After that, you designate the axes of the table, and label each row and column in a very specific way (we'll get to why later).
| AB | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C |
|
The letter labels across the top mean that the columns represent the inputs A and B, and the inputs along the side are for C.
Why do you combine A and B together? It's an arbitrary choice to pick A and B. We could have picked any two inputs, but we do need to combine some variables together. If we gave each variable its own axis, we would need a 3D map, and if we had 6 variables, we would need a six dimensional map!
Now we populate the map with values from the truth table. Each cell corresponds to a row from the truth table, so the top left corresponds to the row with inputs (0, 0, 0), and the one to the right of it is from inputs (0, 1, 0), and so on. You figure this out by looking at the numeric labels along the columns and rows. The top left is in the AB = 00 column, and the C = 0 row, thus your inputs are (0, 0, 0), which lives in the first row of the table.
The value in each cell is what is outputted from the truth table when you put in the corresponding input from the map. So the top right has A = 1, B = 0, and C = 0. The truth table with the row that has those input values outputs a 0, so we write a 0 in that cell.
| AB | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C |
|
We can now instantly see that the output of this function is 1 whenever C is 1. Just looking at this map could have let us figure out that we could express that function before by just writing C. However, that was a simple example, let's invent a totally different function so we can do some real work with Karnaugh maps.
| AB | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C |
|
If this is our map, created from some random truth table, we need to figure out the corresponding function.
To start, we're going to use the minterm strategy to create an expression for this function. We look at the map and see what cells have 1s, thus the function should output a 1 for the corresponding input, so we create a minterm for that input. However, by using this map because we can glean some useful information about how to simplify some of the minterms.
When two cells are adjacent to each other in the map (not diagonally), it means that there is something in common between them. (This is a result of the specific way we labeled the rows and columns). To see this, look at the fourth column (the one labeled 10). There are 2 adjacent 1s in that column. This tells us that when A = 1 and B = 0, the value of C actually doesn't matter, because whether C is 0 or 1, so long as A = 1 and B = 0, the value is true. So we can create a minterm of sorts, AB', which will evaluate to true if A=1 and B=0, and doesn't care about what C is. This is the same as writing AB'C + AB'C', which is what we would have gotten by writing out explicit minterms. Later on we would have algebraically reduced that expression into AB'. By using a Karnaugh map, we can find places where ORing together those minterms can be reduced, and automatically do it without much work. It very conveniently allows us to skip steps.
As we find these groups of adjacent 1s, we can create more simplified expressions and OR them together to get an expression for the function that is already reduced for us.
There's another pair of adjacent 1s is in the first row of the map we just worked with. We see that A and C are constant, and changing B doesn't affect the output. So when C = 0 and A = 0, no matter what B is, the output will be 1. So the reduced minterm expression that evalutes to true for those two 1s is A'C'. No B term required.
So when we OR that together with the other simpilifed expression we get AB' + A'C', which is not only a function that matches the map, but is also the most reduced form possible.
I've skipped a crucial part of the explanation so far. How did we label the rows and columns?
The key idea behind Karnaugh maps that let us eyeball these simplifications is that two adjacent 1s have a variable they don't care about. For example, if ABC and ABC' are both 1, they will be adjacent in the map, and the value of C doesn't matter, i.e we can factor out the AB to get AB AND (C OR C'), which is equivalent to AB.
We label the rows and columns by gray code, as we want adjacent cells to be separated by only a single changed variable. Doing this allows us to find variables we don't care about. Gray code is specifically designed so that consecutive gray code values are separated by only 1 bit. So we begin the labeling with 00, and then add 1 to get 01, then we go to 11, which changes only the leftmost bit, and then we go to 10. Each of those changes is only a single bit. That way, adjacent values in the map mean that the inputs are identical for all but one variable. That way, when 1s are next to each other, we know that they don't depend on that one variable that changes, and we can eliminate it from the expression.
However, if you have a row of 3 1s, then there is a change of two variables between the first and the third 1. Because two variables change, we can't get any meaningful information out of those 1s being adjacent. This results in us not caring about anything other than groups of 2 adjacent 1s.
However, there is one exception. If you have a line of 1s that spans every value of two (or more) variables, then it's totally possible you just have more than 1 variable you don't care about. For example, consider the following map:
| AB | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C |
|
There is a row of 4 adjacent 1s, across the whole first row. So no matter what A or B are, so long as C is 0, the output is 1.
If there were 3 variables, that would need to be 8 1s long. 4 variables requires 16, and so on. As a general pattern, you can only get useful information in groups of 1s that have an amount of 1s that is a power of 2. If your group is 2n 1s long, it represents that you don't care about n variables. And if n = 0, then you end up doing the exact same process as we did earlier! You're just enumerating all possible outputs of 1 with no simplification.
To recap:
- Write out a square (or as close to square as possible) table with a number of cells equal to rows in your truth table
- Number each row and column in gray code, so that each adjacent cell's input differs by only one variable
- Fill in values in the cell from the table
- Find adjacent groups of 1s, with length equal to a power of 2
- Write an expression that is true for any member of that group by omitting the variables you don't care about, and forcing the constant inputs to be 1s. Much like creating a minterm.
- OR together all of the expressions you've created, and you have a neatly reduced function
And the key ideas behind the map are that:
- Adjacent cells have inputs that differ by only one variable
- If you have adjacent cells with 1s in them, it means that those 1s can be expressed without the variable that changes between those two adjacent cells
- By writing out those expressions, we don't include any useless information, so we get a simplified expression for the function
We'll finish up with one problem to demonstrate all of this.
Given the following truth table, find a function that matches the table.
| A | B | C | Out |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
We start by creating our Karnaugh map. There are 8 rows in the table, so we will create a 2x4 map (it's the closest we can get to a square), with AB as the column inputs and C as the row input.
| AB | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C |
|
After this, we find groups of adjacent 1s with group size equal to a power of 2.
| AB | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| C |
|
The two groups we'll use are highlighted. Notice that we have to use two groups. If we included all 4 1s into a single group, we would change more than a single variable per group. If they were all in a line this would be fine, because 4 is a power of 2 and all cells are adjacent, but because they are not all on the same line, we change too much information within the group to get anything useful out of it.
The yellow group changes the value of A between them, which means that they are independent of A. We can identify those two cells with the expression BC', so for B=1 and C=0, the output will be 1.
The blue group only changes the value of B, so the expression there is A'C, so that any input for A=0 and C=1 will result in 1.
By ORing those two together, we get BC' + A'C, which gives us a completely simplified expression of the function.