G3.3.1 Minimal Product of Sums

MediumOptimizeIcarus · browser samples / server checksReview the topic

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

SignalWidthRole
row4input of each check
Full specification
cd = 00cd = 01cd = 11cd = 10
ab = 000010
ab = 010110
ab = 11xxxx
ab = 1001xx

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.

How one group of 0s is written: the cells where a is 1 and c is 0. The check reads it as the sum (a' + c)
CARE  = 4'b1010   // the sum uses a and c
VALUE = 4'b1000   // inside the group a is 1 and c is 0
RuleDetail
GroupA group of 0s of the map. The lamp is 0 on every row that some group holds, and 1 on every other row.
VALUEThe 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 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.
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.
LiteralOne 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

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

Floor 3

Input
abcd = 0011
Expected output
f = 1

The cell at row ab = 00, column cd = 11 holds a 1, so no group of 0s may hold this row.

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

Icarus · browser samples / server checks