G3.7.1 Shared Terms for Two Outputs

HardOptimizeIcarus · browser samples / server checksReview the topic

Minimize two outputs of the same four inputs together, so that the circuit uses the fewest distinct product terms.

Hardware context: Two lamps of a pump panel decoded from the same four inputs through one set of AND gates. Minimize the walk lamp and the timer start of a traffic controller together.

A traffic controller decodes a four-bit state code, a b c d, into two signals. Signal f turns on the walk lamp, and g starts a timer. Both come from one AND plane. Each product term is one AND gate, and both outputs may use it.

This is an Optimize problem. The starter minimizes each output alone: eight distinct terms. It is correct. Find a term both outputs can share, and rebuild the table with fewer gates.

You write no logic. Your answer is one shared list of product terms, plus one PICK byte per output that says which terms the output ORs. The check builds both outputs and tests all sixteen rows.

It then counts the distinct terms that some output uses, and their literals. Both counts must equal the true joint minimum.

Signals in the Timeline

SignalWidthRole
row4input of each check
Full specification
fgcd = 00cd = 01cd = 11cd = 10
ab = 0000001101
ab = 0110110000
ab = 1110110110
ab = 1011011101

Each cell shows f then g. Rows are ab and columns are cd, both in Gray order. As lists, f = Σm(3, 4, 5, 8, 11, 12, 13, 14). And g = Σm(2, 3, 5, 8, 9, 10, 11, 13, 15).

How the table is written: term 0 is a b', and both outputs OR it
N     = 1;
CARE  = 4'b1100     // term 0 uses a and b
VALUE = 4'b1000     // a must be 1, b must be 0
PICK  = {8'b00000001, 8'b00000001}   // byte 1 is g, byte 0 is f; bit 0 is term 0
RuleDetail
Bit orderEach group of 4 bits is in the order a b c d: a is the left bit.
Term orderTerm 0 is the rightmost group in the braces. The order of terms does not change the result.
NThe number of terms that count, from 0 to 8. Groups beyond N are ignored.
VALUE where CARE is 0Ignored. Write 0 there to keep the table easy to read.
PICKOne byte per output: byte 0 is f, byte 1 is g. Bit t set means the output ORs term t.
CostA term counts once if any output picks it. Its literals are the 1 bits of its CARE group.
ModuleKeep the module name answer and its four outputs. Change only N, CARE, VALUE and PICK.

Each row check reports f and g for one input row. The two cost checks pass only for a table that no correct table can beat.

Examples

Example 1

A 1 of Both Outputs
Input
abcd = 1000
Output
f = 1, g = 1

Row row ab = 10, column cd = 00 is a 1 of f and of g. Some term must hold it for each output.

Example 2

A 1 of g Only
Input
abcd = 1001
Output
f = 0, g = 1

Row row ab = 10, column cd = 01 is a 1 of g and a 0 of f. A term that f picks must not hold it.

Example 3

A 0 of Both
Input
abcd = 0000
Output
f = 0, g = 0

Row row ab = 00, column cd = 00 is a 0 of both outputs.

Constraints and Contract

  • Keep the module name answer and the outputs n, care, value and pick.
  • N is a whole number from 0 to 8. CARE and VALUE hold one 4-bit group per term; PICK holds one byte per output.

Hints

Hint 1

Minimize each output alone first. Then look for a 1 that both outputs cover with different terms.

Hint 2

A shared term must hold no 0 of either output. It may be smaller than every group either output chose alone.

Hint 3

Row 1000 is a 1 of both outputs. Ask which single term could serve both there, and which two terms it would replace.

What the grader checks: The check builds f and g from the table and PICK bytes, and compares both with their functions on all 16 rows. It then counts the distinct terms that some output picks, and their literals. An exact search over the multiple-output prime implicants gives the minimum.

18 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 1 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

A 1 of Both Outputs

Input
abcd = 1000
Expected output
f = 1, g = 1

Row row ab = 10, column cd = 00 is a 1 of f and of g. Some term must hold it for each output.

Run samples executes all 3 public checks. Check all tests runs 18 checks on the server.

Icarus · browser samples / server checks