Finite State Machines in VHDL

00 — Why an FSM?

What must this circuit remember?

Combinational logic produces an output from the inputs that exist now. A digital system also needs to respond to a sequence: what happened on earlier clock cycles can change what it should do next. That is sequential logic.

The state register holds that memory. At a clock edge, it loads the next state calculated from the current state and inputs. Reset places it in a known starting state.

01 — Example 1 · divideby3FSM

Three states make a repeating pulse

Start with the smallest possible transition problem: there is no data input. Every rising edge advances one place around a three-state cycle. Reset selects S0.

Read each row as an edge-to-edge rule. In S1, for instance, y is low now and the next rising edge loads S2.

type statetype is (S0, S1, S2);
signal state, nextstate: statetype;

statetype defines three symbolic values. state is the value held in the register; nextstate is the value waiting to be loaded.

process(clk, reset) begin
  if reset = '1' then state <= S0;
  elsif rising_edge(clk) then
    state <= nextstate;
  end if;
end process;

nextstate <= S1 when state = S0 else
             S2 when state = S1 else
             S0;

y <= '1' when state = S0 else '0';

The code follows the same three objects as the diagram and table: the register stores the state, the transition expression selects the next one, and the output expression marks S0 with a high pulse.

Read the timing at rising edges

Starting from reset in S0, each rising edge loads the next state. The output is high only while S0 is held:

Keep the three views together: the state diagram shows the loop, the table lists each transition, and the VHDL implements exactly those rows.

02 — Reusable implementation structure

Find the three pieces in every FSM

The next two designs add an input, but keep the same architecture. When reading FSM VHDL, identify these parts before following individual conditions.

03 — Example 2 · patternMoore

Detect 01 by remembering a useful prefix

Now a serial input a supplies one bit per clock. We want a pulse when the most recently sampled two bits are 01. Before looking at VHDL, ask: What does the circuit need to remember about the previous input bits? After a 0, it needs to remember that a 1 next would complete the pattern.

Start at S0, with no useful trailing zero. A sampled 0 moves to S1. In S1, another 0 keeps the same useful memory, while a sampled 1 completes 01 and moves to S2. The remaining arrows prepare for the next match.

In S1, another 0 keeps a useful trailing zero. A 1 takes the machine to S2, where the Moore output is high. From S2, a new 0 starts the next possible match. Thus 0101 produces two detections; no bit must be discarded between them.

type statetype is (S0, S1, S2);
signal state, nextstate: statetype;

process(clk, reset) begin
  if reset = '1' then         state <= S0;
  elsif rising_edge(clk) then state <= nextstate;
end process;

process(all) begin
  case state is
    when S0 =>
      if a = '1' then nextstate <= S0;
      else      nextstate <= S1;
      end if;
    when S1 =>
      if a = '1' then nextstate <= S2;
      else      nextstate <= S1;
      end if;
    when S2 =>
      if a = '1' then nextstate <= S0;
      else      nextstate <= S1;
      end if;
    when others => nextstate <= S0;
  end case;
end process;

y <= '1' when state = S2 else '0';

The output expression mentions state only. If a changes while the state stays S1, y remains low. The detecting 1 must be sampled at a rising edge to enter S2; then y goes high after the state updates.

Trace four sampled bits from reset. Each row shows the state and Moore output after the edge:

04 — Example 3 · patternMealy

Detect the same 01 with the input on the output path

Can we recognize the same event without creating a dedicated detection state? The Mealy design needs only two states. S0 means there is no useful trailing zero; S1 means the last sampled bit was zero. When the circuit is in S1 and a is currently 1, the pattern is present at the input and y asserts directly.

For a Mealy diagram, label an edge with input/output. The detecting transition is S1 — 1/1 → S0. The output belongs to the transition condition, not to a separate detected state.

type statetype is (S0, S1);
signal state, nextstate: statetype;

process(all) begin
  case state is
    when S0 =>
      if a = '1' then nextstate <= S0;
      else      nextstate <= S1;
      end if;
    when S1 =>
      if a = '1' then nextstate <= S0;
      else      nextstate <= S1;
      end if;
    when others => nextstate <= S0;
  end case;
end process;

y <= '1' when (a = '1' and state = S1) else '0';

Its state register is the same clocked pattern as the Moore design: reset sets S0, and each rising edge loads nextstate. The key difference is visible in the output expression: a appears beside state.

For 0, 1, 0, 1, observe the Mealy output just before each sampling edge, while the old state still holds:

05 — Put the detectors side by side

Same pattern, different output timing

Neither architecture is universally preferable. The Mealy version saves a state and can respond earlier; the Moore version keeps the output independent of direct input changes. Choose according to the interface and timing your system needs.

For a stable input sequence 0, 1, 0, 1, both machines recognize two 01 occurrences. The table below names exactly which side of each edge is being observed.

The matching values in different columns are not simultaneous output waveforms: the Mealy assertion occurs before the detecting edge; the Moore assertion follows that edge.

06 — Check your understanding

Predict before you simulate

07 — Design method

A repeatable way to design an FSM

Work from required behavior toward code. Each step should agree with the diagram and table before simulation.

1. Understand the required behavior.
2. Identify what the circuit must remember from the past.
3. Define states for that information.
4. Draw the state diagram.
5. Build the transition table.
6. Choose Moore or Mealy outputs.
7. Write the clocked state register.
8. Write the combinational next-state logic.
9. Write the output logic.
10. Simulate and verify reset, transitions, output timing, and overlaps.

08 — Week summary

State is the useful part of the past

The original source files remain available: divide-by-3, Moore detector, and Mealy detector. Use the linked teaching copies above when compiling with VHDL-2008.

Back to EE 322 →