Home >> Digital Logic Circuits >> Boolean Algebra and Logic Gates >> Minimization of Boolean function using k-map

Minimization of Boolean function using k-map

by | Last updated Sep 9, 2021 | Boolean Algebra and Logic Gates

The Karnaugh map or K-map is used for minimization or simplification of Boolean function either in Sum of Product(SOP) form or in Product of Sum(POS) form.

Before proceeding with the minimization procedures using K-map, you should be clear with the concept of K-map, plotting of K-map and grouping of cells in K-map. If you are not clear in these topics, learn it here before proceeding.

Follow the below procedure to minimize the SOP expression.

  1. Select the size of the K-map, based on the number of variables present in the Boolean function.
  2. Plot the K-map.
  3. Check the K-map for isolated 1s, which are not adjacent to any other 1s and encircle those isolated 1s.
  4. Check the K-map for pair of 1s, which are adjacent to only one other 1s and group it.
  5. Check the K-map for quads and octets and group them, even if contain any 1s, that have been already encircled. But be sure to form minimum number of groups.
  6. Form the expression from the groups that have been encircled by summing them.

Let us minimize the expression Y = AB’C + A’B’C + A’BC + AB’C’ + A’B’C’

Solution:

Step 1: The given function has three variables and hence 23 = 8 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

Minimization Of Boolean Function Using K-Map - problem 1

Step 3: No isolated 1s are there in the K-map.

Step 4: Group the pair of 1s in the K-map. Learn how to group.

Minimization Of Boolean Function Using K-Map - problem 1.1

Step 5: Group the Quad of 1s in the K-map.

Minimization Of Boolean Function Using K-Map - problem 1.2

Step 6: There is no octet group.

Hence, from the K-map, the simplified output expression is Y = A’C + B’

Let us minimize the boolean expression Y = ABC’D + ABC’D’ + ABCD + A’BCD + ABCD’ + A’BCD’.

Solution:

Step 1: The given function has four variables and hence 24 = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

Minimization Of Boolean Function Using K-Map - problem 2

Step 3: No isolated 1s are there in the K-map.

Step 4: Group the pair of 1s in the K-map. But here, two quad groups can be formed. [Thus the number of groups are minimized by grouping the quad cells instead of pairing two cells].

Step 5: There is no octet group.

Hence, from the K-map, the simplified output expression is Y = AB + BC.

Simplify the boolean expression Y(A, B, C, D) = ∑ m (0, 1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 14)

Solution:

Step 1: The given function has four variables and hence 24 = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

Minimization Of Boolean Function Using K-Map - problem 3

Step 3: No isolated 1s are there in the K-map.

Step 4: Group the pair of 1s in the K-map.

Step 5: Group the Quad and octet of 1s in the K-map.

Hence, from the K-map, the simplified output expression is Y = B’ + C’D’ + AD’ + A’CD

Follow the below procedure to minimize the POS expression.

  1. Select the size of the K-map, based on the number of variables present in the Boolean function.
  2. Plot the K-map by placing 0s for the given Maxterms and place 1s for the remaining cells.
  3. Check the K-map for isolated 0s, which are not adjacent to any other 0s and encircle those isolated 0s.
  4. Check the K-map for pair of 0s, which are adjacent to only one other 0s and group it.
  5. Check the K-map for quads and octets and group them, even if contain any 0s, that have been already encircled. But be sure to form minimum number of groups.
  6. Form the expression from the groups that have been encircled by summing them.

Let us minimize the boolean function Y = (A’+B’+C+D)(A+B’+C+D)(A+B+C+D’)(A+B+C’+D’)(A’+B+C+D’)(A+B+C’+D).

Solution:

Step 1: The given function has four variables and hence 24 = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

Minimization Of Boolean Function Using K-Map - problem 4

Step 3: No isolated 0s are there in the K-map.

Step 4: Group the pair of 0s in the K-map.

Step 5: There is no Quad and octet group of 0s.

Hence, from the K-map, the simplified output expression is Y = (B’+C+D) (B+C+D’) (A+B+C’)

Simplify the boolean function Y(A, B, C, D) = Π M (2, 3, 8, 9, 11, 13, 15).

Solution:

Step 1: The given function has four variables and hence 24 = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

Minimization Of Boolean Function Using K-Map - problem 5

Step 3: No isolated 0s are there in the K-map.

Step 4: Group the pair and quad of 0s in the K-map. There is no octet group of 0s here.

Hence, from the K-map, the simplified output expression is Y = (A’+B+C) (A’+D’) (A+B+C’)

In logic circuit design, there may be a situation, where certain input and output conditions can never occur. In that case, the output can be either 0 or 1, that is, the output cannot be defined for such inputs and so they are indicated as ‘x’, which represents don’t care output.

Don't care conditions for K map

In the above truth table, we can observe that, the output is seen for the inputs from 000 to 100. For remaining three inputs(101, 110, 111), the output is not defined and hence called as don’t care conditions, denoted as x.

These don’t care outputs are indicated in the boolean expression using a letter d in the function., where d indicates don’t care condition.

For the above truth table, the Boolean function can be written as

F(A, B, C) = ∑ m (1, 2, 4) + d (5, 6, 7).

From the boolean function, it is observed that, the logic is true for minterms 1, 2, 4 and the output is not defined for minterms 5, 6, 7. Similarly the Boolean function in terms of maxterm can be written as

F(A, B, C) = Π M (0, 3) + d (5, 6, 7).

Using K-map, the boolean function with don’t care condition can be minimized by considering either 0 or 1 for don’t care outputs, depending on the minterms to get the simplest expression.

Let us consider the below example.

In the above K-map example, minterms 4 and 5 are don’t care outputs and hence denoted as x. To minimize this boolean expression to the simplest one, we are considering the minterm 5 as logic 1 and the minterm 4 as logic 0. Since the minterm 5 is considered as logic 1, it forms a quad group with minterms 1, 3 an 7. Thus we get a simplified expression Y = C as output.

From this, we can observe that, it is important to decide, which don’t care output is to be changed to 1 and which is to be changed to 0, so that best grouping is produced.

Let us have a look at some example problems here or your better understanding.

Simplify the boolean function with don’t care conditions Y(A, B, C, D) = ∑ m (1, 3, 7, 11, 15) + d (0, 2, 5).

Solution:

Step 1: The given function has four variables and hence 24 = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

Minimization Of Boolean Function Using K-Map - problem 6

Step 3: Here, instead of pairing cells, quad group can be formed. To form a quad group of 1s, the don’t care outputs of cells 0, 2 are replaced by 1s and grouping is done. The remaining don’t care outputs are left alone or replaced by 0s.

Hence, from the K-map, the simplified output expression is Y = A’B’ + CD

Simplify the boolean function with don’t care conditions Y(A, B, C, D) = Π M (4, 5, 6, 7, 8, 12) + d (1, 2, 3, 9, 11, 14).

Solution:

Step 1: The given function has four variables and hence 24 = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

Minimization Of Boolean Function Using K-Map - problem 7

Step 3: Here, instead of pairing cells, quad group can be formed. To form a quad group of 0s, the don’t care outputs of cells 0, 2 are replaced by 0s and grouping is done. The remaining don’t care outputs are left alone or replaced by 1s.

Hence, from the K-map, the simplified output expression is Y = (A+B’) (A’+C+D)

FAQs

What is meant by don’t care condition in K-map?

In logic circuit design, there may be a situation, where certain input and output conditions can never occur. In that case, the output can be either 0 or 1, that is, the output cannot be defined for such inputs and so they are indicated as ‘x’, which represents don’t care output.

What are the limitations of K-map?

The Minimization of Boolean function using K-map is suitable only if the number of variables does not exceed four or five. If the number of variables is beyond five, then it becomes difficult to simplify the expression.
As the minimization of K-map is done manually, it is impossible to simplify the expression with more number of variables.

Categories

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *

Shares
Share This