In this, the second installment of a two-part mini-series, we consider grouping minterms in more detail, along with the concepts of incompletely specified functions and populating Karnaugh maps using 0s versus 1s.

Just to refresh our memories, in 1953 the American physicist Maurice Karnaugh invented a form of logic diagram called a Karnaugh map, which provides a graphical technique for representing Boolean functions. In Part 1 of this mini-series, we introduced Karnaugh Maps and demonstrated how they can be used to minimize logic functions. Now read on...

Grouping Minterms
In the case of a 3-input Karnaugh map, any two horizontally or vertically adjacent minterms, each composed of three variables, can be combined to form a new product term composed of only two variables. Similarly, in the case of a 4-input map, any two adjacent minterms, each composed of four variables, can be combined to form a new product term composed of only three variables. Additionally, the 1s associated with the minterms can be used to form multiple groups. For example, consider the 3-input function shown in Figure 2-1, in which the minterm corresponding to a = 1, b = 1, and c = 0 is common to three groups.

Figure 2-1. Using the same minterm to form multiple Karnaugh map groups.

Groupings can also be formed from four adjacent minterms, in which case two redundant variables can be discarded; consider some 4-input Karnaugh Map examples as illustrated in Figure 2-2.

Figure 2-2. Karnaugh map groupings of four adjacent minterms.

In fact, any group of 2ⁿ adjacent minterms can be gathered together (where n is a positive integer). For example, 2¹ = two minterms, 2² = 2 × 2 = four minterms, 2³ = 2 × 2 × 2 = eight minterms, and so forth.

As was noted earlier, Karnaugh map input values are ordered so that the values associated with adjacent rows and columns differ by only a single bit. One result of this ordering is that the top and bottom rows are also separated by only a single bit (it may help to visualize the map rolled into a horizontal cylinder such that the top and bottom edges are touching). Similarly, the left and right columns are separated by only a single bit (in this case it may help to visualize the map rolled into a vertical cylinder such that the left and right edges are touching). This leads to some additional groupings, a few of which are shown in Figure 2-3.

Figure 2-3. Some additional Karnaugh map grouping possibilities.

Note especially the last example. Diagonally adjacent minterms generally cannot be used to form a group: however, remembering that the left-right columns and the top-bottom rows are logically adjacent, this means that the four corner minterms are also logically adjacent, which in turn means that they can be used to form a single group.

Incompletely Specified Functions
In certain cases a function may be incompletely specified; that is, the output may be undefined for some of the input combinations. If, for example, the designer knows that certain input combinations will never occur, then the value assigned to the output for these combinations is irrelevant. Alternatively, for some input combinations, the designer may simply not care about the value on the output. In both cases, the designer can represent the output values associated with the relevant input combinations as question marks in the Karnaugh map (Figure 2-4).

Figure 2-4. Karnaugh map for an incompletely specified function.

The ? characters indicate don’t care states, which can be considered to represent either 0 or 1 values at the designer’s discretion. In the example shown in Figure 2-4, we have no interest in the ? character in the box referenced by a = 0, b = 0, c = 1, d = 0 or the ? character in the box at a = 0, b = 1, c = 1, d = 1, because neither of these can be used to form a larger group. However, if we decide that the other three ? characters are going to represent 1 values, then they can be used to form larger groups, which allows us to minimize the function to a greater degree than would otherwise be possible.

As an aside, it should be noted that many electronics references use X characters to represent don’t care states. Unfortunately, this may lead to confusion, as some computer-aided design tools (such as logic simulators) use X characters to represent don’t know states, which are a completely different barrel of fish ... but we don't want to wander off into the weeds here). Unless otherwise indicated, I tend to use ? and X to represent don’t care and don’t know states, respectively.

Note: Also of interest are checkerboard Karnaugh map patterns, which indicate the possibility of Reed Müller implementations using only XOR and XNOR gates (see also my paper on Reed Müller Logic).

Populating Karnaugh Maps Using 0s Versus 1s
When we are extracting Boolean equations from truth tables, in the case of a function whose output is logic 1 fewer times than it is logic 0, it is generally easier to extract an equation in the sum-of-products form. Similarly, if the output is logic 0 fewer times than it is logic 1, then it is generally easier to extract an equation in the product-of-sums form.

The same thing applies to a Karnaugh map. If the output is logic 1 fewer times than it is logic 0, then it’s probably going to be a lot easier to populate the map using logic 1’s. Alternatively, if the output is logic 0 fewer times than it is logic 1, then populating the map using logic 0s may be a better idea.

When a Karnaugh Map is populated using the 1s assigned to the truth table’s output, the resulting Boolean expression is extracted from the map in sum-of-products form. By comparison, if the Karnaugh Map is populated using the 0s assigned to the truth table’s output, then the groupings of 0s are used to generate expressions in product-of-sums form (Figure 2-5).

Figure 2-5. Populating Karnaugh maps with 0s versus 1s.

Although the sum-of-products and product-of-sums expressions appear to be somewhat different, they do produce identical results. The expressions can be shown to be equivalent using algebraic means, or by constructing truth tables for each expression and comparing the outputs.

Karnaugh maps are most often used to represent 3-input and 4-input functions. It is possible to create similar maps for 5-input and 6-input functions, but these maps can quickly become unwieldy and difficult to use. Thus, the Karnaugh technique is generally not considered to have any application for functions with more than six inputs.

Author's Note: The material presented here was abstracted from my book Bebop to the Boolean Boogie (An Unconventional Guide to Electronics) 3rd Edition, with the kind permission of my publisher, Newnes (an imprint of Elsevier).