Write the minimum product of sums for a function of a decimal digit by grouping the 0s of its map.
Hardware context: An express-mode lamp of a lift, driven from the floor digit through OR gates and one AND gate. Write the minimum product of sums of a BCD function with don't-cares.
A lift has an express mode. A lamp must light when the floor digit is odd and above 1: the floors 3, 5, 7 and 9. The digit arrives in four bits, a b c d, where a is the most significant bit. The codes 10 to 15 never occur.
The board has OR gates followed by one AND gate. So the lamp logic must be a product of sums. The first version has one sum for each floor where the lamp is dark. It is correct, and it has six sums of four literals.
This is an Optimize problem. Group the 0s of the map, and use the unused codes where they help. Then replace the table with the minimum product of sums.
You write no logic. Each group of the table is a group of 0s, and the check reads it as one sum term. It builds the product of sums, tests the ten digits, and counts your sums and literals against the true minimum.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
row | 4 | input of each check |
Full specification
| cd = 00 | cd = 01 | cd = 11 | cd = 10 | |
|---|---|---|---|---|
| ab = 00 | 0 | 0 | 1 | 0 |
| ab = 01 | 0 | 1 | 1 | 0 |
| ab = 11 | x | x | x | x |
| ab = 10 | 0 | 1 | x | x |
The map above is the lamp. Rows are ab and columns are cd, both in Gray order. A cell with x is an unused code: you may treat it as 0 or as 1, cell by cell.
CARE = 4'b1010 // the sum uses a and c
VALUE = 4'b1000 // inside the group a is 1 and c is 0
| Rule | Detail |
|---|---|
| Group | A group of 0s of the map. The lamp is 0 on every row that some group holds, and 1 on every other row. |
| VALUE | The value a used variable has inside the group. The sum holds the variable plain where VALUE is 0 and complemented where it is 1. |
| 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. |
| Module | Keep the module name answer and its three outputs. Change only N, CARE and VALUE. |
| Literal | One used variable in one sum. The check counts the 1 bits of CARE in the first N groups. |
Each row check reports the lamp for one digit. The codes 10 to 15 are not checked. The two cost checks pass only for a product of sums that no correct one can beat.
Examples
Example 1
Floor 3- Input
abcd = 0011
- Output
f = 1
The cell at row ab = 00, column cd = 11 holds a 1, so no group of 0s may hold this row.
Example 2
Floor 4- Input
abcd = 0100
- Output
f = 0
The cell at row ab = 01, column cd = 00 holds a 0, so some group of the table must hold this row.
Example 3
Floor 9- Input
abcd = 1001
- Output
f = 1
The cell at row ab = 10, column cd = 01 holds a 1. Its neighbours 1000 and 1011 are a 0 and an unused code.
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 sum, in the order a b c d.
Hints
Hint 1
Draw the map and look at the 0s, not the 1s. A group of 0s may take in an x cell, and it must not take in a 1.
Hint 2
Every even digit is a 0. With three of the unused codes, the even rows fill two whole columns of the map.
Hint 3
One 0 remains, at the digit 1. Pair it with the digit 0. That cell is already covered, and the pair is still the larger group.
What the grader checks: The check builds the product of sums from the table. It compares it with the lamp on the ten digit rows and skips the six unused codes. Then it compares the number of sums and of literals with the true minimum. That minimum is the minimum sum of products of the complement, found by an exhaustive search over its prime implicants. The check reads the table, not a circuit: delay and hazards are outside this problem.
12 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