Don't-Care Conditions

Motivation

Sometimes certain input combinations never occur in a given application, or the designer does not care about the output value for those combinations. These are called don’t-care conditions. When simplifying a Boolean function, don’t-cares can be treated as either 0 or 1, whichever yields the simplest expression. This extra flexibility often leads to more minimal circuits.

Don’t-cares are denoted by $X$ on a Karnaugh map.

Example: BCD to 7-Segment Decoder

Binary Coded Decimal (BCD) represents decimal digits 0-9 using 4 bits (0000 to 1001). The six combinations 1010 through 1111 (decimal 10-15) never occur in valid BCD input. In a BCD to 7-segment decoder, the outputs for these six input combinations are don’t-cares: we do not care what the display shows because the input will never be presented.

This means we have 6 don’t-care conditions (cells $m_{10}$ through $m_{15}$) on a 4-variable K-map for each output segment. By choosing to treat some don’t-cares as 1s, we can form larger groups and simplify the output expression significantly.

K-Map with Don’t-Cares

Don’t-cares are marked as $X$ on the K-map. The grouping strategy is:

• Treat an $X$ as 1 if it helps form a larger group (leading to fewer literals).
• Treat an $X$ as 0 (ignore it) if including it would not enlarge any group.

In other words: use don’t-cares opportunistically to maximise group sizes, but do not include them if they do not help.

Worked Example

Simplify $f = \bar{a} \cdot \bar{b} \cdot d + \bar{a} \cdot c \cdot d + a \cdot c \cdot d$ with don’t-care conditions: $\bar{a} \cdot \bar{b} \cdot \bar{c} \cdot \bar{d}$, $\bar{a} \cdot \bar{b} \cdot c \cdot d$, $\bar{a} \cdot b \cdot \bar{c} \cdot d$.

First, identify all the terms and don’t-cares as minterm indices.

$f$ minterms:

• $\bar{a} \cdot \bar{b} \cdot d$: $a=0, b=0, d=1$ → $\bar{a}\bar{b}d$ covers $\bar{a}\bar{b}\bar{c}d$ ($m_1$) and $\bar{a}\bar{b}cd$ ($m_3$). $m_1$ = 0001, $m_3$ = 0011.
• $\bar{a} \cdot c \cdot d$: $a=0, c=1, d=1$ → $\bar{a}cd$ covers $\bar{a}\bar{b}cd$ ($m_3$) and $\bar{a}bcd$ ($m_7$).
• $a \cdot c \cdot d$: $a=1, c=1, d=1$ → $acd$ covers $a\bar{b}cd$ ($m_{11}$) and $abcd$ ($m_{15}$).

So $f$ minterms (1s): $m_1, m_3, m_7, m_{11}, m_{15}$.

Don’t-cares:

• $\bar{a} \cdot \bar{b} \cdot \bar{c} \cdot \bar{d}$: $m_0$ (0000)
• $\bar{a} \cdot \bar{b} \cdot c \cdot d$: $m_3$ (0011) — note this is already a minterm of $f$, so it does not add a new don’t-care
• $\bar{a} \cdot b \cdot \bar{c} \cdot d$: $m_5$ (0101)

K-map (4 variables, $a, b, c, d$):

$$\begin{array}{c|cccc} ab \setminus cd & 00 & 01 & 11 & 10 \\ \hline 00 & X & 1 & 1 & \\ 01 & & X & 1 & \\ 11 & & & 1 & \\ 10 & & & 1 & \end{array}$$

Grouping without using don’t-cares: the 1s at $m_1, m_3, m_7, m_{11}, m_{15}$ would require multiple small groups.

Grouping using don’t-cares: Column $cd=11$ contains 1s at all four rows ($m_3, m_7, m_{11}, m_{15}$), forming a group of 4. Constant: $c=1, d=1$; $a$ and $b$ vary. Term: $c \cdot d$. This covers four of the five 1s.

The remaining 1 at $m_1$ (0001) can pair with the don’t-care at $m_0$ (0000) to form a group of 2: constant $a=0, b=0, c=0$; $d$ varies. Term: $\bar{a} \cdot \bar{b} \cdot \bar{c}$. Alternatively, $m_1$ could pair with the don’t-care at $m_5$ (0101) for a vertical group: constant $b=0, c=0, d=1$; $a$ varies. Term: $\bar{b} \cdot \bar{c} \cdot d$.

Both options yield valid simplified expressions with the same gate cost (1 AND-2 + 1 AND-3 + 1 OR-2):

$f = c \cdot d + \bar{a} \cdot \bar{b} \cdot \bar{c}$ $f = c \cdot d + \bar{b} \cdot \bar{c} \cdot d$

Alternative: Use more don’t-cares for even larger group

What if we treat both $m_0$ and $m_5$ as 1s? Then $m_0$ (0000) and $m_1$ (0001) give $\bar{a}\bar{b}\bar{c}$. And $m_5$ and $m_7$ give $\bar{a}bd$, which is another term. But remember, all we need is a covering set: a minimum set of prime implicants that covers ALL the 1s. The don’t-cares DON’T need to be covered; they are optional. The two solutions above both cover all 1s (the column group covers $m_3, m_7, m_{11}, m_{15}$; the second group covers $m_1$). Done.

Another Worked Example: BCD Counter Decoder

Consider a BCD to decimal decoder with 4 inputs ($a, b, c, d$) and 10 outputs ($y_0$ through $y_9$). Input combinations 1010 to 1111 are don’t-cares. Let us design the output $y_9$, which is TRUE only when the BCD input is 9 (binary 1001).

Truth table for $y_9$:

a	b	c	d	$y_9$
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	X
1	0	1	1	X
1	1	0	0	X
1	1	0	1	X
1	1	1	0	X
1	1	1	1	X

Without don’t-cares: $y_9 = a \cdot \bar{b} \cdot \bar{c} \cdot d$ (a single minterm, 4 literals).

With don’t-cares: Plot on K-map.

$$\begin{array}{c|cccc} ab \setminus cd & 00 & 01 & 11 & 10 \\ \hline 00 & 0 & 0 & 0 & 0 \\ 01 & 0 & 0 & 0 & 0 \\ 11 & X & X & X & X \\ 10 & 0 & 1 & X & X \end{array}$$

The 1 is at $m_9$ (1001): $ab=10$, $cd=01$. The Xs are at $m_{10}$ through $m_{15}$: rows $ab=10$ (cols 10,11) and $ab=11$ (all four cols).

Without don’t-cares, $y_9 = a \cdot \bar{b} \cdot \bar{c} \cdot d$ (4 literals).

With don’t-cares, $m_9$ (1001) pairs with $m_{11}$ (1011, X) horizontally: constant $a=1, b=0, d=1$; $c$ varies. Term: $a \cdot \bar{b} \cdot d$ (3 literals). But we can do better: $m_9$, $m_{11}$, $m_{13}$ (1101, X), and $m_{15}$ (1111, X) form a 2×2 rectangle (rows 10 and 11, columns 01 and 11). Constant: $a=1, d=1$; $b$ and $c$ vary. Term: $a \cdot d$ (2 literals).

Check: $a \cdot d$ is 1 when $a=1$ and $d=1$. This covers $m_9$ (1001), $m_{11}$ (1011), $m_{13}$ (1101), and $m_{15}$ (1111). The latter three are all don’t-cares, so this is valid.

$y_9 = a \cdot d$

This is a dramatic simplification: from 4 literals down to 2, made possible by treating the don’t-cares as 1s to form a larger group.

Important Definitions

When discussing K-map simplification with don’t-cares:

Prime Implicant: A product term that cannot be combined with any other term to eliminate a variable. On a K-map, a prime implicant corresponds to a maximal group of adjacent 1s (and optionally Xs) that cannot be enlarged while remaining rectangular. A group is not a prime implicant if it can be expanded to a larger valid group.

Essential Prime Implicant: A prime implicant that covers at least one minterm (a 1, not a don’t-care) that is NOT covered by any other prime implicant. Essential prime implicants MUST be included in the final expression.

Covering Set: A minimum set of prime implicants that includes all essential prime implicants plus any non-essential prime implicants needed to cover the remaining uncovered 1s. The covering set gives the minimal SOP expression.

K-Map Example Illustrating Definitions

Consider the K-map below for a 4-variable function. Let 1s be at: $m_4, m_5, m_6, m_8, m_9, m_{10}, m_{13}$. Don’t-cares: $m_0, m_7, m_{15}$.

$$\begin{array}{c|cccc} ab \setminus cd & 00 & 01 & 11 & 10 \\ \hline 00 & X & & & \\ 01 & 1 & 1 & X & 1 \\ 11 & & 1 & X & \\ 10 & 1 & 1 & & 1 \end{array}$$

Prime implicants:

• PI1: Row $ab=01$ (all four cells: $m_4, m_5, m_7, m_6$). $m_7$ is X, the rest are 1s. Group of 4: $\bar{a} \cdot b$.

• PI2: Column $cd=01$, rows 01 and 11 ($m_5, m_{13}$). Rows 01 and 11 are adjacent in Gray code. Constant: $b=1, c=0, d=1$; $a$ varies. Term: $b \cdot \bar{c} \cdot d$.

• PI3: Row $ab=10$ has 1s at $m_8, m_9, m_{10}$ but a gap at $m_{11}$ (empty), so no group of 4. Two groups of 2: $m_8$ and $m_9$ (horizontal, columns 00 and 01) → $a \cdot \bar{b} \cdot \bar{c}$; $m_8$ and $m_{10}$ (horizontal wrap, columns 00 and 10) → $a \cdot \bar{b} \cdot \bar{d}$.

• PI4: $m_{13}$ (1101) and $m_{15}$ (1111) in row $ab=11$, columns 01 and 11 (adjacent in Gray code). $m_{13}$ is 1, $m_{15}$ is X. Horizontal group of 2: constant $a=1, b=1, d=1$; $c$ varies. Term: $a \cdot b \cdot d$.

Prime implicants found:

• $\bar{a} \cdot b$ (covers $m_4, m_5, m_6$)
• $b \cdot \bar{c} \cdot d$ (covers $m_5, m_{13}$ — rows 01 and 11 are adjacent in Gray code, so the vertical group in column $cd=01$ is valid)
• $a \cdot \bar{b} \cdot \bar{c}$ (covers $m_8, m_9$)
• $a \cdot \bar{b} \cdot \bar{d}$ (covers $m_8, m_{10}$)
• $a \cdot b \cdot d$ (covers $m_{13}, m_{15}$)

Essential prime implicants: Look at each 1-minterm and see how many PIs cover it:

• $m_4$: covered only by $\bar{a} \cdot b$ → essential.
• $m_5$: covered by $\bar{a} \cdot b$ and $b \cdot \bar{c} \cdot d$.
• $m_6$: covered only by $\bar{a} \cdot b$ → essential (already covered).
• $m_8$: covered by $a \cdot \bar{b} \cdot \bar{c}$ and $a \cdot \bar{b} \cdot \bar{d}$.
• $m_9$: covered only by $a \cdot \bar{b} \cdot \bar{c}$ → essential.
• $m_{10}$: covered only by $a \cdot \bar{b} \cdot \bar{d}$ → essential.
• $m_{13}$: covered by $b \cdot \bar{c} \cdot d$ and $a \cdot b \cdot d$.

Essential PIs: $\bar{a} \cdot b$, $a \cdot \bar{b} \cdot \bar{c}$, $a \cdot \bar{b} \cdot \bar{d}$.

These cover: $\bar{a} \cdot b$ covers $m_4, m_5, m_6$. $a \cdot \bar{b} \cdot \bar{c}$ covers $m_8, m_9$. $a \cdot \bar{b} \cdot \bar{d}$ covers $m_8, m_{10}$.

All 1s covered? $m_4$ ✓, $m_5$ ✓, $m_6$ ✓, $m_8$ ✓ (by both second and third), $m_9$ ✓, $m_{10}$ ✓, $m_{13}$ ✗ (NOT covered!).

$m_{13}$ is not covered by any essential PI. We need to add a non-essential PI to cover it. Options: $b \cdot \bar{c} \cdot d$ or $a \cdot b \cdot d$. The former requires 3 literals, the latter 3 literals. We can pick either (both same cost). Adding $a \cdot b \cdot d$ gives:

$f = \bar{a} \cdot b + a \cdot \bar{b} \cdot \bar{c} + a \cdot \bar{b} \cdot \bar{d} + a \cdot b \cdot d$

Or adding $b \cdot \bar{c} \cdot d$ gives:

$f = \bar{a} \cdot b + a \cdot \bar{b} \cdot \bar{c} + a \cdot \bar{b} \cdot \bar{d} + b \cdot \bar{c} \cdot d$

Both are valid minimal covers. The first covers $m_{13}$ and also the don’t-care $m_{15}$; the second covers $m_{13}$ and also $m_5$ (which is already covered by $\bar{a} \cdot b$, so the overlap doesn’t matter).

The minimality does not depend on covering don’t-cares. What matters is covering all 1s with the fewest prime implicants (or fewest literals, depending on the cost metric).

Summary

• Don’t-care conditions arise when certain input combinations can never occur in a specific application.
• On a K-map, don’t-cares are marked with X.
• In grouping, treat X as 1 if it helps form a larger group; ignore it otherwise.
• Don’t-cares do NOT need to be covered by the final expression; only the actual 1s must be covered.
• The definitions of prime implicants, essential prime implicants, and covering sets remain the same, but don’t-cares can participate in forming prime implicants.
• Don’t-cares often enable dramatic simplifications, as seen in the BCD examples.