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 showed that by converting a truth table to a Karnaugh map, we can identify pairs of products in an unsimplified sum-of-products expression that can be combined to create a single, simpler product. It turns out that we can go beyond combining just pairs of ones from truth table rows into a single product.
In a sum-of-products expression, the products, also referred to as implicants, identify the conditions where the expression outputs a one. The Karnaugh map gives us a mechanism to identify individual implicants that can be joined to create a simpler product. Take, for example, the simplified four-input sum-of-products expression A·B·C·D + A·C·D + A·B (read A-bar AND B AND C AND D-bar OR-ed with A-bar AND C-bar AND D OR-ed with A AND B-bar).
The output of the first implicant, A·B·C·D (read A-bar AND B AND C AND D-bar), is one only if A is zero and B is one and C is one and D is zero. Since this expression has been simplified, the one corresponding to this product would manifest itself in the Karnaugh map as a single cell containing a one with all adjacent cells containing zeros. If any of the neighboring cells contained a one, its product would have combined with the first product to create a simpler implicant.
The output of the second implicant, A·C·D (read A-bar AND C-bar AND D), is one if A is zero and C is zero and D is one. Since B is not included in this product, it can be whatever it wants to be, and hence, the Karnaugh map would place the two ones corresponding to these two rows adjacent to each other. Since the second column represents C equals zero and D equals one in the four-variable Karnaugh map, and the first and second rows are the rows where A equals zero in the Karnaugh map, the pair of cells that combine to create this product are in the first and second row of the second column.
Lastly, the output of the third implicant, A·B (read A AND B-bar), equals one as long as A is one and B is zero. Since neither C nor D is included in this product, they can be whatever they want to be. This one product combines the four implicants from the rows 1-0-0-0, 1-0-0-1, 1-0-1-0, and 1-0-1-1. Examination of the expression shows that this product cannot be absorbed or simplified with any other products meaning that it is in its most simplified form. We refer to this as a prime implicant. When transferring the four rows represented by A and B-bar to the Karnaugh map, the cells representing these rows would all be adjacent to one another. They would appear either as a column or row of four ones or as a two-by-two square of ones. We will see later that the ones for this particular implicant will be in a row at the bottom of the Karnaugh map.
How does this work? Well, remember that we number the rows and columns of the Karnaugh map using Gray code. When transferring the truth table to a Karnaugh map, this Gray code numbering causes the ones that will generate products to arrange themselves into rectangle-shaped patterns, each of which represents a product. The key to effectively using Karnaugh maps is to find the largest group of adjacent ones that follow some simple rules. The bigger the group, the fewer inputs needed for our implicant. Larger groups also mean fewer groups, and hence, fewer implicants in our sum-of-products expression. If all it takes is following a few simple rules, let’s see what those rules are.
First, the group of cells must be in the shape of a horizontal or vertical rectangle or a square. There are no diagonal adjacencies allowed.
Second, all cells in a rectangle must contain ones. No zeros are allowed inside a rectangle.
Third, the number of cells in the rectangle must equal a power of two. In other words, only groups of 1, 2, 4, 8, 16, and so on are allowed. This is because the variables that drop out must be allowed to take on any pattern of ones and zeros. For example, a product that uses all of the input variables generates a single one in the output column of the truth table. A product with one input taken out will generate two rows with ones in the truth table. Two inputs missing from a product generates four ones in the truth table. Three inputs missing from a product generates 23 or 8 ones in the truth table, and so on. If we’ve drawn a rectangle where the number of cells is not a power of two, then of the variables that drop out, there will be one or more patterns that should output a zero in the truth table, instead of a one.
Fourth, the outside edges of Karnaugh maps are considered adjacent, so rectangles may wrap from one side of the map to the other, either left to right or top to bottom.
Fifth, any cell of the Karnaugh map may be contained in more than one rectangle, but every rectangle must have at least one cell that is unique to it. In other words, the rectangles of cells containing ones may overlap, but each rectangle must possess at least one cell that is not overlapped by any other rectangle. Any rectangles that are completely overlapped by other rectangles should not be used to generate a product in the final sum-of-products expression and should be removed from the map. Every one generated by this redundant implicant will only be duplicating ones generated by other implicants.
Sixth, every rectangle must be made as large as possible. If the rectangle could be made larger, but is not, the resulting sum-of-products expression will not be fully simplified, other words, the implicant will not be prime.
Lastly, every one in the Karnaugh map must be covered by at least one rectangle, even if it requires adding a rectangle of size one to cover a lone cell. If we fail to cover a one with a rectangle, we won’t create a product to place that one back into the truth table.
The ultimate goal is to create the fewest number of valid rectangles while still covering every one in the Karnaugh map. Each rectangle represents a product, and the larger the rectangle, the fewer variables will be contained in that product.
As for deriving the product represented by a rectangle, the easiest method is to list the input values for all cells in the rectangle and eliminate the inputs that change across the different cells contained in the rectangle. Let’s show this with an example.
Assume we have a three-input Karnaugh map with zeros in the cells of the top row where A equals zero and B equals zero, ones in the cells of the second row where A equals zero and B equals one, ones in the cells of the third row where A equals one and B equals one, and zeros in the cells of the bottom row where A equals one and B equals zero. We can group the four ones in the second and third row in a single four-cell rectangle. Since this rectangle is valid, it represents a single product. If we can determine the one or more variables that are consistent across all four cells, we can figure out the product it constitutes. The top left cell of the rectangle represents A equals zero, B equals one, and C equals zero. The top right cell of the rectangle represents A equals zero, B equals one, and C equals one. The bottom left cell of the rectangle represents A equals one, B equals one, and C equals zero. The bottom right cell of the rectangle represents A equals one, B equals one, and C equals one.
The inputs that have the same values across all cells in the rectangle are the inputs that will be used to create the product that represents this rectangle. For this example, both A and C equal zero for some cells and one for others. That means that these inputs will drop out leaving only B, which remains one for all four cells. Therefore, the product for this rectangle will equal one as long as B equals one. That means that the final sum-of-products expression for this Karnaugh map is simply X equals B.
We could have done this the hard way by simplifying the expression derived from a product generated from each of these cells. That expression would have started out as A·B·C + A·B·C + A·B·C + A·B·C (read A-bar AND B AND C-bar OR-ed with A-bar AND B AND C OR-ed with A AND B AND C-bar OR-ed with A AND B AND C).
Pulling A-bar AND B out of the first two terms would have left C-bar OR-ed with C, which becomes one, which then drops out of the product to leave just A-bar AND B. Pulling A AND B of the last two terms would also have left C-bar OR-ed with C, which would have dropped out. This would have simplified the expression to A·B + A·B (read A-bar AND B OR-ed with A AND B). Pulling B out of these two products would give us the expression B · (A + A) (read B AND-ed with the sum A-bar OR A). A-bar OR A becomes one, which when AND-ed with B drops out leaving B. It seems a whole lot easier to simplify by looking for rectangles in the Karnaugh map, doesn’t it?
As for the benefits of simplification with Karnaugh maps, each time we are able to double the size of a rectangle, two products combine into one and one input to the resulting product drops out. Rectangles containing only one cell will have all of the input variables represented in the final product. Two-cell rectangles will have one fewer input variables. Four-cell rectangles will have two fewer input variables. Eight-cell rectangles will have three fewer input variables. A rectangle with sixteen cells will have four variables drop out.
In our next episode, we are going to practice by converting some truth tables to their corresponding Karnaugh maps, identifying the rectangles, and then generating the simplest sum-of-products expressions from them. 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.