What is Karnaugh Map?
In realization of digital electronic systems, the simplification of Boolean expressions is one of the most crucial steps because it reduces the hardware complexity and cost of production. There are several tools and methods available for simplifying complex Boolean expression. K-Map or Karnaugh Map is one of such simplification methods. K-Map was developed by Maurice Karnaugh in the year of 1953. It is a visual or graphical method used to simplify the Boolean expressions.
K-Map is one of the most efficient simplification tools when the number of variables in the Boolean expression are less than or equal to four. However, for five, six, and more variables, the K-Map becomes quite difficult.
The K-Map or Karnaugh map makes the use of two dimensional table for simplification of the Boolean functions. The size of this table increases considerably with the increase in the number of variables in the Boolean functions.
Some typical examples of K-Map of two variable, three variable, and four variables are shown in Figure-1.
From Figure-1, it is clear that the number of squares or cells in the Karnaugh map depends on the number of variables in the expression.
If n is the number of variables in the given Boolean function, then the corresponding Karnaugh map (K-Map) will have 2n squares or cells. For examples, if the number of variables in the Boolean function is 3, then the corresponding K-Map will have 8 (= 23) cells.
Why K-Map has states in sequence of 00, 01, 11, 10 instead of 00, 01, 10, 11?
- The definition of the K-Map states that consecutive cells of the K-Map must have only 1-bit change.
- The sequence 00, 01, 10, 11 is called binary code sequence and the sequence 00, 01, 11, 10 is called the gray code sequence.
- In the binary code sequence 00, 01, 10, 11 the second and third state i.e., 01 and 10 violates the rule that the consecutive cells must have only 1- bit change as in these states there is 2-bit difference. So, the binary sequence 00, 01, 10, 11 cannot be used in K-Map.
- The gray code sequence 00, 01, 11, 10 follows the rule that consecutive cells must have only 1-bit as every consecutive state in this sequence has only 1-bit difference. So, it is used in K-Map.
- The above stated reasons the K-Map has states in sequence of 00, 01, 11, 10 instead of 00, 01, 10, 11.
Steps to Solve Expression using K-map
- Select the K-map according to the number of variables.
- Identify minterms or maxterms as given in the problem.
- For SOP put 1’s in blocks of K-map respective to the minterms (0’s elsewhere).
- For POS put 0’s in blocks of K-map respective to the max terms (1’s elsewhere).
- Make rectangular groups containing total terms in power of two like 2,4,8 ..(except 1) and try to cover as many elements as you can in one group.
- From the groups made in step 5 find the product terms and sum them up for SOP form.