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 \(\textrm{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\,\backslash\,y\) | \(\displaystyle 0 \to y^{\,\prime}\) | \(\displaystyle 1 \to y\) |
|---|---|---|
| \(\displaystyle 0 \to x^{\,\prime}\) | \(\displaystyle 00 \to m_0 = M_{0}^{\,\prime} = x^{\,\prime} \cdot y^{\,\prime}\) | \(\displaystyle 01 \to m_1 = M_{1}^{\,\prime} = x^{\,\prime} \cdot y\) |
| \(\displaystyle 1 \to x\) | \(\displaystyle 10 \to m_2 = M_{2}^{\,\prime} = x \cdot y^{\,\prime}\) | \(\displaystyle 11 \to m_3 = M_{3}^{\,\prime} = x \cdot y\) |
Three-variable K-map
| \(x\,\backslash\,yz\) | \(\displaystyle 00 \to y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle 01 \to y^{\,\prime} \cdot z\) | \(\displaystyle 11 \to y \cdot z\) | \(\displaystyle 10 \to y \cdot z^{\,\prime}\) |
|---|---|---|---|---|
| \(\displaystyle 0 \to x^{\,\prime}\) | \(\displaystyle 000 \to m_0 = M_{0}^{\,\prime} = x^{\,\prime} \cdot y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle 001 \to m_1 = M_{1}^{\,\prime} = x^{\,\prime} \cdot y^{\,\prime} \cdot z\) | \(\displaystyle 011 \to m_3 = M_{3}^{\,\prime} = x^{\,\prime} \cdot y \cdot z\) | \(\displaystyle 010 \to m_2 = M_{2}^{\,\prime} = x^{\,\prime} \cdot y \cdot z^{\,\prime}\) |
| \(\displaystyle 1 \to x\) | \(\displaystyle 100 \to m_4 = M_{4}^{\,\prime} = x \cdot y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle 101 \to m_5 = M_{5}^{\,\prime} = x \cdot y^{\,\prime} \cdot z\) | \(\displaystyle 111 \to m_7 = M_{7}^{\,\prime} = x \cdot y \cdot z\) | \(\displaystyle 110 \to m_6 = M_{6}^{\,\prime} = x \cdot y \cdot z^{\,\prime}\) |
Four-variable K-map
| \(wx\,\backslash\,yz\) | \(\displaystyle 00 \to y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle 01 \to y^{\,\prime} \cdot z\) | \(\displaystyle 11 \to y \cdot z\) | \(\displaystyle 10 \to y \cdot z^{\,\prime}\) |
|---|---|---|---|---|
| \(\displaystyle 00 \to w^{\,\prime} \cdot x^{\,\prime}\) | \(\displaystyle 0000 \to m_0 = M_{0}^{\,\prime} = w^{\,\prime} \cdot x^{\,\prime} \cdot y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle 0001 \to m_1 = M_{1}^{\,\prime} = w^{\,\prime} \cdot x^{\,\prime} \cdot y^{\,\prime} \cdot z\) | \(\displaystyle 0011 \to m_3 = M_{3}^{\,\prime} = w^{\,\prime} \cdot x^{\,\prime} \cdot y \cdot z\) | \(\displaystyle 0010 \to m_2 = M_{2}^{\,\prime} = w^{\,\prime} \cdot x^{\,\prime} \cdot y \cdot z^{\,\prime}\) |
| \(\displaystyle 01 \to w^{\,\prime} \cdot x\) | \(\displaystyle 0100 \to m_4 = M_{4}^{\,\prime} = w^{\,\prime} \cdot x \cdot y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle 0101 \to m_5 = M_{5}^{\,\prime} = w^{\,\prime} \cdot x \cdot y^{\,\prime} \cdot z\) | \(\displaystyle 0111 \to m_7 = M_{7}^{\,\prime} = w^{\,\prime} \cdot x \cdot y \cdot z\) | \(\displaystyle 0110 \to m_6 = M_{6}^{\,\prime} = w^{\,\prime} \cdot x \cdot y \cdot z^{\,\prime}\) |
| \(\displaystyle 11 \to w \cdot x\) | \(\displaystyle 1100 \to m_{12} = M_{12}^{\,\prime} = w \cdot x \cdot y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle 1101 \to m_{13} = M_{13}^{\,\prime} = w \cdot x \cdot y^{\,\prime} \cdot z\) | \(\displaystyle 1111 \to m_{15} = M_{15}^{\,\prime} = w \cdot x \cdot y \cdot z\) | \(\displaystyle 1110 \to m_{14} = M_{14}^{\,\prime} = w \cdot x \cdot y \cdot z^{\,\prime}\) |
| \(\displaystyle 10 \to w \cdot x^{\,\prime}\) | \(\displaystyle 1000 \to m_8 = M_{8}^{\,\prime} = w \cdot x^{\,\prime} \cdot y^{\,\prime} \cdot z^{\,\prime}\) | \(\displaystyle 1001 \to m_9 = M_{9}^{\,\prime} = w \cdot x^{\,\prime} \cdot y^{\,\prime} \cdot z\) | \(\displaystyle 1011 \to m_{11} = M_{11}^{\,\prime} = w \cdot x^{\,\prime} \cdot y \cdot z\) | \(\displaystyle 1010 \to m_{10} = M_{10}^{\,\prime} = w \cdot x^{\,\prime} \cdot y \cdot z^{\,\prime}\) |
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
Construction
Each cell represents a maxterm \(M_i\) or the complement of minterm \(m_i\).
Two-variable K-map
| \(x\,\backslash\,y\) | \(\displaystyle 0 \to y\) | \(\displaystyle 1 \to y^{\,\prime}\) |
|---|---|---|
| \(\displaystyle 0 \to x\) | \(\displaystyle 00 \to M_0 = m_{0}^{\,\prime} = x + y\) | \(\displaystyle 01 \to M_1 = m_{1}^{\,\prime} = x + y^{\,\prime}\) |
| \(\displaystyle 1 \to x^{\,\prime}\) | \(\displaystyle 10 \to M_2 = m_{2}^{\,\prime} = x^{\,\prime} + y\) | \(\displaystyle 11 \to M_3 = m_{3}^{\,\prime} = x^{\,\prime} + y^{\,\prime}\) |
Three-variable K-map
| \(x\,\backslash\,yz\) | \(\displaystyle 00 \to y + z\) | \(\displaystyle 01 \to y + z^{\,\prime}\) | \(\displaystyle 11 \to y^{\,\prime} + z^{\,\prime}\) | \(\displaystyle 10 \to y^{\,\prime} + z\) |
|---|---|---|---|---|
| \(\displaystyle 0 \to x\) | \(\displaystyle 000 \to M_0 = m_{0}^{\,\prime} = x + y + z\) | \(\displaystyle 001 \to M_1 = m_{1}^{\,\prime} = x + y + z^{\,\prime}\) | \(\displaystyle 011 \to M_3 = m_{3}^{\,\prime} = x + y^{\,\prime} + z^{\,\prime}\) | \(\displaystyle 010 \to M_2 = m_{2}^{\,\prime} = x + y^{\,\prime} + z\) |
| \(\displaystyle 1 \to x^{\,\prime}\) | \(\displaystyle 100 \to M_4 = m_{4}^{\,\prime} = x^{\,\prime} + y + z\) | \(\displaystyle 101 \to M_5 = m_{5}^{\,\prime} = x^{\,\prime} + y + z^{\,\prime}\) | \(\displaystyle 111 \to M_7 = m_{7}^{\,\prime} = x^{\,\prime} + y^{\,\prime} + z^{\,\prime}\) | \(\displaystyle 110 \to M_6 = m_{6}^{\,\prime} = x^{\,\prime} + y^{\,\prime} + z\) |
Four-variable K-map
| \(wx\,\backslash\,yz\) | \(\displaystyle 00 \to y + z\) | \(\displaystyle 01 \to y + z^{\,\prime}\) | \(\displaystyle 11 \to y^{\,\prime} + z^{\,\prime}\) | \(\displaystyle 10 \to y^{\,\prime} + z\) |
|---|---|---|---|---|
| \(\displaystyle 00 \to w + x\) | \(\displaystyle 0000 \to M_0 = m_{0}^{\,\prime} = w + x + y + z\) | \(\displaystyle 0001 \to M_1 = m_{1}^{\,\prime} = w + x + y + z^{\,\prime}\) | \(\displaystyle 0011 \to M_3 = m_{3}^{\,\prime} = w + x + y^{\,\prime} + z^{\,\prime}\) | \(\displaystyle 0010 \to M_2 = m_{2}^{\,\prime} = w + x + y^{\,\prime} + z\) |
| \(\displaystyle 01 \to w + x^{\,\prime}\) | \(\displaystyle 0100 \to M_4 = m_{4}^{\,\prime} = w + x^{\,\prime} + y + z\) | \(\displaystyle 0101 \to M_5 = m_{5}^{\,\prime} = w + x^{\,\prime} + y + z^{\,\prime}\) | \(\displaystyle 0111 \to M_7 = m_{7}^{\,\prime} = w + x^{\,\prime} + y^{\,\prime} + z^{\,\prime}\) | \(\displaystyle 0110 \to M_6 = m_{6}^{\,\prime} = w + x^{\,\prime} + y^{\,\prime} + z\) |
| \(\displaystyle 11 \to w^{\,\prime} + x^{\,\prime}\) | \(\displaystyle 1100 \to M_{12} = m_{12}^{\,\prime} = w^{\,\prime} + x^{\,\prime} + y + z\) | \(\displaystyle 1101 \to M_{13} = m_{13}^{\,\prime} = w^{\,\prime} + x^{\,\prime} + y + z^{\,\prime}\) | \(\displaystyle 1111 \to M_{15} = m_{15}^{\,\prime} = w^{\,\prime} + x^{\,\prime} + y^{\,\prime} + z^{\,\prime}\) | \(\displaystyle 1110 \to M_{14} = m_{14}^{\,\prime} = w^{\,\prime} + x^{\,\prime} + y^{\,\prime} + z\) |
| \(\displaystyle 10 \to w^{\,\prime} + x\) | \(\displaystyle 1000 \to M_8 = m_{8}^{\,\prime} = w^{\,\prime} + x + y + z\) | \(\displaystyle 1001 \to M_9 = m_{9}^{\,\prime} = w^{\,\prime} + x + y + z^{\,\prime}\) | \(\displaystyle 1011 \to M_{11} = m_{11}^{\,\prime} = w^{\,\prime} + x + y^{\,\prime} + z^{\,\prime}\) | \(\displaystyle 1010 \to M_{10} = m_{10}^{\,\prime} = w^{\,\prime} + x + y^{\,\prime} + 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 \(0\)s in a group. The sum term obtained from such a group becomes the prime implicant of the boolean function.
- Each \(0\) on the map must be included in at least one group. The \(0\)s already in a group can be included in another group as long as the overlapping groups include non-common \(0\)s.
Minimization Procedure
- Arrange the Boolean expression into a product-of-sums (POS) or product-of-maxterms expression.
- Since each sum term represents a group, a \(0\) is placed in the cells where the variables within that sum term remain constant across the group. If the sum term is a maxterm, a \(0\) is placed in the corresponding cell.
- All other cells that are not part of the groups should remain as \(1\)s. Additionally, don’t-care maxterms can be utilized to further simplify the Boolean expression.
- Group the cells that have \(0\)s. Or group the cells that have \(1\)s to obtain the complemented Boolean expression.
- Determine the minimum sum term for each group. Variables that occur both uncomplemented and complemented within the group are eliminated.
- When all the minimum sum terms are derived from the map, they are AND-ed \((\cdot)\) to form the minimum POS expression.