Karnaugh Map (K-Map) Simplification

Karnaugh Map simplification:

The simplification of the switching functions using Boolean laws and theorems becomes complex with the increase in the number of variables and terms. The Karnaugh Map technique provides a systematic method for simplifying and manipulating switching expressions.

In this technique, the information contained in a truth table or available in the POS or SOP form represented on the Karnaugh Map (K-map). The K-map is a modified form of a truth table. Here, the combinations conventionally arranged to aid the simplification process by applying the rule [no-highlight]Ax + Ax’ = A[/no-highlight].

In an n-variable K-map, there are 2ⁿ cells. Each cell corresponds to one combination of n variables. Therefore, for each row of the truth table, for each minterm and each maxterm, there is one specific cell in the K-map.

Principles of Karnaugh Map Simplification:

Simplification is based on the principle of combining the terms present in adjacent cells. The 1s in the adjacent cells can be grouped by drawing a loop around those cells following the given rules:

1. Construct the K-map and enter the 1s in those cells corresponding to the combinations for which the function value is 1, then enter the 0s in the other cells.

2. Examine the map for 1s that can’t be combined with any other 1 cells and form groups with such a single 1.

3. Next, look for those 1s which are adjacent to only one other 1 and form groups containing only 2 cells and which are not part of any group of 4 or 8 cells. A group of 2 cells called a pair.

4. Group the 1s which results in groups of 4 cells but are not part of an 8-cells group. A group of 4 cells called a quad.

5. Group the 1s which results in groups of 8 cells. A group of 8 cells called an octet.

6. Form more pairs, quads and octets to include this 1s that have not yet been grouped, and use only a minimum number of groups. There can be overlapping of groups if they include common 1s.

7. Omit any redundant group.

8. Form the logical sum of all the terms generated by each group.

Karnaugh map solved examples:

Example: Simplify the expression Y = ∑_m(7,9, 10, 11, 12, 13, 14, 15), using the k-map method.

Solution: In the given K-map, there are three quads and one pair, the corresponding simplified terms are AB, AD, AC and BCD.

Now, the simplified expression is: [no-highlight]Y = AB + AD + AC + BCD[/no-highlight]

Since the quads and pair formed in the above K-map overlap, the expression can be further simplified using the boolean algebra as follows:
[no-highlight] Y = AB + AD + AC + BCD
= A(B + D + C) + BCD
[/no-highlight]

Example: simplify the expression Y = π(0,1,4,5,6,8,9,12,13,14), using the K-map method.

Solution: The given function is in the POS form.

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) (A+B+C+D) (A+B+C+D) (A+B+C+D) (A+B+C+D)

To simplify a POS expression, for each extreme in the expression, O has to be entered in corresponding to each group can be obtained by the OR operation of the variables that are the same for all cells of the group. Here, a variable corresponding to O has to be represented in an uncomplemented form and corresponding to 1 in the complemented form. The K-map for the function is shown below figure:

In the above K-map, one octet and one quad are produced by combining O cells. The simplified sum term corresponding to the octet is C whereas for the quad is (B+D). Hence, the simplified POS expression for the given function is Y=C(B+D)