G7.5.2 Fill the Implication Chart

MediumImplementIcarus · browser samples / server checksReview the topic

Fill the implication chart of a six-state Mealy machine pass by pass, and say how many states remain after merging.

Hardware context: A protocol block drawn with more states than it needs, under an area review. Fill an implication chart pass by pass and count the states after merging.

Before a state machine is coded, the team checks it for equivalent states with an implication chart. You do the chart for the machine below.

This is an Implement problem with no logic to write. Write one constant per cell: 1 if the two states can be told apart (crossed), 0 if it stays open. Then give the number of states after merging.

The first three constants are worked examples. The check compares every constant with the right value and names the first wrong one.

Signals in the Timeline

SignalWidthRole
question8input of each check
Full specification
Statenext if x = 0next if x = 1z if x = 0z if x = 1
S0S3S001
S1S3S201
S2S3S301
S3S1S400
S4S5S201
S5S4S100
ConstantWhat to write
X_S0_S1The cell for S0 and S1: 1 if crossed (not equivalent), 0 if it stays open.
X_S0_S2The cell for S0 and S2: 1 if crossed (not equivalent), 0 if it stays open.
X_S0_S3The cell for S0 and S3: 1 if crossed (not equivalent), 0 if it stays open.
X_S0_S4The cell for S0 and S4: 1 if crossed (not equivalent), 0 if it stays open.
X_S0_S5The cell for S0 and S5: 1 if crossed (not equivalent), 0 if it stays open.
X_S1_S2The cell for S1 and S2: 1 if crossed (not equivalent), 0 if it stays open.
X_S1_S3The cell for S1 and S3: 1 if crossed (not equivalent), 0 if it stays open.
X_S1_S4The cell for S1 and S4: 1 if crossed (not equivalent), 0 if it stays open.
X_S1_S5The cell for S1 and S5: 1 if crossed (not equivalent), 0 if it stays open.
X_S2_S3The cell for S2 and S3: 1 if crossed (not equivalent), 0 if it stays open.
X_S2_S4The cell for S2 and S4: 1 if crossed (not equivalent), 0 if it stays open.
X_S2_S5The cell for S2 and S5: 1 if crossed (not equivalent), 0 if it stays open.
X_S3_S4The cell for S3 and S4: 1 if crossed (not equivalent), 0 if it stays open.
X_S3_S5The cell for S3 and S5: 1 if crossed (not equivalent), 0 if it stays open.
X_S4_S5The cell for S4 and S5: 1 if crossed (not equivalent), 0 if it stays open.
STATES_AFTERHow many states the machine has after merging every open pair.

Examples

Example 1

Worked Example: S0 And S3
Input
the cell for S0 and S1: 1 if crossed (not equivalent), 0 if it stays open
Output
x_s0_s1 = 1

S0 has z = 1 on x = 1, S3 has z = 0. Different outputs: crossed on pass 0. This constant is already filled in.

Example 2

Worked Example: S0 And S5
Input
the cell for S0 and S2: 1 if crossed (not equivalent), 0 if it stays open
Output
x_s0_s2 = 1

S5 has z = 0 on x = 1 too, so S0 and S5 are crossed on pass 0 as well.

Example 3

Worked Example: S2 And S3
Input
the cell for S0 and S3: 1 if crossed (not equivalent), 0 if it stays open
Output
x_s0_s3 = 1

The same output difference on x = 1. Every pair of one state from {S0 S1 S2 S4} and one from {S3 S5} is crossed.

Constraints and Contract

  • Keep the module name answer and the names of the constants.
  • Each cell is 0 or 1.

Hints

Hint 1

Cross every cell whose two states have a different z for x = 0 or for x = 1. That is pass 0.

Hint 2

In every other cell, list the pairs of next states for x = 0 and x = 1. Cross the cell if one of them is crossed. Pass over the chart again until nothing changes.

Hint 3

A cell that implies only itself or other open cells stays open. Each open pair merges into one state.

What the grader checks: The check reads each constant and compares it with a chart computed in JavaScript from the table. It cannot see how a value was found.

16 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

Worked Example: S0 And S3

Input
the cell for S0 and S1: 1 if crossed (not equivalent), 0 if it stays open
Expected output
x_s0_s1 = 1

S0 has z = 1 on x = 1, S3 has z = 0. Different outputs: crossed on pass 0. This constant is already filled in.

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

Icarus · browser samples / server checks