Karnaugh Maps for Boolean Minimization

1. The Karnaugh Map: A Visual Truth Table

A Karnaugh map is a grid-like representation of a function's truth table. Its power comes from a special arrangement of cells where any two adjacent cells (including wrapping around the edges) differ in the value of only a single input variable. This property, known as adjacency, is achieved by ordering the rows and columns using Gray code, a binary numeral system where two successive values differ in only one bit.

This adjacency is what allows us to spot opportunities for simplification visually. When we group adjacent cells containing '1's, we are effectively applying the Boolean algebra rule $XY+X{Y}^{\prime }=X$.

Let's first understand the structure of the most common type you'll encounter in GATE, the 4-variable K-map.

A 2-variable map has $2^2=4$ cells, and a 3-variable map has $2^3=8$ cells. Their structures follow the same principle, just with fewer variables.

2. Minimization using K-maps: Sum-of-Products (SOP)

The goal of minimization is to find the simplest possible SOP expression, which corresponds to a digital circuit with the fewest gates and inputs. This is a three-step process: Map, Group, and Derive.

Step 1: Mapping the Function

To map a function, you place a '1' in each cell corresponding to a minterm present in the function. If the function is given as $F=\Sigma m(i_1,i_2,...)$, you simply fill the cells with indices $i_1,i_2,...$ with '1's. All other cells are filled with '0's.

Step 2: Grouping the '1's

This is the core of the K-map method. You group adjacent '1's according to a set of rules to form what are called prime implicants.

Rules of Grouping:

1. Group Size: Groups must contain a number of '1's that is a power of two: 1, 2, 4, 8, etc. No groups of 3, 5, or 6.
2. Shape: Groups must be rectangular (including squares).
3. Adjacency: You can group '1's that are adjacent horizontally or vertically.
4. Wrap-around: The map is considered to wrap around. The top row is adjacent to the bottom row, and the leftmost column is adjacent to the rightmost column. This allows you to group '1's across the edges. For example, minterms $m_0$ and $m_8$ are adjacent in a 4-variable map.
5. Goal: Create the largest possible groups.
6. Coverage: Every '1' on the map must be included in at least one group.
7. Overlapping: Groups are allowed to overlap if this helps in creating a larger group.

The following video resource demonstrates these grouping possibilities brilliantly.

Step 3: Deriving the Simplified Expression

Each group you've created corresponds to a single product term in the final simplified expression. To find the term for a group:

• Identify the input variables whose values do not change across all the cells in that group.
• If a non-changing variable's value is '1', include it in its true form (e.g., $A$).
• If its value is '0', include it in its complemented form (e.g., $A^{\prime }$).
• The final simplified function is the logical OR (sum) of the product terms derived from all the groups.

A group of size $2^k$ in an n-variable map will result in a product term with $n-k$ variables. For instance, in a 4-variable map, a group of 4 ($2^2$) '1's yields a term with $4-2=2$ variables.

Essential vs. Redundant Groups

After forming groups, you must select the minimum set of groups that covers all the '1's.

• An Essential Prime Implicant is a group that covers at least one '1' that cannot be covered by any other group. You must include all essential prime implicants in your final expression.
• A Redundant Group is one where all of its '1's are already covered by other essential groups. These should be eliminated to achieve the truly minimal expression.

This concept is a common source of error, so it's vital to master.

3. Don't-Care Conditions

In some digital systems, certain input combinations are guaranteed never to occur, or their output value doesn't matter. These are called don't-care conditions, denoted by an 'X' or 'd' on the K-map.

The great advantage of don't-cares is that they offer flexibility.

• You can choose to include a don't-care cell in a group if it helps you form a larger group of '1's.
• You are not required to cover any of the 'X's. You can ignore them if they don't help.

Essentially, you treat an 'X' as a '1' if it helps you, and as a '0' if it doesn't.

Example: Minimize the function $F(A,B,C,D)=\Sigma m(1,5,13,15)+d(0,7,14)$.

1. Map: Place '1's at cells 1, 5, 13, 15. Place 'X's at cells 0, 7, 14.
2. Group:
   • The four '1's at 1, 5, 13, 15 form a group. The variables that don't change are B (which is 0) and D (which is 1). So this group gives the term $B^{\prime }D$.
   • We could stop here, as all '1's are covered. However, let's see if the don't-cares help.
   • The '1' at 15 can be grouped with the 'X' at 7 and the '1' at 13. This gives a group of four: 5, 7, 13, 15. This group gives the term $BD$.
   • The '1' at 13 can also be grouped with the 'X' at 14 and the '1' at 15. This gives another group of four: 13, 14, 15. This group gives the term $AC$.

Wait, the first group $B^{\prime }D$ already covered all the '1's. The other groups are redundant. Let's re-evaluate to get larger groups.

• Consider the group of four: cells 1, 5, 13, 9. Oh, wait, 9 is a 0.
• Let's try again. The '1' at 1 is adjacent to the 'X' at 0. But that's just a pair. The '1' at 1 is also adjacent to the '1' at 5. Let's group (1, 5). This gives $A^{\prime }{C}^{\prime }D$.
• The '1' at 13 is adjacent to the '1' at 5. But they are already part of a bigger potential group.
• Let's think strategically. How to cover the '1' at 1? We can group it with the '1' at 5. That's a group of two: (1, 5) -> $A^{\prime }{C}^{\prime }D$.
• How to cover the '1' at 13? We can group it with the '1' at 15. But we can make that group bigger by including the don't-care 'X' at 14. So we have a group of four: (13, 15, 14, 12 is a 0). Ah, the group is (13, 15) along with the X at 14. That's not a valid rectangular group of 4.
• Let's try grouping (13, 15). This gives $ABD$.
• Okay, let's restart with the goal of LARGEST groups first.
  • The four corners (0, 2, 8, 10) are all 0 or X. Not useful.
  • Let's look at the '1' at 15. It can be grouped with 13, and also with the 'X' at 7 and 14.
  • Group 1: (5, 7, 13, 15). This is a valid group of four. The '1's are at 5, 13, 15, and the 'X' is at 7. What is constant? B is 1, D is 1. The term is $BD$.
  • Group 2: The only '1' not covered is at cell 1. It can be grouped with the '1' at 5. This is group (1, 5). What is constant? A is 0, C is 0, D is 1. Term: $A^{\prime }{C}^{\prime }D$.
  • So, one solution is $F=BD+A^{\prime }{C}^{\prime }D$.

Let's see if there's a better way.

• What if we cover the '1' at 1 by grouping it with the 'X' at 0? That's group (0,1). Term is $A^{\prime }{B}^{\prime }{C}^{\prime }$. This seems worse.
• The previous grouping seems best. Group 1: (5, 7, 13, 15) gives $BD$. Group 2: (1, 5) gives $A^{\prime }{C}^{\prime }D$. All '1's are covered. Final function: $F=BD+A^{\prime }{C}^{\prime }D$. The don't-care at 7 was useful, the others were not.

4. Minimization for Product-of-Sums (POS)

You can also use a K-map to find a minimal POS expression. The process is nearly identical, but with a few inverted rules:

1. Group the '0's instead of the '1's. The rules for forming groups (power of 2, wrap-around, etc.) are the same.
2. Derive Sum Terms: For each group of '0's, find the variables that don't change.
   • If a non-changing variable is '0', use its true form (e.g., $A$).
   • If it is '1', use its complemented form (e.g., $A^{\prime }$).
   • These variables are ORed together to form a sum term.
3. Final Expression: The final simplified function is the logical AND (product) of all the sum terms derived from the groups of '0's. This gives you the simplified $F^{\prime }$. To get F, you apply De Morgan's theorem to the whole expression. A more direct way is to get the sum terms and product them together.

For example, if a group of '0's gives you the term $A+B^{\prime }$, and another group gives $C+D$, the final POS expression is $F=(A+B^{\prime })(C+D)$.

Conclusion

In this lesson, we have transformed the task of Boolean simplification from an algebraic puzzle into a systematic, graphical process. The Karnaugh map is your go-to tool for quickly and accurately minimizing functions of up to 4 variables, a skill that directly translates to marks in the GATE exam.

Key Takeaways:

• K-map Structure: K-maps are arranged using Gray code to ensure adjacent cells differ by only one bit.
• SOP Minimization: Map the function's '1's, form the largest possible groups of '1's (in powers of two, allowing wrap-around and overlap), and derive a product term for each group. The result is a sum of these terms.
• Don't-Care Conditions: Use 'X's to your advantage. Include them in groups to make the groups larger, but you are not required to cover them.
• POS Minimization: The same process applies, but you group the '0's and derive sum terms with inverted variable logic.
• Minimal Expression: Always check for and eliminate redundant groups to ensure you have the simplest possible expression.

Now that you can derive simplified logic expressions, the next logical step is to see what we build with them. In the upcoming lesson, we will begin our study of Combinational Circuits, starting with fundamental building blocks like adders and subtractors. You will see how the expressions we've learned to minimize are directly implemented using logic gates to perform arithmetic.