Don't-Cares and the Combinational Design Procedure
Use input codes that never occur to make larger groups, and take a design from a sentence to a tested circuit.
You Will Be Able To
- Mark the don't-care rows of a truth table.
- Choose each don't-care as 1 or 0 to make larger groups.
- Follow the design procedure from words to a bench.
- Lesson
- G3.2
- Time
- 30 min
- Runs on
- Your browser
- Check
- 5 questions
A clock display shows the digits 0 to 9. Its decoder was designed from a full truth table, with every unused code set to 0. The top bar then needed 11 literals. The codes 10 to 15 never reach the display, and using that fact cuts the top bar to 6.
| Top bar of the display | Product terms | Literals |
|---|---|---|
| Unused codes forced to 0 | 4 | 11 |
| Unused codes as don't-cares | 4 | 6 |
Computed for the digits 0, 2, 3, 5, 6, 7, 8, 9. Both designs are correct for every digit.
Inputs That Never Happen
A BCD digit is a decimal digit in four bits, abcd. Only the codes 0000 to 1001 are used. The six codes 1010 to 1111 never occur.
For those six rows, the output has no required value. Such a row is a don't-care. It is written x in the table and on the map.
An input that cannot occur
The source of the input never makes that code. A BCD digit above 9 is the common example.
An output that nobody reads
Another signal says the output is not valid now, so its value has no effect.
A Don't-Care Is Yours to Choose
A group may include an x cell. That choice sets the cell to 1. An x cell that no group covers is set to 0. Each cell is chosen on its own.
Every group here grew by taking in x cells. Larger groups mean shorter terms, so the gates have fewer inputs.
Some Become 1 and Some Stay 0
A don't-care is used only when it helps. The top-right bar of the same display shows both choices on one map.
After minimization, nothing is left open. The circuit gives a fixed 0 or 1 for every code, also for the ones that never occur.
The Design Procedure, End to End
Every small combinational design follows the same steps. The top bar went through all of them.
- Neutral
- Datapath
- Test
- Structure
- Say it, then tabulate it
Name the inputs and outputs. Write one row per input code: 1, 0, or
xfor a code that cannot occur. - Map and group
Fill one map per output. Group the 1s, using
xcells where they make a group larger. - Build and test
Draw one AND gate per term and one OR gate. Then run every required row against the words.
Read the diagram as text
- Words: what the circuit must do
- Truth table: 0, 1 and x per row
- K-map: one map per output
- Expression: one term per group
- Gates: AND, OR, NOT
- Bench: every required row
- Words → Truth table: list rows
- Truth table → K-map: fill
- K-map → Expression: group
- Expression → Gates: draw
- Gates → Bench: simulate
- Bench → Words: compare
The bench skips the don't-care rows: the words say nothing about them.
| Step | For the top bar |
|---|---|
| Words | Light the top bar for every digit except 1 and 4. |
| Truth table | 1 for the rows 0, 2, 3, 5, 6, 7, 8, 9; 0 for 1 and 4; x for 10 to 15 |
| K-map and groups | Four groups: a, c, bd, b'd' |
| Expression | top = a + c + bd + b'd' |
| Gates | Two inverters, two two-input AND gates and one four-input OR gate |
| Bench | Ten rows checked, six skipped |
The lab below is the last step: it checks the ten digits and counts the cost.
Asked in interviews
What is a don't-care condition?
It is an input row whose output value has no effect, because the row cannot occur or the output is not read. The designer may choose 0 or 1 for it.
How do don't-cares reduce logic?
On a K-map an
xcell may join a group of 1s. The group becomes larger, so its term loses a literal. Anxcell that helps no group is left as 0.What does the circuit do on a don't-care input?
It gives a fixed value: 1 if a chosen group covers the row, and 0 if none does. The specification allowed either, so check that both are harmless.
Try It
The table holds the top bar with every unused code forced to 0. The bench checks the ten digits only. It finds no wrong row, and counts 4 terms and 11 literals.
Now use the don't-cares. Set CARE = {4'b0101, 4'b0101, 4'b0010, 4'b1000} and VALUE = {4'b0000, 4'b0101, 4'b0010, 4'b1000}. The bench prints minimum is 4 terms, 6 literals: reached.
Then delete the group a: set N = 3 and remove the leftmost group of CARE and of VALUE. The bench prints first wrong row: abcd = 1001 (top is 1, the table gives 0).
0 of 10 rows wrong 4 terms, 11 literals minimum is 4 terms, 6 literals: not reachedRead included file: tb.sv
// tb.sv: the bench (read-only). It builds the sum of products from the table in module answer,
// compares it with top on every row that is not a don't-care, and counts terms and literals.
module tb;
// Bit m of F is top on row m, where m is the binary value of abcd. DC marks the don't-care rows.
localparam logic [15:0] F = 16'b0000001111101101;
localparam logic [15:0] DC = 16'b1111110000000000;
wire [7:0] n;
wire [31:0] care, value;
answer ans (.n(n), .care(care), .value(value));
// The sum of products on one row: 1 when some term of the table holds the row.
function automatic logic table_at(input logic [3:0] row);
logic hit;
hit = 1'b0;
for (int t = 0; t < 8; t++)
if (t < n && ((row ^ value[4*t +: 4]) & care[4*t +: 4]) == '0) hit = 1'b1;
return hit;
endfunction
initial begin
int wrong, lits;
logic [3:0] row, used;
#1; // let the table reach the wires
wrong = 0;
lits = 0;
for (int m = 0; m < 16; m++) begin
row = m[3:0];
if (!DC[m] && table_at(row) !== F[m]) begin
if (wrong == 0) $display("first wrong row: abcd = %b (top is %b, the table gives %b)", row, F[m], table_at(row));
wrong++;
end
end
for (int t = 0; t < 8; t++) if (t < n) begin
used = care[4*t +: 4]; // one group's CARE bits
lits += $countones(used);
end
$display("%0d of 10 rows wrong", wrong);
$display("%0d terms, %0d literals", n, lits);
if (wrong == 0 && n == 4 && lits == 6) $display("minimum is 4 terms, 6 literals: reached");
else if (wrong == 0) $display("minimum is 4 terms, 6 literals: not reached");
end
endmodule
Check Yourself
Common Mistakes
Wrong Fill every unused row of the truth table with 0.
The map then has fewer cells to group, so the terms keep more literals.
Fix Mark a row that cannot occur with x. Let the map choose its value.
Wrong Cover every don't-care with a group.
A don't-care is optional; a group drawn only to cover one adds a gate for nothing.
Fix Use a don't-care only when it makes a needed group larger.
Wrong Mark a row as a don't-care because it is rare.
After minimization the circuit gives that row a fixed value, which may be the harmful one.
Fix Use a don't-care only when the row cannot occur, or when nothing reads the output then.
Wrong Test the don't-care rows in the bench against 0.
The bench then fails a correct design that chose 1 for such a row.
Fix Skip the don't-care rows in the bench. Check only the rows the words describe.
Remember
- A don't-care is a row whose output has no effect; write it as
x. - An
xcell may join a group as 1, or stay outside every group as 0. - Use a don't-care only when it makes a needed group larger.
- The built circuit gives every row a fixed value, so the promise about the inputs must hold.
- Design in order: words, truth table, map, expression, gates, bench.