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
| Signal | Width | Role |
|---|---|---|
row | 4 | input of each check |
Full specification
| fg | cd = 00 | cd = 01 | cd = 11 | cd = 10 |
|---|---|---|---|---|
| ab = 00 | 00 | 00 | 11 | 01 |
| ab = 01 | 10 | 11 | 00 | 00 |
| ab = 11 | 10 | 11 | 01 | 10 |
| ab = 10 | 11 | 01 | 11 | 01 |
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).
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
| Rule | Detail |
|---|---|
| Bit order | Each group of 4 bits is in the order a b c d: a is the left bit. |
| Term order | Term 0 is the rightmost group in the braces. The order of terms does not change the result. |
| N | The number of terms that count, from 0 to 8. Groups beyond N are ignored. |
| VALUE where CARE is 0 | Ignored. Write 0 there to keep the table easy to read. |
| PICK | One byte per output: byte 0 is f, byte 1 is g. Bit t set means the output ORs term t. |
| Cost | A term counts once if any output picks it. Its literals are the 1 bits of its CARE group. |
| Module | Keep 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