G3.1.1 Minimal Cover, Four Variables

MediumOptimizeIcarus · browser samples / server checksReview the topic

Shrink a correct eight-term expression to the minimum sum of products for a four-variable function: the fewest terms, then the fewest literals.

Hardware context: A four-input warning-lamp function of a greenhouse controller, given as a Karnaugh map. Shrink a correct one-term-per-row lamp equation to its minimum sum of products.

A greenhouse controller turns on a warning lamp from four sensor bits: a, b, c and d. The lamp function f is 1 for eight of the sixteen input rows. The first engineer wrote one product term per row. That works, but it costs eight AND gates with four inputs each.

This is an Optimize problem. The starter is that eight-term answer, and it is correct. Draw the Karnaugh map, group the 1s, and replace the table with the minimum cover.

You write no logic. Your answer is a table of product terms. N is the number of terms. CARE marks the variables a term uses. VALUE gives the value each used variable must have. The check builds the sum of products from your table, tests all sixteen rows, and counts your terms and literals.

Your cover must be right on every row. It must also use the fewest terms that any correct cover can use, and the fewest literals for that number of terms.

Signals in the Timeline

SignalWidthRole
row4input of each check
Full specification
cd = 00cd = 01cd = 11cd = 10
ab = 001011
ab = 010010
ab = 111100
ab = 101001

The map above is f. Rows are ab and columns are cd, both in Gray order (00, 01, 11, 10). As a list: f = Σm(0, 2, 3, 7, 8, 10, 12, 13). The minterm number is the binary value of abcd.

How one term is written: the term a b' (a is 1, b is 0, c and d are not used)
CARE  = 4'b1100   // the term uses a and b
VALUE = 4'b1000   // a must be 1, b must be 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.
LiteralOne used variable in one term. The check counts the 1 bits of CARE in the first N terms.
VALUE where CARE is 0Ignored. Write 0 there to keep the table easy to read.
ModuleKeep the module name answer and its three outputs. Change only N, CARE and VALUE.

Each row check reports f for one input row. The two cost checks report your number of terms and your number of literals. They pass only for a cover that no correct cover can beat.

Examples

Example 1

A Corner of the Map
Input
abcd = 0000
Output
f = 1

The cell at row ab = 00, column cd = 00 holds a 1. So some term of the table must cover the row abcd = 0000.

Example 2

A 0 Between Two 1s
Input
abcd = 0110
Output
f = 0

The cell at row ab = 01, column cd = 10 holds a 0. A group that grows over this cell makes the cover wrong, even if it saves a literal.

Example 3

A 1 in the Middle of the Map
Input
abcd = 0111
Output
f = 1

The cell at row ab = 01, column cd = 11 holds a 1. Some term of the table must cover it.

Constraints and Contract

  • Keep the module name answer and the three outputs n, care and value.
  • N is a whole number from 0 to 8. CARE and VALUE hold one 4-bit group per term, in the order a b c d.

Hints

Hint 1

Draw the map from the specification first. A group is a rectangle of 1, 2, 4 or 8 cells. It may wrap around the edges of the map.

Hint 2

Look at the four corners. They touch each other through both wrap-arounds. A cell that only one group can cover tells you that group is needed.

Hint 3

After you cover every 1, check each group again. If every cell of a group is also inside another chosen group, the group is extra. Then read each group: a variable that changes inside the group is left out (CARE 0).

What the grader checks: The check builds the sum of products from the table. It compares it with the specified function on all 16 input rows. Then it compares the number of terms and of literals with the true minimum. An exhaustive search over the prime implicants finds that minimum. The check reads the table, not a circuit: delay and hazards are outside this problem.

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 Corner of the Map

Input
abcd = 0000
Expected output
f = 1

The cell at row ab = 00, column cd = 00 holds a 1. So some term of the table must cover the row abcd = 0000.

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

Icarus · browser samples / server checks