Rewrite a five-state Moore machine as a Mealy machine with four states, whose output comes one cycle sooner.
Hardware context: A pedestrian crossing on a busy road, and a pattern flag that a downstream block needs one cycle sooner. Rewrite a five-state Moore machine as a four-state Mealy machine.
A five-state Moore machine flags a pattern one cycle after the pattern ends. The block that reads the flag needs it one cycle sooner, and the design is short of flip-flops.
This is an Implement problem. Write mealy4: the same machine as a Mealy machine with four states, S0 to S3. Its z must be 1 in the cycle that the Moore machine enters S4.
st is the state register itself, with the codes given. The check samples z and st in the middle of every cycle and compares both with a model. The design must synthesize with no latches and at most 18 cells.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
xs | 24 | input of each check |
Full specification
module mealy4 (
input logic clk,
input logic rst, // synchronous reset, active high: state S0
input logic x,
output logic z, // Mealy output: from the state and x, in the same cycle
output logic [1:0] st // the state register itself: S0 = 0, S1 = 1, S2 = 2, S3 = 3
);
...
endmodule
| Moore state | z | next if x = 0 | next if x = 1 |
|---|---|---|---|
| S0 | 0 | S1 | S0 |
| S1 | 0 | S1 | S2 |
| S2 | 0 | S1 | S3 |
| S3 | 0 | S4 | S0 |
| S4 | 1 | S1 | S2 |
| Rule | Detail |
|---|---|
| States | Four: S0, S1, S2 and S3, with st = 0, 1, 2, 3. No state means "a flag". |
| z | 1 in exactly the cycles where the Moore machine is about to enter S4: the cycle of the bit, not the next. |
| Sampling | x is set at the start of a cycle. z and st are read in the middle of the same cycle. |
Examples
Example 1
One Pass Through Every State- Input
x = 100110111111111111111111 (cycle 0 first)
- Output
z_cycles = {5}, st_cycle0 = S0 (0), st_cycle1 = S0 (0), st_cycle2 = S1 (1), st_cycle3 = S1 (1), st_cycle4 = S2 (2), st_cycle5 = S3 (3), st_cycle6 = S1 (1), st_cycle7 = S2 (2), st_cycle8 = S3 (3), st_cycle9 = S0 (0), st_cycle10 = S0 (0), st_cycle11 = S0 (0), st_cycle12 = S0 (0), st_cycle13 = S0 (0), st_cycle14 = S0 (0), st_cycle15 = S0 (0), st_cycle16 = S0 (0), st_cycle17 = S0 (0), st_cycle18 = S0 (0), st_cycle19 = S0 (0), st_cycle20 = S0 (0), st_cycle21 = S0 (0), st_cycle22 = S0 (0), st_cycle23 = S0 (0)
The stream walks the machine through S0 to S3. The flag comes in the cycle of the bit that would take the Moore machine into S4.
Example 2
Two Flags That Share Bits- Input
x = 011011011111111111111111 (cycle 0 first)
- Output
z_cycles = {3, 6}, st_cycle0 = S0 (0), st_cycle1 = S1 (1), st_cycle2 = S2 (2), st_cycle3 = S3 (3), st_cycle4 = S1 (1), st_cycle5 = S2 (2), st_cycle6 = S3 (3), st_cycle7 = S1 (1), st_cycle8 = S2 (2), st_cycle9 = S3 (3), st_cycle10 = S0 (0), st_cycle11 = S0 (0), st_cycle12 = S0 (0), st_cycle13 = S0 (0), st_cycle14 = S0 (0), st_cycle15 = S0 (0), st_cycle16 = S0 (0), st_cycle17 = S0 (0), st_cycle18 = S0 (0), st_cycle19 = S0 (0), st_cycle20 = S0 (0), st_cycle21 = S0 (0), st_cycle22 = S0 (0), st_cycle23 = S0 (0)
After a flag the machine acts as if it had seen the last bit of the pattern. So a second flag can follow three cycles later.
Example 3
Ones Only, Then Zeros Only- Input
x = 111111000000111111111111 (cycle 0 first)
- Output
z_cycles = {}, st_cycle0 = S0 (0), st_cycle1 = S0 (0), st_cycle2 = S0 (0), st_cycle3 = S0 (0), st_cycle4 = S0 (0), st_cycle5 = S0 (0), st_cycle6 = S0 (0), st_cycle7 = S1 (1), st_cycle8 = S1 (1), st_cycle9 = S1 (1), st_cycle10 = S1 (1), st_cycle11 = S1 (1), st_cycle12 = S1 (1), st_cycle13 = S2 (2), st_cycle14 = S3 (3), st_cycle15 = S0 (0), st_cycle16 = S0 (0), st_cycle17 = S0 (0), st_cycle18 = S0 (0), st_cycle19 = S0 (0), st_cycle20 = S0 (0), st_cycle21 = S0 (0), st_cycle22 = S0 (0), st_cycle23 = S0 (0)
Long runs of one value never complete the pattern. st shows where each run leaves the machine.
Constraints and Contract
- All inputs are known 0/1 values and change only between edges.
- Keep the module name and the ports; st is the only state register.
Hints
Hint 1
In a Mealy machine the output moves from the state onto the arc. Every arc that enters S4 now carries z = 1.
Hint 2
With S4 gone, each arc that entered it must go somewhere. Compare the rows: S4 behaves exactly like one of the other states after it.
Hint 3
z depends on the state and on x, so compute it in the combinational block. A register on z brings back the Moore delay.
What the grader checks: Five directed and twelve seeded streams of 24 bits after a reset. In every cycle z and the state register st are compared with a JavaScript model of the four-state Mealy machine. The state count is graded through st and a cap of 18 cells. Four states took 8 to 16 cells in the usual styles; a hidden fifth state took 24. Synthesis must report no latches.
The submitted design must synthesize with 0 latches and no combinational loop. It must use at most 18 cells; a result equal to the limit passes. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.
17 checks on Icarus Verilog + Yosys · server. 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