Karnaugh Map (K-map)

A Karnaugh map (K-map) is an array of cells in which each cell represents a binary value of the input variables. The cells are arranged in a way so that simplification of a given expression is simply a matter of properly grouping the cells.

The number of cells in a Karnaugh map, as well as the number of rows in a truth table, is equal to $2^{n}$ possible input variable combinations, where $n$ is the number of variables in a Boolean function.

The simplified expressions produced by the map are always in one of the two standard forms: sum-of-products (SOP) or product-of-sums (POS). This expression produces a circuit diagram with a minimum number of gates and the minimum number of inputs to each gate.

The process that results in an expression containing the fewest possible terms with the fewest possible variables (literals) is called minimization.

The cells in Karnaugh map are arranged so that there is only a single-variable change (Gray code) between adjacent cells. Adjacency is defined by a single-variable change. A cell is not adjacent to the cells that diagonally touch any of its corners. Also, the cells in the top row are adjacent to the corresponding cells in the bottom row and the cells in the outer left column are adjacent to the corresponding cells in the outer right column. This is called wrap-around adjacency.

A prime implicant is a product/sum term obtained by combining the maximum possible number of adjacent cells in the map. A prime implicant is an essential prime implicant if it is the only prime implicant that covers the minterm/maxterm.

Boolean functions that have unspecified outputs for some input combinations are called incompletely specified functions. It is customary to call the unspecified minterms/maxterms of a Boolean function as don’t-care conditions.

A don’t-care minterm/maxterm is a combination of variables whose logical value is not specified. To distinguish the don’t-care condition from $1$ and $0$ , an $X$ is used.

When simplifying the Boolean function, each don’t-care minterm/maxterm can be included along with either $1$ or $0$ , depending on which combination gives the simplest expression.

Sum-of-Products (SOP) Minimization

Construction

Each cell represents a minterm $m_{i}$ or the complement of maxterm $M_{i}$ .

Two-variable K-map

$x ∖ y$	$0 \to y^{'}$	$1 \to y$
$0 \to x^{'}$	$00 \to m_{0} = M_{0}^{'} = x^{'} \cdot y^{'}$	$01 \to m_{1} = M_{1}^{'} = x^{'} \cdot y$
$1 \to x$	$10 \to m_{2} = M_{2}^{'} = x \cdot y^{'}$	$11 \to m_{3} = M_{3}^{'} = x \cdot y$

Three-variable K-map

$x ∖ y z$	$00 \to y^{'} \cdot z^{'}$	$01 \to y^{'} \cdot z$	$11 \to y \cdot z$	$10 \to y \cdot z^{'}$
$0 \to x^{'}$	$000 \to m_{0} = M_{0}^{'} = x^{'} \cdot y^{'} \cdot z^{'}$	$001 \to m_{1} = M_{1}^{'} = x^{'} \cdot y^{'} \cdot z$	$011 \to m_{3} = M_{3}^{'} = x^{'} \cdot y \cdot z$	$010 \to m_{2} = M_{2}^{'} = x^{'} \cdot y \cdot z^{'}$
$1 \to x$	$100 \to m_{4} = M_{4}^{'} = x \cdot y^{'} \cdot z^{'}$	$101 \to m_{5} = M_{5}^{'} = x \cdot y^{'} \cdot z$	$111 \to m_{7} = M_{7}^{'} = x \cdot y \cdot z$	$110 \to m_{6} = M_{6}^{'} = x \cdot y \cdot z^{'}$

Four-variable K-map

$w x ∖ y z$	$00 \to y^{'} \cdot z^{'}$	$01 \to y^{'} \cdot z$	$11 \to y \cdot z$	$10 \to y \cdot z^{'}$
$00 \to w^{'} \cdot x^{'}$	$0000 \to m_{0} = M_{0}^{'} = w^{'} \cdot x^{'} \cdot y^{'} \cdot z^{'}$	$0001 \to m_{1} = M_{1}^{'} = w^{'} \cdot x^{'} \cdot y^{'} \cdot z$	$0011 \to m_{3} = M_{3}^{'} = w^{'} \cdot x^{'} \cdot y \cdot z$	$0010 \to m_{2} = M_{2}^{'} = w^{'} \cdot x^{'} \cdot y \cdot z^{'}$
$01 \to w^{'} \cdot x$	$0100 \to m_{4} = M_{4}^{'} = w^{'} \cdot x \cdot y^{'} \cdot z^{'}$	$0101 \to m_{5} = M_{5}^{'} = w^{'} \cdot x \cdot y^{'} \cdot z$	$0111 \to m_{7} = M_{7}^{'} = w^{'} \cdot x \cdot y \cdot z$	$0110 \to m_{6} = M_{6}^{'} = w^{'} \cdot x \cdot y \cdot z^{'}$
$11 \to w \cdot x$	$1100 \to m_{12} = M_{12}^{'} = w \cdot x \cdot y^{'} \cdot z^{'}$	$1101 \to m_{13} = M_{13}^{'} = w \cdot x \cdot y^{'} \cdot z$	$1111 \to m_{15} = M_{15}^{'} = w \cdot x \cdot y \cdot z$	$1110 \to m_{14} = M_{14}^{'} = w \cdot x \cdot y \cdot z^{'}$
$10 \to w \cdot x^{'}$	$1000 \to m_{8} = M_{8}^{'} = w \cdot x^{'} \cdot y^{'} \cdot z^{'}$	$1001 \to m_{9} = M_{9}^{'} = w \cdot x^{'} \cdot y^{'} \cdot z$	$1011 \to m_{11} = M_{11}^{'} = w \cdot x^{'} \cdot y \cdot z$	$1010 \to m_{10} = M_{10}^{'} = w \cdot x^{'} \cdot y \cdot z^{'}$

Grouping

A group must contain cells in a powers of two $(1, 2, 4, 8, 16, \dots)$ . For boolean function with $n$ variables, the maximum possible number of cells in a group is $2^{n}$ cells.
Each cell in a group must be adjacent to one or more cells in that same group, but all cells in the group do not have to be adjacent to each other.
Always include the largest possible number of $1$ s in a group. The product term obtained from such a group becomes the prime implicant of the boolean function.
Each $1$ on the map must be included in at least one group. The $1$ s already in a group can be included in another group as long as the overlapping groups include non-common $1$ s.

Minimization Procedure

Arrange the Boolean expression into a sum-of-products (SOP) or sum-of-minterms expression.
Since each product term represents a group, a $1$ is placed in the cells where the variables within that product term remain constant across the group. If the product term is a minterm, a $1$ is placed in the corresponding cell.
All other cells that are not part of the groups should remain as $0$ s. Additionally, don’t-care minterms can be utilized to further simplify the Boolean expression.
Group the cells that have $1$ s. Or group the cells that have $0$ s to obtain the complemented Boolean expression.
Determine the minimum product term for each group. Variables that occur both uncomplemented and complemented within the group are eliminated.
When all the minimum product terms are derived from the map, they are OR-ed $(+)$ to form the minimum SOP expression.

Product-of-Sums (POS) Minimization