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 lamps | AND gates (distinct terms) | Literals |
|---|---|---|
| Each lamp minimized alone | 6 | 19 |
| Both lamps minimized together | 5 | 17 |
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.
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.
- I/O
- Datapath
- Data
- Five AND gates
The joint design has five product terms, so five AND gates.
- 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.
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.
| Lamp | Terms alone | Literals alone | Terms together | Literals together |
|---|---|---|---|---|
| f | 3 | 9 | 3 | 10 |
| g | 3 | 10 | 3 | 11 |
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 term | Rows | Serves | Prime of |
|---|---|---|---|
a'c'd | 1, 5 | f | f |
a'b'd' | 0, 2 | g | g |
a'b'c' | 0, 1 | g | g |
a'b'c'd | 1 | f and g | f · g |
a'bd | 5, 7 | f | f |
ab'cd | 11 | g | g |
abd' | 12, 14 | f | f |
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.
| Structure | What is shared | Cost to minimize |
|---|---|---|
| Separate two-level circuits | nothing | terms of each output |
| Two-level circuit with shared ANDs | AND gates | distinct terms, then literals |
| PLA | the whole AND plane | distinct terms |
| PAL | nothing: each output has fixed terms | terms 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
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.
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.
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.
f: 0 of 16 rows wrong g: 0 of 16 rows wrong 6 shared terms, 19 literals minimum is 5 terms, 17 literals: not reachedRead 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
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.