BitFlow
← Academy·Finite State Machines
◎GATE~45 min

Finite State Machines

Moore and Mealy machines, the design recipe from words to gates, sequence detectors and state reduction.

Interactive·FSM State Explorer

A simple Moore memory-controller FSM. Press valid inputs to walk the state diagram — invalid inputs are rejected.

IDLEREADWRITEDONE

Current state: IDLE

Inputs

FSM reset → IDLE

What a state machine is

A counter steps through a fixed sequence. A finite state machine (FSM) chooses its next step based on inputs, which makes it the control logic of nearly every digital system: vending machines, traffic lights, communication protocols and the control unit of a processor.

Every FSM has three parts: state registers remembering where it is, next-state logic deciding where to go, and output logic. The state tells you what the machine needs to remember about the past, and nothing more.

Moore and Mealy

The two kinds of FSM differ only in where outputs come from.

MooreMealy
Outputs depend onState onlyState and current inputs
In the diagramWritten in the circleWritten on the arrow
States neededOften moreOften fewer
Output timingChanges just after the clock edgeCan change as soon as an input does
RiskOutput is a cycle laterInput glitches reach the output

Loading the animation…

TipOverlap matters when detecting sequences. After 1 0 1, the last 1 can start the next match, so the machine returns to S1, not S0. Try feeding 1 0 1 0 1.
Practice

How many states does a Moore machine need at minimum to detect a 4-bit pattern like 1011?

From words to gates

Every FSM design follows the same six steps. Here's a small one from start to finish: output 1 once the input has been 1 for two clocks in a row, and stay 1 until it goes 0.

  1. Draw the state diagram. S0: no 1s yet. S1: one 1. S2: two or more, where the output is 1.
  2. Write the state table. Any 0 goes back to S0. A 1 moves S0 to S1, S1 to S2, and S2 stays.
  3. Reduce the states, if any are equivalent. These aren't.
  4. Encode them. Using 2 flip-flops: S0 = 00, S1 = 01, S2 = 10. Pattern 11 is unused, so it's a don't-care.
  5. Find the next-state equations with K-maps.
  6. Find the outputs and draw the circuit.
Nowq1 q0x = 0: nextx = 1: nextOutput y
S00 00 00 10
S10 10 01 00
S21 00 01 01
q1q0x00011110010010312040517X6Xq0·xq1·x
Grouping

D1 = q0·x + q1·x

D1 is 1 when going to S2. Don't-cares for the unused 11 make it short.
q1q0x00011110010011302040507X6Xq1'·q0'·x
Grouping

D0 = q1'·q0'·x

D0 is 1 only when going from S0 to S1.
D1 = x(q1 + q0) D0 = x q1' q0' y = q1

Loading the circuit…

The finished machine: exactly those equations, in slow motion. Set x, then press Clock edge.
  • Set x = 1 and clock twice. y comes on at the second edge and stays on.
  • Set x = 0 and clock once. y goes off.
  • Set x = 1, clock once, set x = 0, clock again. y never came on, because the 1s weren't in a row.
Open the FSM designer →Draw a state diagram, run it on an input sequence, minimise it, and generate Verilog.Challenge: 101 sequence detector →Follow the six steps for the machine in the animation above, in the circuit editor.

Encoding the states

Which pattern each state gets doesn't change what the machine does, but it does change how big and fast the logic is.

EncodingFlip-flops for N statesGood for
Binary⌈log₂ N⌉Fewest flip-flops, typical in ASICs
One-hotNSimple, fast logic, typical in FPGAs
Gray⌈log₂ N⌉Sequences where only one bit should change per step
Practice

A machine has 9 states. How many flip-flops does it need in binary encoding, and in one-hot?

Removing redundant states

Two states are equivalent if they give the same outputs for every possible input sequence, so one can replace the other. You don't have to try every sequence. Use partition refinement: start by grouping by output, and split groups until they stop splitting.

Loading the animation…

NoteReducing states doesn't always cut flip-flops. Going from 7 states to 4 here does (3 to 2), but going from 8 to 5 wouldn't (both need 3). It may still simplify the logic.

FSMs in Verilog

The standard style splits an FSM into three parts: the state register, the next-state logic and the output logic. It reads directly from a state table, and the synthesis tool chooses the encoding if you let it.

localparam S0 = 2'd0, S1 = 2'd1, S2 = 2'd2;
reg [1:0] state, next;

always @(posedge clk or posedge rst)      // state register
  if (rst) state <= S0;
  else     state <= next;

always @(*) begin                         // next-state logic
  next = S0;                              // default: no latches
  case (state)
    S0: if (x) next = S1;
    S1: if (x) next = S2;
    S2: if (x) next = S2;
  endcase
end

assign y = (state == S2);                 // Moore output
The chapter's machine in Verilog. The default assignment matters: leaving next unset on any path would create an unwanted latch.

Loading the animation…

Challenge: traffic light →A classic FSM that also has timing. Build it in the circuit editor, and earn XP.

Exam pointsGATE: fine to skip at first

Converting between the two kinds is routine. To go from Moore to Mealy, move each state's output onto the arrows that enter it. To go from Mealy to Moore, split any state that's entered with different outputs. So the Moore form has at most (states × outputs) states.

Practice · GATE-style

How many flip-flops does a machine with 17 states need in binary encoding?

Practice · GATE-style

A Mealy detector for a pattern of length n, with overlaps, needs how many states?

Practice · GATE-style

How many states does the machine in the animation reduce to?

Practice · GATE-style

Which is true of a Moore machine?

Was this chapter helpful?