Section5.3Boolean Function Minimization¶ permalink

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 SoPs

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 is one where all other mathematically equivalent PoSs

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.4).

Subsection5.3.1Minimization 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.3.1}
\end{equation}
The expression on the right-hand side is an SoM. The circuit to implement this function is shown in Figure 5.3.1.

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

Now let us simplify the expression in Equation (5.3.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.3.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)\label{mrow-57}\tag{5.3.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.3.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 pf 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.3.5}
\end{equation}
The expression on the right-hand side is a PoM. The circuit for this function is shown in Figure 5.3.2.

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' \label{mrow-61}\tag{5.3.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.3.7}\\
&= x' \cdot y' \label{mrow-63}\tag{5.3.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.

Subsubsection5.3.1.1Exercises

1

Design a function that will detect the even 4-bit integers.

Let a 4-bit integer be \(wxyz\) where each literal represents one bit. The even 4-bit integers are given by the function:
\begin{alignat*}{1}
F(w,x,y,z) \amp {}={} w' \cdot x' \cdot y' \cdot z' + w' \cdot x' \cdot y \cdot z' + w' \cdot x \cdot y' \cdot z' + w' \cdot x \cdot y \cdot z' \\
\amp \quad + w \cdot x' \cdot y' \cdot z' + w \cdot x' \cdot y \cdot z' + w \cdot x \cdot y' \cdot z' + w \cdot x \cdot y \cdot z'
\end{alignat*}
Using the distributive property repeatedly we get:
\begin{alignat*}{1}
F(w,x,y,z) \amp {}={} z' \cdot (w' \cdot x' \cdot y' + w' \cdot x' \cdot y + w' \cdot x \cdot y' + w' \cdot x \cdot y \\
\amp \quad + w \cdot x' \cdot y' + w \cdot x' \cdot y + w \cdot x \cdot y' + w \cdot x \cdot y) \\
\amp {}={} z' \cdot (w' \cdot (x' \cdot y' + x' \cdot y + x \cdot y' + x \cdot y) \\
\amp \quad + w \cdot (x' \cdot y' + x' \cdot y + x \cdot y' + x \cdot y)) \\
\amp {}={} z' \cdot (w' + w) \cdot (x' \cdot y' + x' \cdot y + x \cdot y' + x \cdot y) \\
\amp {}={} z' \cdot (w'+ w) \cdot (x' \cdot (y' + y) + x \cdot (y' + y)) \\
\amp {}={} z' \cdot (w' + w) \cdot (x' + x) \cdot (y' + y)
\end{alignat*}
And from the complement property we arrive at a minimal sum of products:
\begin{gather*}
F(w,x,y,z) = z'
\end{gather*}
which you recognize as Figure 5.1.3.

Subsection5.3.2Minimization Using Pictorial Tools¶ permalink

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.3.3 shows how all four minterms for two variables are mapped onto a four-cell 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 an SoP 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.

Larger groups result in simpler expressions.

The number of cells in a group must be a power of \(2\text{.}\)

The edges of the Karnaugh map are considered to wrap around to the other side, both vertically and horizontally.

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.3.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.3.2)–Equation (5.3.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.3.4

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.3.9}
\end{align}
The simplification in Equation (5.3.9) is shown graphically by the grouping in Figure 5.3.5

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

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.3.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.2.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.3.7 shows how the three-variable minterms map onto 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.5.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.3.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.

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

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 an SoP 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.

Larger groups result in simpler expressions.

The number of cells in a group must be a power of \(2\text{.}\)

The edges of the Karnaugh map are considered to wrap around to the other side, both vertically and horizontally.

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')\label{mrow-76}\tag{5.3.10}\\
F_2(x,y,z) = (x + y + z)\label{mrow-77}\tag{5.3.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.3.9(a) shows how the minterm appears on a Karnaugh map, and Figure 5.3.9(b) shows the Maxterm.

Figure 5.3.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.

A four-variable Karnaugh map of Maxterms is shown in Figure 5.3.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.

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.3.2.1.4 and Exercise 5.3.2.1.5.

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 hardware symbol for the XOR gate is shown in Figure 5.3.12. The inputs are \(x\) and \(y\text{.}\) The resulting output, \(x \oplus y\text{,}\) is shown in the truth table in this figure.

\(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}\)

Figure5.3.12The XOR 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.3.13. The “\(\times\)” represents a “don't care” cell—we don't care whether this cell is grouped with other cells 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.3.14.

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.

Subsubsection5.3.2.1Exercises

1

Find a minimal sum of products (mSoP) expression for the function
\begin{align*}
F(x,y,z) &= x' \cdot y' \cdot z' + x' \cdot y' \cdot z + x' \cdot y \cdot z'\\
&\quad+\ x \cdot y' \cdot z' + x \cdot y \cdot z' + x \cdot y \cdot z
\end{align*}

This expression includes Maxterms 0, 1, 3, 4, and 7. These appear in a Karnaugh map:

Next we encircle the largest adjacent blocks, where the number of cells in each block is a power of two. Notice that Maxterm \(M_{0}\) appears in two groups.

From this Karnaugh map it is very easy to write the function as a minimal product of sums:
\begin{equation*}
F(x,y,z) = (x + y) \cdot (y + z) \cdot (y' + z')
\end{equation*}

3

Find a minimal product of sums (mPoS) expression for the function
\begin{align*}
F(x,y,z) &= x' \cdot y' \cdot z' + x' \cdot y' \cdot z + x' \cdot y \cdot z'\\
&\quad+\ x \cdot y' \cdot z' + x \cdot y \cdot z' + x \cdot y \cdot z
\end{align*}

we obtain the complement of our desired function:
\begin{equation*}
F'(x,y,z) = x' \cdot y \cdot z + x \cdot y' \cdot z
\end{equation*}
and from DeMorgan's Law:
\begin{equation*}
F(x,y,z) = (x + y' + z') \cdot (x' + y + z')
\end{equation*}

4

Show where each minterm is located with this Karnaugh map axis labeling using the notation of Figure 5.3.7.

Design a logic function that detects the prime single-digit numbers. Assume that the numbers are coded in 4-bit BCD (see Section 4.5.1). The function is 1 for each prime number.

The prime numbers correspond to the minterms \(m_{2}\text{,}\) \(m_{3}\text{,}\) \(m_{5}\text{,}\) and \(m_{7}\text{.}\) The minterms \(m_{10}\text{,}\) \(m_{11}\text{,}\) \(m_{12}\text{,}\) \(m_{13}\text{,}\) \(m_{14}\text{,}\) \(m_{15}\) cannot occur so are marked “don't care” on the Karnaugh map.

which gives:
\begin{equation*}
F(w,x,y,z) = x \cdot z + x' \cdot y
\end{equation*}