Karnaugh map (K-Map)

A Karnaugh map (k-map) is a graphical tool to simplify the boolean expression. This K-map was introduced in 1953 by Maurice Karnaugh. The Karnaugh map comprises of small squares put together to form a table. Each cell of the table has one minterm derived from the Boolean expression. A 2-variable Boolean expression has four minterms and thus, has four cells in the Karnaugh map. In general, n variables have 2ⁿ cells in the Karnaugh map. While performing the sum of the product method “1” is taken as the variable and “0” as its complement. Thus, a 2-variable map has 4 squares, a 3-variable map has 8 squares, and a 4-variable map has 16 squares and so on.

K-map is perhaps the most extensively used method for simplification of Boolean function as compared to other methods. The k-map technique may be used for any number of variables but it is generally used up to 5 or 6 variables beyond which it becomes very complicated. The number of squares becomes excessively large and a reasonable selection of adjacent squares becomes more difficult.

Karnaugh Map for two variables

Consider a 2-variable Boolean expression having the truth table as shown below:

The Karnaugh map for the given truth table is drawn in the following steps:

1. A table comprising of four cells are drawn.
2. The complement of the variables is first written followed by the uncomplemented variables.
3. The 1’s from the table is filled in the map.
4. Finally, the 0’s are filled.

Following are the Karnaugh map for 2-input OR and AND gates, respectively.

Any given Boolean expression can be depicted as a Karnaugh map in the following formats:

• Sum of the product form (SOP): In the sum of the product term, the product of the minterms abiding with the given Boolean expression is taken and then they are summed up together. Example, AB + BD
• Product of the sum form (POS): In the product of sum term, the sum of the minterms is performed first, and later their product is taken. Example, (A + B) (B + D)

Both of these methods are implemented to simplify the complexity of the Boolean expression.

Karnaugh Map for three variables

Karnaugh map is best proven for 3-variable Boolean expressions since they minimize the complexity to a greater extent. A 3-variable input has eight cells in the k-map. A 3-variable Boolean expression having the truth table as shown below is considered.

The Karnaugh map for the given truth table is drawn in the following steps:

1. A table comprising of eight cells are drawn.
2. The complement of the variables is first written followed by the uncomplemented variables.
3. The 1’s from the table is filled in the map.
4. Finally, the 0’s are filled.

Karnaugh Map for four variables

A 4-variable k-map consists of 16 squares or cells for each minterm. The gray code representation of the map is depicted in Figure 5.3.

In the map, m₇ is derived from (10) and (11) which gives the binary code (1011) whose decimal equivalent is 7. Similarly, m₁₃ is obtained from (11) and (10) that give 13 as its decimal equivalent. Thus, the map is filled with the gray code equivalents.

k-map for five variables

A k-map for 5-variable expression can be denoted with two 4-variable maps one beside the other. This is depicted as shown in Figure 5.4. The map has 32 cells to fill each minterm. As the number of variables keeps increasing, the efficacy of the Karnaugh map decreases. The five variables are A, B, C, D, and E. Variable E has two conditions. For the minterms 0 to 15, E is 0 and for minterms 16 to 31 variable E takes the value 1.

It is to be noted only one-bit changes between the adjacent cells in both the map. This can be achieved only by representing the map in gray code. While forming groups both the maps are visualized one on top of the other. The minterms m8 and m24 are adjacent while m2 is adjacent to m18. Thus, the minterms of both maps can be grouped together. Grouping in the vertical direction is also allowable in the same approach. But the above procedure proves to be tedious especially for six variables where four maps each consisting of four variables are placed one beside the other. Solving a k-map for five and six variables is highly complicated and can be more practically solved using computer programs.

Grouping of the bits in a k-map is done by using following methods.

Pairs

A Karnaugh map always consists of a pair of 1’s adjacent to each other. This can be well explained from the following example. The steps for obtaining the Karnaugh map is as similar to the 2-variable Boolean expression.

Rules for Karnaugh Mapping

The following rules are incorporated while grouping together the closest cells containing ‘1’s for the simplification of expressions.

1. Groups formed should not contain a zero.

2. Formation of groups may be in vertical or horizontal but NOT diagonal.

3. The groups in general contain 2ⁿ cells. The number of ‘1’s in the map depends on the n. If n = 1, then 2¹ = 2.

If n = 2, the group consists of four 1’s since 2² = 4.

4. The groups must as large as possible without exempting the Boolean laws.

5. The ‘1’s in the Karnaugh map must be grouped in at least one group. If pairing is not possible they can be taken individually but not neglected.

6. Overlapping of groups are allowed to achieve minimal sum of product terms or minimal product of sum terms.

7. The map can be rolled in any manner that forms maximum numbers of groups. They can be wrapped from left to right, top to bottom, along the diagonals.

Example:

Map the standard POS expression on the K-ma and minimize the expression.

(A+B+C+D)(\bar{A}+B+C+D)(\bar{A}+B+C+\bar{D})(\bar{A}+\bar{B}+\bar{C}+\bar{D})

Solution:

(A+B+C+D)=0000;

(\bar{A}+B+C+D)=1000;

(\bar{A}+B+C+\bar{D})=1001;

(\bar{A}+\bar{B}+\bar{C}+\bar{D})=1111

The above numbers are assigned value 1 in the appropriate cell of a 4-variable K-map.

The above k-map shows the grouping or pairing of 1’s.

The minimized expression is given as:

Minimized POS = \bar{A}BC+(\bar{A}\bar{B}\bar{C}\bar{D})+BCD