State Machines Interview Questions

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.

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.

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.

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.

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.

Binary uses the fewest flops, about log2 of the state count, but needs decoding. One-hot uses one flop per state, so testing a state reads one bit. Gray changes one bit per step, which suits machines that move in a fixed sequence. The real answer comes from measuring, because it depends on the machine and the tool. Check the flop count in the report: synthesis tools may re-encode your FSM.

Each arm tests one state bit, not the whole 5-bit vector. So "am I in RUN?" is one wire, and each next-state bit is a small OR of a few terms. On this flow it is 13 cells and 3 levels, against 27 and 5 for full-vector compares. The coding has to use the one-hot property for the encoding to save logic.

Look at the flop count and the FSM section of the synthesis log. Here the binary machine came out with 5 flops: Yosys re-encoded it one-hot. That is often fine for speed. It matters when other logic reads the state code or the code crosses a clock domain. It also matters when recovery logic depends on it.

Then the reader may see a code that changes several bits at once, so it can sample a mix of two states. First, do not cross the state register at all. Cross a one-bit status through a synchronizer, or use a handshake. If you must keep the code, tell the tool not to re-encode it, and check the log after every run.

Pick Gray when the machine walks a fixed loop, like a counter, and you want one bit to change per step. Each step then toggles one flop instead of two. It also matters if the state is read in another clock domain, because a Gray step is never a torn value. One-hot is usually better for speed in a branching machine.

First look for hidden counters: chains of states that only count cycles. Replace them with one counter and one waiting state. Then split the rest into a main machine and small sub-machines that talk through start and done signals. Each piece gets fewer states, smaller next-state logic, and its own tests.

The enum names five codes, but three bits hold eight. The upset wrote 110, which has no arm. The block starts with st_d = st_q, so the machine holds 110 forever. Add a default arm that goes back to IDLE. Then check synthesis kept it, because a tool that re-encodes the FSM can drop arms for unreachable codes.

The register is just N flops, so it can hold 2^N codes. The enum gives names to only the codes you use: five of eight here. The hardware does not know which codes have names. Only your next-state logic decides what happens in the other three.

Yes, you need both. The default arm says what unnamed codes must do. Keeping the encoding makes sure the netlist still contains those codes and that arm. On this flow, the default alone was dropped by re-encoding, and the attribute alone kept a machine with no way out. Other tools offer a "safe FSM" option for the same job.

Check the netlist, not the RTL. Simulate the gates, force each unnamed code into the state flops, and check the machine reaches IDLE within a few cycles. Read the FSM section of the synthesis log and the flop count too. They show whether the machine was extracted and re-encoded.

Every machine must leave any illegal code in a bounded number of cycles, to a known safe state. It should also flag the event, so the system knows something went wrong. Prove the recovery on the netlist, not the RTL: check the encoding was kept and run upset tests at gate level. A formal check that every code reaches IDLE covers all codes at once.