16.3 State machines: Mealy and Moore models

State Machine Models

Finite State Machines and Sequential Circuits

A finite state machine (FSM) models a system that can only be in one of a limited number of states at any given time. FSMs are the foundation for designing sequential circuits, where the circuit has memory and its behavior depends on what happened before, not just what's happening right now.

In a synchronous sequential circuit, state transitions happen on the rising or falling edge of a clock signal. This keeps everything predictable: the circuit only changes state at well-defined moments, which makes the design much easier to reason about and debug.

Mealy and Moore Machines

These are the two main FSM models, and the difference comes down to one question: what determines the output?

• A Mealy machine produces outputs based on both the current state and the current input.
  • Output = $f(\text{state}, \text{input})$
  • Because the input affects the output directly, a Mealy machine can produce different outputs while sitting in the same state, depending on what input it sees. This means more output combinations are possible with fewer states.
• A Moore machine produces outputs based only on the current state.
  • Output = $f(\text{state})$
  • The output stays the same for a given state no matter what the input is. This makes the output logic simpler and more predictable, but you typically need more states to achieve the same behavior as a Mealy machine.

State Representation

State Diagrams and Tables

A state diagram is a graphical way to visualize an FSM. States are drawn as circles (or rectangles), and arrows between them represent transitions. The key difference in how you label them:

• Mealy diagrams: Each arrow is labeled with the input and the output (often written as input/output on the transition arrow).
• Moore diagrams: Each state circle is labeled with its output, and the arrows only show the input condition that triggers the transition.

A state table captures the same information in tabular form. Each row represents a combination of current state and input, and the columns show the resulting next state and output. State tables are especially useful when you're ready to move from a diagram to actual logic design, since they map directly to truth tables for your combinational logic.

State Registers and Encoding

The state register is a group of flip-flops that holds the current state of the FSM. The number of flip-flops you need depends on how many states you have: $n$ flip-flops can represent up to $2^n$ states.

How you assign binary codes to your states matters. Common encoding schemes:

• Binary encoding: Uses the minimum number of flip-flops (e.g., 3 flip-flops for up to 8 states). Compact, but the next-state logic can get complex.
• One-hot encoding: Uses one flip-flop per state (e.g., 8 flip-flops for 8 states). More flip-flops, but the next-state and output logic is often much simpler and faster.
• Gray coding: Adjacent states differ by only one bit, which reduces the chance of glitches during transitions.

State Machine Components

Next State and Output Logic

An FSM has two blocks of combinational logic working alongside the state register:

1. Next state logic takes the current state (from the state register) and the current input, then computes which state the machine should move to next. This is built from standard combinational components like gates and multiplexers. Its output feeds into the state register inputs so the state updates on the next clock edge.

2. Output logic generates the FSM's outputs.

   • In a Moore machine, this logic reads only the state register.
   • In a Mealy machine, this logic reads both the state register and the current input.

The outputs can drive external pins, LEDs, control signals for a datapath, or feed into other parts of your circuit.

State Transitions and Timing

A transition is the change from one state to another. In synchronous FSMs, transitions happen only at the active clock edge (rising or falling, depending on your design). Between clock edges, the next-state logic computes the upcoming state, but the state register doesn't actually update until the edge arrives.

Timing is critical. The clock period must be long enough for two things to happen before the next edge:

1. The next-state logic settles to a stable value.
2. The setup time requirement of the flip-flops is satisfied.

If the clock is too fast, the flip-flops may latch incorrect values, leading to setup time violations. Similarly, inputs that change too close to the clock edge can cause hold time violations. For complex designs, techniques like pipelining (breaking logic into shorter stages) and retiming (redistributing flip-flops across combinational logic) help meet timing requirements while maintaining high clock speeds.