Karnaugh Map Introduction, Grouping Rules With Solved Examples
K-Map is a graphical illustration of a logic circuit in other words it is a graphical illustration of a truth table.
Learning Objectives:
Learn about Karnaugh Map, its grouping rules, cell adjacency rules
Generate K-Map from the truth table
Generate K-Map from a standard SOP/POS expression
Generate K-Map from a non-standard SOP/POS expression
What is a K-Map?
It is a graphical method for simplifying Boolean expressions. It is a map containing boxes called "cells". The values in these cells represent a function in standard form (SOP or POS). For ‘n’ variables there are 2n cells. Each cell is denoted by a binary number or its equivalent decimal number. It is similar to the truth table in a way that both methods contain the output of a logic circuit for all possible input combinations.
The truth table has rows and columns, each row has a different input combination. The K-Map has an array of cells, each cell is represented by a different combination of input variables.
With the help of the truth table, a standard SOP/POS expression is obtained. Each term in standard SOP/POS contains all the variables in the domain. The K-map is used for simplified SOP/POS expression. If applied properly, no need for further simplification.
The values entered in the truth table are curated in ascending order. The counting is in binary number format (not necessary but mostly it is in binary format). While in this method, values are curated in gray code format.
Understanding the principle of K-Map? How to develop a K-Map (Cell Adjacency rules):
Any two adjacent squares on the map differ by only a single variable. If a variable is primed in one cell, it is unprimed in the adjacent cell.
The two minterms are arranged in a way that there is a single variable change in binary numbers. When moving along any row or any column, one and only one variable changes in the product term. Look at the figure below:
How to construct a Karnaugh Map | K-Map?
There are many ways to describe a digital logic system.
The logical expression
The schematic
The truth table
The Karnaugh Map
We can analyze the logic system easily if any of the above-mentioned entities is given. The K- Map can easily be implemented with the help of a logic expression either in standard or non-standard form. It is developed either with a schematic diagram or with the help of a truth table.
One Variable Map:
Consider a function with only one variable A. Since n = 1(number of variables), the number of possible cells in a map will be 2 (2n = 21 = 2). Each minterm is adjacent to only one minterm.
Two-Variable Maps
Consider a function with only one variable A and B. Since n = 2(number of variables), the number of possible cells in a map will be 4 (2n = 22 = 4). Each minterm is adjacent to two minterms.
Three Variable Maps
Consider a function with only one variable A, B and C. Since n = 3(number of variables), the number of possible cells in a map will be 8 (2n = 23 = 8). Each minterm is adjacent to three other minterms.
Four Variable Maps
Consider a function with only one variable A, B, C and D. Since n = 4(number of variables), the number of possible cells in a map will be 16 (2n = 24 = 16). Each minterm is adjacent to four other minterms.
Five Variable Maps
Consider a function with only one variable A, B, C, D and E. Since n = 5(number of variables), the number of possible cells in a map will be 2 (2n = 25 = 32). The 32 (4x8 map) cells map is quite large. Instead of a single larger map, it is constructed from two 4-variable K-Map.
For cell adjacency, place a map on the top of the other.
Examples:
Example: F(A, B, C) = ∑ (0,2,3,7)
Have a look at group 1:
Variables A and C are non-changing while B changes. In one cell it is primed and in the other cell, it is unprimed.
\[=\bar A \bar B \bar C + \bar A B \bar C\]
\[=\bar A \bar C (B + \bar B)\]
\[=\bar A \bar C\]
Look at group 2:
Variables B and C are non-changing, while A changes. In one cell it is primed and in the other cell, it is unprimed.
\[=\bar A B C + A B C\]
\[=B C (A + \bar A)\]
\[=BC\]
Look at group 3:
Variables A and B are non-changing, while C changes. In one cell it is primed and in the other cell, it is unprimed.
\[=\bar A B \bar C + \bar A B C\]
\[=\bar A B(C + \bar C)\]
\[=\bar A B\]
\[F = \bar A \bar C+ B C +\bar AB\]
Example: F = \[\bar A \bar B \bar C + A \bar B \bar C + \bar A \bar B C + \bar A B C \]
Two groups are formed, each group contains only two cells. The simplified expression contains only two SOP terms and each has two variables.
The simplified expression is
\[F = \bar B \bar C + \bar A C\]
Example: R = π (12, 13, 15)
This time a POS expression is given. It is obvious that mapping an SOP expression will give a non-simplified Boolean expression.
Don't Care Condition:
In digital circuits, in some conditions, some input variables are not allowed. An example is the BCD codes. These codes are 0-9 (that is from binary 0000 to 1001). While the rest of the combinations are 10- 15 (that is from binary 1010 to 1111) are invalid. These input combinations will never occur.
In these situations simply draw the K-map according to the rules stated above. Mark the unwanted input combinations as 'don't care ('X')'. These terms or input combinations are termed as "don't care" conditions and marked as 'X' in K-map. These terms are advantageous while grouping. Add these 'X' and form larger groups. Larger groups result in simplified expressions.
Example: \[F (A, B, C, D) = ∑ (0,2,4,6,8)\]
\[d (A, B, C, D) = (10, 11, 12, 13, 14, 15)\]
Here we add some of them don't care terms to simplify the expression. While the rest of them are not included.
Example: \[F (W, X, Y, Z) = ∑ (1, 3, 7, 11, 15)\]
\[F (W, X, Y, Z) = (0, 2, 5)\]
.jpg)
.jpg)
.jpg)
