Simplification of Boolean function using Karnaugh Map

Simplification of Boolean Functions Using Karnaugh Map (K-map)

The Karnaugh Map (K-map) is a graphical method used for simplifying Boolean functions. It is an efficient tool to minimize expressions without using complex algebraic manipulations. The K-map helps to visually group terms, which can then be simplified into a more compact Boolean expression. This method is particularly useful for functions with two to six variables.

Steps to Simplify Boolean Functions Using K-map

1. Construct the K-map:

   • The first step is to construct a Karnaugh map for the given Boolean function. A K-map is a grid where each cell corresponds to a possible minterm of the Boolean function.
   • The number of cells in the K-map depends on the number of variables. A K-map with $n$ variables will have $2^n$ cells.
   • The rows and columns are labeled based on the binary representation of the minterms. The labels must follow Gray Code, which ensures that only one variable changes between adjacent cells.

2. Fill the K-map:

   • For each minterm in the Boolean expression, place a 1 in the corresponding cell.
   • If the Boolean function is given in Sum of Minterms (SOM), you place a 1 in the cells corresponding to the minterms.
   • If the Boolean function is given in Product of Maxterms (POM), place 0 in the corresponding cells (because maxterms represent the "false" combinations).

3. Group the 1s:

   • Next, group adjacent 1s in the K-map. The group sizes must be powers of 2 (1, 2, 4, 8, etc.).
   • Each group of 1s represents a simplified product term in the Boolean expression.
   • Groups should be as large as possible. Larger groups lead to simpler expressions.

4. Write the simplified expression:

   • For each group of 1s, write down the corresponding Boolean product term.
   • If a variable appears the same way in all cells of the group (either true or complemented), that variable is part of the simplified term.
   • Variables that change between cells in the group are eliminated from the term.

5. Combine the terms:

   • After writing the simplified terms for all the groups, combine them using the OR operation to obtain the final simplified Boolean expression.

Example: Simplifying a Boolean Function Using K-map

Let's simplify a Boolean function using the K-map.

Given Function:

$F(A, B, C) = A'B'C + A'BC' + AB'C' + ABC$

This function has three variables: $A$, $B$, and $C$.

Step 1: Construct the K-map

For three variables, we will use a K-map with 8 cells (since $2^3 = 8$).

The K-map will look like this:

Where the minterms correspond to the binary values of the variables $A, B, C$. For example, $M0$ corresponds to $A'B'C'$, $M1$ corresponds to $A'B'C$, etc.

Step 2: Fill the K-map

Now, we fill in the K-map with the minterms of the function.

The minterms for the given function are:

• $A'B'C$ corresponds to minterm $M1$.
• $A'BC'$ corresponds to minterm $M2$.
• $AB'C'$ corresponds to minterm $M6$.
• $ABC$ corresponds to minterm $M5$.

So, the K-map looks like this:

Step 3: Group the 1s

Now, we group the adjacent 1s in the K-map. Remember that the groups must be powers of 2 (1, 2, 4, 8, etc.), and we aim to create the largest possible groups.

• We can group the 1s in minterms $M1$ and $M3$ (adjacent horizontally).
• We can also group the 1s in minterms $M5$ and $M7$ (adjacent horizontally).
• Lastly, we have a group of $M2$ and $M6$, which are adjacent vertically.

Step 4: Write the simplified expression

Now, for each group, we write the corresponding simplified Boolean term:

• The first group of 1s (M1 and M3) corresponds to $A'B$. In this group, $A$ is always 0, and $C$ changes between 0 and 1, so it is eliminated.
• The second group of 1s (M5 and M7) corresponds to $AB$. In this group, $A$ and $B$ are always 1, and $C$ changes.
• The third group of 1s (M2 and M6) corresponds to $B'C'$. In this group, $B$ and $C$ are always 0, and $A$ changes.

Thus, the simplified Boolean expression is:

Step 5: Final Simplified Expression

The simplified Boolean function after applying the K-map is:

Key Points to Remember:

• Gray Code: Label the rows and columns of the K-map using Gray Code to ensure only one variable changes at a time between adjacent cells.
• Grouping: Always group the 1s in the largest possible groups. A larger group leads to a simpler Boolean expression.
• Minimizing: Each group represents a product term, and variables that change within a group are eliminated.
• Simplicity: The K-map provides a visual and intuitive way to simplify Boolean functions, especially for up to 4 variables.

K-maps are a powerful tool in digital logic design and are widely used to minimize expressions for efficient circuit implementation.