K-Maps with Don't Cares

Logic Minimization

226

Incompletely Specified Logic Functions (Don’t Cares)

Situations can arise where a circuit has N input signals, but not all $2^N$ combinations of inputs are possible. Or, if all $2^N$ combinations of inputs are possible, some combinations might be irrelevant. For example, consider a television remote control unit that can switch between control of a television, VCR, or DVD. Some remotes might have operational modes where buttons like “fast forward” are physically switched out of the circuit; other remotes may use modes where such buttons are left in the circuit, but their functions are irrelevant. In either case, some combinations of input signals are completely inconsequential to the proper operation of the circuit. It is possible to take advantage of these situations to further minimize logic circuits.

Input combinations that cannot possibly effect the proper operation of a logic system can be allowed to drive circuit outputs high or low—literally, the designer doesn’t care what the circuit response is to these impossible or irrelevant inputs. This information is encoded by using a special “don’t care” symbol in truth tables and K-maps to indicate that the signal can be a ‘1’ or a ‘0’ without effecting circuit operation. Some sources use an ‘X’ to indicate a don’t care, but this can be confused with a signal named ‘X’. It is perhaps a better practice to use a symbol that is not normally associated with signal names—here, we choose the ‘Φ’ symbol. The “don’t care” can be used on the map to provide simplification of the function.

The truth table above shows two output functions (F and G) for the same three inputs. Both outputs have two rows where the output is a don’t care. This same information is also shown in the associated K-maps. In the ‘F’ K-map, the designers “don’t care” if the output is a ‘1’ or a ‘0’ for minterms 2 and 7, and so cells 2 and 7 in the K-map can be looped as either a ‘1’ or a ‘0’. Clearly, looping cell 7 as a ‘1’ and cell 2 as a ‘0’ results in a more minimal logic circuit. In this case, both an SOP and POS looping would result in identical circuits.

In the ‘G’ K-map, the don’t cares in cells 1 and 3 can be looped as either a ‘1’ or a ‘0’. In an SOP looping, both don’t cares would be looped as 1’s, giving a logic function of $G = \overline A + \overline B \cdot \overline C$. In a POS looping, however, cells 1 and 3 would be looped as 0’s, giving the logic function $G = \overline C \cdot (\overline A + \overline B)$. A little Boolean algebra reveals these two equations are not algebraically equal. Often, the SOP and POS forms of equations looped from K-maps that contain don’t cares are not algebraically equal (although they would perform identically in the circuit). The following examples in Fig. 2 illustrate the use of don’t cares in K-maps.

Important Ideas

• If all combination of $2^N$ inputs are possible, some combinations may be irrelevant.
• Some combinations of input signals can be completely inconsequential to the operation of the circuit.
• It is possible to take advantage of the situations where input combinations are not required for the function of the circuit to further minimize the logic circuit.
• Information for the irrelevant inputs are noted by the ‘Φ’ symbol and are known as Don’t Cares.