G2.4.1 Simplify Within a Literal Budget

MediumOptimizeIcarus · browser samples / server checksReview the topic

Simplify a five-term logic expression with the laws of Boolean algebra until it fits a budget of four literals.

Hardware context: The enable signal of a press interlock, and seven rewrites found in a design review of control logic. Simplify a five-term expression to two terms and four literals.

A press has a safety interlock. Its enable signal f comes from four inputs: a, b, c and d. The first engineer wrote f as five product terms with 14 literals. The cell library has no room for that many gate inputs.

This is an Optimize problem. Simplify the expression with the laws of Boolean algebra: combining, absorption and consensus. The starter is the expression as given, and it is correct.

You write no logic. Your answer is a table of product terms. N is the number of terms. CARE marks the variables a term uses. VALUE gives the value each used variable must have. The check builds the sum of products from your table and tests all sixteen rows.

Your answer must be right on every row. It must also fit the budget: at most 2 terms and at most 4 literals.

Signals in the Timeline

SignalWidthRole
row4input of each check
Full specification
The expression as given (ab is AND, a + b is OR, a' is NOT)
f = abd + abd' + a'c + a'cd' + bcd
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.
BudgetAt most 2 terms and at most 4 literals. No correct answer is smaller.
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 report your number of terms and of literals.

Examples

Example 1

The Press Is Enabled for Abcd = 1100
Input
abcd = 1100
Output
f = 1

With a = 1, b = 1 and d = 0, the term abd' of the given expression is 1. Any simpler form must keep this row at 1.

Example 2

The Press Is Enabled for Abcd = 0010
Input
abcd = 0010
Output
f = 1

With a = 0, c = 1 and d = 0, the terms a'c and a'cd' are both 1. One of them is enough.

Example 3

The Row Where Every Input Is 1
Input
abcd = 1111
Output
f = 1

Three of the five given terms are 1 here. The answer must still give 1.

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

Two terms that differ in one variable only, once plain and once inverted, combine into one term without that variable.

Hint 2

A term that holds every literal of a shorter term is absorbed by it: x + xy = x.

Hint 3

After the first two steps, look for a term that holds neither a nor a'. The consensus theorem may make it redundant.

What the grader checks: The check builds the sum of products from the table. It compares it with the given expression on all 16 input rows. Then it compares the number of terms and of literals with the true minimum, found by an exhaustive search. It reads the table, not a circuit.

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

The Press Is Enabled for Abcd = 1100

Input
abcd = 1100
Expected output
f = 1

With a = 1, b = 1 and d = 0, the term abd' of the given expression is 1. Any simpler form must keep this row at 1.

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

Icarus · browser samples / server checks