What are Karnaugh Maps used for?
Karnaugh maps or K-maps for short are used for simplifying Boolean expressions. K-maps are constructed depending on the number of variables, or bits, in the expression. For example if the expression is f(A,B,C,D) = A + D
, there are 4 bits to consider. Before starting to construct the K-Map you should first create the truth table for the function you are implementing. After this is done it is time to make the K-Map. First thing to do is to draw the box for the K-Map.
Notice that the most significant bit (A) is on top followed by B and so on.On the top bar 00 stand for AB, 01 stand for A, and so on. Also the order of the bits is not the standard binary counting order. The order is created in such a way that only one bit at a time is changed.
Filling out a Karnaugh Map
Once the table has been created it is time to take the data from the truth table to the K-Map. Copy all the outputs from the truth table onto the K-Map according to what the inputs are. For example, if
ABCD | F
0000 | 0
0001 | 1
0010 | 0
etc.
Remember that the 3rd row is flipped with the 4th, so change the outputs accordingly.
After the K-Map has been filled in it is time to try to simplify the boolean expression. There are two ways to do this, either SOP (Sum of Products) or POS( Products of Sum). The difference between the two is what you group together. In SOP you would group all the 1’s in the K-Map together, and in POS you group the 0’s. In the examples, I will be using SOP.
What does grouping mean? Grouping means that if there 1’s which are next to each other than you can circle them together to create a simpler boolean expression in the end. The trick is that you can only circle an even number of 1’s. So if three 1’s are next to each other you can only circle them as groups of 2. It is possible to group 1’s at 0000 and 1000; 1000 and 1010; and so on.
A Karnaugh Map example
For example
CD
AB 00 01 11 10
00 | 1 | 1 | 1 | 1 |
01 | 0 | 0 | 0 | 0 |
11 | 0 | 0 | 0 | 1 |
10 | 1 | 1 | 0 | 1 |
To simply this expression, you should group:
1. all the 1’s in AB = 00
2. 1’s from AB = 10 and C = 0
3. 1’s from CD = 10 and A = 1
The way to simply the expression is you note the changes in bits in the groupings.
In grouping 1: The only bits to stay the same are bits AB which stay at 00. So the simplified expression would be *
In grouping 2 : The only bit to change is D. So the expression becomes A * *
In grouping 3: The only bit to change is B. So the expression becomes A* C *
So the final expression would turn into F(A,B,C,D) = *
+ A *
*
+ A* C *
Note: This expression is not hazard free. To make hazard free group all possible 1’s together.