FSM Interview Questions

1. Engineering intuition — an FSM is registered state plus two clouds of logic

Every FSM, however it is coded, is the same hardware: a state register, a next-state combinational cloud that decides where to go, and an output combinational cloud that decides what to drive. The interview questions all probe how you shape those three pieces. Where do outputs come from decides Moore vs Mealy. How is the state register encoded decides binary vs one-hot vs gray. How many processes decides how cleanly the register is separated from the logic. Is the output registered decides whether it glitches. And what happens on an illegal encoding decides whether the machine recovers. So answer FSM questions by always picturing the register + next-state cloud + output cloud, and explaining how the question reshapes one of them.

2. Formal explanation — Moore vs Mealy, encoding, styles

-- MOORE: outputs depend on STATE ONLY -> glitch-free (change only at the clock), but react one cycle later.
--   moore_out <= '1' when state = DONE else '0';
 
-- MEALY: outputs depend on STATE AND INPUTS -> react in the SAME cycle, but can GLITCH with the inputs.
--   mealy_out <= '1' when (state = RUN and go = '1') else '0';
 
-- ENCODING (a type or attribute choice):
--   BINARY  : ceil(log2 N) flip-flops  -> fewest FFs, more next-state decode logic.
--   ONE-HOT : N flip-flops, one set     -> fast next-state logic, FPGA-friendly (FF-rich fabric).
--   GRAY    : one bit changes per step  -> good for crossing/low-switching, restricted transitions.
 
-- TWO-PROCESS style: clocked process holds state; combinational process computes next state + outputs.
process (clk) begin                         -- (1) state register
    if rst = '1' then state <= IDLE;
    elsif rising_edge(clk) then state <= next_state; end if;
end process;
process (all) begin                         -- (2) next-state + output logic (combinational)
    next_state <= state;                    -- DEFAULT (avoid latch)
    out_sig    <= '0';                      -- DEFAULT (avoid latch)
    case state is
        when IDLE => if go = '1' then next_state <= RUN; end if;
        when RUN  => out_sig <= '1'; next_state <= DONE;
        when others => next_state <= IDLE;  -- SAFE-state recovery (not 'null')
    end case;
end process;

The rule set: Moore = state-only outputs (glitch-free, one cycle later); Mealy = state+input outputs (same cycle, can glitch). Encoding trades flip-flop count against next-state logic speed. The two-process style cleanly separates the state register from the next-state/output combinational logic, with defaults to avoid latches and safe-state recovery under others.

3. Production usage — registered outputs, safe states, the common bugs

-- REGISTERED OUTPUT removes Mealy glitches (cost: one cycle of latency) — a frequent interview fix:
process (clk) begin
    if rising_edge(clk) then
        out_reg <= '1' when (next_state = RUN and go = '1') else '0';   -- glitch-free, registered
    end if;
end process;
 
-- SAFE STATE: 'when others' must drive to a known state, NOT leave next_state unassigned/null:
--   when others => next_state <= IDLE;   -- recovers from an illegal/glitched encoding
 
-- COMMON FSM BUGS the interviewer plants:
--   1. MISSING DEFAULT in the combinational process -> output/next_state latches (19.3).
--   2. INCOMPLETE next-state logic -> some state has no transition -> stuck / latch.
--   3. OUTPUT IN THE WRONG PROCESS -> e.g. output meant to be registered placed combinationally (glitch),
--      or a Moore output accidentally made input-dependent (Mealy by mistake).
--   4. 'when others => null' -> no illegal-state recovery (safe-FSM failure).

What hardware does this become? Always the register-plus-two-clouds, shaped by your choices. Registering a Mealy output adds a flip-flop that removes the glitch but delays the output a cycle — the classic "how do you clean up a Mealy output?" answer. A safe state under others adds recovery logic so a flipped state bit (or unreachable one-hot code) returns to a known state. The planted bugs all map to earlier rules: a missing default infers a latch, incomplete next-state leaves a stuck/latched machine, and an output in the wrong process either glitches or silently turns Moore into Mealy. Naming the bug, the hardware, and the fix is the full answer.

4. Structural interpretation — Moore vs Mealy and encoding

5. Simulation interpretation — Mealy same-cycle vs Moore one cycle later

6. Debugging example — the FSM with a missing default (and a glitchy output)

Expected: a clean state machine with well-defined outputs. Observed: the synthesis report flags an inferred latch on next_state or an output, and/or a combinational output glitches mid-cycle, sometimes causing a downstream block to misfire. Root cause: the combinational next-state/output process is missing defaults (so an unassigned path latches, 19.3), and/or a Mealy output is left combinational where a glitch-free signal was needed. Fix: in the combinational process, default-assign next_state (to current state) and every output before the case, drive a safe state under when others, and register any output that must be glitch-free (accepting the one-cycle latency). Engineering takeaway: an FSM's combinational process must default-assign next-state and outputs (no latches) and recover illegal states under others; register Mealy outputs that feed glitch-sensitive logic — the planted bugs are almost always a missing default or a wrong-process output.

-- BUG: no defaults -> next_state/out latch on unhandled paths; no others -> no recovery.
-- FIX: defaults + safe-state recovery (+ register the output if it must be glitch-free).
process (all) begin
    next_state <= state;  out_sig <= '0';        -- defaults: no latch
    case state is
        when RUN => out_sig <= '1'; next_state <= DONE;
        when others => next_state <= IDLE;       -- safe-state recovery (not null)
    end case;
end process;

7. Common mistakes & what to watch for

• Missing defaults in the combinational process. Default-assign next_state and every output before the case, or you infer latches (19.3).
• when others => null. Provide safe-state recovery (drive to a known state) so a glitched/illegal encoding cannot stick.
• Output in the wrong process. Register outputs that must be glitch-free; do not make a Moore output input-dependent (that silently becomes Mealy).
• Wrong encoding for the target. One-hot for FPGA speed, binary for fewest flip-flops, gray for low-switching transitions — justify the choice.
• Conflating Moore and Mealy. State the difference precisely — outputs from state only vs state+inputs — and the latency/glitch trade-off.

8. Engineering insight & continuity

FSM questions reduce to one picture: a state register plus a next-state cloud and an output cloud. Moore vs Mealy reshapes the output cloud (state-only, glitch-free, +1 cycle vs state+inputs, same-cycle, can glitch); encoding reshapes the register (binary/one-hot/gray); the two-process style separates register from logic with defaults (no latch) and safe-state recovery; and registering outputs trades a cycle for glitch-freedom. Answer as rule → hardware → failure. With reset, clocking, and FSMs covered, interviews move to open-ended design problems — the next lesson, RTL Design Problems, applies all of this to build a small block under interview conditions.