G3.6.1 Break the Cyclic Chart

HardImplementIcarus · browser samples / server checksReview the topic

Find a minimum cover of a function whose prime implicant chart is cyclic, where the largest groups are a trap.

Hardware context: An alarm function whose eight prime implicants form a ring, so no prime is forced. Find a minimum cover of a beacon function where the largest groups are a trap.

A lighting controller drives a warning beacon from four bits, a b c d. The beacon function f is 1 on twelve of the sixteen rows. A quick tool picked the largest groups first and built a correct cover with six terms.

This is an Implement problem. Find all prime implicants and draw the chart. No prime is essential and no dominance applies, so use Petrick's method to find the cheapest cover.

You write no logic. Your answer is a table of product terms. The check builds the sum of products, tests all sixteen rows, and counts your terms and literals.

Your cover must be right on every row. It must also use the fewest terms that any correct cover can use, and the fewest literals for that number of terms.

Signals in the Timeline

SignalWidthRole
row4input of each check
Full specification
cd = 00cd = 01cd = 11cd = 10
ab = 000111
ab = 011101
ab = 111011
ab = 101110

The map above is f. Rows are ab and columns are cd, both in Gray order. As a list: f = Σm(1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 14, 15).

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.
LiteralOne used variable in one term. The check counts the 1 bits of CARE in the first N terms.
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.

Each row check reports f for one input row. The two cost checks pass only for a cover that no correct cover can beat.

Examples

Example 1

A 1 Held by Two Pairs
Input
abcd = 0101
Output
f = 1

The cell at row ab = 01, column cd = 01 holds a 1. Two pairs hold it, and no group of four does.

Example 2

A 0 of f
Input
abcd = 0000
Output
f = 0

The cell at row ab = 00, column cd = 00 holds a 0. No term may hold it.

Example 3

Another 1 Held by Two Pairs
Input
abcd = 1111
Output
f = 1

The cell at row ab = 11, column cd = 11 holds a 1. Each of its two primes is a pair.

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

There are ten prime implicants: two groups of four and eight pairs. Every 1 is held by exactly two of them.

Hint 2

Write one sum per row of f: the two primes that hold it. Multiply the sums out one at a time, and drop any product that holds a smaller one.

Hint 3

A cover with both groups of four still needs four pairs. Count the products of Petrick's method that use only one group of four.

What the grader checks: The check builds the sum of products from the table and compares it with f on all 16 input rows. It then compares the number of terms and of literals with the true minimum. An exhaustive search over the prime implicants finds that minimum. Either minimum cover passes.

18 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

A 1 Held by Two Pairs

Input
abcd = 0101
Expected output
f = 1

The cell at row ab = 01, column cd = 01 holds a 1. Two pairs hold it, and no group of four does.

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

Icarus · browser samples / server checks