G3.5.1 Find the Essential Prime Implicants

HardImplementIcarus · browser samples / server checksReview the topic

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

SignalWidthRole
check3input of each check
Full specification
cd = 00cd = 01cd = 11cd = 10
ab = 0010x0
ab = 010x11
ab = 110100
ab = 101011

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).

WordMeaning in this problem
ImplicantA product term that holds no row where f is 0. It may hold don't-care rows.
Prime implicantAn implicant that stops being one when any of its literals is dropped.
Essential primeA prime implicant that is the only prime holding some row where f is 1.
How one term is written: the term a b' (a is 1, b is 0, c and d are not used)
CARE  = 4'b1100   // the term uses a and b
VALUE = 4'b1000   // a must be 1, b must be 0
RuleDetail
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.

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

Report a problem with this page

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

No Term May Hold a 0

Input
the whole table
Expected 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.

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

Icarus · browser samples / server checks