Unit 5 — Karnaugh Maps

Unit Overview (click to expand)

Welcome to Unit 5, where we learn one of the most elegant tools in a digital designer's toolkit — the Karnaugh map, or K-map. If Boolean algebra gives you the rules and canonical forms give you the starting point, the K-map gives you a visual method to find the simplest possible expression quickly and reliably. A Karnaugh map is a grid that rearranges truth table rows so that physically adjacent cells differ by exactly one variable. This arrangement relies on Gray code ordering. When two adjacent cells both contain a one, the variable that changes between them cancels out. That is the core insight: adjacency on the map corresponds directly to algebraic simplification. Your goal is to circle rectangular groups of ones, where every group must contain a power-of-two number of cells. Groups can wrap around the edges because the K-map is logically a torus. Each group corresponds to a simplified product term. A prime implicant is a group that cannot be made any larger. An essential prime implicant covers at least one minterm not covered by any other prime implicant — you must include it in your final expression. The strategy is to identify all essential prime implicants first, then cover any remaining minterms with the fewest additional prime implicants. Don't care conditions once again prove invaluable. Because don't cares can be treated as either one or zero, you can include them in your groups to make those groups larger, producing fewer literals and a simpler circuit. **Key Takeaways** 1. Gray code ordering on the K-map ensures that adjacent cells differ by one variable, so grouping adjacent ones directly eliminates variables from the expression. 2. Prime implicants and essential prime implicants guide you toward the minimal expression — always identify essentials first, then cover the rest. 3. Don't care conditions can be included in groups to create larger groupings, leading to simpler, more efficient circuit implementations.

Summary

Karnaugh maps (K-maps) provide a powerful graphical method for simplifying Boolean functions, transforming the abstract process of algebraic manipulation into visual pattern recognition. Developed by Maurice Karnaugh in 1953, this technique exploits the adjacency properties of Gray code ordering to identify opportunities for variable elimination. This unit covers K-map construction for 2, 3, 4, and 5 variables, teaching students to recognize valid groupings that lead to simpler expressions. The concepts of implicants, prime implicants, and essential prime implicants formalize the simplification process, enabling systematic derivation of minimal Sum of Products (SOP) and Product of Sums (POS) expressions. Students will learn to handle don't care conditions, recognize when multiple minimal solutions exist, and understand the limitations of K-maps for larger functions.

Concepts Covered

Karnaugh Map
K-Map Structure
K-Map Cell
K-Map Variables
Two Variable K-Map
Three Variable K-Map
Four Variable K-Map
Five Variable K-Map
K-Map Gray Code Order
K-Map Adjacency
Logical Adjacency
Physical Adjacency
K-Map Grouping
Group of Ones
Group of Zeros
Valid Group Sizes
Rectangular Groups
Wrapping in K-Maps
Corner Grouping
Implicant
Prime Implicant
Essential Prime Implicant
Redundant Prime Implicant
K-Map SOP Simplification
K-Map POS Simplification
Minimal SOP Expression
Minimal POS Expression
K-Map with Dont Cares
Using Dont Cares
Overlapping Groups
Covering All Ones
Covering All Zeros
Multiple Solutions
Cost of Expression
Gate Count Minimization
Literal Minimization
K-Map Limitations
Five Variable Technique
Entered Variable K-Map
K-Map vs Algebraic Method

Prerequisites

Before beginning this unit, students should have:

Thorough understanding of minterms and maxterms (Unit 4)
Familiarity with canonical SOP and POS forms
Knowledge of Gray code ordering (Unit 3)
Understanding of don't care conditions

5.1 Introduction to Karnaugh Maps

A Karnaugh map (K-map) is a graphical tool for simplifying Boolean functions that arranges the truth table in a grid format where adjacent cells differ by exactly one variable. This arrangement makes it easy to identify groups of 1s (or 0s) that can be combined to eliminate variables.

K-Map Structure

The K-map structure consists of:

A rectangular grid of K-map cells, one for each minterm
Row and column labels using Gray code order (adjacent labels differ by one bit)
Each cell corresponds to one input combination

The power of K-maps lies in their adjacency property: cells that are physically adjacent on the map are also logically adjacent, meaning their minterms differ in exactly one variable. When two logically adjacent minterms are ORed together, the differing variable cancels out.

Example: Minterms \(m_5 = A\overline{B}C\) and \(m_7 = ABC\) differ only in B:

\[m_5 + m_7 = A\overline{B}C + ABC = AC(\overline{B} + B) = AC\]

K-Map Variables

K-map variables determine the map dimensions:

Variables	Cells	Typical Layout
2	4	2×2 grid
3	8	2×4 grid
4	16	4×4 grid
5	32	Two 4×4 grids
6	64	Four 4×4 grids

K-maps become impractical beyond 5-6 variables due to the difficulty of visualizing adjacencies.

5.2 Two-Variable K-Map

The two-variable K-map is the simplest form, with 4 cells arranged in a 2×2 grid.

	B = 0	B = 1
A = 0	m₀	m₁
A = 1	m₂	m₃

Each cell contains the function value (0, 1, or X) for that minterm.

Example: Simplify \(F(A,B) = \Sigma m(0,1,3)\)

	B = 0	B = 1
A = 0	1	1
A = 1	0	1

Groups:

Horizontal pair (m₀, m₁): A = 0 for both → \(\overline{A}\)
Vertical pair (m₁, m₃): B = 1 for both → \(B\)

Result: \(F = \overline{A} + B\)

5.3 Three-Variable K-Map

The three-variable K-map uses a 2×4 grid with one variable on rows and two on columns (or vice versa).

	BC = 00	BC = 01	BC = 11	BC = 10
A = 0	m₀	m₁	m₃	m₂
A = 1	m₄	m₅	m₇	m₆

Note the Gray code order for BC: 00, 01, 11, 10 (not binary order 00, 01, 10, 11). This ensures adjacent columns differ by exactly one bit.

K-Map Adjacency in 3-Variable Maps

Physical adjacency on the map corresponds to logical adjacency (differing by one variable):

Horizontally adjacent cells differ in one column variable
Vertically adjacent cells differ in the row variable
The left and right edges wrap around (column 00 is adjacent to column 10)

Example: Simplify \(F(A,B,C) = \Sigma m(0,2,4,5,6)\)

	BC = 00	BC = 01	BC = 11	BC = 10
A = 0	1	0	0	1
A = 1	1	1	0	1

Groups:

Wrap-around group (m₀, m₂, m₄, m₆) spans columns 00 and 10 → \(\overline{C}\)
Remaining 1: m₅, covered by pair (m₄, m₅) → \(A\overline{B}\)

Result: \(F = \overline{C} + A\overline{B}\)

Diagram: 3-Variable K-Map Simulator

5.4 Four-Variable K-Map

The four-variable K-map is the most commonly used size, with 16 cells in a 4×4 grid.

	CD = 00	CD = 01	CD = 11	CD = 10
AB = 00	m₀	m₁	m₃	m₂
AB = 01	m₄	m₅	m₇	m₆
AB = 11	m₁₂	m₁₃	m₁₅	m₁₄
AB = 10	m₈	m₉	m₁₁	m₁₀

Both row labels (AB) and column labels (CD) use Gray code order: 00, 01, 11, 10.

Adjacencies in 4-Variable K-Maps

In a 4-variable K-map:

Horizontal adjacency: Left-right neighbors (including wrap from column 10 to 00)
Vertical adjacency: Top-bottom neighbors (including wrap from row 10 to 00)
Corner grouping: All four corners are mutually adjacent (wrap both ways)

The 4-variable K-map forms a torus topology—imagine wrapping the map into a donut shape where both top/bottom and left/right edges connect.

Key Insight — Wrapping: The edges of the K-map connect to form adjacencies. Column 00 is adjacent to column 10 (horizontal wrap), row 00 is adjacent to row 10 (vertical wrap), and all four corner cells (m₀, m₂, m₈, m₁₀) are mutually adjacent (corner wrap).

Example: Four corner cells form a valid group of 4

	CD = 00	CD = 10
AB = 00	1	1
AB = 01	0	0
AB = 11	0	0
AB = 10	1	1

The green-highlighted corner cells form one group: \(\overline{B}\,\overline{D}\) (B = 0 and D = 0 for all four).

Diagram: K-Map Solver

5.5 Valid Groups and Grouping Rules

Valid Group Sizes

Groups in a K-map must contain a power of 2 cells: 1, 2, 4, 8, 16, etc. Each doubling of group size eliminates one variable from the product term.

Group Size	Variables Eliminated	Literals in Term
1	0	n (all variables)
2	1	n − 1
4	2	n − 2
8	3	n − 3
16	4	0 (constant 1)

Rectangular Groups

Groups must form rectangles (including squares) on the K-map. The rectangle can wrap around edges but must maintain its rectangular shape conceptually.

Valid groups:

1×1 (single cell)
1×2 or 2×1 (pair)
1×4, 4×1, or 2×2 (quad)
1×8, 8×1, 2×4, or 4×2 (octet)
4×4 (16 cells)

Invalid groups:

L-shaped
T-shaped
Diagonal
Non-power-of-2 sizes (3, 5, 6, etc.)

Grouping for SOP vs POS

SOP — Group the 1s

Each group of 1s becomes a product term in the sum.

POS — Group the 0s

Each group of 0s becomes a sum term in the product.

Overlapping Groups

Overlapping groups are allowed and often necessary for minimal expressions. A cell can belong to multiple groups—this doesn't duplicate it in the final expression; it just means that cell's minterm is covered by multiple product terms.

Example: Overlapping groups are beneficial

	CD = 00	CD = 01	CD = 11	CD = 10
AB = 00	1	1	0	0
AB = 01	1	1	1	0

Group 1 (m₀, m₁, m₄, m₅): \(\overline{A}\,\overline{C}\) — A = 0, C = 0 for all four cells

Group 2 (m₅, m₇): \(\overline{A}\,B\,D\) — A = 0, B = 1, D = 1 for both cells

Cell m₅ belongs to both groups (shown in orange). The overlap does not cause duplication.

Result: \(F = \overline{A}\,\overline{C} + \overline{A}\,B\,D\)

5.6 Implicants and Prime Implicants

Implicants

An implicant is any product term that covers one or more minterms of the function. Every minterm is an implicant, and any valid K-map group represents an implicant.

Example: Implicants for \(F = \Sigma m(1,3,5,7)\)

\(m_1 = \overline{A}\,\overline{B}\,C\) is an implicant (covers m₁)
\(\overline{A}\,C\) is an implicant (covers m₁ and m₃)
\(C\) is an implicant (covers m₁, m₃, m₅, m₇)

Prime Implicants

A prime implicant is an implicant that cannot be combined with another implicant to form a larger group. It represents the largest possible grouping containing a particular set of minterms.

Finding prime implicants: A group is prime if it cannot be expanded (doubled in size) while remaining a valid group of 1s.

In the example above, \(C\) is the only prime implicant—it covers all 1s and cannot be made larger.

Essential Prime Implicants

An essential prime implicant is a prime implicant that covers at least one minterm not covered by any other prime implicant. Essential prime implicants must be included in any minimal solution.

Finding Essential PIs:

Identify all prime implicants
For each minterm, list which PIs cover it
If a minterm is covered by only one PI, that PI is essential

Redundant Prime Implicants

A redundant prime implicant is a prime implicant that is not needed because all its minterms are already covered by essential prime implicants or other selected PIs.

Systematic Minimization Procedure

Find all prime implicants (largest possible groups)
Identify essential prime implicants (must include)
Select additional PIs to cover remaining minterms (minimize overlap)
The selected PIs form the minimal expression

Diagram: Prime Implicant Finder

5.7 K-Map SOP Simplification

K-Map SOP simplification produces a minimal Sum of Products expression.

Procedure for Minimal SOP

Plot the function: Place 1s in cells corresponding to minterms where F = 1
Identify all prime implicants: Find all maximal groups of 1s
Select essential prime implicants: Include all PIs that cover unique minterms
Cover remaining minterms: Add minimum additional PIs
Write the expression: OR together the product terms from selected groups

Reading Product Terms from Groups

For each group, identify the variables that have constant value across the group:

Variable Behavior	Action
= 1 in all cells	Include uncomplemented
= 0 in all cells	Include complemented
Changes across cells	Omit from term

Example: A group covering cells where A=1, B varies, C=0, D varies: The term is \(A\overline{C}\) (only A and C are constant).

Covering All Ones

The goal is covering all ones with the minimum number of prime implicants. Every cell containing 1 must be included in at least one selected group.

Example: Simplify \(F(A,B,C,D) = \Sigma m(0,1,2,4,5,6,8,9,12,13,14)\)

	CD = 00	CD = 01	CD = 10
AB = 00	1	1	1
AB = 01	1	1	1
AB = 11	1	1	1
AB = 10	1	1	0

Prime implicants (all essential):

\(\overline{C}\) — columns 00 and 01, all rows (covers m₀, m₁, m₄, m₅, m₈, m₉, m₁₂, m₁₃)
\(\overline{A}\,\overline{D}\) — rows 00, 01, columns 00 and 10 wrapping (only PI covering m₂)
\(B\,\overline{D}\) — rows 01, 11, columns 00 and 10 wrapping (only PI covering m₁₄)

Result: \(F = \overline{C} + \overline{A}\,\overline{D} + B\,\overline{D}\)

5.8 K-Map POS Simplification

K-Map POS simplification produces a minimal Product of Sums expression by grouping 0s instead of 1s.

Procedure for Minimal POS

Plot the function: Place 0s in cells where F = 0
Group the 0s: Find all prime implicants of \(\overline{F}\)
Write each group as a sum term:
- Variable = 0 in all cells → include uncomplemented
- Variable = 1 in all cells → include complemented
- (Opposite of SOP rule!)
AND all sum terms together

Reading Sum Terms from Groups of Zeros

For a group of 0s, the sum term includes:

Condition	Action
Variable is 0 throughout the group	Include uncomplemented
Variable is 1 throughout the group	Include complemented
Variable changes	Omit from sum term

This is the dual of the SOP rule — the goal is covering all zeros with the minimum number of groups.

Choosing SOP vs POS

Compare the literal counts of minimal SOP and minimal POS — choose the simpler form.

SOP likely simpler

Few 1s, many 0s — fewer product terms to cover

POS likely simpler

Few 0s, many 1s — fewer sum terms to cover

Balanced

Always check both SOP and POS forms

Function Characteristic	Likely Simpler Form
Few 1s, many 0s	SOP
Few 0s, many 1s	POS
Balanced	Check both

5.9 K-Maps with Don't Cares

K-maps with don't cares include cells marked with X (or d) representing input combinations where the output doesn't matter.

Using Don't Cares

For SOP

Treat don't cares as 1s if they help form larger groups

For POS

Treat don't cares as 0s if they help form larger groups

The optimizer chooses the most beneficial assignment for each don't care independently.

Don't cares are NOT required to be covered. They only help if they extend a group.

Example: \(F(A,B,C,D) = \Sigma m(1,3,7,11,15) + d(0,2,5)\)

	CD = 00	CD = 01	CD = 11	CD = 10
AB = 00	X	1	1	X
AB = 01	0	X	1	0
AB = 11	0	0	1	0
AB = 10	0	0	1	0

Without don't cares: Would need to cover m₁, m₃, m₇, m₁₁, m₁₅

With don't cares:

Treat m₀ and m₂ as 1s to form group (m₀, m₁, m₂, m₃): \(\overline{A}\,\overline{B}\)
Column CD = 11 (m₃, m₇, m₁₁, m₁₅): \(CD\)

Result: \(F = \overline{A}\,\overline{B} + CD\) — much simpler than without don't cares!

Diagram: K-Map with Don't Cares

5.10 Five-Variable K-Maps

The five-variable K-map extends the technique to 32 cells, typically displayed as two adjacent 4×4 maps.

Five-Variable Technique

The five-variable technique uses two 4×4 K-maps — one for the fifth variable = 0 and one for = 1:

E = 0

	CD=00	CD=01	CD=11	CD=10
AB=00	m₀	m₁	m₃	m₂
AB=01	m₄	m₅	m₇	m₆
AB=11	m₁₂	m₁₃	m₁₅	m₁₄
AB=10	m₈	m₉	m₁₁	m₁₀

E = 1

	CD=00	CD=01	CD=11	CD=10
AB=00	m₁₆	m₁₇	m₁₉	m₁₈
AB=01	m₂₀	m₂₁	m₂₃	m₂₂
AB=11	m₂₈	m₂₉	m₃₁	m₃₀
AB=10	m₂₄	m₂₅	m₂₇	m₂₆

Key Insight — 5-Variable Adjacency: Cells in corresponding positions of the two maps are adjacent (they differ only in E). For example, m₅ (in E=0 map) is adjacent to m₂₁ (in E=1 map) because m₅ = 00101 and m₂₁ = 10101 — they differ only in the E bit.

Grouping Across Maps

E = 0 map only

\(\overline{E}\) appears in the product term

E = 1 map only

\(E\) appears in the product term

Both maps (corresponding)

\(E\) is eliminated from the term

Example: If cells m₃, m₇ (E=0) and m₁₉, m₂₃ (E=1) are all 1s, they form a group of 4 with term \(BD\) (E is eliminated).

5.11 Multiple Solutions and Cost Metrics

Multiple Solutions

Some functions have multiple solutions — different groupings that produce expressions with the same minimal cost. Both are equally valid minimal forms.

Example: Multiple Minimal Solutions

Consider \(F(A,B,C,D) = \Sigma m(0,1,2,5,6,7,8,9,10,14)\). After identifying essential prime implicants, suppose minterms m₅ and m₆ remain uncovered. If two different non-essential prime implicants each cover one of these remaining minterms with equal cost, choosing one over the other yields a different but equally minimal expression.

When multiple prime implicants can cover the same remaining minterms after essential PIs, different valid choices lead to different but equally minimal expressions.

Cost of Expression

Literal Count

Total number of variable appearances

Term Count

Number of product terms (SOP) or sum terms (POS)

Gate Count

Number of logic gates needed for implementation

Gate Count Minimization

Gate count minimization considers implementation details:

Example: Gate Count for \(F = AB + \overline{A}C\)

Component	Count	Details
AND gates	2	2 inputs each
OR gates	1	2 inputs
Inverters	1	for \(\overline{A}\)
Total	4	gates

Literal Minimization

Literal minimization is often the primary goal because it directly reduces gate input counts, correlates with wiring complexity, and is simple to count and compare.

K-maps guarantee minimal two-level SOP/POS

K-map minimization produces expressions optimal for two-level AND-OR (SOP) or OR-AND (POS) implementations. Multi-level implementations may be more efficient but require different techniques.

5.12 K-Map Limitations and Alternatives

K-Map Limitations

Limitation	Details
Scalability	Impractical beyond 5–6 variables
Human error	Easy to miss groups or make mistakes
Automation	Difficult to automate (pattern recognition is visual)
Multiple outputs	No direct support for multi-output optimization

Alternatives for Large Functions

For functions with many variables:

Quine-McCluskey algorithm: Systematic tabular method (works for any number of variables)
ESPRESSO: Heuristic minimization for practical large functions
Computer-aided design (CAD) tools: Automated optimization

Entered Variable K-Maps

An entered variable K-map reduces the map size by placing variables (not just 0/1) in cells. This allows an n-variable function to be represented on an (n−1)-variable map.

Example: 4-Variable Function on a 2×2 Map

	B = 0	B = 1
A = 0	\(\overline{C}D\)	\(D\)
A = 1	1	\(C + D\)

Each cell contains an expression in the remaining variables (C, D). Useful for documentation and quick analysis but less common in coursework.

K-Map vs Algebraic Method

Criterion	K-Map	Algebraic
Variables	2–5 practical	Any number
Speed (small functions)	Fast	Slow
Guaranteed minimum	Yes (2-level)	Depends on skill
Error prone	Visual errors	Algebra errors
Automation	Difficult	Straightforward
Learning curve	Visual, intuitive	Abstract

When to use K-maps

4 variables or fewer
Quick simplification needed
Visual verification desired

When to use algebraic methods

Many variables
Computer implementation
Multi-level optimization

Diagram: K-Map Practice Challenge

Summary and Key Takeaways

This unit provided mastery of Karnaugh maps for Boolean function simplification:

Karnaugh maps arrange truth table values in a grid where adjacent cells differ by one variable, enabling visual simplification.
Gray code ordering ensures physical adjacency corresponds to logical adjacency (one-bit difference).
K-map sizes range from 2×2 (2 variables) to paired 4×4 grids (5 variables). Beyond 5–6 variables, K-maps become impractical.
Valid groups must contain a power of 2 cells (1, 2, 4, 8, 16) in rectangular shapes. Groups can wrap around edges.
Grouping rules: For SOP — group 1s, each group becomes a product term. For POS — group 0s, each group becomes a sum term.
Prime implicants are maximal groups that cannot be expanded. Essential prime implicants must appear in every minimal solution.
Don't cares (X) can be treated as 1 or 0 as convenient, enabling larger groups and simpler expressions.
Overlapping groups are allowed — cells can belong to multiple groups without duplication in the expression.
Minimal expressions are achieved by covering all required cells with the fewest prime implicants.
Multiple solutions may exist when non-essential PIs can be chosen differently while maintaining minimum cost.
Literal count and gate count measure expression complexity. K-maps guarantee minimal two-level implementations.

Self-Check: What makes a prime implicant 'essential'?

A prime implicant is essential if it covers at least one minterm that no other prime implicant covers. Essential PIs must be included in every minimal solution.

Self-Check: In a 4-variable K-map, are the four corner cells adjacent to each other?

Yes! Due to wrap-around in both horizontal and vertical directions, all four corners (m₀, m₂, m₈, m₁₀) are mutually adjacent and can form a single group of 4.

Self-Check: When simplifying with don't cares, must all X cells be covered?

No. Don't cares are optional—include them in groups only if they help form larger groups. Uncovered don't cares simply remain undefined in the implementation.

Interactive Walkthrough

Step through K-map simplification of a 4-variable function with grouping and term extraction:

Take the Unit Quiz | See Annotated References