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. And one more thing. Due to the computational nature of this episode, you might want to visit the transcript page found at intermation.com to download the episode worksheet.
In Episode 6.01 – Introduction to Karnaugh Maps, we made the rather obvious statement that a box drawn on a piece of paper has four sides. This was said to bring home the fact that four boxes or cells could be placed adjacent to this box in a Karnaugh map. Remember that the power of a Karnaugh map lies in how it rearranges the truth table so that adjacent cells represent rows that differ by the value of only one input variable, a variable that will drop out of the final product. Since there are four sides to a square cell, then each of the four adjacent cells would represent each of the four input variables that could change.
In Episode 6.01, we focused on the three-variable Karnaugh map, which means that each cell only has three cells adjacent to it resulting in a Karnaugh map with two columns and 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. Remember that we must use the Gray code sequence so that adjacent cells from top to bottom differ only by a single variable. It also means that the cells in the bottom row of the Karnaugh map are considered adjacent to the top row, since the top row where A equals 0 and B equals zero differs only by A from the bottom row where A equals 1 and B equals zero.
In this episode, we are going to double the size of the three-variable Karnaugh map so that we can create simplified sum-of-products expressions for four-variable truth tables. To do this, we are going to add two more columns making our Karnaugh map four-by-four with sixteen cells – the same amount as the number of rows in a four-variable truth table. The four columns represent the four different patterns of the inputs C and D, and just like the rows representing A and B, these columns need to be numbered using the two-bit Gray code sequence. Remember that due to the Gray code numbering of the rows and columns of the Karnaugh map, the outputs of the truth table do not map in order to the cells of the Karnaugh map. We will need to exercise care when mapping a one from a row of the truth table to a cell of the Karnaugh map.
Let’s begin by converting a sample truth table to this four-variable Karnaugh map. Our truth table will have ones in the third, eighth, ninth, eleventh, and sixteenth rows. We are going to describe where each of these five ones goes in the Karnaugh map, fill in the rest of the cells with zeros, identify the pairs that will simplify, and create our sum-of-products expression. As with Episode 6.01, it may help to keep the worksheet for this episode handy.
Since there’s a one in the third row where A equals zero, B equals zero, C equals one, and D equals zero, we need to place a one in the cell of the Karnaugh map in the first row where A equals zero and B equals zero, and the fourth column where C equals one, and D equals zero. That’s going to be the cell in the top right corner. Next, the one from the eighth row of the truth table maps to the cell in the Karnaugh map representing A equals zero, B equals one, C equals one, and D equals one. This cell is located in the second row where A equals zero and B equals one, and the third column where C equals one, and D equals one.
Next, let’s place the one from the row where A equals one, B equals zero, C equals zero, and D equals zero. This one will map to the cell in the bottom left corner of the Karnaugh map where the row represents A equals one and B equals zero and the column represents C equals zero and D equals zero. The fourth one to map from the truth table is the one in the row where A equals one, B equals zero, C equals one and D equals zero. This one goes in the cell in the lower right corner of the Karnaugh map where the row represents A equals one and B equals zero and the column represents C equals one and D equals zero. The last one to map to the Karnaugh map is the one from the bottom row of the truth table where all four inputs equal one. Due to the Gray code sequence, this maps to the third row and third column of the Karnaugh map. All of the remaining cells of the Karnaugh map get the zeros corresponding to the remaining rows of the truth table.
Okay, now comes the time when we see which cells containing ones can be combined into a single simplified product. As a side note, our next episode will show how groups of four, eight, or sixteen cells will also generate a single product. For this example, however, we will be limited to just pairs of cells.
Let’s start with the most obvious pair, the pair of adjacent cells in the second and third rows of the third column. These cells represent the truth table rows A equals zero, B equals one, C equals one, and D equals one and A equals one, B equals one, C equals one, and D equals one. The input signal levels for these two cells differ only by A. This means that as long as B equals one, C equals one, and D equals one, we output a one regardless of what A equals. This gives us the product B AND C AND D. Note that in the truth table, these two rows had seven rows between them, yet in the Karnaugh map, they ended up next to each other revealing the simplification.
Okay, do we have any other adjacent cells? Well, there are two more pairs, but they are not as obvious as the first pair. Remember that Gray code is cyclic, which means that a cell on the top row is considered adjacent to the cell in the same column on the bottom row and that a cell in the left column is considered adjacent to the cell on the same row in the right column. That means that the top right cell, which contains a one in our Karnaugh map, is adjacent to the bottom right cell, which also contains a one. The top right cell represents A equals zero, B equals zero, C equals one, and D equals zero, while the bottom right cell represents A equals one, B equals zero, C equals one, and D equals zero. Once again, the input signal values for these two cells differ only by A. This means that as long as B equals zero, C equals one, and D equals zero, we output a one regardless of what A equals. This gives us the product B-bar AND C AND D-bar. These two rows were also separated by eight positions in the truth table showing how helpful the Karnaugh map can be when it comes to identifying products to simplify.
The bottom right cell is also adjacent to the bottom left cell. The bottom left cell represents the row of the truth table where A equals one, B equals zero, C equals zero, and D equals zero. In this case, the two cells differ only by the input C, which means C drops out leaving a product involving A, B, and D. Since we want B equal to zero and D equal to zero, these two inputs need to be inverted giving us the product A AND B-bar AND D-bar. This gives us the final simplified sum-of-products expression for the truth table: B·C·D + B·C·D + A·B·D (read B AND C AND D OR-ed with B-bar AND C AND D-bar OR-ed with A AND B-bar AND D-bar).
Another thing that this particular Karnaugh map did for us was show that we could use the cell in the bottom right twice to simplify products. When simplifying by hand, it would have been necessary to duplicate the product A AND B-bar AND C AND D-bar so that it could have been combined with the product A-bar AND B-bar AND C AND D-bar to get B-bar AND C AND D-bar and combined with the product A AND B-bar AND C-bar AND D-bar to get the product A AND B-bar AND D-bar. The Karnaugh map made this easy to recognize.
By the way, there is such a thing as a two-variable Karnaugh map, but for the majority of two-variable truth tables, the solution is trivial. There are sixteen ways to populate the output or X column of a two-variable truth tables. If the X column is nothing but zeros, then X equals zero. If the X column is nothing but ones, then X equals one. That takes care of two of them.
There are four cases where the output column, X, has only a single row with a one in it. In this case, there is nothing to pair the one with, and the single product must include both inputs. If the 0-0 row is the only one with a one in it, then X equals A-bar AND B-bar. If the lone one is in the 0-1 row, then X equals A-bar AND B. The 1-0 row generates X equals A AND B-bar. Finally, a one in the bottom row is just the truth table for the AND of A and B.
There are four additional straightforward cases for the two-variable truth table. The first is where the output column, X, simply follows A. This would give us X equals A. The inverse of this would have X equal to one whenever A equals zero. The expression for this is X equals A-bar. X could also follow B giving us X equals B, or X could follow the inverse of B giving us X equals B-bar.
For the remaining six possible patterns, it might help to see the Karnaugh map. Note that a two-variable Karnaugh map is just a two-by-two grid with B defining the columns and A defining the rows. The top left cell maps to the truth table row for A equals zero and B equals zero. The top right cell maps to the truth table row for A equals zero and B equals one. The bottom left cell maps to the truth table row for A equals one and B equals zero. Lastly, the bottom right cell maps to the truth table row for A equals one and B equals one.
There are two cases where there are two rows in the truth table with ones, but those two ones don’t follow A, A-bar, B, or B-bar. The first of those cases is when there is a one in the top row of the truth table, A equals zero and B equals zero, and a one in the bottom row, A equals one and B equals one. When we map these to the Karnaugh map, we see that these two ones are not adjacent to each other. One one is in the top left cell of the map, while the other is in the bottom right cell. That means they will not combine to simplify. The resulting sum-of-products expression is A·B + A·B (read A-bar AND B-bar OR-ed with A AND B). As shown by the Karnaugh map, this expression cannot be simplified.
The last way that we can have two rows with ones in the two-variable truth table is the case when there is a one in the row for A equals zero and B equals one, and the row where A equals one and B equals zero. Note that this is the truth table for the exclusive-OR operation across two inputs. When we map this truth table to the Karnaugh map, we see once again, that the two ones are not adjacent to each other (one is in the top right cell of the map, while the other is in the bottom left cell). That means they will not combine to simplify. The resulting sum-of-products expression is A·B + A·B (read A-bar AND B OR-ed with A AND B-bar). This is the Boolean expression that represents the exclusive-OR operation, and it cannot be simplified.
There are four cases where there is a single zero in the output column of the two-variable truth table. Let’s pick one of them to simplify using a Karnaugh map: the one that has a zero in the top row where A equals zero and B equals zero. When transferred to the two-variable Karnaugh map, this gives us a zero in the top left cell, and ones everywhere else. The Karnaugh map is showing us two pairs of adjacent cells that will simplify. The first pair is the right column that is represented by B equals one. This pairing crosses both values of A, so A drops out of the product leaving only B. The second pair is the bottom row represented by A equals one. This pairing crosses both values of B, so B drops out of this product leaving only A. The final simplified sum-of-products expression becomes A OR B.
Note that this is a sum. In Episode 5.03 – The Product-of-Sums Expression, we showed how a single zero in a truth table can always be represented with a single OR operation where we use inverters to move the zero output to a different row. The Karnaugh map was able to demonstrate this for the two-variable truth table. The same can be done for the remaining three two-variable truth tables that have a single zero in the output column.
In our next episode, we show how the Karnaugh map can be used to combine more than just two rows of the truth table into a single product. We can actually combine groups of four, eight, or even sixteen. 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.