Synchronous State Machine Design

A finite state machine (FSM) is the standard way to describe any piece of control logic whose behavior depends on history — not just on the inputs present right now, but on the sequence of inputs that led here. A traffic-light controller, a UART receiver, a bus arbiter and a sequence detector are all the same kind of object underneath: a small amount of memory (the current state) plus two pieces of combinational logic that decide what happens next. This lesson is about the design method that gets a designer from a written specification to that structure, before any Verilog is typed. The Verilog path's finite state machines lesson covers the coding style for an FSM once the design is settled — this lesson is about everything that has to be decided first.

Reading time: about 11 minutes.

5.1 The five-stage design flow

Every synchronous FSM design, regardless of its size, goes through the same five stages, in the same order. Skipping a stage does not save time; it only moves the decisions that stage would have made into the Verilog itself, where they are harder to see and harder to review.

1. State diagram. A graph of circles (states) and labeled arrows (transitions), drawn directly from the specification's description of behavior.
2. State table. The same information as the diagram, written as rows: current state, input, next state, output — a format a reviewer can check mechanically, row by row, against the specification.
3. State encoding. Assigning a concrete bit pattern to each named state. This lesson uses the simplest possible choice — plain binary, in the order states were named — and leaves the real comparison of encodings to the next lesson.
4. Next-state and output equations. Boolean expressions for each bit of the next state and each output bit, derived from the encoded state table exactly the way lesson 3 of the Digital Electronics path (Karnaugh maps) derived any other combinational function from a truth table — by inspection for a table this small, or by Karnaugh map for anything larger.
5. RTL. The three-process Verilog template from the Verilog path's finite-state-machines lesson: a clocked state register, a combinational next-state block, and a combinational output block.

Thus, writing Verilog is the last step of FSM design, not the first. A designer who opens an editor and starts typing always blocks before stage 1 exists is making the first four decisions implicitly, inside the fifth — which is exactly how an FSM ends up with an unreachable state, a missing transition, or an output that glitches for reasons nobody can explain from the code alone.

5.2 Worked specification: detecting "1101"

Let us work a complete example through all five stages. The specification: build a circuit that watches a single serial bit stream, one bit per clock cycle, and flags every occurrence of the pattern 1101, including occurrences that overlap each other (so the bit stream 1101101 should flag two matches, one ending at the fourth bit and one ending at the seventh, sharing the middle 1).

The state needed at any point is exactly "the longest suffix of the bits seen so far that is also a prefix of 1101" — this is the standard way to think about any overlap-detecting sequence recognizer, and it is what each state below represents.

Each row is checked against the specification independently of the others: from S2 ("11" matched so far), an incoming 1 extends the run of 1s, so the longest matching prefix of the new three-bit suffix "111" is still "11" — the machine stays in S2, not S1, because "11" is a longer valid prefix than "1". From S3 ("110" matched), an incoming 1 completes the pattern, moving to S4. The output is simplest to state as a Moore output: match = 1 exactly when the machine is in S4, and 0 otherwise.

5.3 Encoding and equations

With five states, three bits are needed (2^2 = 4 < 5 \le 2^3 = 8). Binary assignment in declaration order gives S0=000, S1=001, S2=010, S3=011, S4=100. The next-state equations follow directly from the table by the same inspection or Karnaugh-map process used for any combinational function — three unused codes (101, 110, 111) are don't-cares for minimization, but, per lesson 2's discussion of don't-cares, they still need a defined next state in the RTL, because real hardware can land in an unused encoding through an unexpected reset state or a soft error, even if the design never puts it there on purpose.

This lesson does not carry the algebra further than this, because the point being made is about the flow, not about Boolean minimization — that groundwork was laid in the Digital Electronics path's Karnaugh-map lesson, and lesson 6 of this path picks the encoding question back up, measuring binary against one-hot on a synthesized example and describing what Gray-coded assignment is for.

5.4 Moore versus Mealy: two correct answers

A Moore machine's output depends only on the current state; a Mealy machine's output depends on the current state and the current input. Both are completely standard, both get used constantly in real designs, and the state table above describes a Moore machine. A Mealy machine for the identical specification needs one fewer state: instead of a dedicated S4 whose only job is to mean "match," the transition out of S3 on input 1 can go straight to S1 — because S4's own outgoing transitions (0 to S0, 1 to S2) turn out to be identical to S1's — with the output asserted on that transition itself rather than on arrival in a dedicated state. In the Moore machine S4 and S1 are not equivalent, because S4's output is 1 and S1's is 0; moving the output onto the transition removes the only difference between them, which is exactly why the Mealy version can merge them. Lesson 6 turns this comparison (same outputs and same next states) into a systematic method rather than something spotted by inspection.

The practical difference between the two is timing, not correctness, and it is worth seeing in simulation rather than taking on faith. For the three-process coding style that turns either table into working Verilog — the clocked state register, the combinational next-state block and the combinational output block — see the Verilog path's finite state machines lesson; that lesson is not repeated here.

5.5 Verified in simulation

Both machines were coded to the three-process template and driven with the bit stream 11011010 (the overlapping 1101101 plus one trailing bit, so the Moore output's second assertion is observed) through Icarus Verilog. Each bit is applied on a falling clock edge, and both outputs are sampled twice per bit period: EARLY, 2 ns after the bit is applied and before the next rising edge, and LATE, 1 ns after that rising edge, once the state register has clocked the bit in. The testbench checks Mealy at every EARLY point and Moore at every EARLY and LATE point.

always @* begin
    case (state)
        S0: next_state = bit_in ? S1 : S0;
        S1: next_state = bit_in ? S2 : S0;
        S2: next_state = bit_in ? S2 : S3;
        S3: next_state = bit_in ? S1 : S0;
        default: next_state = S0;
    endcase
end

always @* begin
    match = (state == S3) && bit_in;   // Mealy: reads bit_in directly
end

i=3 bit=1 EARLY  moore=0 mealy=1
i=3 bit=1 LATE   moore=1 mealy=0
i=4 bit=1 EARLY  moore=1 mealy=0
i=4 bit=1 LATE   moore=0 mealy=0
i=5 bit=0 EARLY  moore=0 mealy=0
i=5 bit=0 LATE   moore=0 mealy=0
i=6 bit=1 EARLY  moore=0 mealy=1
i=6 bit=1 LATE   moore=1 mealy=0
i=7 bit=0 EARLY  moore=1 mealy=0
i=7 bit=0 LATE   moore=0 mealy=0
SELF-CHECK PASSED

At bit index 3 — the bit that completes the first occurrence of 1101 — the Mealy machine's match is already 1, because it is a combinational function of the state the machine was in before this bit arrived, plus this bit itself. The Moore machine's match is still 0 at that same point; it reads 1 only after the rising edge clocks the machine into S4 (the LATE sample at index 3) and stays 1 through the EARLY sample of index 4. By then the Mealy output has already dropped back to 0, because the same edge moved the Mealy machine from S3 to S1. Thus, a Mealy output responds within the same cycle the triggering input arrives, while a Moore output always lags by one clock cycle, because it can only change after the state register has clocked into the state that produces it. Both machines detected both matches, including the second, overlapping one completed at index 6, and in each case the Moore output asserted one clock cycle after the Mealy output. Yosys's synthesis and check pass reported zero problems and no inferred latches for either module — confirming both case statements are complete and both designs are purely combinational next-state and output logic driving a clean set of flip-flops.

5.6 Interview questions

What are the five stages of FSM design, in order? State diagram, state table, state encoding, next-state and output equations, then RTL. Each stage's output is the mechanical input to the next one, which is what makes the result reviewable at every step instead of only once the Verilog compiles.

Why does a Mealy implementation of a given specification often need fewer states than the equivalent Moore implementation? A Moore machine sometimes needs a dedicated state purely to hold an output value steady for a full cycle. A Mealy machine can assert that same output on a transition instead, which can let a state whose only purpose was "remember that we just matched" collapse into an existing, behaviorally identical state — exactly what happened to S4 above, which turned out to behave identically to S1.

If a Moore and a Mealy machine implement the identical specification and are driven by the identical input stream, do their outputs ever disagree? Not on the pattern being detected — both must flag the same event — but they disagree on timing. The Mealy output appears the same cycle the deciding input bit is applied; the Moore output for the same event appears one clock cycle later, once the state register has moved into the state that represents the match.

Why does an FSM's next-state logic need a default branch even for unused state encodings? A state register's bit width is often wider than the number of states actually used — three states here go unused out of eight possible 3-bit codes — and real hardware can still land in one of those codes through an unexpected power-on value or a transient upset, not just through a coding mistake. An FSM without a defined transition out of every reachable code either infers an unintended latch or leaves its recovery behavior undefined. A default branch alone does not guarantee recovery in silicon, however: synthesis FSM extraction can remove unreachable states and re-encode the machine, optimizing the recovery path away. Guaranteed recovery needs the tool's safe-FSM option or attribute, or FSM re-encoding disabled for that machine.

Does state encoding change what an FSM does? No — encoding is purely an implementation choice about which bit pattern represents which named state, and it never changes which states exist, which transitions connect them, or what the outputs are. It does change the resulting gate count and timing, which is exactly what the next lesson measures.