Boolean Function Simplification using Karnaugh Maps

The complexity of the logic diagram that implements a Boolean function is directly related to the complexity of the algebraic expression from which the function is derived. Although the truth table representation of a function is unique, the function can appear in numerous algebraic forms. Simplifying these expressions using the basic relations of Boolean algebra can be challenging due to the absence of specific rules that predict each subsequent step in the manipulation process.

The Karnaugh map (K-map) method provides a simple, straightforward procedure for simplifying Boolean expressions. This method can be regarded as a pictorial arrangement of the truth table, allowing for an easy interpretation to determine the minimum number of terms needed to express the function algebraically.

Minterms and Karnaugh Maps

Each combination of the variables in a truth table is called a minterm. For example, a truth table with three variables ($x$, $y$, $z$) will contain $2^3 = 8$ minterms. A Boolean function is equal to 1 for some minterms and to 0 for others. The information contained in a truth table can be expressed in a compact form by listing the decimal equivalents of those minterms that produce a 1 for the function. For instance, consider a function $F(x, y, z)$ represented by the truth table in Figure 1-3. It can be expressed as follows:

Here, the symbol $\sum$ stands for the sum of the minterms that follow in parentheses. The minterms that produce 1 for the function are listed in their decimal equivalent, and the minterms missing from the list are the ones that produce 0 for the function.

Constructing the K-map

A K-map is a diagram made up of squares, where each square represents one minterm. The squares corresponding to minterms that produce 1 for the function are marked by a 1, while the others are marked by a 0 or left empty. By recognizing various patterns and combining squares marked by 1's in the map, it is possible to derive alternative algebraic expressions for the function. The most convenient expression can then be selected.

The K-maps for functions of two, three, and four variables are shown in Figure 1-7. The number of squares in a map of $n$ variables is $2^n$. The minterm numbers are assigned in an orderly arrangement such that adjacent squares represent minterms that differ by only one variable. Variable names are listed across both sides of the diagonal line in the corner of the map. The 0's and 1's along each row and column designate the value of the variables. Each variable under brackets contains half of the squares in the map where that variable appears unprimed (non-complemented). The variable appears complemented in the remaining half of the squares.

Example K-Map Construction and Simplification

Consider the following Boolean function:

The three-variable K-map for this function is shown in Figure 1-8. There are four squares marked with 1's, corresponding to the minterms 3, 4, 6, and 7.

1. The two adjacent squares in the third column represent the term $BC$.
2. The remaining two 1's in the corners of the second row belong to row $A$ and the two columns of $C'$, producing the term $AC'$.

The simplified algebraic expression for the function is:

Example 2: Another Three-Variable Function

Consider another Boolean function:

The five minterms are marked with 1's in the corresponding squares of the three-variable K-map shown in Figure 1-9.

1. The four squares in the first and fourth columns represent the term $C'$.
2. The remaining 1 at minterm 5 can be combined with the square at minterm 4, producing the term $AB'$.

The simplified function is:

Example 3: Four-Variable Function

For a four-variable function:

The K-map for this function, shown in Figure 1-10, has 1's marked in the squares corresponding to these minterms.

1. The 1's in the four corners of the map form the term $B'D'$.
2. The two 1's on the left of the top row and the bottom row together form the term $B'C'$.
3. The remaining 1 at minterm 6 combines with minterm 2 to form the term $A'CD'$.

The simplified function is:

Product-of-Sums Simplification

The expressions derived so far are in sum-of-products (SOP) form, where product terms (AND terms) are ORed together. It is sometimes convenient to express the function in product-of-sums (POS) form, where sum terms (OR terms) are ANDed together. To obtain a POS form from a K-map, mark the 0's representing the minterms that produce 0 for the function. The complement of the function $F$ (denoted as $F'$) is then obtained by combining these 0's. The POS form of $F$ is obtained by taking the complement of $F'$.

Example: Converting SOP to POS

Consider the function:

The corresponding K-map is shown in Figure 1-11.

1. Combine the 1's to get the SOP form: $$F = B'D' + B'C' + A'C'D$$
2. Combine the 0's to get the complement $F'$: $$F' = AB + CD + BD'$$
3. Taking the complement of $F'$ gives the POS form of $F$: $$F = (A' + B')(C' + D')(B' + D)$$

Implementing Boolean Functions

NAND and NOR Implementations

A sum-of-products expression can be implemented with NAND gates, as shown in Figure 1-13(a). A product-of-sums expression can be implemented with NOR gates, as shown in Figure 1-13(b).

Don't-Care Conditions

Sometimes, the function does not matter for certain minterms, known as don't-care conditions, marked with an 'x' in the K-map. These can be assumed to be either 0 or 1 to achieve the simplest expression.

Example with Don't-Care Conditions

Consider:

The K-map is shown in Figure 1-14. The minterms of $F$ are marked with 1's, those of $d$ are marked with x's, and the remaining squares are marked with 0's.

1. Combine the 1's and x's to form the simplest expression. The simplified expression is: $$F = A' + BC'$$ If the don't-care conditions 1 and 3 were not included, the expression would be: $$F = A'C' + BC'$$

This would require more gates compared to the expression with don't-care conditions included.

Final Function Representation

The function is determined completely once the x's are assigned to either 1's or 0's in the map. For the example:

The K-map method simplifies the Boolean algebraic expressions by providing a visual and systematic approach. The resulting expressions can be implemented using various logic gates, such as AND, OR, NAND, and NOR, to create efficient logic circuits. Don't-care conditions further enhance simplification by offering flexibility in grouping terms, ultimately leading to more optimized digital logic designs.