Click here to download the episode worksheet.
Welcome to the Geek Author series on Computer Organization and Design Fundamentals. I’m David Tarnoff, and in this series, we are working our way through the topics of Computer Organization, Computer Architecture, Digital Design, and Embedded System Design. If you’re interested in the inner workings of a computer, then you’re in the right place. The only background you’ll need for this series is an understanding of integer math, and if possible, a little experience with a programming language such as Java.
Okay, raise your hand if you love simplifying Boolean expressions. How about like? Tolerate? That many, huh? Well there’s good news for the majority out there. In this episode, we’re going to introduce a tool that will do the heavy lifting for us. The Karnaugh map is a graphical tool, that when used correctly, can reveal to us a most simplified sum-of-products expression. And yes, I did say graphical, so for those of you listening to the audio version of this episode, I’ll wait here while you download the episode worksheet found at intermation.com. Go on…I’ll wait. <insert elevator music here> Okay, welcome back.
Let’s look at a three-input truth table with ones in the third row (0-1-0), the fifth row (1-0-0), the seventh row (1-1-0), and the eighth row (1-1-1). Using the method presented in Episode 5.01 – The Sum-of-Products Expression, we can convert this truth table to a Boolean expression by creating a product for each row with a one output.
To get a product that generates a one in the third row, where A equals zero and B equals one and C equals zero, we need a product A·B·C (read A-bar AND B AND C-bar). To get a product that generates a one in the fifth row, where A equals one and B equals zero and C equals zero, we need a product A·B·C (read A AND B-bar AND C-bar). For the seventh row, we need a product A·B·C (read A AND B AND C-bar). And the bottom row is just a product of all three inputs, A·B·C (read A AND B AND C). OR-ing these four products together gives us the sum-of-products expression A·B·C + A·B·C + A·B·C + A·B·C (read A-bar AND B AND C-bar OR-ed with A AND B-bar AND C-bar OR-ed with A AND B AND C-bar OR-ed with A AND B AND C).
Nice, but it isn’t simplified. Episode 5.01 also showed how the simplification of a sum-of-products expression typically involves finding two products that differ only by an inverse on one of the inputs. Using the distributive law, we pull all the common inputs from these two products so that we have a product AND-ed with the sum of an input OR-ed with its inverse. Anything OR-ed with its inverse equals one, and that one drops out leaving only the common product.
For example, the products from the third and seventh rows differ by only A and A-bar. If we pull B and C-bar out of those two products, we get B·C·(A + A) (read B AND C-bar AND-ed with the sum of A-bar OR A), which simplifies to B AND C-bar. The same can be done with the fifth and seventh rows, which differ by just B-bar and B, to get A·C·(B + B) (read A AND C-bar AND-ed with the sum of B-bar OR B), which simplifies to A AND C-bar. Lastly, the products from the seventh and eighth rows differ by only C-bar and C. Together, they can be simplified to A·B·(C + C) (read A AND B AND-ed with the sum of C-bar OR C), which simplifies to A AND B.
Notice that all three of these product simplifications include the product from row seven: A·B·C (read A AND B AND C-bar). That means that to simplify the whole expression, we need to make three copies of this product, one to be combined with each of the other three terms. How did we see this? Well, “we” have been doing this for a while, and experience helps us see things that the new comer to Boolean algebra might not notice so quickly. There is, however, a graphical tool we can use to help anyone physically see these connections: the Karnaugh map.
The row pairs of the truth table that merged into simplified products differ by only a single input value. For example, the third row, 0-1-0, and the seventh row, 1-1-0, both have B equal to one and C equal to zero, but A can be whatever it wants to be. This defines the product B AND C-bar. The fifth row, 1-0-0, and the seventh row, 1-1-0, differ by just B, so as long as A equals one and C equals zero, we output a one. This gives us the product A AND C-bar. Lastly, the seventh and eighth rows differ by just C giving us the A AND B term. The Karnaugh map is designed to take advantage of this method of simplification by rearranging the truth table so that these row pairs are next to each other in a grid of cells. This will allow us to quickly identify which inputs drop out of each product, and which products can be merged.
To describe the way it works, let’s build one of these two-dimensional grids cell-by-cell from a truth table. This isn’t the way a Karnaugh map is typically drawn. We’re doing it this way to show how the Karnaugh map works. Using the truth table presented above, let’s start with the cell that each of the products shared, the seventh row where A equals one, B equals one, and C equals zero. We draw a box to represent this row, and inside this box, we place the one that is the truth table output for this row. Being a box, it has four sides, which means that four cells could be placed adjacent to this box. How do we select which boxes get placed next to the first box? Well, we place boxes adjacent to the first box that represent rows that differ by a single input variable. For the three-input truth table, that means we need to have three cells adjacent to the first cell. The fourth side will be left empty until we move to four input variables.
The first box that we will put adjacent to the one representing 1-1-0 is the one where A changes from a one to a zero. This box will contain the output shown in the truth table for row 0-1-0, the third row, and we will place it adjacent to the top edge of our starting cell. It too has a one it in, and since the Karnaugh map shows two ones next to each other, we know that we’re going to get to combine two products into one product and have an input term drop out. We will explain later why we’ve placed the second cell above the first one.
The next cell we will place adjacent to 1-1-0 is the one representing the truth table row where B changes from a one to a zero. This will be the fifth row, 1-0-0, and we are going to place it below the first cell. Once again, this cell has a one in it, and since the Karnaugh map shows two ones next to each other, we know we are going to get two products to combine into a single product with one input term dropping out, in this case, the input B, to give us A AND C-bar.
The next adjacent cell to place is for row 1-1-1, where C has changed from a zero to a one. This cell will get placed to the right of our starting cell. Since the row in the truth table for 1-1-1 has a one in it, this cell will also get a one. Being adjacent to 1-1-0, we see that the cells can be combined to create the product A AND B.
At this point, it may not be clear how we are going to get the correct cells adjacent to one another, so let’s take a step back and see what we’ve put together so that we can figure out where to put the cells for the remaining rows of the truth table. After that, we will present the process for quickly drawing the three input Karnaugh map.
We’ve placed four cells, three of which are in a column representing the rows 0-1-0, 1-1-0, and 1-0-0. Note that the input C is zero for all three cells, and that A and B are 0-1, 1-1, and 1-0 when going from top to bottom. Note that the values for the inputs A and B follow the last three patterns of the two-bit Gray code sequence. Remember Gray code? Well, way back in Episode 2.09 we presented this alternate method for ordering the patterns of ones and zeros such that exactly one digit position changes when going from pattern to pattern through the sequence. The two-bit Gray code sequence is 0-0, 0-1, 1-1, and 1-0. The sequence is also cyclic in that the last value and the first value also differ by only one of the digits.
Appending the input C equals zero to A equals zero and B equals zero, we discover the fourth cell to place in this column, the cell representing the row 0-0-0. This cell can be placed either at the top or bottom of the column. Let’s put it at the top, and inside of that cell, we write a zero to represent the output value for that row of the truth table. Now what we have is a column of cells representing the truth table rows 0-0-0, 0-1-0, 1-1-0, and 1-0-0 with a cell coming off to the right of 1-1-0 which represents the truth table row 1-1-1.
There are three more rows of the truth table that have yet to be placed in the Karnaugh map. All three of these have C equal to one: 0-0-1, 0-1-1, and 1-0-1. It just so happens that there is a corresponding cell already in the Karnaugh map for each of these input patterns with C equal to zero: 0-0-0, 0-1-0, and 1-0-0. Placing each C equals one cell to the right of the corresponding cell with C equals zero gives us our final Karnaugh map for the three input variables. All three of these newly placed cells contain the zeros from the truth table.
Once again, note that the bottom row, which represents the truth table rows where is A is one and B is zero, differ only by A when wrapping around to the top row, where A is zero and B is zero. This trait means that the bottom and top rows are actually adjacent to each other.
So the final three-input Karnaugh map looks like this. There are two columns of four rows. The left column represents the four rows of the truth table where C equals zero while the right column represents the four rows of the truth table where C equals one. The rows are identified by the four possible binary patterns of A and B ordered in the two-bit Gray code sequence: 0-0, 0-1, 1–1, and 1-0.
For the example truth table, the values in the cells of the top row representing A equals zero and B equals zero are zero and zero. The values in the cells of the second row representing A equals zero and B equals one are from left to right one and zero. The values in the cells of the third row representing A equals one and B equals one are both one. In the bottom row representing A equals one and B equals zero, the values from left to right are one and zero.
The key is that we have three adjacent pairs showing, each overlapping the cell for A equals one, B equals one, and C equals zero. The adjacent pair that includes the 0-1-0 cell combines with the 1-1-0 cell to give us the product B AND C-bar. The adjacent pair that includes the 1-0-0 cell combines with the 1-1-0 cell to give us the product A AND C-bar. The adjacent pair that includes the 1-1-1 cell combines with the 1-1-0 cell to give us the product A AND B.
Although this episode may have been painfully slow, practice will make mapping a truth table to the Karnaugh map trivial. In our next episode, we will start with a new truth table, convert it to a Karnaugh map, then show how to make a most simplified sum-of-products expression from it. Later in the series, we will show how more than two cells can be combined to merge more products and force more inputs drop out. After that, we will extend our Karnaugh map to four input variables, the upper limit for Karnaugh maps to remain two-dimensional.
For episode transcripts, worksheets, links, or other podcast notes, please visit us at intermation.com where you will also find links to our Instagram, Twitter, Facebook, and Pinterest pages. Until the next episode remember that while the scope of what makes a computer is immense, it’s all just ones and zeros.