What is Karnaugh map (K-map)?
As we know, for any complex digital logic circuit the algebraic expression will be also very complex. And from this expression implementation of hardware is also very difficult and cost effective. So if we can minimize the expression then it will reduce the complexity and also reduce the number of gate used to make the hardware. Now question is how we will do that. As we know we can minimize the expression by implementing Boolean algebra and also minimized by another method which is called the map method. And the map method is very simple and straightforward procedure for minimizing Boolean functions. This map method is also known as the Karnaugh map or K-map
We can draw Karnaugh map for depending upon the number of variable present in that expression. It may be
- Two variable Karnaugh map.
- Three variable Karnaugh map.
- Four variable Karnaugh map.
See the picture bellow
Now question is how we can minimize the Boolean expression using Karnaugh map.
In the case of a minterm Karnaugh map, ‘1’ is placed in all those squares for which the output is ‘1’, and ‘0’ is placed in all those squares for which the output is ‘0’. 0s are omitted for simplicity. An ‘X’ is placed in squares corresponding to ‘don’t care’ conditions. In the case of a maxterm Karnaugh map, a ‘1’ is placed in all those squares for which the output is ‘0’, and a ‘0’ is placed for input entries corresponding to a ‘1’ output. Again, 0s are omitted for simplicity, and an ‘X’ is placed in squares corresponding to ‘don’t care’ conditions.
The choice of terms identifying different rows and columns of a Karnaugh map is not unique for a given number of variables. The only condition to be satisfied is that the designation of adjacent rows and adjacent columns should be the same except for one of the literals being complemented. Also, the extreme rows and extreme columns are considered adjacent.
In bellow I discussed some very important thing which we should remember to group inside Karnaugh map.
- Each square containing a ‘1’ must be considered at least once, although it can be considered as often as desired.
- The objective should be to account for all the marked squares in the minimum number of groups.
- The number of squares in a group must always be a power of 2, i.e. groups can have 1, 2, 4, 8, 16 squares.
- Each group should be as large as possible, which means that a square should not be accounted for by itself if it can be accounted for by a group of two squares; a group of two squares should not be made if the involved squares can be included in a group of four squares and so on.
- ‘Don’t care’ entries can be used in accounting for all of 1-squares to make optimum groups. They are marked ‘X’ in the corresponding squares. It is, however, not necessary to account for all ‘don’t care’ entries. Only such entries that can be used to advantage should be used.