Manipulating Boolean using Karnaugh maps - part 1
A Karnaugh map gives you a visual method of simplifying a Boolean expression. You construct a table of cells, and each cell represents a possible combination on inputs into a system. The table cells are arranged in a special way, so that each cell's input combination is different to the cells next to it by just one bit and only one bit. This kind of organisation is called Gray code. By completing the table, you can spot immediately where some terms in a Boolean expression are redundant and can then simplify it. This is best understood by working through some examples.
Constructing the map
The size and layout of a Karnaugh map depends upon how many inputs your have. We have already said that a table's cells are arranged in a special way, so that each cell's input combination is different to the cells next to it by just one bit and only one bit. Study the following Karnaugh maps for two, three and four inputs.
The cells are not in binary order. They are organised so that the cells next any particular one differ by just one bit. You can also think of the map as 'wrapping around' itself. In other words, the right most cell differs to the left most cell in any row by just one bit, and the top cell in a column differs by just one bit to the cell in the bottom of that column. The value contained in any cell is given by its row and then column value. For example, the pink cell shown here:
has a value 101 (row 1, column 01).
An example of using a Karnaugh map
Let's look at an example to see how Karnaugh maps are used. Consider this truth table that we want to produce a simplified Boolean expression for:
Let's work out what the Boolean expression is for this truth table:
Is this the simplest form of the equation? Is there a better way of deriving this equation? We will use a Karnaugh to investigate!
First, we need to construct the correct table for three inputs. Then, wherever a 1 occured in the truth table, we have to find the corresponding cell in our Karnaugh table and put a 1 in it. That gives us:
Now, if there are ones in two cells next to each other, that means that there is some redundancy in the system! What you have to do is:
- group ones together in squares and rectangles in groups of one, two, four, eight, sixteen etc (powers of 2).
- ensure that the total number of groups is as small as possible
- make groups as large as you can.
If we follow the rules above for our example, we can identify two groups of two cells:
We then look at each group in turn. Remember, that the output is a 1 in each group. If a bit changes in that group, the output is still a 1. That means that that bit that changed didn't have any effect on the output. It's therefore redundant. We don't need it and can ignore it in the Boolean expression that we then need to construct for that group.
In the top group, bit C changed, so is redundant, as the output was still a 1 in all cells in that grouping.
In the lower group, bit A changed, so is redundant, as the output was still a 1 in all cells in that grouping.
Finally, we write out all of the Boolean expressions and then OR them. In our example, we get:
AB + AC = Q
You can see that the output is actually the same as the Boolean expression we worked out from the truth table so in this case, we can say that the Boolean expression is as simplified as it can be.
On a general note, we should obey the following rules when constructing Karnaugh maps:
- Every cell that has a 1 in it must be included in at least one group.
- Groups may overlap; cells may appear in more than one group.
- Aim for the largest groups possible with the fewest number of groups.
- The bigger the group, the larger the number of redundant inputs:
- a group of 1 has no redundant inputs.
- a group of 2 has 1 redundant input.
- a group of 4 has 2 redundant inputs.
- a group of 8 has 4 redundant inputs.
- a group of 16 has 8 redundant inputs.
- Groups can have 1, 2, 4, 8 etc cells (powers of 2).
- Groups can wrap around right to left, up to down but must always be square or rectangular.