Skip to content

K-Maps

Introduction to Karnaugh Maps (K-Maps)

A Karnaugh Map (K-map) is a graphical tool used to simplify Boolean expressions and minimize the number of logic gates required for a given Boolean function. It’s especially useful for reducing the complexity of expressions in digital circuits.

In simple terms, K-map helps us convert a Boolean expression into a simpler and more efficient circuit by grouping terms in a way that makes simplification easy.

🌍 How Does a Karnaugh Map Work?

The K-map is a 2D grid (usually) where each cell represents a minterm of the Boolean expression. By organizing the minterms into a specific pattern, we can group adjacent 1’s (for SOP) or 0’s (for POS) in powers of 2 (1, 2, 4, 8, etc.), and then simplify the Boolean expression.

Basic Structure of a K-map:

  • Rows and Columns represent all possible combinations of input variables.
  • Cells in the map correspond to the minterms of the Boolean expression.

🔢 How to Create a K-map:

  1. Determine the number of variables in the Boolean expression.
    • For n variables, the K-map will have 2n2^n2n cells.
    • For example, a 3-variable K-map will have 23=82^3 = 823=8 cells.
  2. Label the rows and columns with all possible combinations of variables (in Gray code).
    • Gray code is used to minimize the number of changes between adjacent cells (only one variable changes between two adjacent cells).
  3. Fill the K-map with 1’s and 0’s:
    • Place 1 in the cell if the corresponding minterm is 1 in the Boolean expression, and 0 if it is 0.
  4. Group the adjacent 1’s:
    • Group 1’s in powers of 2 (1, 2, 4, 8, etc.). The groups must be rectangular or square and can wrap around the edges of the map.
    • Larger groups mean simpler Boolean expressions.
  5. Simplify the Boolean expression:
    • For each group, derive a simplified term.
    • The terms for each group are ORed together to get the final simplified Boolean expression.

🧑‍🏫 Example 1: 2-Variable K-map

Let’s begin with a 2-variable K-map.

Boolean Expression: F(A,B)=A⋅B+A‾⋅BF(A, B) = A \cdot B + \overline{A} \cdot BF(A,B)=A⋅B+A⋅B

Step 1: Create the K-map

  1. A 2-variable Boolean function will have 4 cells. Label the rows and columns as follows (in Gray code):
B = 0B = 1
A = 001
A = 101
  1. The function A⋅B+A‾⋅BA \cdot B + \overline{A} \cdot BA⋅B+A⋅B has 1’s at the positions corresponding to:
    • A=1,B=1A = 1, B = 1A=1,B=1 (for A⋅BA \cdot BA⋅B)
    • A=0,B=1A = 0, B = 1A=0,B=1 (for A‾⋅B\overline{A} \cdot BA⋅B)

Step 2: Group the 1’s

  • We have two 1’s adjacent to each other in the same column (for B=1B = 1B=1).
  • These can be grouped together.

Step 3: Simplify

  • The group of 1’s represents BBB (since AAA varies within the group, we eliminate it).
  • The simplified Boolean expression is: F(A,B)=BF(A, B) = BF(A,B)=B

Thus, the expression simplifies from A⋅B+A‾⋅BA \cdot B + \overline{A} \cdot BA⋅B+A⋅B to just B.

🧑‍🏫 Example 2: 3-Variable K-map

Let’s now look at a 3-variable K-map.

Boolean Expression: F(A,B,C)=A⋅B⋅C‾+A⋅B‾⋅C+A‾⋅B⋅CF(A, B, C) = A \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot C + \overline{A} \cdot B \cdot CF(A,B,C)=A⋅B⋅C+A⋅B⋅C+A⋅B⋅C

Step 1: Create the K-map

  1. A 3-variable Boolean function will have 8 cells (since 23=82^3 = 823=8).
  2. Label the rows and columns in Gray code:
C = 0C = 1
AB = 0000
AB = 0110
AB = 1111
AB = 1001
  1. The function F(A,B,C)=A⋅B⋅C‾+A⋅B‾⋅C+A‾⋅B⋅CF(A, B, C) = A \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot C + \overline{A} \cdot B \cdot CF(A,B,C)=A⋅B⋅C+A⋅B⋅C+A⋅B⋅C has 1’s at the positions corresponding to:
    • A=1,B=1,C=0A = 1, B = 1, C = 0A=1,B=1,C=0 (for A⋅B⋅C‾A \cdot B \cdot \overline{C}A⋅B⋅C)
    • A=1,B=0,C=1A = 1, B = 0, C = 1A=1,B=0,C=1 (for A⋅B‾⋅CA \cdot \overline{B} \cdot CA⋅B⋅C)
    • A=0,B=1,C=1A = 0, B = 1, C = 1A=0,B=1,C=1 (for A‾⋅B⋅C\overline{A} \cdot B \cdot CA⋅B⋅C)

Step 2: Group the 1’s

  • We have two 1’s in the column for C = 1 (positions for AB=01AB = 01AB=01 and AB=11AB = 11AB=11).
  • These 1’s can be grouped together.

Step 3: Simplify

  • The group of 1’s represents B⋅CB \cdot CB⋅C (since AAA varies within the group, we eliminate it).
  • The simplified Boolean expression is: F(A,B,C)=B⋅CF(A, B, C) = B \cdot CF(A,B,C)=B⋅C

Thus, the expression simplifies from A⋅B⋅C‾+A⋅B‾⋅C+A‾⋅B⋅CA \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot C + \overline{A} \cdot B \cdot CA⋅B⋅C+A⋅B⋅C+A⋅B⋅C to B⋅CB \cdot CB⋅C.

🧑‍🏫 Example 3: 4-Variable K-map

Let’s now examine a 4-variable K-map.

Boolean Expression: F(A,B,C,D)=A⋅B‾⋅C⋅D‾+A‾⋅B⋅C‾⋅D+A⋅B⋅C‾⋅DF(A, B, C, D) = A \cdot \overline{B} \cdot C \cdot \overline{D} + \overline{A} \cdot B \cdot \overline{C} \cdot D + A \cdot B \cdot \overline{C} \cdot DF(A,B,C,D)=A⋅B⋅C⋅D+A⋅B⋅C⋅D+A⋅B⋅C⋅D

Step 1: Create the K-map

  1. A 4-variable Boolean function will have 16 cells (since 24=162^4 = 1624=16).
  2. Label the rows and columns in Gray code.
CD = 00CD = 01CD = 11CD = 10
AB = 000000
AB = 010110
AB = 110110
AB = 101000
  1. The function F(A,B,C,D)F(A, B, C, D)F(A,B,C,D) has 1’s at the positions corresponding to:
    • A=1,B=0,C=1,D=0A = 1, B = 0, C = 1, D = 0A=1,B=0,C=1,D=0
    • A=0,B=1,C=0,D=1A = 0, B = 1, C = 0, D = 1A=0,B=1,C=0,D=1
    • A=1,B=1,C=0,D=1A = 1, B = 1, C = 0, D = 1A=1,B=1,C=0,D=1

Step 2: Group the 1’s

  • Group the adjacent 1’s in powers of 2. For instance, the 1’s at AB=01AB = 01AB=01 and AB=11AB = 11AB=11 for CD=01CD = 01CD=01 and CD=11CD = 11CD=11 can be grouped.

Step 3: Simplify

  • The group of 1’s can simplify the Boolean expression by factoring out the common variables.

🔥 Summary

  1. K-map is used to simplify Boolean expressions by organizing minterms into a grid.
  2. Adjacent 1’s (or 0’s for POS) are grouped in powers of 2.
  3. Each group is simplified into a term, and all the terms are ORed together for the final simplified expression.