Interview Question · Waveform

Moore vs Mealy Outputs on One Waveform

L0 FresherL1 JuniorL2 Mid-Levelfsmmoore mealy

Asked at Google

The interviewer asks

This machine detects two 1s in a row, with both a Mealy and a Moore output. Read the trace. When does each output rise, and why?

Reveal the Model Answer

The Mealy output rises in the cycle where the second 1 is on din. It depends on the state and the input together. The Moore output depends only on the state, so it rises one edge later, when the machine enters S2. Mealy is a cycle earlier, but its output follows the input inside the cycle. Moore changes only at clock edges.

Sampled 1 ns after each rising edge

The detector fed 0, 1, 1, 0, one bit per cycle, printed just after each edge.

RUNIcarus Verilog · in your browser

Edit the code, then run it

Expected: t=5 din=0 mealy=0 moore=0 t=15 din=1 mealy=1 moore=0 t=25 din=1 mealy=1 moore=1 t=35 din=0 mealy=0 moore=0

module two_ones (input logic clk, rst_n, din, output logic mealy, moore);
  typedef enum logic [1:0] {S0, S1, S2} st_e;   // S1: one 1 seen; S2: two or more
  st_e st;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) st <= S0;
    else case (st)
      S0: st <= din ? S1 : S0;
      S1: st <= din ? S2 : S0;
      S2: st <= din ? S2 : S0;
      default: st <= S0;
    endcase
  assign mealy = (st != S0) && din;      // state and the input now
  assign moore = (st == S2);             // state only
endmodule
module tb;
  logic clk = 0, rst_n = 1, din = 0, mealy, moore;
  two_ones dut (.clk(clk), .rst_n(rst_n), .din(din), .mealy(mealy), .moore(moore));
  always #5 clk = ~clk;
  initial begin
    #1 rst_n = 0; #1 rst_n = 1;
    @(negedge clk) din = 1;  @(negedge clk) din = 1;  @(negedge clk) din = 0;  @(negedge clk) din = 0;
    #1 $finish;
  end
  always @(posedge clk) #1 $display("t=%0t din=%b mealy=%b moore=%b", $time - 1, din, mealy, moore);
endmodule

Self-Check

Tick each key point you covered in your answer.

Key point 1 The Mealy output rises in the cycle where the second 1 is on din. Key point 2 It depends on the state and the input together. Key point 3 The Moore output depends only on the state, so it rises one edge later, when the machine enters S2. Key point 4 Mealy is a cycle earlier, but its output follows the input inside the cycle. Key point 5 Moore changes only at clock edges.

What Interviewers Listen For (Fresher)

A good fresher answer reads the trace correctly. It says which output uses the input directly.

Cross-Questions

Where the interviewer goes next. Open a node to practise that follow-up.

WhyWhat IfProve ItBreak ItCompare

Moore vs Mealy Outputs on One Waveform
WhyWhy a Mealy Output Arrives EarlyL1 JuniorL2 Mid-Level
Why is the Mealy output early, and what does that early output cost?

Reveal the Model Answer

Its logic takes the current input, so it does not wait for the state to update at the next edge. The cost is a combinational path from the input pin to the output pin. That path adds to the timing of whatever drives the input and whatever reads the output.

Self-Check
Tick each key point you covered in your answer.
Key point 1 Its logic takes the current input, so it does not wait for the state to update at the next edge. Key point 2 The cost is a combinational path from the input pin to the output pin. Key point 3 That path adds to the timing of whatever drives the input and whatever reads the output.

Missed Corner

"A path through one small block cannot be critical."

Timing counts the whole path: logic in the sender, the Mealy gates and logic in the receiver, all in one cycle.

Source Sutherland, RTL Modeling with SystemVerilog (2017) ch. 8.2.1 Mealy and Moore FSM architectures (note on glitches in 8.2.3.1)
- Lesson R3.1Moore, Mealy and When the Output Changes
- Lesson R4.2Latency, Throughput and Registered Outputs
Break ItTwo Mealy Machines Facing Each OtherL2 Mid-LevelL3 Senior
How can Mealy outputs break a design? Think of two blocks handshaking with valid and ready.
2:30

You have two and a half minutes. Speak or type, then press Get Feedback under your answer. No credits needed.

Speech-to-text runs in your browser. Chrome and Edge may send audio to their own speech service.
Reveal the Model Answer

Suppose block A makes valid from ready, and block B makes ready from valid. The two Mealy paths then form a loop through both modules. Each module looks fine on its own. Synthesis or lint finds the loop only at the level above. Register one side, or follow the rule that valid must not wait for ready.

The Loop and the Two Ways OutArrows are combinational paths inside one clock cycle. A flop ends a path; the next cycle starts from it.

The loop
valid depends on ready and ready depends on valid in the same cycle. No flop sits on the circle, so its value has no clock to settle on.
Source from state
Write valid = send. The arrow from ready to the valid gate is gone; the circle is open. The source waits for ready at the edge, as the handshake rule asks.
Sink from state
Write ready = empty. The sink promises room before it sees a beat. This is the shipped lab: both outputs come from flops.

Read the diagram as text
src state: flop: IDLE or SEND
valid gate: send && ready
ready gate: empty && valid
snk state: flop: EMPTY or FULL
sink takes beat: at the edge
src state → valid gate: send
snk state → ready gate: empty
valid gate → ready gate: valid
ready gate → valid gate: ready
valid gate → sink takes beat: beat

Opening either arrow breaks the loop. The house style opens both.

Self-Check
Tick each key point you covered in your answer.
Key point 1 Suppose block A makes valid from ready, and block B makes ready from valid. Key point 2 The two Mealy paths then form a loop through both modules. Key point 3 Each module looks fine on its own. Key point 4 Synthesis or lint finds the loop only at the level above. Key point 5 Register one side, or follow the rule that valid must not wait for ready.
Tool as Truth

"Lint was clean on both modules, so there is no loop."

A loop through two modules is invisible to a check of either module alone. It shows only when they are connected.

Source Lesson R3.3 measurement: Yosys 0.70 check reports the loop through both modules only when they are connected
CompareA Registered Mealy Output vs a Moore OutputL2 Mid-Level
Compare registering the Mealy output with converting the machine to Moore.

Reveal the Model Answer

Registering the Mealy output puts a flop after its logic. The output then changes only at edges, one cycle after the Mealy version, like a Moore output. It often needs fewer states than a Moore machine with the same behaviour. The output logic is computed from next-cycle information, so it can be decoded early.

Self-Check
Tick each key point you covered in your answer.
Key point 1 Registering the Mealy output puts a flop after its logic. Key point 2 The output then changes only at edges, one cycle after the Mealy version, like a Moore output. Key point 3 It often needs fewer states than a Moore machine with the same behaviour. Key point 4 The output logic is computed from next-cycle information, so it can be decoded early.

Half-Truth

"A registered output and a Moore output are the same thing."

Both change only at edges, but a registered Mealy output is computed from state and input before the edge. A Moore output is decoded from the state after it.

Source Sutherland, RTL Modeling with SystemVerilog (2017) ch. 8.2.3 One, two and three-procedure FSM coding styles
- Lesson R3.1Moore, Mealy and When the Output Changes
- Lesson R3.2Coding an FSM: States, Encodings, the Default
What IfA Mealy Output Fed by a Late InputL2 Mid-Level
Asked if they say Mealy is simply faster

What if the input to the Mealy output arrives late in the cycle, from another block's logic?

Reveal the Model Answer

Then the Mealy output also settles late. The receiver has only what remains of the cycle. If the input glitches before it settles, the output glitches too. A receiver that samples at the edge does not care. A clock, a latch enable or another clock domain does.

Self-Check
Tick each key point you covered in your answer.
Key point 1 Then the Mealy output also settles late. Key point 2 The receiver has only what remains of the cycle. Key point 3 If the input glitches before it settles, the output glitches too. Key point 4 A receiver that samples at the edge does not care. Key point 5 A clock, a latch enable or another clock domain does.

Half-Truth

"Glitches do not matter in synchronous design."

They do not matter to a flop that samples after the logic settles. They matter to anything that reacts to levels, such as a latch enable or a crossing.

Source Sutherland, RTL Modeling with SystemVerilog (2017) ch. 8.2.3.1 Three process state machine models (glitches on outputs)
- Lesson R3.1Moore, Mealy and When the Output Changes
- Lesson R6.2The Two-Flop Synchronizer and What It Cannot Carry
Prove ItSolve R3.1.1: An Acknowledge That Waits for the EdgeSimulator-graded

Show it, don't just say it: this Silicon Lab problem is graded by the simulator.
Open Problem R3.1.1

What People Get Wrong

Common wrong answers and why they fail. Run It shows the wrong belief failing on a real simulator.

Misconception

"Every FSM output, Mealy included, changes only at clock edges."

A Mealy output is logic on the input. When din drops in the middle of a cycle, the twin sees mealy drop at the same moment.

Run It

A watcher that flags any change of mealy away from a rising edge, then the same watcher on moore.

RUNIcarus Verilog · in your browser

Edit the code, then run it

Expected: FAIL: mealy changed at t=29, between clock edges, because din changed

module two_ones (input logic clk, rst_n, din, output logic mealy, moore);
  typedef enum logic [1:0] {S0, S1, S2} st_e;   // S1: one 1 seen; S2: two or more
  st_e st;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) st <= S0;
    else case (st)
      S0: st <= din ? S1 : S0;
      S1: st <= din ? S2 : S0;
      S2: st <= din ? S2 : S0;
      default: st <= S0;
    endcase
  assign mealy = (st != S0) && din;      // state and the input now
  assign moore = (st == S2);             // state only
endmodule
module tb;
  logic clk = 0, rst_n = 1, din = 0, mealy, moore;
  two_ones dut (.clk(clk), .rst_n(rst_n), .din(din), .mealy(mealy), .moore(moore));
  always #5 clk = ~clk;                         // rising edges at 5, 15, 25, ...
  int mid = 0;
  // The belief: this output, like any FSM output, changes only at clock edges.
  always @(mealy) if ($time % 10 != 5 && $time > 2) begin
    mid++;
    $display("FAIL: mealy changed at t=%0t, between clock edges, because din changed", $time);
  end
  initial begin
    #1 rst_n = 0; #1 rst_n = 1;
    #10 din = 1;      // t=12: S0 -> S1 at the edge at 15
    #10 din = 1;      // t=22: still 1
    #7  din = 0;      // t=29: the input drops mid-cycle
    #10;
    
    $finish;
  end
endmodule

See the Fix

module two_ones (input logic clk, rst_n, din, output logic mealy, moore);
  typedef enum logic [1:0] {S0, S1, S2} st_e;   // S1: one 1 seen; S2: two or more
  st_e st;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) st <= S0;
    else case (st)
      S0: st <= din ? S1 : S0;
      S1: st <= din ? S2 : S0;
      S2: st <= din ? S2 : S0;
      default: st <= S0;
    endcase
  assign mealy = (st != S0) && din;      // state and the input now
  assign moore = (st == S2);             // state only
endmodule
module tb;
  logic clk = 0, rst_n = 1, din = 0, mealy, moore;
  two_ones dut (.clk(clk), .rst_n(rst_n), .din(din), .mealy(mealy), .moore(moore));
  always #5 clk = ~clk;                         // rising edges at 5, 15, 25, ...
  int mid = 0;
  // The belief: this output, like any FSM output, changes only at clock edges.
  always @(moore) if ($time % 10 != 5 && $time > 2) begin
    mid++;
    
  end
  initial begin
    #1 rst_n = 0; #1 rst_n = 1;
    #10 din = 1;      // t=12: S0 -> S1 at the edge at 15
    #10 din = 1;      // t=22: still 1
    #7  din = 0;      // t=29: the input drops mid-cycle
    #10;
    if (mid == 0) $display("PASS: moore changed only at clock edges");
    $finish;
  end
endmodule

Prints: PASS: moore changed only at clock edges

Half-Truth

"Moore is always one cycle slower than Mealy."

A Moore machine can decode earlier with more states, and a registered Mealy output has the same timing as Moore. The real difference is which signals drive the output.

Source Sutherland, RTL Modeling with SystemVerilog (2017) ch. 8.2.1 Mealy and Moore FSM architectures

Buzzword Without Mechanism

"Mealy machines are asynchronous."

Their state is clocked like any FSM. Only the output logic reads the input directly.

Source Sutherland, RTL Modeling with SystemVerilog (2017) ch. 8.2.1 Mealy and Moore FSM architectures

Find Your Next Track

Put Your Skills to Work

Prepare to Explain Your Thinking

An Idea to Try? Pick a Tool.

Moore vs Mealy Outputs on One Waveform

Your Answer

Self-Check

What Interviewers Listen For (Fresher)

What Interviewers Listen For (Mid-Level)

Cross-Questions

Your Answer

Self-Check

Your Answer

Self-Check

Your Answer

Self-Check

Your Answer

Self-Check

What People Get Wrong

Learn It, Then Prove It

The Question

Your Answer

Self-Check

What Interviewers Listen For (Fresher)

What Interviewers Listen For (Mid-Level)

Cross-Questions

Your Answer

Self-Check

Your Answer

Self-Check

Your Answer

Self-Check

Your Answer

Self-Check

What People Get Wrong

Learn It, Then Prove It