EN

State machines (Moore and Mealy)

From the state diagram to the table and the flip-flop equations, with a sequence detector

Sequence detector designer

Machine

State diagram

Each arrow carries the value of input x that causes it; in Mealy, also the output it produces ("input/output"). In Moore the output is inside the state, and the double-circled states are the ones that give z = 1.

State table

Equations with D flip-flops

Simulation

Input

What a state machine is

A finite state machine is a sequential circuit that is, at any moment, in one of a limited number of states. The state sums up everything that matters about the past. On each clock edge it moves to a new state that depends on the current state and the inputs. It is built from a register of flip-flops, which holds the state, and two blocks of combinational logic: one computes the next state and the other the outputs.

It is the orderly way to design any automated sequence: a traffic light, the control of an automatic door, a vending machine, the protocol of a serial port or the stages of a washing cycle. In a PLC it is programmed the same way with GRAFCET or with steps in ladder, and in a microcontroller with a switch on a state variable.

Moore and Mealy

MooreMealy
The output depends onThe state onlyThe state and the inputs
Where the output is drawnInside each stateOn each arrow, "input/output"
Number of statesUsually needs a few moreUsually needs fewer
ResponseThe output changes on the next clock edgeThe output changes as soon as the input changes
OutputStable for the whole cycle, no glitchesCan glitch if the input does

Compare both types in the simulator with the same sequence: the Mealy detector gives z = 1 in the same cycle as the last bit arrives, and the Moore one a cycle later, once it has entered the final state. If the output of a Mealy machine feeds another synchronous circuit, that delay appears anyway when it is registered.

Design steps

  1. State diagram. Describe the behaviour: which states exist, which one is reached with each input and which output is produced. In a sequence detector, each state means "I have received the first k bits of the sequence".
  2. State table. The same as the diagram, as a table: current state and input on the left, next state and output on the right.
  3. Encoding. Assign a binary code to each state. With S states, ⌈log₂ S⌉ flip-flops are needed. Binary encoding uses the minimum number of flip-flops; one-hot encoding (one flip-flop per state) uses more flip-flops but greatly simplifies the equations, and is common in FPGAs.
  4. Equations. With D flip-flops, the D input of each one is directly the corresponding bit of the next state. Unused codes are don't-cares and help simplify in the Karnaugh map. With JK flip-flops the excitation table is used instead of copying the next state.
  5. Unused states. Check where the machine goes if it starts in an unused code, through noise or at power-up, and provide a reset that takes it to the initial state.

Overlapping

With overlapping, the last bits of a detected sequence can be the start of the next one: looking for 1011 in 1011011, it is detected twice. Without overlapping, after each detection the machine starts over and finds only one. To decide which state to return to when a bit arrives that does not fit, look for the longest part of what was received that matches the beginning of the sequence; it is the same idea used by the KMP text search algorithm.

Example: a traffic light

A traffic light for cars with a pedestrian button is a Moore machine: the lights depend only on the state. A timer gives the "time elapsed" signal and the button press is latched until it is served.

StateCar lightsPedestrian lightsMoves on when
S0 GreenGreenRedA pedestrian has pressed and the minimum green time has elapsed
S1 AmberAmberRedAmber time elapsed
S2 RedRedGreenPedestrian crossing time elapsed
S3 ClearanceRedFlashing greenClearance time elapsed; back to S0

Four states are encoded with two flip-flops. The outputs are functions of Q1 and Q0, for example car green = Q1'·Q0' and pedestrian red = Q1'.

Related: latches and flip-flops, Karnaugh map, logic gate simulator and ladder simulator.