Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 37 ยท Finite State Machines

Finite State Machines: Moore and Mealy

Learn what a finite state machine is, how Moore and Mealy machines differ, how to draw state diagrams and how the idea maps onto VHDL registers and logic.

A finite state machine (FSM) is the standard way to describe hardware that follows a sequence: a traffic light, a vending machine, a protocol decoder, a memory controller. The machine is always in exactly one of a small, fixed number of states. On every clock edge it looks at its inputs and moves to the next state. Its outputs depend on the state, and sometimes on the inputs as well.

Real VHDL tools and FPGA boards are not available on this site, so VHDL code here is shown read-only. To let you experiment, each lesson also gives runnable C stand-ins: small programs that model the same ideas (a state register, next-state logic, output logic) so you can watch the behavior step by step. The stand-ins are not VHDL and run on a normal CPU, not on hardware.

The three parts of every FSM

Every synchronous FSM has the same three blocks:

  1. State register: flip-flops that hold the current state and update on the clock edge.
  2. Next-state logic: combinational logic that computes the next state from the current state and the inputs.
  3. Output logic: combinational logic that computes the outputs.
flowchart LR
  I["inputs"] --> NS["next-state logic"]
  S["state register<br/>(flip-flops)"] --> NS
  NS --> S
  S --> OL["output logic"]
  I -.->|"Mealy only"| OL
  OL --> O["outputs"]

The dotted arrow is the only difference between Moore and Mealy.

Moore machines

In a Moore machine the outputs depend only on the current state. Outputs change only after a clock edge, because the state only changes on a clock edge. Moore outputs are glitch-free in practice (they come straight from the state) and easy to reason about, but they can need more states and react to an input one clock later.

Mealy machines

In a Mealy machine the outputs depend on the current state and the current inputs. An input change can change an output immediately, without waiting for the clock. Mealy machines often need fewer states, but the outputs inherit any glitches from the inputs, and a long input-to-output path can hurt timing.

Property Moore Mealy
Output depends on state state and inputs
Reaction to input after the next clock edge immediately (combinational path)
Number of states usually more usually fewer
Glitches on outputs rare possible
Good for safe control signals fast reactions

A turnstile as a state diagram

A turnstile has two states, locked and unlocked. Inserting a coin unlocks it. Pushing through locks it again. Pushing while locked does nothing; a coin while unlocked is wasted.

flowchart LR
  L(["locked"]) -->|"coin"| U(["unlocked"])
  L -->|"push"| L
  U -->|"push"| L
  U -->|"coin"| U

Moore version: the output "gate open" is 1 in state unlocked and 0 in state locked.

The following C program models this machine. The state is one variable, the next-state logic is a switch, and the loop body is one "clock edge". It shows both a Moore output (function of state only) and a Mealy output (a "beep" when a coin arrives while already unlocked).

C C stand-in: a turnstile as Moore and Mealy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Notice that the beep appears in the same row as the second coin, before the state changes, while the gate output always lags the input by one edge.

Converting between the two

Any Mealy machine can be turned into a Moore machine, usually by adding states that remember "the output I should show next". Any Moore machine is already a special Mealy machine. Choose by requirement:

  • Need an output to react in the same cycle as an input? Mealy.
  • Need clean, registered outputs for another module or a pin? Moore, or a Mealy with registered outputs.

A good habit is to register outputs when they leave the chip or cross to another clock-sensitive block. We will see how in the next lessons.

Mapping to VHDL

In VHDL, the states become an enumeration type, the state register becomes a clocked process, and the next-state logic and output logic become either one or two more processes or concurrent statements. The next lesson shows the standard structure. Here is a preview of the types only (read-only):

VHDL
type state_t is (LOCKED, UNLOCKED);
signal state, next_state : state_t;

An enumeration lets the synthesis tool choose the encoding of each state and lets the simulator print readable names in the waveform.

Designing an FSM, step by step

  1. Write the requirements as a list of "when X happens in situation Y, do Z".
  2. List the situations: these are the states. Name them with verbs or conditions (wait_coin, dispense).
  3. Draw the diagram with every state and every transition. Check that each state has an outgoing transition for every input combination.
  4. Decide Moore or Mealy for each output.
  5. Write the VHDL and a testbench that walks every transition.

A missing transition is the most common FSM bug. Write down the rule "unmentioned input = stay in the same state" and make it explicit in your code.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What makes a machine a Moore machine?

    In a Moore machine the output logic sees only the state register, so outputs change only after a clock edge.
  2. 2. Which part of an FSM holds the memory?

    The state register is a bank of flip-flops that stores the current state between clock edges. The other blocks are combinational.
  3. 3. A Mealy machine reacts to an input change

    Mealy outputs include the inputs in their logic, so an input change can change an output before the next clock edge.
  4. 4. Why is an enumeration type a good fit for FSM states in VHDL?

    Enumerations are readable in code and in waveforms, and synthesis tools can re-encode them (binary, one-hot, and so on).

Summary

  • An FSM = state register + next-state logic + output logic.
  • Moore outputs depend on state only; Mealy outputs depend on state and inputs.
  • Mealy machines need fewer states and react faster; Moore outputs are cleaner.
  • Draw a diagram first and make sure every state handles every input.
  • VHDL states are an enumeration type; the register is a clocked process.
  • C programs here only model the behavior; VHDL is shown read-only.

Next: The Two-Process FSM Style