G3.4.1 Minimal Cover, Five Variables

HardOptimizeIcarus · browser samples / server checksReview the topic

Shrink a six-term cover of a five-variable function to its minimum by merging groups across the two maps.

Hardware context: A belt-stop function of a packaging line from five sensor bits, given as two Karnaugh maps. Shrink a cover that grouped each of the two maps alone to the five-variable minimum.

A packaging line stops its belt from five sensor bits: a, b, c, d and e. The stop function is 1 for sixteen of the 32 input rows. An engineer drew one map for e = 0 and one for e = 1, and minimized each map alone.

This is an Optimize problem. The starter is that answer: six product terms, each on one map. It is correct on every row. Find the groups that sit at the same cells of both maps, merge them, and replace the table with the minimum cover.

You write no logic. Your answer is a table of product terms with five bits per term, in the order a b c d e. The check builds the sum of products, tests all 32 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
row5input of each check
Full specification
e = 0cd = 00cd = 01cd = 11cd = 10
ab = 001001
ab = 010000
ab = 110100
ab = 100101
e = 1cd = 00cd = 01cd = 11cd = 10
ab = 001001
ab = 011111
ab = 111111
ab = 100100

The two maps above are the stop function. Rows are ab and columns are cd, both in Gray order. The row number is the binary value of abcde, so e is the last bit. A cell is a neighbour of the cell at the same place on the other map.

How one term is written: the term a b' (a is 1, b is 0, c, d and e are not used)
CARE  = 5'b11000   // the term uses a and b
VALUE = 5'b10000   // a must be 1, b must be 0
RuleDetail
Bit orderEach group of 5 bits is in the order a b c d e: 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 the function 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 1 on the Map for e = 0
Input
abcde = 00100
Output
f = 1

Row abcde = 00100 holds a 1. The same cell on the other map, row 00101, also holds a 1.

Example 2

A 0 on the Map for e = 0
Input
abcde = 00010
Output
f = 0

Row abcde = 00010 holds a 0. No group may take it in, on either map.

Example 3

A 1 on the Map for e = 1
Input
abcde = 11111
Output
f = 1

Row abcde = 11111 holds a 1. The same cell on the other map, row 11110, holds a 0.

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 5-bit group per term, in the order a b c d e.

Hints

Hint 1

Lay one map over the other. Where both maps hold a 1 in the same cell, a group can use both, and e leaves its term.

Hint 2

A group on both maps must have the same shape at the same place on each. Two groups at different places stay two terms.

Hint 3

After merging, check each group again. Drop a group whose cells are all inside other groups. Do not merge a group whose twin cell on the other map holds a 0.

What the grader checks: The check builds the sum of products from the table. It compares it with the specified function on all 32 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.

34 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 2 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 on the Map for e = 0

Input
abcde = 00100
Expected output
f = 1

Row abcde = 00100 holds a 1. The same cell on the other map, row 00101, also holds a 1.

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

Icarus · browser samples / server checks