Shrink an eight-term cover of a six-variable function to its minimum by finding the groups that span the four maps.
Hardware context: A belt-stop function of a packaging line from five sensor bits, given as two Karnaugh maps. Merge the groups of a six-variable sorter function across its four maps.
A sorter reads six sensor bits, a to f. Its divert signal is 1 on 34 of the 64 rows. An engineer drew four maps, one for each value of ab, and minimized each map alone. The result is correct, with eight terms.
This is an Optimize problem. Find the groups that sit at the same cells of neighbouring maps, merge them, and replace the table with the minimum cover. Maps are neighbours when their ab values differ in one bit.
You write no logic. Your answer is a table of product terms with six bits per term, in the order a b c d e f. The check tests all 64 rows and counts your terms and literals.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
row | 6 | input of each check |
Full specification
| ab = 00 | ef = 00 | ef = 01 | ef = 11 | ef = 10 |
|---|---|---|---|---|
| cd = 00 | 1 | 0 | 1 | 1 |
| cd = 01 | 1 | 0 | 1 | 1 |
| cd = 11 | 0 | 0 | 0 | 0 |
| cd = 10 | 0 | 0 | 1 | 1 |
| ab = 01 | ef = 00 | ef = 01 | ef = 11 | ef = 10 |
|---|---|---|---|---|
| cd = 00 | 1 | 0 | 1 | 1 |
| cd = 01 | 1 | 0 | 0 | 0 |
| cd = 11 | 0 | 0 | 0 | 0 |
| cd = 10 | 0 | 0 | 1 | 1 |
| ab = 11 | ef = 00 | ef = 01 | ef = 11 | ef = 10 |
|---|---|---|---|---|
| cd = 00 | 0 | 0 | 0 | 0 |
| cd = 01 | 1 | 1 | 1 | 1 |
| cd = 11 | 1 | 1 | 1 | 1 |
| cd = 10 | 0 | 0 | 0 | 0 |
| ab = 10 | ef = 00 | ef = 01 | ef = 11 | ef = 10 |
|---|---|---|---|---|
| cd = 00 | 1 | 1 | 1 | 1 |
| cd = 01 | 1 | 1 | 1 | 1 |
| cd = 11 | 1 | 1 | 1 | 1 |
| cd = 10 | 0 | 0 | 0 | 0 |
The four maps above are the divert signal. On each map, rows are cd and columns are ef, in Gray order. The row number is the binary value of abcdef. Maps 00 and 11 are not neighbours, and neither are 01 and 10.
CARE = 6'b100100 // the term uses a and d
VALUE = 6'b100100 // a must be 1, d must be 1
| Rule | Detail |
|---|---|
| Bit order | Each group of 6 bits is in the order a b c d e f: 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. |
| Literal | One used variable in one term. The check counts the 1 bits of CARE in the first N terms. |
| VALUE where CARE is 0 | Ignored. Write 0 there to keep the table easy to read. |
| Module | Keep the module name answer and its three outputs. Change only N, CARE and VALUE. |
Each row check reports the signal for one input row. The two cost checks pass only for a cover that no correct cover can beat.
Examples
Example 1
A 1 on Map 10- Input
abcdef = 101110
- Output
f = 1
Row abcdef = 101110 holds a 1. Its twin on map 11, row 111110, also holds a 1.
Example 2
A 0 on Map 01- Input
abcdef = 011100
- Output
f = 0
Row abcdef = 011100 holds a 0. No group may take it in.
Example 3
A 1 on Map 00- Input
abcdef = 000000
- Output
f = 1
Row abcdef = 000000 holds a 1. Its twin on map 01, row 010000, holds a 1 too.
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 6-bit group per term, in the order a b c d e f.
Hints
Hint 1
Compare maps that are neighbours: 00 with 01 and with 10, and 11 with 01 and with 10. A group at the same cells of both maps loses a or b.
Hint 2
One large group covers two whole rows of cells on maps 10 and 11. Another pair of groups sits at the same place on maps 00 and 10.
Hint 3
After merging, check each group again. A group whose cells are all inside other groups is extra.
What the grader checks: The check builds the sum of products from the table and compares it with the function on all 64 rows. It compares the term and literal counts with the true minimum. The table is read once, and every check grades that copy.
66 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