Reduce a five-variable prime implicant chart with essential primes and dominance, and list the primes the reduced chart forces.
Hardware context: The start signal of a pump from four level sensors, minimized by a table instead of a picture. Finish a five-variable chart with column and row dominance.
A fault detector reads five bits, a to e, and is 1 on fifteen rows. Its nine prime implicants and their chart are given below. Three primes are essential and are already chosen.
This is an Implement problem. Remove the columns the essential primes cover. Then apply column and row dominance until some column has a single X again. Keep going until the chart is empty.
List the primes that the reduced chart forces, and nothing else. Leave out the three essential primes and the primes that dominance drops.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
check | 3 | input of each check |
Full specification
| Prime | 2 | 3 | 7 | 9 | 13 | 15 | 18 | 20 | 22 | 23 | 25 | 26 | 29 | 30 | 31 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| cde | X | X | X | X | |||||||||||
| b'c'de' | X | X | |||||||||||||
| bd'e | X | X | X | X | |||||||||||
| bce | X | X | X | X | |||||||||||
| a'b'de | X | X | |||||||||||||
| a'b'c'd | X | X | |||||||||||||
| ade' | X | X | X | X | |||||||||||
| acd | X | X | X | X | |||||||||||
| ab'ce' | X | X |
The essential primes are bd'e, ade', ab'ce'. Row numbers are the binary value of abcde.
CARE = 5'b11000 // the term uses a and b
VALUE = 5'b10000 // a must be 1, b must be 0
| Rule | Detail |
|---|---|
| Bit order | Each group of 5 bits is in the order a b c d e: 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. |
The check reads each listed term. It counts the terms that hold a 0, are not prime, are essential or were dropped. It also shows which forced primes you listed.
Examples
Example 1
No Term May Hold a 0- Input
the whole table
- Output
terms_holding_a_0 = 0
A listed term that holds a row where f is 0 is not an implicant.
Example 2
Every Term Must Be Prime- Input
the whole table
- Output
implicants_not_prime = 0
Only rows of the chart count. A smaller term inside a prime is not a row of the chart.
Example 3
The Essential Primes Are Already Chosen- Input
the whole table
- Output
essential_primes_listed = 0
Listing an essential prime here is wrong: the question is what the chart forces after them.
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
After the essential primes, only columns 2, 3, 7, 15, 23 and 31 are left. Compare the rows that hold X in those columns.
Hint 2
A column whose X rows include every X row of another column can go. Then look for a row whose columns all sit inside a row that costs no more.
Hint 3
Each time a column is left with one X, that prime is forced. Two primes end up forced.
What the grader checks: The check reads the table once. For each listed term it tests every row of f and tests primality by dropping each literal. It compares the term with the essential and forced primes of the JavaScript chart reduction.
7 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