Multiple-Output Minimization

Minimize two outputs together, so that a product term both need is built once. The joint minimum can beat two separate minima.

You Will Be Able To

  • Count the cost of a multiple-output circuit by its distinct product terms.
  • Explain why two separate minimum covers are not a joint minimum.
  • Tag a candidate term with the outputs it can serve.
  • Find a shared term that is prime for neither output alone.
Lesson
G3.7
Time
30 min
Runs on
Your browser
Check
5 questions

A pump panel has two lamps driven from the same four inputs. Each lamp's logic was minimized on its own map: three AND gates each. One AND gate could have served both lamps.

Design of both lampsAND gates (distinct terms)Literals
Each lamp minimized alone619
Both lamps minimized together517

Computed by the exact multiple-output minimizer for f = Σm(1, 5, 7, 12, 14) and g = Σm(0, 1, 2, 11).

Two Outputs, One Set of AND Gates

In a two-level circuit, each product term is one AND gate. An output is an OR of some of those gates. If two outputs use the same term, the gate is built once and wired to both ORs.

Each lamp minimized alone

f

ab / cd00011110
00
01
11
10

g

ab / cd00011110
00
01
11
10
  • f = ~a & b & d | a & b & ~d | ~a & ~b & ~c & d
  • g = ~a & ~b & ~d | ~a & ~b & ~c & d | a & ~b & c & d

Shared minimum: 5 distinct product terms · 17 literals, 1 term used by more than one output. Minimized one output at a time: 6 terms · 19 literals.

f = a'c'd + a'bd + abd' and g = a'b'd' + a'b'c' + ab'cd: six distinct terms.

So the cost of the circuit is its number of distinct terms, then their literals. A term used by two outputs costs the same as a term used by one.

One AND Plane, Two OR GatesArrows show signals. Each middle box is a group of AND gates; each right box is the OR gate of one lamp.
  • I/O
  • Datapath
  • Data
One AND plane, two OR gatesArrows show signals. Each middle box is a group of AND gates; each right box is the OR gate of one lamp. io Inputs a b c d shared by every gate datapath Terms for f only a'bd, abd' datapath Shared term a'b'c'd, built once datapath Terms for g only a'b'd', ab'cd datapath OR for f 3 inputs datapath OR for g 3 inputs ffgg
  1. datapath Terms for f onlya'bd, abd'
    • f → OR for f
  2. datapath Shared terma'b'c'd, built once
    • f → OR for f
    • g → OR for g
  3. datapath Terms for g onlya'b'd', ab'cd
    • g → OR for g
  4. datapath OR for f3 inputs
  5. datapath OR for g3 inputs
  6. io Inputs a b c dshared by every gate
    • Terms for f only
    • Shared term
    • Terms for g only
  1. Five AND gates

    The joint design has five product terms, so five AND gates.

  2. One gate, two outputs

    The shared term feeds both OR gates. It is paid for once.

Read the diagram as text
  • Inputs a b c d: shared by every gate
  • Terms for f only: a'bd, abd'
  • Shared term: a'b'c'd, built once
  • Terms for g only: a'b'd', ab'cd
  • OR for f: 3 inputs
  • OR for g: 3 inputs
  • Inputs a b c d → Terms for f only
  • Inputs a b c d → Shared term
  • Inputs a b c d → Terms for g only
  • Terms for f only → OR for f: f
  • Shared term → OR for f: f
  • Shared term → OR for g: g
  • Terms for g only → OR for g: g

Separate minimization would need six AND gates: one more box of terms, nothing shared.

The Best Shared Term Can Be Small

Look at row 0001. It is a 1 of both lamps. Lamp f covers it with a'c'd. Lamp g covers it with a'b'c'. Those are two different gates.

Both lamps minimized together

f

ab / cd00011110
00
01
11
10

g

ab / cd00011110
00
01
11
10
  • f = ~a & b & d | a & b & ~d | ~a & ~b & ~c & d
  • g = ~a & ~b & ~d | ~a & ~b & ~c & d | a & ~b & c & d

Shared minimum: 5 distinct product terms · 17 literals, 1 term used by more than one output. Minimized one output at a time: 6 terms · 19 literals.

  1. One cell for both. The single cell `a'b'c'd` is a 1 of f and a 1 of g. One AND gate serves both lamps.
  2. The rest of f. Lamp f still needs `a'bd` and `abd'`. Row 0001 is already covered.
  3. The rest of g. Lamp g needs `a'b'd'` and `ab'cd`. With row 0001 covered, `a'b'd'` takes rows 0 and 2.

f = a'b'c'd + a'bd + abd' and g = a'b'd' + a'b'c'd + ab'cd: 5 distinct terms, 17 literals.

The shared term a'b'c'd is a single cell. On its own map, each lamp has a larger group that holds it. Yet using it for both saves a gate and two literals.

LampTerms aloneLiterals aloneTerms togetherLiterals together
f39310
g310311

Each lamp alone gets worse: f grows from 9 to 10 literals. The circuit as a whole gets better, because one gate is shared.

Tag Each Term with Its Outputs

An exact method needs every useful candidate. A term may serve f, g or both. Tag it with the outputs it can serve, that is, the outputs of which it is an implicant.

A term that serves both must be an implicant of f · g, the AND of the two outputs. So the candidates are the primes of f, of g, and of f · g.

Candidate termRowsServesPrime of
a'c'd1, 5ff
a'b'd'0, 2gg
a'b'c'0, 1gg
a'b'c'd1f and gf · g
a'bd5, 7ff
ab'cd11gg
abd'12, 14ff

The 7 multiple-output prime implicants. Here f · g is 1 on row 1 only, so its prime is that single cell.

Then the method is the one you know. Build a chart with a column for each (output, 1) pair. Choose the fewest terms that cover every column. A term covers a column only for an output in its tag.

Where Shared Terms Pay

In a PLA, the AND plane is shared by every output. Its size is the number of distinct product terms, so joint minimization sets the size of the device. Module G13 builds one.

StructureWhat is sharedCost to minimize
Separate two-level circuitsnothingterms of each output
Two-level circuit with shared ANDsAND gatesdistinct terms, then literals
PLAthe whole AND planedistinct terms
PALnothing: each output has fixed termsterms of each output, within its limit

Joint minimization pays wherever product terms can be shared.

Synthesis tools share logic between outputs in many ways, not only in two levels. The idea is the same: a function computed once and used twice is paid once.

Asked in interviews
  1. What is multiple-output minimization?

    Minimizing several outputs of the same inputs together, so that product terms can be shared. The cost is the number of distinct terms, then literals.

  2. Why is the sum of separate minima not optimal?

    Each output then prefers its own large groups. A smaller term that both outputs could share is never chosen, though it would save a gate.

  3. What candidates does an exact multiple-output method use?

    The prime implicants of each output and of each product of outputs, such as f · g. Each is tagged with the outputs it may serve.

Try It

The table now has one shared list of terms. PICK holds one byte per output: bit t set means the output ORs term t. Byte 0 is f and byte 1 is g.

The starter has each lamp minimized alone. The bench finds both lamps right on every row, with six terms and 19 literals.

Share the single cell: N = 5, CARE = {4'b1101, 4'b1111, 4'b1101, 4'b1111, 4'b1101}, VALUE = {4'b1100, 4'b1011, 4'b0101, 4'b0001, 4'b0000} and PICK = {8'b00001011, 8'b00010110}. The bench prints minimum is 5 terms, 17 literals: reached.

Now clear bit 1 of g's byte, so g no longer ORs the shared term. The bench prints g: 1 of 16 rows wrong.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: f: 0 of 16 rows wrong g: 0 of 16 rows wrong 6 shared terms, 19 literals minimum is 5 terms, 17 literals: not reached
Read included file: tb.sv
// tb.sv: the bench (read-only). It builds every output from the shared term table in module answer,
// compares each with its function on all 16 rows, and counts the terms in use and their literals.
module tb;
  localparam logic [15:0] F0 = 16'b0101000010100010;   // f
  localparam logic [15:0] F1 = 16'b0000100000000111;   // g
  wire [7:0]  n;
  wire [31:0] care, value;
  wire [15:0] pick;
  answer ans (.n(n), .care(care), .value(value), .pick(pick));

  function automatic logic hit(input int t, input logic [3:0] row);
    return t < n && ((row ^ value[4*t +: 4]) & care[4*t +: 4]) == '0;
  endfunction
  // Output o on one row: the OR of the terms its PICK byte selects.
  function automatic logic out(input int o, input logic [3:0] row);
    logic y;
    y = 1'b0;
    for (int t = 0; t < 8; t++) if (pick[8*o + t] && hit(t, row)) y = 1'b1;
    return y;
  endfunction

  initial begin
    int wrong, bad, terms, lits;
    logic used;
    #1;                                  // let the table reach the wires
    bad = 0;
    wrong = 0;
    for (int m = 0; m < 16; m++) if (out(0, m[3:0]) !== F0[m]) wrong++;
    $display("f: %0d of 16 rows wrong", wrong);
    bad += wrong;
    wrong = 0;
    for (int m = 0; m < 16; m++) if (out(1, m[3:0]) !== F1[m]) wrong++;
    $display("g: %0d of 16 rows wrong", wrong);
    bad += wrong;
    terms = 0;
    lits = 0;
    for (int t = 0; t < 8; t++) begin
      used = 1'b0;
      for (int o = 0; o < 2; o++) if (pick[8*o + t]) used = 1'b1;
      if (t < n && used) begin
        terms++;
        lits += $countones(care[4*t +: 4]);
      end
    end
    $display("%0d shared terms, %0d literals", terms, lits);
    if (bad == 0 && terms == 5 && lits == 17) $display("minimum is 5 terms, 17 literals: reached");
    else if (bad == 0) $display("minimum is 5 terms, 17 literals: not reached");
  end
endmodule

Check Yourself

Predict the outputThe program builds both lamps from the shared design and applies row 0001. Predict the exact line.
module tb;
  logic a, b, c, d;
  wire s = ~a & ~b & ~c & d;          // the shared term a'b'c'd
  wire f = s | (~a & b & d) | (a & b & ~d);
  wire g = s | (~a & ~b & ~d) | (a & ~b & c & d);
  initial begin
    {a, b, c, d} = 4'b0001;
    #1 $display("f=%b g=%b", f, g);
  end
endmodule
Spot the bugEach option builds both lamps. The bench compares f and g with their functions on all 16 rows. Which one fails?
ConceptTwo outputs are minimized alone, with 3 and 4 terms. One term appears in both covers. How many AND gates does the circuit need?
ConceptWhich term is a candidate for sharing between outputs f and g?
ConceptWhy can the joint minimum make one output's own cover larger?

Common Mistakes

Wrong Minimize each output on its own and add the results.

Each output then picks its own largest groups. A smaller group that both outputs could use is never seen.

Fix Minimize the outputs together and count each distinct term once.

Wrong Share only terms that are prime for each output.

The best shared term is often smaller than the primes of either output, as a'b'c'd is here.

Fix Include the primes of the product functions, such as f · g, as candidates.

Wrong Attach a term to an output whose 0 it covers.

A term may serve an output only if it is an implicant of that output.

Fix Check each output a term serves: no 0 of that output may sit in the term.

Remember

  • A multiple-output circuit pays for each distinct product term once, however many outputs use it.
  • Separate minimum covers are not a joint minimum; the best shared term may be prime for neither output.
  • Candidates are the primes of each output and of the products of outputs, tagged with the outputs they serve.
  • Joint minimization sets the size of a shared AND plane, as in a PLA.

Practice

Report a problem with this page