Interview questions & answers
Q1. What is the fundamental difference between a Mealy and a Moore state machine?
In a Moore machine, the output depends only on the current state, while in a Mealy machine, the output depends on both the current state and the current input. A Moore traffic light controller's output (red/green/yellow) changes only when the state changes, whereas a Mealy vending machine can immediately output 'dispense' the moment the coin input completes — without waiting for a state transition. This makes Mealy machines faster in response but harder to debug because outputs can glitch with input noise.
Follow-up: When would you specifically choose a Moore machine over a Mealy machine in a design?
Q2. Which has fewer states — a Mealy or a Moore machine implementing the same function?
A Mealy machine generally requires fewer states than a Moore machine for the same function because a single Mealy state can produce different outputs based on inputs, whereas a Moore machine needs separate states for each distinct output combination. A sequence detector for '101' requires 3 states in a Mealy machine but 4 states in the equivalent Moore machine. The trade-off is that Mealy's output combinational logic is more complex.
Follow-up: Design a Moore state machine to detect the sequence '1011'. How many states do you need?
Q3. What is a sequence detector and how is the design process approached using an FSM?
A sequence detector is an FSM that asserts an output when a specific input bit sequence is received, designed by drawing a state diagram where each state represents how much of the target sequence has been matched so far. For a '1011' sequence detector, there are states S0 (no match), S1 (matched '1'), S2 (matched '10'), S3 (matched '101'), and S4 (matched '1011' — output 1). Overlapping sequences are handled by transitioning back to a partial-match state rather than S0, which is the most common design mistake.
Follow-up: How does the design change for an overlapping versus a non-overlapping sequence detector?
Q4. How do you convert a Mealy machine to a Moore machine?
You convert a Mealy machine to Moore by splitting each Mealy state into multiple Moore states — one for each distinct output value that state can produce depending on input — and associating the output with the new state. A Mealy machine with 3 states where state S1 produces output 0 on input 0 and output 1 on input 1 becomes a Moore machine with states S1a (output 0) and S1b (output 1). The resulting Moore machine has more states but outputs are glitch-free.
Follow-up: What hardware constructs in FPGAs benefit from the Moore machine's glitch-free output property?
Q5. What are the timing characteristics of Mealy vs Moore machine outputs?
Mealy machine outputs change immediately when inputs change within a clock cycle, making them potentially combinational (asynchronous), while Moore machine outputs only change on clock edges (synchronous). In a 50MHz digital system like a Xilinx Artix-7 FPGA design, Mealy output glitches lasting nanoseconds can cause logic errors in downstream registers if not properly timed. Moore machines are preferred in synchronous designs where output stability between clock edges is required.
Follow-up: How do you handle Mealy output glitches in a practical FPGA implementation?
Q6. How do you draw a state transition table for a 2-state Mealy machine?
A state transition table lists current state, input, next state, and output as columns, with one row for each combination of current state and input. For a 2-state Mealy machine with 1-bit input, the table has 4 rows: (S0,0)→(S0,out=0), (S0,1)→(S1,out=0), (S1,0)→(S0,out=1), (S1,1)→(S1,out=0). This table is the starting point for deriving flip-flop excitation equations and output logic.
Follow-up: How do you derive the D flip-flop excitation equations from a state transition table?
Q7. Design a modulo-3 counter using a Moore FSM.
A modulo-3 counter cycles through states 00→01→10→00, with the 2-bit state value as the Moore output. Three states (S0=00, S1=01, S2=10) are sufficient; the transition is unconditional on each clock edge. Using two D flip-flops with combinational next-state logic: D1 = Q1 XOR Q0, D0 = NOT(Q1) AND NOT(Q0) yields a standard 2-bit Gray-coded modulo-3 counter. This is a Moore machine because output (state bits) depends only on the current state.
Follow-up: How would you modify this FSM to reset to state 00 when an asynchronous reset input goes high?
Q8. What is the role of state encoding in FSM design and how does it affect implementation?
State encoding assigns binary codes to states and directly affects the complexity of next-state and output combinational logic. Binary encoding (00, 01, 10, 11) minimizes the number of flip-flops but may require more gates; one-hot encoding (0001, 0010, 0100, 1000) uses more flip-flops but simplifies next-state logic, which is preferred in FPGAs where flip-flops are abundant. In a 16-state Mealy machine implemented on a Spartan-6 FPGA, one-hot encoding often achieves higher clock speeds due to simpler logic between registers.
Follow-up: What is one-hot encoding and what are its advantages in FPGA implementation?
Q9. What is a state minimization technique and when is it applied?
State minimization reduces the number of states by merging equivalent states — states that produce the same output for every input and transition to equivalent next states. The implication table (Paull-Unger method) is the formal technique for identifying and merging equivalent states. For a Moore machine with 8 states, minimization might reduce it to 5 states, saving one flip-flop and reducing gate count — critical in ASICs where area is a premium.
Follow-up: What are the conditions under which two states in a Moore machine can be merged?
Q10. How is an FSM used to implement a serial communication protocol like UART?
A UART receiver is implemented as a Moore FSM with states for IDLE (waiting for start bit), START (detecting start bit), DATA0–DATA7 (receiving 8 data bits), STOP (checking stop bit), and ERROR. The state machine samples the RX line at each baud clock tick, transitioning through states to assemble the received byte. A standard 115200 baud UART FSM implemented in a Verilog always block on a Spartan-7 FPGA uses one-hot encoding for its 12 states to achieve reliable operation.
Follow-up: How does the UART FSM handle a framing error when the stop bit is not detected correctly?
Q11. What is the difference between synchronous and asynchronous FSM design?
In a synchronous FSM, state transitions occur only on clock edges (flip-flops clocked by a common clock), making the design predictable and immune to input glitches that don't persist to the clock edge. In an asynchronous FSM, transitions occur immediately when inputs change, which makes the design faster but prone to hazards and race conditions. All FPGA-based designs at Qualcomm and Texas Instruments mandate synchronous FSMs; asynchronous designs appear only in custom VLSI or ECL logic for extreme speed applications.
Follow-up: What is a race condition in an asynchronous FSM and how does it manifest as incorrect behavior?
Q12. How do you implement an FSM in Verilog?
An FSM in Verilog is typically coded with two always blocks: one combinational block for next-state and output logic, and one sequential block sensitive to clock and reset that updates the state register on each clock edge. For a 3-state sequence detector, the combinational block uses a case statement on the current state, and the sequential block uses a non-blocking assignment (<=) for the state flip-flop. Using parameter or localparam to name states (e.g., S0, S1, S2) rather than raw numbers makes the code readable and maintainable.
Follow-up: What is the difference between blocking (=) and non-blocking (<=) assignments in Verilog sequential logic?
Q13. What are the hazards in FSM design and how are they prevented?
The main hazards in FSM design are output glitches in Mealy machines (combinational outputs changing with inputs mid-cycle) and next-state glitches from combinational logic. Registering the outputs (adding a D flip-flop at the output) converts a Mealy machine to behave like a Moore machine and eliminates output glitches at the cost of one cycle latency. In Samsung SoC designs, all FSM outputs driving critical control signals are registered to meet setup and hold time requirements.
Follow-up: What is the trade-off of registering FSM outputs to eliminate glitches?
Q14. Design a 3-bit binary up-counter as a Moore FSM and derive its next-state equations.
An 8-state Moore FSM cycles S0→S1→...→S7→S0, with state bits Q2Q1Q0 as output. The next-state equations for D flip-flops are: D0 = NOT(Q0), D1 = Q0 XOR Q1, D2 = Q2 XOR (Q0 AND Q1). This is the standard T flip-flop binary counter logic rewritten for D flip-flops. The output is simply the state encoding, confirming this is a Moore machine — output depends only on current state.
Follow-up: How do you modify the next-state equations to make this a modulo-5 counter instead of modulo-8?
Q15. What is a safe FSM and why is it important in FPGA design?
A safe FSM includes defined transitions from illegal or unreachable states back to a known valid state (usually the reset state), preventing the machine from locking up if power-on random initialization or SEU (single-event upset) lands it in an illegal state. In a 3-bit one-hot FSM on a Xilinx FPGA exposed to radiation (e.g., aerospace applications), a stray particle can flip a flip-flop and create an illegal state; without a safe design, the FSM hangs. Adding a 'default' branch in the Verilog case statement to go to the reset state implements a self-recovering safe FSM.
Follow-up: What is a single-event upset (SEU) and how does it affect flip-flop-based digital circuits?
Common misconceptions
Misconception: A Mealy machine always requires fewer gates than a Moore machine because it has fewer states.
Correct: While Mealy machines use fewer states, their output logic is more complex (depending on both state and input), so total gate count is not necessarily lower than a Moore machine.
Misconception: Moore machine outputs are always registered (synchronous) and Mealy outputs are always combinational.
Correct: By default Mealy outputs are combinational and Moore outputs are combinational functions of state; registering either type's output is a design choice that adds one cycle latency.
Misconception: State minimization always improves the final circuit, so it should always be applied.
Correct: State minimization reduces flip-flop count but can increase next-state logic complexity; sometimes a larger state space with simpler logic gives better timing and lower area in FPGA implementation.
Misconception: In a sequence detector FSM, the machine always returns to the initial state after detecting the target sequence.
Correct: For overlapping sequence detectors, the machine transitions to a partial-match state after detection, not the initial state, allowing detection of sequences that share a prefix with the next sequence.