Boolean Function Minimization

Section 5.5 Boolean Function Minimization

In this section we explore some important tools for manipulating Boolean expressions in order to simplify their hardware implementation. When implementing a Boolean function in hardware, each “\(\cdot\)” operator represents an AND gate and each “\(+\)” operator an OR gate. In general, the complexity of the hardware is related to the number of AND and OR gates. NOT gates are simple and tend not to contribute significantly to the complexity.

Good design consists of looking for a minimal expression that specifies a solution to the problem.

minimal Sum of Products (mSoP)

A sum of products expression where all other mathematically equivalent sum of product expressions

have at least as many product terms, and
those with the same number of product terms have at least as many literals.

minimal Product of Sums (mPoS)

A product of sums expression where all other mathematically equivalent product of sums

have at least as many sum terms, and
those with the same number of sum terms have at least as many literals.

These definitions imply that there can be more than one minimal solution to a problem. Good hardware design practice involves finding all the minimal solutions, then assessing each one within the context of the available hardware. For example, judiciously placed NOT gates can actually reduce hardware complexity (Section 6.2).

Subsection 5.5.1 Minimization Using Algebraic Manipulations

To illustrate the importance of reducing the complexity of a Boolean function, consider the following function:

\begin{equation} F_{1}(x,y) = x \cdot y' + x' \cdot y + x \cdot y\label{eq-twocomplex}\tag{5.5.1} \end{equation}

The expression on the right-hand side is a sum of minterms (SoM). The circuit to implement this function is shown in Figure 5.5.1.

Figure 5.5.1. Hardware implementation of the function in Equation (5.5.1).

It requires three AND gates, one OR gate, and two NOT gates.

Now let us simplify the expression in Equation (5.5.1) to see if we can reduce the hardware requirements. This process will probably seem odd to a person who is not used to manipulating Boolean expressions, because there is not a single correct path to a solution. We present one way here.

First we use the idempotency property (Equation (5.1.12)) to duplicate the third term, and then rearrange a bit:

\begin{gather} F_{1}(x,y) = x \cdot y' + x \cdot y + x' \cdot y + x \cdot y\label{eq-dupterm}\tag{5.5.2} \end{gather}

Next we use the distributive property (Equation (5.1.13)) to factor the expression:

\begin{gather} F_{1}(x,y) = x \cdot (y' + y) + y \cdot (x' + x)\tag{5.5.3} \end{gather}

And from the complement property (Equation (5.1.10)) we get:

\begin{align} F_1(x,y) &= x \cdot 1 + y \cdot 1 \notag\\ &= x + y \label{eq-twomin}\tag{5.5.4} \end{align}

which you recognize as the simple OR operation. It can be implemented with a single OR gate—see Figure 5.1.2—which is clearly less expensive and faster. It is easy to see that this is a minimal sum of products (mSoP) for this function.

To illustrate how a product of sums expression can be minimized, consider the function:

\begin{equation} F_{2}(x,y) = (x + y') \cdot (x' + y) \cdot (x' + y') \label{eq-threecomplex}\tag{5.5.5} \end{equation}

The expression on the right-hand side is a product of maxterms (PoM). The circuit for this function is shown in Figure 5.5.2.

Figure 5.5.2. Hardware implementation of the function in Equation (5.5.5).

It requires three OR gates, one AND gate, and two NOT gates.

To simplify this function, we will start with the distributive property (Equation (5.1.14)) on the right two factors and recognize the complement (Equation (5.1.9)):

\begin{align} F_2(x,y) &= (x + y') \cdot (x' + y \cdot y') \notag\\ &= (x + y') \cdot x' \tag{5.5.6} \end{align}

Now, use the distributive (Equation (5.1.13)) and complement (Equation (5.1.9)) properties to obtain:

\begin{align} F_2(x,y) &= x \cdot x' + x' \cdot y' \label{eq-threesimple}\tag{5.5.7}\\ &= x' \cdot y' \tag{5.5.8} \end{align}

Thus, the function can be implemented with two NOT gates and a single AND gate, which is clearly a minimal product of sums. See Figure 5.1.1 and Figure 5.1.3 for the circuits to implement this function.

Subsection 5.5.2 Minimization Using Pictorial Tools

The Karnaugh map was invented in 1953 by Maurice Karnaugh while working as a telecommunications engineer at Bell Labs. Also known as a K-map, it provides a pictorial view of all the possible minterms for a given number of variables. The format is a rectangular grid with a cell for each minterm. There are \(2^{n}\) cells for \(n\) variables.

Figure 5.5.3 shows how all four minterms for two variables are mapped onto a four-cell Karnaugh map.

Two-variable Karnaugh map. — Figure 5.5.3. Mapping of two-variable minterms on a Karnaugh map.

The vertical axis is used for plotting \(x\) and the horizontal for \(y\text{.}\) The value of \(x\) for each row is shown by the number (\(0\) or \(1\)) immediately to the left of the row, and the value of \(y\) for each column appears at the top of the column. Although it occurs automatically in a two-variable Karnaugh map, the cells must be arranged such that only one variable changes between two cells that share an edge. This is called the adjacency property.

The procedure for simplifying a sum of products expression using a Karnaugh map is:

Place a \(1\) in each cell that corresponds to a minterm that evaluates to \(1\) in the expression.
Combine cells with \(1\)s in them and that share edges into the largest possible groups.
1. Larger groups result in simpler expressions.
2. The number of cells in a group must be a power of \(2\text{.}\)
3. The edges of the Karnaugh map are considered to wrap around to the other side, both vertically and horizontally.
4. Groups may overlap. In fact, this is common. However, no group should be fully enclosed by another group.
The result is the sum of the product terms that represent each group.

The Karnaugh map provides a pictorial means to find the same simplifications as algebraic manipulations, but some people find it easier to spot simplification patterns on a Karnaugh map. Probably the easiest way to understand how Karnaugh maps are used is through an example. We start with Equation (5.5.1) (repeated here):

\begin{equation*} F_1(x,y) = x \cdot y' + x' \cdot y + x \cdot y \end{equation*}

and use a Karnaugh map to pictorially find the same minimal sum of products that the algebraic steps in Equation (5.5.2)–Equation (5.5.4) gave us.

We start by placing a \(1\) in each cell corresponding to a minterm that appears in the equation, as shown in Figure 5.5.4

Figure 5.5.4. Karnaugh map for \(F_{1}(x,y) = x \cdot y' + x' \cdot y + x \cdot y\text{.}\)

The two cells on the right side correspond to the minterms \(m_{1}\) and \(m_{3}\) and represent \(x' \cdot y + x \cdot y\text{.}\) Using the distributive (Equation (5.1.13)) and complement (Equation (5.1.10)) properties, we can see that

\begin{align} x' \cdot y + x \cdot y &= (x + x') \cdot y \notag\\ &= y \label{eq-karnaughsimple}\tag{5.5.9} \end{align}

The simplification in Equation (5.5.9) is shown graphically by the grouping in Figure 5.5.5

Figure 5.5.5. A Karnaugh map grouping showing that \(x \cdot y' + x' \cdot y + x \cdot y = x \cdot y' + y\text{.}\)

Since groups can overlap, we create a second grouping as shown in Figure 5.5.6.

Figure 5.5.6. A Karnaugh map grouping showing that \(x \cdot y' + x' \cdot y + x \cdot y = x + y\text{.}\)

The group in the bottom row represents the product term \(x\text{,}\) and the one in the right-hand column represents \(y\text{.}\) So the simplification is:

\begin{equation*} F_{1}(x,y) = x + y \end{equation*}

Note that the overlapping cell, \(x \cdot y\text{,}\) is the term that we used the idempotent property to duplicate in Equation (5.5.2). Grouping overlapping cells is a graphical application of the idempotent property (Equation (5.1.12)).

Next we consider a three-variable Karnaugh map. Table 5.3.1 lists all the minterms for three variables, \(x\text{,}\) \(y\text{,}\) and \(z\text{,}\) numbered from \(0\) – \(7\text{.}\) A total of eight cells are needed, so we will draw it four cells wide and two high. Our Karnaugh map will be drawn with \(y\) and \(z\) on the horizontal axis, and \(x\) on the vertical. Figure 5.5.7 shows how the three-variable minterms map onto a Karnaugh map.

Figure 5.5.7. Mapping of three-variable minterms on a Karnaugh map.

Notice the order of the bit patterns along the top of the three-variable Karnaugh map, which is chosen such that only one variable changes value between any two adjacent cells (the adjacency property). It is the same as a two-variable Gray code (see Table 4.6.3). That is, the order of the columns is such that the \(yz\) values follow the Gray code.

A four-variable Karnaugh map is shown in Figure 5.5.8. The \(y\) and \(z\) variables are on the horizontal axis, \(w\) and \(x\) on the vertical. From this four-variable Karnaugh map we see that the order of the rows is such that the \(wx\) values also follow the Gray code, again to implement the adjacency property.

Figure 5.5.8. Mapping of four-variable minterms on a Karnaugh map.

We may wish to implement a function as a product of sums instead of a sum of products. From DeMorgan's Law, we know that the complement of an expression exchanges all ANDs and ORs, and complements each of the literals. The zeros in a Karnaugh map represent the complement of the expression. So if we

place a \(0\) in each cell of the Karnaugh map corresponding to a missing minterm in the expression,
find groupings of the cells with \(0\)s in them,
write a sum of products expression represented by the grouping of \(0\)s, and
complement this expression,

we will have the desired expression expressed as a product of sums. Compare Exercise 5.6.2 and Exercise 5.6.3.

As you probably expect by now a Karnaugh map also works when a function is specified as a product of sums. The procedure for simplifying a product of sums expression using a Karnaugh map is:

Place a \(0\) in each cell that corresponds to a maxterm that evaluates to \(0\) in the expression.
Combine cells with \(0\)s in them and that share edges into the largest possible groups.
1. Larger groups result in simpler expressions.
2. The number of cells in a group must be a power of \(2\text{.}\)
3. The edges of the Karnaugh map are considered to wrap around to the other side, both vertically and horizontally.
4. Groups may overlap. In fact, this is common. However, no group should be fully enclosed by another group.
The result is the product of the sum terms that represent each group.

To see how this works let us first compare the Karnaugh maps for two functions,

\begin{gather} F_1(x,y,z) = (x' \cdot y' \cdot z')\tag{5.5.10}\\ F_2(x,y,z) = (x + y + z)\tag{5.5.11} \end{gather}

\(F_1(x,y,z)\) is a sum of products with only one minterm, and \(F_2(x,y,z)\) is a product of sums with only one maxterm. Figure 5.5.9(a) shows how the minterm appears on a Karnaugh map, and Figure 5.5.9(b) shows the maxterm.

Figure 5.5.9. Comparison of one minterm (a) versus one maxterm (b) on a Karnaugh map.

Figure 5.5.10 shows how three-variable maxterms map onto a Karnaugh map. As with minterms, \(x\) is on the vertical axis, \(y\) and \(z\) on the horizontal. To use the Karnaugh map for maxterms, place a \(0\) in each cell corresponding to a maxterm.

Figure 5.5.10. Mapping of three-variable maxterms on a Karnaugh map.

A four-variable Karnaugh map of maxterms is shown in Figure 5.5.11. The \(w\) and \(x\) variables are on the vertical axis, \(y\) and \(z\) on the horizontal. To use the Karnaugh map for maxterms, place a \(0\) in each cell corresponding to a maxterm.

Figure 5.5.11. Mapping of four-variable maxterms on a Karnaugh map.

Other axis labeling schemes also work. The only requirement is that entries in adjacent cells differ by only one bit (which is a property of the Gray code). See Exercise 5.6.5 and Exercise 5.6.6.

There are situations where some minterms (or maxterms) are irrelevant in a function. This might occur, say, if certain input conditions are impossible in the design. As an example, assume that you have an application where the exclusive or (XOR) operation is required.

XOR

A binary operator; the result is \(\binary{1}\) if one, and only one, of the two operands is \(\binary{1}\text{,}\) otherwise the result is \(\binary{0}\text{.}\) We will use ‘\(\oplus\)’ to designate the XOR operation. The OR gate operation is shown in Figure 5.5.12 with inputs \(x\) and \(y\text{.}\)

\(x\)	\(y\)	\(x \oplus y\)
\(\binary{0}\)	\(\binary{0}\)	\(\binary{0}\)
\(\binary{0}\)	\(\binary{1}\)	\(\binary{1}\)
\(\binary{1}\)	\(\binary{0}\)	\(\binary{1}\)
\(\binary{1}\)	\(\binary{1}\)	\(\binary{0}\)

Figure 5.5.12. The OR gate acting on two variables, \(x\) and \(y\text{.}\)

The minterms required to implement this operation are:

\begin{equation*} x \oplus y = x \cdot y' + x' \cdot y \end{equation*}

This is the simplest form of the XOR operation. It requires two AND gates, two NOT gates, and an OR gate for realization.

But let us say that we have the additional information that the two inputs, \(x\) and \(y\) can never be \(1\) at the same time. Then we can draw a Karnaugh map with an “\(\times\)” for the minterm that cannot exist as shown in Figure 5.5.13. The “\(\times\)” represents a “don't care” cell—we don't care whether this cell is grouped with other cells or not.

Figure 5.5.13. A “don't care” cell on a Karnaugh map. Since it is known that \(x\) and \(y\) cannot both be \(1\) at the same time, we don't care if the cell \(xy = 11\) is included in our groupings or not.

Since the cell that represents the minterm \(x \cdot y\) is a “don't care,” we can include it in our minimization groupings, leading to the two groupings shown in Figure 5.5.14.

Figure 5.5.14. Karnaugh map for XOR function if we know \(x = y = 1\) cannot occur.

The solution is

\begin{equation*} F(x,y) = x + y \end{equation*}

a simple OR gate, which saves two AND gates and two NOT gates.