Karnaugh Maps for Boolean Function Simplification

Karnaugh Maps

Introduction

• Karnaugh Maps (K-Maps) are used to simplify boolean algebra expressions and derive functions from truth tables.
• A K-Map provides a visual method to minimize boolean functions.

Three-Variable Karnaugh Map

• For a three-variable function $f(a, b, c)$, a three-variable K-Map with eight squares is needed.
• The eight squares correspond to the eight possible input combinations.
• A three-variable K-Map can be drawn in two common ways:
  • Two rows and four columns.
  • Two columns and four rows.

Horizontal Orientation

• Variables $a$ and $b$ are represented on the top (columns), and variable $c$ on the side (rows).
• The order of inputs for $a$ and $b$ is 00, 01, 11, and 10 (Gray code) to ensure only one variable changes between adjacent columns.
• The input for $c$ is binary, 0 or 1.

Filling the K-Map

• The values inside each square are the function values from the truth table.
• Example: If $a=0$, $b=0$, and $c=0$, the corresponding function value from the truth table is placed in the square corresponding to $a=0$, $b=0$, and $c=0$.

Vertical Orientation

• Variable $a$ is represented above the diagonal line, and variables $b$ and $c$ below it.
• $a$ has two possibilities: 0 or 1.
• $b$ and $c$ can be 00, 01, 11, or 10.

Converting K-Map to Function

• Circle groups of ones in the K-Map.
• The number of ones that can be grouped together must be a power of two (1, 2, 4, 8, etc.).
• Groups can be pairs, quads, octets, etc., but not three, five, or six.
• Identify the variables that do not change within the group.
  • If a variable is 1, use the variable as is.
  • If a variable is 0, use the complement of the variable.
• Write the product term for each group of ones.
• Sum the product terms to form the simplified boolean expression.
• $f = \sum (\text{product terms})$

Example

• Consider a pair of ones in the K-Map.
• If for these ones, $b$ is always 1 and $c$ is always 0, the term is $b \cdot \overline{c}$.
• If for another pair of ones, $a$ is always 1 and $b$ is always 0, the term is $a \cdot \overline{b}$.
• The function is the sum of these terms: $f = b \cdot \overline{c} + a \cdot \overline{b}$.

Testing the Function

• Plug in values from the truth table into the derived function.
• Verify that the function output matches the truth table output.

Converting Function to Circuit Diagram

• Each product term (AND operation) requires an AND gate.
• The sum of products (OR operation) requires an OR gate.
• Inverters (NOT gates) are used to implement complemented variables.

Example

• For the function $f = b \cdot \overline{c} + a \cdot \overline{b}$,
  • An AND gate connects $b$ and $\overline{c}$.
  • Another AND gate connects $a$ and $\overline{b}$.
  • An OR gate connects the outputs of these AND gates to produce the final output $f$.

Four-Variable Karnaugh Map

• A four-variable K-Map has 16 squares (4 rows and 4 columns).
• Variables $a$ and $b$ are represented on the top, and variables $c$ and $d$ on the side.
• The order of inputs for $a$, $b$, $c$, and $d$ is based on Gray code.

Example

• Consider a group of two ones where $a$ and $b$ are always 1 and $c$ is always 0. The term is $a \cdot b \cdot \overline{c}$.
• Consider another group of two ones where $a$ is always 0, $c$ is always 1, and $d$ is always 0. The term is $\overline{a} \cdot c \cdot \overline{d}$.
• The function is the sum of these terms.

Larger Groups

• A group of four ones corresponds to a term with two variables.
• A group of eight ones corresponds to a term with one variable.

Filling K-Map from a Function

• For each term in the function, identify where the variables match the term.
• Put a '1' in those squares.
• Fill the remaining squares with '0's.

Example

• Given the function $f = a \cdot \overline{b} + \overline{a} \cdot c \cdot d + a \cdot b \cdot \overline{c}$,
  • For $a \cdot \overline{b}$, put '1' where $a=1$ and $b=0$.
  • For $\overline{a} \cdot c \cdot d$, put '1' where $a=0$, $c=1$, and $d=1$.
  • For $a \cdot b \cdot \overline{c}$, put '1' where $a=1$, $b=1$, and $c=0$.

Color Coding

• Use color-coding to differentiate terms from each other.
• Terms with one variable result in eight ones.
• Terms with two variables result in four ones.
• Terms with three variables result in two ones.
• Terms with four variables result in one one.