Show understanding of Karnaugh maps (K-map)

15.2 Boolean Algebra and Logic Circuits – Karnaugh Maps

What is a Karnaugh Map?

A K‑map is a grid that arranges all possible combinations of input variables so that adjacent cells differ in only one variable. This adjacency property lets you spot patterns (groups) that correspond to simplified product terms.

How to Build a K‑map

1. Decide how many variables you have (e.g., 4 variables → 16 cells).
2. Use Gray code ordering for rows and columns so that only one bit changes between adjacent cells.
3. Fill in the cells with the minterm numbers (or 1/0 if you’re mapping a function).
4. Wrap around the edges: the left edge is adjacent to the right edge, and the top edge is adjacent to the bottom edge.

Grouping Rules

• Groups must contain powers of two cells: 1, 2, 4, 8, …
• Cells in a group must be adjacent (including wrap‑around).
• Try to make groups as large as possible; larger groups mean fewer variables in the product term.
• Each minterm must be covered by at least one group (overlap is allowed).

Example: Simplifying a 4‑Variable Function

Let’s simplify the function $$F(A,B,C,D) = \sum m(0,1,2,5,6,7,8,9,10,14).$$
🗺️ Here’s the K‑map for this function:

Step 1 – Identify groups:

• Group A: Cells 0,1,8,9 (a 2×2 block). Resulting term: $\bar{B}\bar{C}$
• Group B: Cells 2,6,10,14 (a vertical column). Resulting term: $C\bar{D}$
• Group C: Cells 5,7 (a pair). Resulting term: $\bar{A}BD$

Simplified Expression

Combining the three product terms gives the minimal sum‑of‑products form: $$F = \bar{B}\bar{C} + C\bar{D} + \bar{A}BD.$$
🎯 Notice how the number of variables in each term is reduced compared to the original expression.

Analogy Recap

Think of the K‑map as a neighbourhood map where each house (cell) has a unique address (minterm). By grouping houses that share a common feature (variable), you’re essentially creating a neighbourhood association that can be described with fewer words (variables). This makes it easier to design efficient logic circuits.