Karnaugh Map (K-Map)

Karnaugh map method or K-map method is the pictorial representation of the Boolean equations and Boolean manipulations are used to reduce the complexity in solving them. The K-map is a systematic way of simplifying Boolean expressions. With the help of the K-map method, we can find the simplest POS and SOP expression, which is known as the minimum expression. These can be considered as a special or extended version of the ‘Truth table’.

Just like the truth table, a K-map contains all the possible values of input variables and their corresponding output values. However, in K-map, the values are stored in cells of the array. In each cell, a binary value of each input variable is stored.

Advantages of K-Maps

• The K-map simplification technique has simpler and easy rules, hence less error-prone compared to the method of solving the logical expressions using Boolean laws.
• It prevents the need to remember each and every Boolean algebraic theorem.
• It involves fewer steps than the algebraic minimization technique to arrive at a simplified expression.
• K-map simplification technique always results in minimum expression if carried out properly.

 How does Simplification take place using K-map?

These are the steps that are to be followed to solve an expression using K-Map:

• First, find the K-map as per the number of variables.
• Then, find the maxterm and minterm in the given expression.
• Fill cells of K-map for SOP with 1 respective to the minterms. And, fill cells of the block for POS with 0 respective to the maxterm.
• Next, we create rectangular groups that contain total terms in the power of two like 2, 4, 8, … and try to cover as many elements as we can in one group.
• With the help of these groups, we find the product terms and sum them up for the SOP form.

K-Map follows Gray Code. As we will see the structure we will get to know more.

Structure Of K-Map

For 2-variable:

As there are 2-variable hence total cells will be 4.

As we know boolean function can be in two forms, so mapping can be done in two ways,

SOP (minterms): m0, m1, m2, m3

POS (maxterms): M0, M1, M2, M3

Mapping for SOP expression: 

Mapping for POS expression:

For 3-variable:

As there are 3-variable hence total cells will be 9.

Mapping for SOP expression:

Mapping for POS expression:

For 4-variable:

As there are 4-variable hence total cells will be 16.

 Grouping or Looping of Variables

There are some rules to follow while grouping the variables in K-maps.

1. The square that contains ‘1’ should be taken in simplifying, at least once.
2. The square that contains ‘1’ can be considered as many times as the grouping is possible with it.
3. Group shouldn’t include any zeros (0).
4.  A group should be the as large as possible.
5.  Groups can be horizontal or vertical. Grouping of variables in diagonal manner is not allowed.

Grouping of Two:

Grouping of four:

Grouping Of Eight:

Example 2:

Simplify the given 4-variable Boolean equation by using k-map. F (W, X, Y, Z) = (1, 5, 12, 13)

Sol: F (W, X, Y, Z) = (1, 5, 12, 13)

By preparing k-map, we can minimize the given Boolean equation as

F = W Y’ Z + W ‘Y’ Z