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 displayProduct termsLiterals
Unused codes forced to 0411
Unused codes as don't-cares46

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.

The top bar: ten digits and six don't-cares
ab / cd00011110
00
01
11
10

~b & ~d | c | b & d | a

Minimum SOP: 4 terms · 6 literals.

    A 1 lights the bar. The digits 1 and 4 leave it dark. The rows `ab = 11` and half of `ab = 10` hold `x`.

    1. An input that cannot occur

      The source of the input never makes that code. A BCD digit above 9 is the common example.

    2. 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.

    The top bar with the don't-cares in use
    ab / cd00011110
    00
    01
    11
    10

    ~b & ~d | c | b & d | a

    Minimum SOP: 4 terms · 6 literals.

    1. Eight cells for the digits 8 and 9. The digits 8 and 9 sit beside six `x` cells. Together they fill the lower half of the map: the term `a`.
    2. Eight cells for c. The columns with `c = 1` hold four 1s and four `x` cells. That group is the term `c`.
    3. Two groups of four. The digits 5 and 7 join two `x` cells as `bd`. The four corners are `b'd'`.

    top = a + c + bd + b'd': 4 terms and 6 literals. With the unused codes forced to 0 it is b'c'd' + a'c + a'bd + ab'c': 11 literals.

    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.

    The top-right bar
    ab / cd00011110
    00
    01
    11
    10

    ~b | ~c & ~d | c & d

    Minimum SOP: 3 terms · 5 literals.

    1. Three groups. The terms are `c'd'`, `cd` and `b'`. They take in the `x` cells 1010, 1011, 1100 and 1111.
    2. Two cells left out. No group covers 1101 or 1110. Covering them would need a fourth group, so they stay 0.

    right = c'd' + cd + b': 3 terms and 5 literals. Four don't-cares became 1 and two became 0.

    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.

    From a Sentence to a Tested CircuitArrows show the order of the work. The bench checks the last box against the first.
    • Neutral
    • Datapath
    • Test
    • Structure
    From a sentence to a tested circuitArrows show the order of the work. The bench checks the last box against the first. neutral Words what the circuit mustdo neutral Truth table 0, 1 and x per row neutral K-map one map per output neutral Expression one term per group datapath Gates AND, OR, NOT test Bench every required row list rowsfillgroupdrawsimulatecompare
    1. neutral Wordswhat the circuit must do
      • list rows → Truth table
    2. neutral Truth table0, 1 and x per row
      • fill → K-map
    3. neutral K-mapone map per output
      • group → Expression
    4. neutral Expressionone term per group
      • draw → Gates
    5. datapath GatesAND, OR, NOT
      • simulate → Bench
    6. test Benchevery required row
      • compare → Words
    1. Say it, then tabulate it

      Name the inputs and outputs. Write one row per input code: 1, 0, or x for a code that cannot occur.

    2. Map and group

      Fill one map per output. Group the 1s, using x cells where they make a group larger.

    3. 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.

    StepFor the top bar
    WordsLight the top bar for every digit except 1 and 4.
    Truth table1 for the rows 0, 2, 3, 5, 6, 7, 8, 9; 0 for 1 and 4; x for 10 to 15
    K-map and groupsFour groups: a, c, bd, b'd'
    Expressiontop = a + c + bd + b'd'
    GatesTwo inverters, two two-input AND gates and one four-input OR gate
    BenchTen rows checked, six skipped

    The lab below is the last step: it checks the ten digits and counts the cost.

    Asked in interviews
    1. 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.

    2. How do don't-cares reduce logic?

      On a K-map an x cell may join a group of 1s. The group becomes larger, so its term loses a literal. An x cell that helps no group is left as 0.

    3. 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).

    RUNIcarus Verilog · in your browser
    Edit the code, then run it
    Expected: 0 of 10 rows wrong 4 terms, 11 literals minimum is 4 terms, 6 literals: not reached
    Read 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

    Predict the outputBoth expressions are correct designs of the top bar. The program counts the input codes, out of all 16, on which they differ. What does it print?
    module tb;
      logic a, b, c, d;
      wire lean = a | c | (b & d) | (~b & ~d);
      wire wide = (~b & ~c & ~d) | (~a & c) | (~a & b & d) | (a & ~b & ~c);
      initial begin
        int differ;
        differ = 0;
        for (int m = 0; m < 16; m++) begin
          {a, b, c, d} = m[3:0];
          #1 if (lean !== wide) differ++;
        end
        $display("%0d", differ);
      end
    endmodule
    Spot the bugEach option is an expression for the top bar. The bench checks the ten digits and skips the six unused codes. Which one fails?
    ConceptWhich signal row is a safe don't-care?
    ConceptOn the map of the top-right bar, the x cells 1101 and 1110 are in no group. What does the built circuit give for them?
    ConceptA bench for a BCD decoder compares the output with 0 on the codes 10 to 15. What goes wrong?

    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 x cell 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.

    Practice

    Report a problem with this page