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
| Signal | Width | Role |
|---|---|---|
question | 8 | input of each check |
Full specification
| State | next if x = 0 | next if x = 1 | z if x = 0 | z if x = 1 |
|---|---|---|---|---|
| S0 | S3 | S0 | 0 | 1 |
| S1 | S3 | S2 | 0 | 1 |
| S2 | S3 | S3 | 0 | 1 |
| S3 | S1 | S4 | 0 | 0 |
| S4 | S5 | S2 | 0 | 1 |
| S5 | S4 | S1 | 0 | 0 |
| Constant | What to write |
|---|---|
| X_S0_S1 | The cell for S0 and S1: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S0_S2 | The cell for S0 and S2: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S0_S3 | The cell for S0 and S3: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S0_S4 | The cell for S0 and S4: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S0_S5 | The cell for S0 and S5: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S1_S2 | The cell for S1 and S2: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S1_S3 | The cell for S1 and S3: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S1_S4 | The cell for S1 and S4: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S1_S5 | The cell for S1 and S5: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S2_S3 | The cell for S2 and S3: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S2_S4 | The cell for S2 and S4: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S2_S5 | The cell for S2 and S5: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S3_S4 | The cell for S3 and S4: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S3_S5 | The cell for S3 and S5: 1 if crossed (not equivalent), 0 if it stays open. |
| X_S4_S5 | The cell for S4 and S5: 1 if crossed (not equivalent), 0 if it stays open. |
| STATES_AFTER | How 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