What is a Karnaugh Map & Its Examples
Earlier we have discussed how to simplify Boolean functions through Boolean postulates & theorems. But this process is time-consuming and after each step, we have to rephrase the simplified expressions. So, Karnaugh Map has introduced a method to overcome this difficulty by simplifying Boolean functions in a simple way. This method is called the Karnaugh map or K-map method. It is a graphical method and includes 2n cells for ‘n’ variables. The contiguous cells are changed simply in a single-bit location. For instance, in several digital circuits as well as practical problems, minimum variables are used to find out the expression. Boolean expressions can be reduced for 3 to 4 variables using the Karnaugh Map method without using any theorems of Boolean algebra. Based on the problem, k-map uses two forms like SOP – Sum of Product & POS – Product of Sum. As compared to the truth table, k-map provides more data. This article discusses an overview of karnaugh map solved examples.
What is a Karnaugh Map/K-Map?
The Karnaugh Map or K-Map is one kind of method used to simplify Boolean expressions in a systematic way. This method is very helpful in finding the simplest sum of product and product of sum expression, which is called the minimum expression. For simplification, the Karnaugh Map gives a cookbook.
Similar to the truth table, a karnaugh map includes all the achievable values for input variables as well as their equivalent output values. But, in Karnaugh-map, all the values will be stored within the array cells. So, in every cell, each inputs binary value variable can be stored. The Karnaugh Map method is mainly used for expressions that include 2 to 5 variables. For a high number of variables, the Quine-McClusky technique is used for simplification.
In karnaugh-map, the number of cells is related to the whole number of variable input arrangements. For instance, if the variables are three, then the number of cells is 23 = 8. Similarly, if the number of variables is 4 then the number of cells is 24 =16. The K-map uses two forms like the SOP & POS. The K-map network is filled with 1’s and 0’s. The karnaugh-map can be solved through making groups.
How to use Karnaugh Map?
There are different steps to solve expression using K-map. So based on the variables available, choose the Karnaugh map. The following list is the karnaugh map rules.
- Recognize minterms otherwise max terms as shown in the problem.
- For the sum of products, place 1’s in the k-map blocks respective to the minterms like 0’s in another place).
- For the product of sum, place 0’s in the k-map blocks respective to the max terms like 1’s in another place).
- Create rectangular groups which include whole terms in the power of 2 or 4 or 8 apart from 1 & try to cover up several elements as you can within a single group.
- After forming groups, product terms need to find to add them to get the form of a sum of the product.
Karnaugh Maps for Variables
Karnaugh Map method is mainly used to reduce Boolean functions for 2 to 5 variables. Let us discuss the karnaugh map for 2, 3, 4, and 5 variables one by one
K-Map for 2 Variables
In this type of K amp, the number of cells used is four, as the number of variables is 2 then the number of cells will be 2n. So, the following diagram is the K map for 2 variables is shown below.
There is simply one option to make groups for 4 contiguous minterms. So, the achievable combinations for grouping 2 contiguous minterms are like (m0, m1), (m2, m3), (m0, m2) & (m1, m3).
Example of 2 Variable K Maps
By using K-map, we can simplify the following Boolean expression for two variables.
F = A B’ + A’ B + A’B’
For that above equation, the truth table will be like the following.
A | B | F |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
We place ‘1’ at the output terms provided within the equation.
In the above 2 variables Karnaugh-map, two groups can be formed based on the rules. The first rule is by combining the two terms like (A’, B) & (A’, B’) and the second rule is by combining the two terms like (A, B’) & (A’, B’).
Here in both groups, the lesser right cell can be used. Once the grouping of variables is done the following step is determining the minimized expression. By removal of the frequent terms from two groups like A’ & B’, we can get a combination of the reduced expression. So the minimized equation will be X’ +Y’.
K-Map for 3 Variables
In 3 variables K-map, the number of cells is eight, as the number of variables is n = 3, so the cells will become 2n = 8. So, the diagram of the K map for 3variables is shown below.
For making 8 adjacent minterms, there is simply one possibility
The achievable combinations for grouping four contiguous minterms are like (m0, m1, m3, m2), (m0, m1, m4, m5), (m4, m5, m7, m6), (m1, m3, m5, m7), (m2, m0, m6, m4) & (m3, m2, m7, m6).
The achievable combinations for grouping two contiguous min terms are {(m0, m1), (m3, m2), (m1, m3), (m2, m0), (m5, m7), (m4, m5), (m7, m6), (m0, m4), (m6, m4), (m1, m5), and (m2, m6) & (m3, m7)}.
If X=0, then K-map for three variables will become into two variable K-map.
Example of 3 Variable K Maps
By using K-map, we can simplify the following Boolean expression for three variables.
F = A’B C + A’ B’ C + A B C’ + A’ B’ C’ + ABC + AB’C’
For the above equation, first, we have to make the truth table
A | B | C | F |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
We place ‘11 at the o/p terms provided in the equation.
In the three variable karnaugh map, there are 8 cells that will look like the following.
In this k-map, we consider the left-most column like the contiguous column of the rightmost column. So the 4 size group can be formed like the following.
In both terms, we have ‘B’ in common. So the 4 size group can be decreased like the conjunction B. To use each cell which includes ‘1’ in it, we combine the remaining cells to make 2 size groups like the following.
This group doesn’t include common variables, thus they are written by their variables & their conjugates. So the decreased equation will be AB’ + B’ + A’ B and in this equation, no further reduction is achievable.
K-Map for 4 Variables
For 4 variables karnaugh map, the number of cells is 16, as the number of variables is 4. So, the diagram of the K map for 4 variables is shown below.
There is simply one opportunity for grouping 16 contiguous minterms.
Let minterms of all the rows can be represented with R1, R2, R3 & R4 correspondingly. Likewise, the minterms of all the columns can be represented with C1, C2, C3 & C4 correspondingly. The achievable combinations for grouping 8 contiguous minterms are {(R1, R2), (R3, R4), (R4, R1), (R2, R3), (C1, C2), (C3, C4), (C2, C3), (C4, C1)}.
If A = 0, then K-map for 4 variables will become three variable K-map.
Example of 4 Variable K Maps
By using the karnaugh map, simplify the following Boolean equation for 4-variables
F (X, Y, Z, W) = (1, 5, 12, 13)
By forming a k-map, we can reduce the provided Boolean equation like the following.
F = X Z’ W + X‘Z’W
K-Map for 5 Variables
For 5 variables K-map, the number of cells is 32, as the number of variables is five. So, the diagram of the K map for 5 variables is shown below.
There is only one opportunity for grouping 32 contiguous minterms. So, the possibilities for grouping 16 contiguous minterms are two like grouping m0 to m15 min terms & m16 to m31.
If V = 0, then the K-map for 5 variables will become K-map for 4 variable
In the above-mentioned all K maps, the minterms notation is used. Likewise, you can utilize the Max terms notation.
Example of 5 Variable K Maps
Simplify the given 5-variable Boolean equation by using a k-map.
f (X, Y, Z, W, A) = ∑ m (0, 5, 6, 8, 9, 10, 11, 16, 20, 42, 25, 26, 27)
By forming a k-map, we can reduce the provided Boolean equation.
Karnaugh Map with Don’t Care Conditions
In Karnaugh-map, the “Don’t care” conditions are mainly used to substitute the blank cell to figure out an achievable grouping of variables which can be used as either 1 or 0 depending on the contiguous variables within the group.
The cells with “don’t care” conditions are signified through a symbol asterisk (*) between the standard 0’s and 1’s. In variables grouping, Don’t Care can be ignored. These conditions are extremely helpful in grouping the large-size variables.
Reducing an Expression through Don’t Care
We can reduce the Boolean expression by locating the ‘don’t care condition’s relative functions by assigning them 1 or 0. In the Boolean equation, if the number of don’t care is ‘n’ then the number of functions attained will be 2n.
Thus, this is all about an overview of the Karnaugh map or k-map method. This method is more helpful in reducing the Boolean expression which includes the number of variables like Boolean expression with 2-variables, 3-variables, 4-variables, 5-variables. Here is a question for you, what are the applications of the Karnaugh map.