How to make a Karnaugh Map with "don't care" inputs?

Question

I know that don't cares mean that it doesn't matter whether it is a 0 or a 1 and when don't cares are just outputs I can kind of understand how they work. But I am having a really hard time understanding how they work when they are inputs.

I have read that when an input is a don't care the whole input doesn't count. But if one or more of the inputs no longer count then how do you make a k-map? Don't k-maps use the first two and latter two in a longitude latitude sort of way when you mark down the outputs?

Here is what I am currently working on:

inputs    outputs 
A B C D | Q R S
0 0 0 0 | x x 0
0 0 0 1 | 0 0 1
0 0 1 x | 0 1 1
0 1 x x | 1 0 1
1 x x x | 1 1 1

my first attempt at making a k-map:

  00 01 1X
0 X    
0
0 0
1
1 0
X
X    1   1
X    

Then I was theorizing that if they don't count that means that the bit length is either shortened or the don't cares count as 1's or zeros if it is shortened I was thinking it is like this:

1XXX=1'b1 = 1 01XX=2'b01=1

but if that is true wouldn't

0 1 x x | 1 0 1
1 x x x | 1 1 1

not be like that and instead the out puts would be identical?

Or perhaps it is what I first thought and it's like:

0 1 x x | 1 0 1 means put an output in 5,6, and 7? Or maybe just 7?

Finally how do you mark things as don't care in the test bench? Do you even mark them at all? Is there a specific mark?

Answer 1

Here's how to create the K-Map for the Q output. Remember that you need to do a separate Karnaugh Map for each of the three outputs.

inputs    output 
A B C D | Q
0 0 0 0 | x
0 0 0 1 | 0
0 0 1 x | 0
0 1 x x | 1
1 x x x | 1

1. 0000 = x. This first line is standard. The "don't care" is an output. Simply put the "x" in the appropriate place.

2. 0001 = 0. This next line is also standard. Put the "0" where it belongs.

3. 001x = 0. The third line contains a "don't care" input. In this case, there should be an output of "0" for both 0010 and 0011. Insert these into the map:

4. 01xx = 1. Similarly, the fourth line states that there should be a "1" in all of the following cases: 0100, 0101, 0110, and 0111. Put these in the map:

5. 1xxx = 1. Following the same reasoning, the last line does the following:

Now, do the same for your R and S outputs!

Answer 2

When an input is X (don't care), that means that the line applies both when the X is replaced by a 0 and by a 1.

For your example, you could expand your first table to be:

inputs    outputs 
A B C D | Q R S
0 0 0 0 | x x 0
0 0 0 1 | 0 0 1
0 0 1 0 | 0 1 1
0 0 1 1 | 0 1 1
0 1 0 0 | 1 0 1
0 1 0 1 | 1 0 1
0 1 1 0 | 1 0 1
0 1 1 1 | 1 0 1
1 0 0 0 | 1 1 1
(I'll leave the remaining 7 lines to you)

A line with 1 X will expand to 2 lines, a line with 2 X's will expand to 4 lines, ... (n X's will expand to \$2^n\$ lines)

Regarding your question about how to mark a don't care in a test bench (assuming you are still talking about input don't cares, not outputs), you should have your testbench loop through all of the \$2^n\$ input combinations just like we did when expanding the table above.

Answer 3

As you said "don't cares mean that it doesn't matter whether it is a 0 or a 1". So if it is said that the output corresponding to input "1x" is '1', then it means that output will be '1' if first bit (MSB) is '1'. LSB can be either '0' or '1'. In other words, output will be '1' for both "10" and "11".

One more example: If I want to write the truth table for system, with 4 input lines, whose output will be '1' if last bit of the input combination (LSB) is '0', I will prefer to write:

input   output
--------------
xxx0       1
xxx1       0
-------------

rather than listing all the 16 combinations. Because this is compact.

Whenever you find x in the input sequence, replace x with all the possible combinations. A few examples are given:

$$\begin{array}{rll} \text{symbol} &\text{equivalent numbers} &\text{meaning}\\ \hline \mathrm{\color{red}{x}} & \Rightarrow \color{red}{0},\color{red}{1} & \text{any 1-bit number}\\ \mathrm{\color{red}{xx}} & \Rightarrow \color{red}{00},\color{red}{01},\color{red}{10},\color{red}{11} & \text{any 2-bit number}\\ \mathrm{1\color{red}{x}} & \Rightarrow 1\color{red}{0},1\color{red}{1} &\text{any 2-bit number starting with 1} \\ \mathrm{\color{red}{xx}1} & \Rightarrow \color{red}{00}1,\color{red}{01}1,\color{red}{10}1,\color{red}{11}1 &\text{any 3 bit numbers ending with 1} \\ \mathrm{1\color{red}{x}00} & \Rightarrow 1\color{red}{0}00,1\color{red}{1}00&\text{any 4-bit no starting with 1 and ending with 00} \\ \hline \end{array}$$

Answer 4

When drawing a Karnaugh map, it may be important to distinguish between:

1. Cases where where the circuit should behave identically when a particular input is stable low and when that input is stable high.

2. Cases where the circuit behavior should be unaffected by an input.

The two cases might seem synonymous, but there can sometimes be a major difference. Consider the truth table:

abc
00X -> 0
01X -> 1
1X0 -> 0
1X1 -> 1
X00 -> 0
X11 -> 1

One could simply draw the circuit as a truth table:

   |00 01 11 10 bc
---+--------------
a=0| 0  0  1  1
a=1| 0  1  1  0

but that wouldn't quite give the whole picture, since that would suggest that the circuit could be implemented as a sum-of-products:

out=!a*b*!c + !a*b*c + a*!b*c + a*b*c

but such an output may glitch briefly when an input--even one that should have no effect--switches from high to low or vice versa. For example, if the inputs change from 010 to 011, then even though the output should be high in both of those states, there may be a time when neither !ab!c nor !abc registers as true [since "c" isn't stable high and isn't stable low]. If an input really needs to be "don't care", it may be a good idea to draw an oval around the states which need to behave as a unit, and ensure that a single product term is used to encompass all of them.

Note that while two product terms would suffice to handle the truth table, ensuring that transitions on a "don't care" input won't affect the output will require adding a third one. Failure to have a product term that encompasses one of the filled in ovals can lead to what are called logic hazards. In some designs they don't matter, but in others they can be deadly.