Karnaugh Maps for Boolean Minimization

In our previous lessons, you've seen how to simplify Boolean expressions using algebraic laws and how to use truth tables to define a function's behavior exhaustively. While algebra is powerful, it doesn't always guarantee you've found the simplest form. Truth tables, on the other hand, perfectly describe a function but don't simplify it at all. This lesson introduces a bridge between these two worlds: the Karnaugh map.

A Karnaugh map, or K-map, is a brilliant graphical tool that translates a truth table into a visual grid. By leveraging our natural ability to spot patterns, it allows us to perform Boolean simplification systematically and confidently find a minimal expression. Your background in data science has likely exposed you to various data visualization techniques that reveal underlying patterns; you can think of a K-map as a specialized visualization for Boolean functions.

By the end of this lesson, you will be able to take a Boolean function of up to four variables—either from a truth table or a list of minterms—and use a K-map to derive its simplified sum-of-products expression.

From Truth Table to K-Map

A K-map is essentially a rearranged truth table. For a function with $n$ variables, it has $2^n$ cells, with each cell corresponding to one minterm (one row of the truth table). The magic of the K-map lies in its unique cell arrangement.

Notice the numbering of the rows and columns in the maps above: 00, 01, 11, 10. This is not standard binary counting; it's a special sequence called Gray code. The key property of Gray code is that only one bit changes between any two adjacent numbers. This means that any two cells next to each other in the K-map (horizontally or vertically) represent input combinations that differ by only a single variable. This adjacency is the foundation for the entire simplification process.

The following article gives a great overview of the K-map structure and the importance of Gray code.

The K-Map Simplification Process

Simplifying a function with a K-map involves three main steps:

1. Plotting the function: Transfer the function's output from its truth table or minterm list into the K-map. For a Sum-of-Products (SOP) simplification, you place a 1 in every cell corresponding to a minterm where the function is true.
2. Grouping the 1s: This is the core step. You circle adjacent 1s to form rectangular groups. The goal is to cover all the 1s using the largest possible groups and the fewest number of groups.
3. Deriving the expression: Each group you've circled corresponds to a single, simplified product term. The final simplified function is the sum (ORing) of these terms.

Let's break down the rules for grouping.

Rules of Grouping

• Groups must contain only 1s.
• Groups must be rectangular. Diagonal or L-shaped groups are not allowed.
• The size of each group must be a power of two (1, 2, 4, 8, ...).
• Make groups as large as possible. A group of four is better than two groups of two.
• All 1s must be covered by at least one group.
• Groups can overlap. It is often necessary to overlap groups to ensure they are as large as possible.
• Use the minimum number of groups necessary to cover all the 1s.
• The map wraps around. The top and bottom edges are adjacent, and the left and right edges are adjacent. This means you can form groups across these edges. The four corners are also adjacent to each other.

The video below from ALL ABOUT ELECTRONICS provides excellent visual examples of how to form valid groups of two, four, and eight, including the crucial wrap-around groups.

From Groups to Simplified Terms

How does a group of 1s translate into a simplified term? The rule is simple: within a group, if a variable changes its value (from 0 to 1 or vice versa), it is eliminated from the term. The variables that remain constant form the product term.

• If a variable is constant at 1 throughout the group, it appears in the term (e.g., A).
• If a variable is constant at 0 throughout the group, it appears as its complement (e.g., $\overline{A}$).

The larger the group, the more variables change, and thus the more simplified the resulting term will be.

• A group of 1 eliminates 0 variables (e.g., $\overline{A}B\overline{C}D$).
• A group of 2 eliminates 1 variable (e.g., $\overline{A}B\overline{C}$).
• A group of 4 eliminates 2 variables (e.g., $\overline{A}B$).
• A group of 8 eliminates 3 variables (e.g., $\overline{A}$).

The video from The Organic Chemistry Tutor provides a clear, narrated walkthrough of this process, starting with a 3-variable map and moving to 4-variable examples.

A Complete Worked Example

Let's walk through the entire process for the function:
$F(A,B,C,D)=\Sigma m(1,3,4,5,6,7,13,15)$

Step 1: Plot the 1s on the K-map.

First, we place '1's in the cells corresponding to the minterms in our function.

Step 2: Identify the largest possible groups.

We find the largest possible groups to cover all the '1's. Here, we have three groups of four. Notice the green group (G1) covers an entire row, and the other two groups (G2 and G3) overlap.

• Green Group (G1): This group covers m4, m5, m6, m7.

  • A is constant at 0.
  • B is constant at 1.
  • C and D both change.
  • Therefore, the term is $\overline{A}B$.

• Blue Group (G2): This group covers m5, m7, m13, 15.

  • A changes (0 -> 1).
  • B is constant at 1.
  • C changes (0 -> 1).
  • D is constant at 1.
  • Therefore, the term is $BD$.

• Red Group (G3): This group covers m1, m3, m5, m7.

  • A is constant at 0.
  • B changes (0 -> 1).
  • C is constant at 1.
  • D changes (0 -> 1).
  • Therefore, the term is $\overline{A}C$.

Step 3: Combine the terms.

The final simplified expression is the sum of the terms from each group:
$F=\overline{A}B+BD+\overline{A}C$
We have successfully reduced a complex function of 8 minterms into a much simpler expression with only three product terms.

The video from ALL ABOUT ELECTRONICS provides several more solved examples, including cases with redundant groups, which are excellent for practice.

Conclusion

In this lesson, we've transformed the abstract task of Boolean simplification into a concrete, visual process. The Karnaugh map is a cornerstone of digital logic design, providing a systematic method to ensure you arrive at a minimal sum-of-products expression.

Here are the key takeaways:

• A Karnaugh map is a grid-based representation of a truth table where adjacent cells differ by only one bit, thanks to Gray code.
• The simplification process involves plotting 1s on the map and then grouping them into the largest possible rectangular blocks whose sizes are powers of two (1, 2, 4, 8...).
• The map wraps around from top-to-bottom and left-to-right, allowing for groups that cross the edges.
• Each group translates to a simplified product term by identifying the variables that remain constant within that group. The final expression is the sum of these terms.

Now that you can simplify a Boolean function into its minimal form, the next logical step is to build the circuit that implements it. In our next lesson, we will do just that, using both basic logic gates (AND, OR, NOT) and universal gates (NAND, NOR) to bring our simplified expressions to life.