Minimization of Boolean function using k-map

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.

Minimization of SOP Boolean function using K-map

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.

Example Problem 1

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 2³ = 8 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

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.

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

Step 6: There is no octet group.

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

Example Problem 2

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 2⁴ = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

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.

Example Problem 3

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 2⁴ = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

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

Minimization of POS Boolean function using K-map

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.

Example problem 4

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 2⁴ = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

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’)

Example problem 5

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 2⁴ = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

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’)

Don’t care conditions 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.

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

Minimization of Boolean function with don’t care conditions

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.

Example Problem 6

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 2⁴ = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

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

Example Problem 7

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 2⁴ = 16 cells K-map is necessary to minimize the expression.

Step 2: Plotting of k-map.

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