List exactly the essential prime implicants of a four-variable function with don't-cares, using the tabular method.
Hardware context: The start signal of a pump from four level sensors, minimized by a table instead of a picture. List the essential prime implicants of a reject function with don't-cares.
A sorting gate reads four sensor bits, a b c d. Its reject signal f is 1 on seven rows. The rows 0011 and 0101 never occur, because two of the sensors cannot both see a part there. They are don't-cares.
This is an Implement problem. Run the Quine-McCluskey method: merge the terms, find every prime implicant, and draw the chart. Then list the essential prime implicants, and nothing else.
You write no logic. Your answer is a table of product terms, as in the earlier problems. Here it is not a cover. It is the set of essential primes.
The check reads each listed term. It tests whether the term holds a 0 of f, whether it is prime, and whether it is essential. It also checks that every essential prime is there.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
check | 3 | input of each check |
Full specification
| cd = 00 | cd = 01 | cd = 11 | cd = 10 | |
|---|---|---|---|---|
| ab = 00 | 1 | 0 | x | 0 |
| ab = 01 | 0 | x | 1 | 1 |
| ab = 11 | 0 | 1 | 0 | 0 |
| ab = 10 | 1 | 0 | 1 | 1 |
The map above is f. Rows are ab and columns are cd, both in Gray order. As a list: f = Σm(0, 6, 7, 8, 10, 11, 13) + d(3, 5).
| Word | Meaning in this problem |
|---|---|
| Implicant | A product term that holds no row where f is 0. It may hold don't-care rows. |
| Prime implicant | An implicant that stops being one when any of its literals is dropped. |
| Essential prime | A prime implicant that is the only prime holding some row where f is 1. |
CARE = 4'b1100 // the term uses a and b
VALUE = 4'b1000 // a must be 1, b must be 0
| Rule | Detail |
|---|---|
| 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. |
The check does not count literals. It reports how many listed terms hold a 0 and how many are not prime. It also reports which essential primes you listed, and how many other primes.
Examples
Example 1
No Term May Hold a 0- Input
the whole table
- Output
terms_holding_a_0 = 0
A term that holds a row where f is 0 is not an implicant. Such a term can never be prime.
Example 2
Every Term Must Be Prime- Input
the whole table
- Output
implicants_not_prime = 0
A term that still holds no 0 after one literal is dropped is not prime. The starter has seven such terms.
Example 3
A Row with One Prime- Input
row abcd = 0000
- Output
listed = 1
Row 0000 is held by one prime only. That prime must be in your list.
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 term, in the order a b c d.
Hints
Hint 1
Merge the don't-care rows 3 and 5 like 1s. They make some primes larger. But give the chart a column only for the seven 1s.
Hint 2
In the chart, look for a column with a single X. The prime in that row is essential. Some prime is essential only because a don't-care made it large.
Hint 3
A minimum cover may need one more prime after the essential ones. Do not list it: it is prime, but not essential.
What the grader checks: The check reads the table, not a circuit. For each listed term it tests every row of f. A term holding a row where f is 0 is not an implicant. An implicant is prime when dropping any one literal makes it hold a 0. The essential primes come from the exact minimizer in JavaScript and are compared term by term.
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