Karnaugh Map(K-Map) method

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. The K-map provides a cookbook for
simplification.

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.

The K-map method is used for expressions containing 2, 3, 4, and 5 variables. For a
higher number of variables, there is another method used for simplification called
the Quine-McClusky method. In K-map, the number of cells is similar to the total
number of variable input combinations. For example, if the number of variables is
three, the number of cells is 23=8, and if the number of variables is four, the
number of cells is 24. The K-map takes the SOP and POS forms. The K-map grid is
filled using 0's and 1's. The K-map is solved by making groups. There are the
following steps used to solve the expressions using K-map:

1. First, we find the K-map as per the number of variables.

2. Find the maxterm and minterm in the given expression.

3. Fill cells of K-map for SOP with 1 respective to the minterms.

4. Fill cells of the block for POS with 0 respective to the maxterm.

5. 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.

6. With the help of these groups, we find the product terms and sum them up
for the SOP form.

2 Variable K-map
There is a total of 4 variables in a 2-variable K-map. There are two variables in the
2-variable K-map. The following figure shows the structure of the 2-variable K-map:

o In the above figure, there is only one possibility of grouping four adjacent
minterms.
 o The possible combinations of grouping 2 adjacent minterms are {(m0, m1),
(m2, m3), (m0, m2) and (m1, m3)}.

3-variable K-map
The 3-variable K-map is represented as an array of eight cells. In this case, we used
A, B, and C for the variable. We can use any letter for the names of the variables.
The binary values of variables A and B are along the left side, and the values of C
are across the top. The value of the given cell is the binary values of A and B at left
side in the same row combined with the value of C at the top in the same column.
For example, the cell in the upper left corner has a binary value of 000, and the cell
in the lower right corner has a binary value of 101.

The 4-Variable Karnaugh Map

The 4-variable K-map is represented as an array of 16 cells. Binary values of A and
B are along the left side, and the values of C and D are across the top. The value of
the given cell is the binary values of A and B at left side in the same row combined
with the binary values of C and D at the top in the same column. For example, the
cell in the upper right corner has a binary value of 0010, and the cell in the lower
right corner has a binary value of 1010
5-variable K-map
With the help of the 32- cell K-map, the boolean expression with 5 variables can be
simplified. For constructing a 5-variable K-map, we use two 4-variable K-maps. The
cell adjacencies within each of the 4- variable maps for the 5-variable map are
similar to the 4- variable map.

ADVERTISEMENT

A K-map for five variables (PQRST) can be constructed using two 4-variable maps.
Each map contains 16 cells with all combinations of variables Q, R, S, and T. One
map is for P = 0, and the other is for P = 1).

Simplification of boolean expressions using

Karnaugh Map
As we know that K-map takes both SOP and POS forms. So, there are two possible
solutions for K-map, i.e., minterm and maxterm solution. Let's start and learn about
how we can find the minterm and maxterm solution of K-map.

Minterm Solution of K Map

There are the following steps to find the minterm solution or K-map:

Step 1:

Firstly, we define the given expression in its canonical form.

Step 2:

Next, we create the K-map by entering 1 to each product-term into the K-map cell
and fill the remaining cells with zeros.

Step 3:

Next, we form the groups by considering each one in the K-map.

Notice that each group should have the largest number of 'ones'. A group cannot
contain an empty cell or cell that contains 0.

ADVERTISEMENT

In a group, there is a total of 2n number of ones. Here, n=0, 1, 2, …n.

Example: 20=1, 21=2, 22=4, 23=8, or 24=16.

We group the number of ones in the decreasing order. First, we have to try to make
the group of eight, then for four, after that two and lastly for 1.
In horizontally or vertically manner, the groups of ones are formed in shape of
rectangle and square. We cannot perform the diagonal grouping in K-map.

The elements in one group can also be used in different groups only when the size of
the group is increased.

The elements located at the edges of the table are considered to be adjacent. So, we
can group these elements.

We can consider the 'don't care condition' only when they aid in increasing the
group-size. Otherwise, 'don't care' elements are discarded.
Step 4:

In the next step, we find the boolean expression for each group. By looking at the
common variables in cell-labeling, we define the groups in terms of input variables.
In the below example, there is a total of two groups, i.e., group 1 and group 2, with
two and one number of 'ones'.

In the first group, the ones are present in the row for which the value of A is 0.
Thus, they contain the complement of variable A. Remaining two 'ones' are present
in adjacent columns. In these columns, only B term in common is the product term
corresponding to the group as A'B. Just like group 1, in group 2, the one's are
present in a row for which the value of A is 1. So, the corresponding variables of this
column are B'C'. The overall product term of this group is AB'C'.

ADVERTISEMENT

Step 5:
Lastly, we find the boolean expression for the Output. To find the simplified boolean
expression in the SOP form, we combine the product-terms of all individual groups.
So the simplified expression of the above k-map is as follows:

A'+AB'C'

Let's take some examples of 2-variable, 3-variable, 4-variable, and 5-variable K-

map examples.

Example 1: Y=A'B' + A'B+AB

Simplified expression: Y=A'+B

Example 2: Y=A'B'C'+A' BC'+AB' C'+AB' C+ABC'+ABC

Simplified expression: Y=A+C'

Example 3: Y=A'B'C' D'+A' B' CD'+A' BCD'+A' BCD+AB' C' D'+ABCD'+ABCD

Simplified expression: Y=BD+B'D'

Maxterm Solution of K-Map

To find the simplified maxterm solution using K-map is the same as to find for the
minterm solution. There are some minor changes in the maxterm solution, which are
as follows:

1. We will populate the K-map by entering the value of 0 to each sum-term into
the K-map cell and fill the remaining cells with one's.

2. We will make the groups of 'zeros' not for 'ones'.

3. Now, we will define the boolean expressions for each group as sum-terms.

4. At last, to find the simplified boolean expression in the POS form, we will
combine the sum-terms of all individual groups.

Let's take some example of 2-variable, 3-variable, 4-variable and 5-variable K-map
examples

Example 1: Y=(A'+B')+(A'+B)+(A+B)
Simplified expression: A'B

Example 2: Y=(A + B + C') + (A + B' + C') + (A' + B' + C) + (A' + B' + C')

Simplified expression: Y=(A + C') .(A' + B')

Example 3: F(A,B,C,D)=π(3,5,7,8,10,11,12,13)

Simplified expression: Y=(A + C') .(A' + B')

Don't Care Condition

The "Don't care" condition says that we can use the blank cells of a K-map to make
a group of the variables. To make a group of cells, we can use the "don't care" cells
as either 0 or 1, and if required, we can also ignore that cell. We mainly use the
"don't care" cell to make a large group of cells.

The cross(×) symbol is used to represent the "don't care" cell in K-map. This cross
symbol represents an invalid combination. The "don't care" in excess-3 code are
0000, 0001, 0010, 1101, 1110, and 1111 because they are invalid combinations.
Apart from this, the 4-bit BCD to Excess-3 code, the "don't care" are 1010, 1011,
1100, 1101, 1110, and 1111.
We can change the standard SOP function into a POS expression by making the
"don't care" terms the same as they are. The missing minterms of the POS form are
written as maxterms of the POS form. In the same way, we can change the standard
POS function into an SOP expression by making the "don't care" terms the same as
they are. The missing maxterms of the SOP form are written as minterm of the SOP
form.

Example 1: Minimize f = m(1,5,6,12,13,14) + d(4) in SOP minimal form

Solution:

The k-map of the given function in the SOP form is as follows:

So, the minimized SOP form of the function is:

f = BC' + BD' + A'C'D

Example 2: Minimize F(A,B,C,D) = m(0,1,2,3,4,5) + d(10,11,12,13,14,15) in

SOP minimal form

Solution:

The POS form of the given function is:

F(A,B,C,D) = M(6,7,8,9) + d(10,11,12,13,14,15)

The POS K-map for the given expression is:

So, the minimized POS form of the function is:

F = A'(B' + C')

Example-3:
Minimize the following function in SOP minimal form using K-Maps: F(A, B,
C, D) = m(1, 2, 6, 7, 8, 13, 14, 15) + d(3, 5, 12)

Explanation:

The SOP K-map for the given expression is:

Therefore,

f = AC'D' + A'D + A'C + AB

Significance of "Don't Care" Conditions:

Don't Care conditions has the following significance with respect to the digital circuit
design:

Simplification:

These conditions denote the set of inputs that never occurs for given digital circuits.
Therefore, to simplify the boolean output expressions, the 'don't care' are used.

Reduced Power Consumption:

The switching of the state is reduced when we group the terms long with "don't
care". This reduces the required memory space resulting in lower power
consumption.

Lesser number of gates:

For reducing the number of gates that are used to implement the given expression,
simplification places an important role. So, the 'don't care' makes the logic design
more economical.

Prevention of Hazards:

In the digital system, the 'don't care' place an important role in hazards prevention.
States in Code Converters:

These also play an important role in code conversion. For example- In the design of
a 4-bit BCD-to-XS-3 code converter, the input combinations 1010, 1011, 1100,
1101, 1110, and 1111 are don't cares.