G7.1.2 Moore to Mealy with One State Fewer

MediumImplementIcarus Verilog + Yosys · serverReview the topic

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

SignalWidthRole
xs24input of each check
Full specification
The module (keep the name and the ports)
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 stateznext if x = 0next if x = 1
S00S1S0
S10S1S2
S20S1S3
S30S4S0
S41S1S2
RuleDetail
StatesFour: S0, S1, S2 and S3, with st = 0, 1, 2, 3. No state means "a flag".
z1 in exactly the cycles where the Moore machine is about to enter S4: the cycle of the bit, not the next.
Samplingx 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

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

One Pass Through Every State

Input
x = 100110111111111111111111 (cycle 0 first)
Expected 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.

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

Icarus Verilog + Yosys · server