Karnaugh Map

Tags: #◇Computer Science #◇CSARCH1 #◇Problem Solving #◇M3

---

◇Overview

This sub-module discusses how to minimize Boolean functions using the Karnaugh Map.
The objectives are:

• Learn how to minimize Boolean functions using Karnaugh Map.
• Learn how to minimize Boolean functions with don’t care conditions using Karnaugh Map.

◇Karnaugh Map

A Karnaugh Map (K-map) is represented by $2^m$ squares where $m$ is the number of variables, and each of these squares represents a corresponding minterm or maxterm. It is a modified truth table intended to allow minimal SOP (Sum of Products) and POS (Product of Sums) expressions to be obtained by visual inspection.

Rules for Implementing K-Map

1. Groupings should be a factor of $2^n$ (1, 2, 4, 8, 16, etc.), where $n = 0, 1, \dots, m$.
2. Groupings should either be horizontal or vertical only. No diagonal groupings.
3. For each group, cover as many 1’s (for SOP) or 0’s (for POS) as possible since it will minimize the number of literals.
4. For each group, there should be at least one exclusive minterm or maxterm (a cell not covered by any other group).
5. You are allowed to use a minterm or a maxterm more than once if it would make a group bigger.
6. Each group corresponds to one product or sum term.
7. Remove redundant groups (a group is redundant when all its entries are already covered by other essential groups).

Number of Variables

• 2-Variable K-Map: 4 squares. Columns/Rows typically A, B.
• 3-Variable K-Map: 8 squares. Example headers using gray code (00, 01, 11, 10) to ensure adjacent columns differ by only one bit.
• 4-Variable K-Map: 16 squares.
• 5-Variable K-Map: 32 squares. Often split into two 16-square 4-variable K-maps representing A=0 and A=1.
• 6-Variable K-Map: 64 squares. Grouped as four 4-variable maps representing AB=00, AB=01, AB=10, AB=11.

Don't Care Conditions

• Don’t care conditions (represented by X or d) can be treated as either 0 or 1.
• They can be included in groups to make K-map groups bigger and further simplify the expression.
• Do not use them (i.e., just treat them as 0s) if they do not help in forming larger groups.

◇Worked Examples

• $F(A,B) = \Sigma m(0,2)$ simplifies to $B'$
• $F(A,B,C) = \Sigma m(0,1,2,5,6,7)$ simplifies to $A'B' + AC + BC'$
• $F(A,B,C,D) = \Sigma m(0,2,3,7,8,10,11,13)$ simplifies to $B'C + B'D' + A'CD + ABC'D$
• With Don't Care: $F(A,B,C,D) = \Sigma m(1,3,7,11,15)$ with $d(A,B,C,D) = \Sigma m(0,2,5)$ simplifies to $A'D + CD$

◇References & Navigation

• Previous Topic: ◇Logic Gates
• Next Topic: ◇Introduction to Hardware Description Language
• Related Notes: ◇Boolean Algebra, ◇Combinational Circuit - Design