Karnaugh Maps

Overview

Karnaugh Maps (K-Maps) are a visual tool used to simplify Boolean expressions by minimising the number of terms and operations. Simplifying Boolean expressions reduces the complexity of digital circuits, improving efficiency.

K-Maps provide an intuitive way to group and eliminate redundant terms in a Boolean expression. They are particularly useful for simplifying expressions with up to four variables.

Structure of a K-Map

A K-Map is a grid where each cell represents a minterm (a specific combination of variable values). The size of the grid depends on the number of variables:

2 variables: 2x2 grid
3 variables: 2x4 grid
4 variables: 4x4 grid

lightbulbExample

Example for 3 Variables (A, B, C):

AB \ C	0	1
00	0	1
01	2	3
11	6	7
10	4	5

The rows and columns are arranged in Gray code order, where only one-bit changes between adjacent cells (e.g., 00, 01, 11, 10).

Filling a K-Map

Identify the minterms from the Boolean function or truth table.
Mark 1s in the cells corresponding to the minterms.
Unused cells are filled with 0s.

Grouping 1s

To simplify, group adjacent cells containing 1s. Groups must be powers of 2 (e.g., 1, 2, 4, 8 cells):

Groups can wrap around the edges.
Larger groups lead to simpler expressions.

Simplifying Boolean Expressions

Step 1: Identify all groups of 1s in the K-Map.

Step 2: For each group, write the simplified term by eliminating variables that change within the group.

Step 3: Combine all simplified terms with OR (∨).

Example

lightbulbExample

Example: Simplifying a Boolean Expression Given Expression: $f(A, B, C) = \sum(1, 3, 5, 7)$

Step 1: Fill in the K-Map.

AB \ C	0	1
00	0	1
01	0	1
11	0	1
10	0	1

Step 2: Group the 1s.

AB \ C	0	1
00		1
01		1
11		1
10		1

Group 1: $C = 1$

Simplified Expression: $f(A, B, C) = C$

Benefits of Using K-Maps

Simplifies Boolean Expressions: Reduces circuit complexity.
Visual Representation: Easy to spot opportunities for simplification.
Handles Up to 4 Variables Easily: Beyond 4 variables, more advanced methods like the Quine-McCluskey algorithm may be preferable.

Note Summary

infoNote

Common Mistakes

Incorrect Grouping:

Groups must be powers of 2.
Overlapping groups are allowed but must contribute to simplification.

Ignoring Wrap-Around:

Failing to group cells that wrap around the edges.

Missing Simplification Opportunities:

Always aim for the largest possible groups.

Variable Misinterpretation:

Ensure the correct variable is simplified based on the group.