The counters of the last two chapters walk through their states in a fixed order, with no inputs except the clock. Most real circuits are more interesting: a traffic light reacts to a car sensor, a vending machine reacts to coins, a serial receiver reacts to incoming bits, and a CPU's control unit reacts to the instruction it is decoding. All of these are finite state machines (FSMs): circuits that remember "where they are" in a small number of states, and decide what to do next from that state and the current input.
In this chapter we define FSMs precisely, meet the two standard models (Moore and Mealy), learn to analyse a given sequential circuit, learn to design one from a word description, convert between the two models, and reduce the number of states. The next chapter, Sequence Detector Design, applies all of this to the most common exam problem.
What Is a Finite State Machine?
Finite state machine (FSM): a sequential circuit with a finite set of states. On each active clock edge it moves from its present state to a next state determined by the present state and the inputs, and it produces outputs determined by the present state (and, in one model, the inputs).
Formally, a synchronous FSM is a 6-tuple (S, I, O, δ, λ, s0):
S: finite set of states; s0 ∈ S: the reset (initial) state.
I: set of input values; O: set of output values.
δ : S × I → S: the next-state function.
λ: the output function. Its form is the only difference between the two models below.
Every FSM in hardware has the same three parts:
+------------------+ +----------------+
inputs ───┬────►| next-state logic |──D───►| state register |──┬──► present state
│ ┌─►| δ | | (flip-flops) | │
│ │ +------------------+ +-------▲--------+ │
│ │ │ CLK │
│ └─────────── present state ───────────┼───────────┤
│ │
│ +------------------+ │
└ ─ ─►| output logic |◄──────────────────────────┘
| λ |──────► outputs
+------------------+
─ ─ ► : the input-to-output path exists only in a MEALY machine
A counter is the special case with no inputs, where the outputs are just the state bits.
Moore and Mealy Machines
Moore machine: the outputs depend only on the present state: λ : S → O. Outputs are written inside the state circles.
Mealy machine: the outputs depend on the present state and the present inputs: λ : S × I → O. Outputs are written on the transition arrows, as input/output.
An everyday picture: a Moore machine is a traffic light. Whatever happens, the colour shown depends only on which phase it is in. A Mealy machine is a ticket gate that opens the moment a valid card is tapped: the output reacts to the input right away, without waiting for a clock edge.
Running Example: A Rising-Edge Detector
Specification. Input x is a slowly changing signal (for example a push button that has already been debounced). Output z must be 1 for exactly one clock cycle each time x changes from 0 to 1.
Moore Version
The output must be 1 for one whole state, so we need a state that means "an edge just happened":
ZERO (z = 0): x was 0 last time.
EDGE (z = 1): x has just become 1.
ONE (z = 0): x has been 1 for more than one cycle.
x=0 x=1
┌───┐ ┌───┐
│ ▼ x=1 │ ▼
+---------+ ─────────► +---------+ x=1 +---------+
| ZERO | | EDGE | ─────► | ONE |
| z = 0 | ◄───────── | z = 1 | | z = 0 |
+---------+ x=0 +---------+ +---------+
▲ │
└──────────────────── x=0 ────────────────┘
State table (Moore: one output column, beside the present state):
| Present state | Next (x = 0) | Next (x = 1) | Output z |
|---|---|---|---|
| ZERO | ZERO | EDGE | 0 |
| EDGE | ZERO | ONE | 1 |
| ONE | ZERO | ONE | 0 |
Mealy Version
In a Mealy machine the output can look at x directly. We only need to remember the previous value of x:
S0: the last sampled x was 0.
S1: the last sampled x was 1.
0/0 1/0
┌───┐ ┌───┐
│ ▼ 1/1 │ ▼
+------+ ───────────────► +------+
| S0 | | S1 |
+------+ ◄─────────────── +------+
0/0
label on an arrow = input x / output z
| Present state | x = 0: next, z | x = 1: next, z |
|---|---|---|
| S0 | S0, 0 | S1, 1 |
| S1 | S0, 0 | S1, 0 |
The Mealy machine needs 2 states (1 flip-flop) where the Moore machine needs 3 states (2 flip-flops). This is typical: a Mealy machine usually needs the same number of states or fewer, because the output can be "attached" to a transition instead of needing a state of its own.
Implementing Both: The Design Steps
The design procedure is the one from Synchronous Counters, with inputs and outputs added:
Draw the state diagram from the specification.
Write the state table; reduce states if possible (see below).
Assign a binary code to each state (state assignment).
Choose flip-flops, derive their input equations from the excitation table, simplify with K-maps.
Derive the output equations.
Check unused codes, draw the circuit, verify by simulation.
Mealy Edge Detector with a D Flip-Flop
Assign S0 = 0, S1 = 1 and call the flip-flop output Q. The next state is simply the present input, and the output is 1 only in S0 with x = 1:
D = x ; z = Q̅ · x
Moore Edge Detector with D Flip-Flops
Assign ZERO = 00, EDGE = 01, ONE = 10 (bits Q1Q0); code 11 is unused and becomes a don't-care.
| Q1 Q0 | x | Next Q1 Q0 (= D1 D0) | z |
|---|---|---|---|
| 00 (ZERO) | 0 | 00 | 0 |
| 00 (ZERO) | 1 | 01 | 0 |
| 01 (EDGE) | 0 | 00 | 1 |
| 01 (EDGE) | 1 | 10 | 1 |
| 10 (ONE) | 0 | 00 | 0 |
| 10 (ONE) | 1 | 10 | 0 |
| 11 (unused) | x | xx | x |
With K-maps (verified by computer minimisation):
D1 = x · (Q1 + Q0) ; D0 = x · Q̅1 · Q̅0 ; z = Q0
Unused state check: from 11, x = 0 gives 00 and x = 1 gives 10, both legal, so the machine recovers in one clock.
Seeing the Timing Difference
Both detectors are written below in SystemVerilog, in the usual "state register + next-state logic + output logic" style. The testbench changes x in the middle of each clock cycle and prints the outputs just after.
// Rising-edge detector, two ways
module edge_mealy (input logic clk, rst, x, output logic z);
logic prev; // state: last value of x (1 flip-flop)
always_ff @(posedge clk)
if (rst) prev <= 1'b0; else prev <= x;
assign z = x & ~prev; // output uses the INPUT directly
endmodule
module edge_moore (input logic clk, rst, x, output logic z);
typedef enum logic [1:0] {ZERO = 2'b00, EDGE = 2'b01, ONE = 2'b10} state_t;
state_t state, next;
always_ff @(posedge clk) // state register
if (rst) state <= ZERO; else state <= next;
always_comb // next-state logic
case (state)
ZERO: if (x) next = EDGE; else next = ZERO;
EDGE: if (x) next = ONE; else next = ZERO;
ONE: if (x) next = ONE; else next = ZERO;
default: next = ZERO;
endcase
assign z = (state == EDGE); // output depends on the STATE only
endmodule
module tb;
logic clk = 0, rst = 1, x = 0, z_mealy, z_moore;
logic [0:9] pattern = 10'b0111010011;
edge_mealy m1 (.clk(clk), .rst(rst), .x(x), .z(z_mealy));
edge_moore m2 (.clk(clk), .rst(rst), .x(x), .z(z_moore));
always #5 clk = ~clk; // rising edges at 5, 15, 25, ...
initial begin
@(posedge clk) #1 rst = 0;
$display("cycle : x mealy z moore z");
for (int i = 0; i < 10; i++) begin
@(negedge clk) x = pattern[i]; // input changes in the middle of a cycle
#1 $display(" %0d : %b %b %b", i, x, z_mealy, z_moore);
end
$finish;
end
endmodule
Output (Icarus Verilog):
cycle : x mealy z moore z
0 : 0 0 0
1 : 1 1 0
2 : 1 0 1
3 : 1 0 0
4 : 0 0 0
5 : 1 1 0
6 : 0 0 1
7 : 0 0 0
8 : 1 1 0
9 : 1 0 1
Read the table carefully, because this is the most important practical difference between the two models:
The Mealy output rises in the same cycle as the input (cycles 1, 5, 8), immediately when x changes. It reacts one clock earlier.
The Moore output rises one cycle later (cycles 2, 6, 9), right after the clock edge, and stays for a full clock period. In cycle 6 it is still 1 even though x has already dropped to 0, because the output only looks at the state.
The Mealy pulse here lasts only from the middle of the cycle to the next edge. If x had a glitch, z would show it too. Moore outputs change only after clock edges, so they are cleaner. Designers who need a clean Mealy output often add a register on it, which turns it back into a Moore-like, one-cycle-late output.
Moore vs Mealy at a Glance
| Point | Moore | Mealy |
|---|---|---|
| Output depends on | Present state only | Present state and present input |
| Output shown | Inside the state circle | On the transition arrow (input/output) |
| Number of states | Same or more | Same or fewer |
| Output timing | Changes only after a clock edge; one cycle later | Can change any time the input changes; reacts in the same cycle |
| Glitches on output | Only from the output decoder; input glitches do not pass | Input glitches can pass straight to the output |
| Output logic | Function of the state bits only | Function of state bits and inputs |
| Typical use | Control units, traffic lights, safe glitch-free outputs | Fast response, fewer flip-flops, serial protocols |
Analysing a Given Sequential Circuit
Exams often give you a circuit and ask "what does it do?". The analysis procedure is the reverse of design:
Write the flip-flop input equations and the output equation from the circuit.
For every present state and every input, compute the flip-flop inputs, then the next state (using the flip-flop's characteristic equation), and the output.
Put the results in a state table and draw the state diagram.
Look for a pattern and describe the behaviour in words.
Example. A circuit has two D flip-flops A and B, input x and output y:
DA = A·x̅ + A̅·B·x
DB = B̅·x + A·x̅
y = A·x (depends on the input x, so this is a MEALY machine)
For a D flip-flop the next state equals D, so we just evaluate the equations for all 8 combinations of A, B, x:
| Present AB | x = 0: next AB, y | x = 1: next AB, y |
|---|---|---|
| 00 | 00, 0 | 01, 0 |
| 01 | 00, 0 | 10, 0 |
| 10 | 11, 0 | 01, 1 |
| 11 | 11, 0 | 00, 1 |
Check one row by hand, AB = 10 with x = 1: DA = 1·0 + 0·0·1 = 0; DB = 1·1 + 1·0 = 1; y = 1·1 = 1. So next = 01, y = 1, matching the table.
0/0 0/0
┌───┐ ┌───┐
│ ▼ 1/0 1/0 0/0 │ ▼
+----+ ──────► +----+ ─────► +----+ ──────► +----+
| 00 | | 01 | | 10 | | 11 |
+----+ ◄────── +----+ +----+ +----+
▲ 0/0 ▲ 1/1 │ │
│ └──────────────┘ │
└───────────────────── 1/1 ──────────────────┘
Notice that y = 1 only on transitions out of 10 or 11 with x = 1. A machine described this way can be studied further (for example, which input sequences produce y = 1), which is precisely the skill the next chapter uses.
Converting Between Mealy and Moore
Every Mealy machine has an equivalent Moore machine and vice versa (equivalent meaning the same output sequence for the same input sequence, with the Moore output delayed by one clock).
Moore → Mealy (Easy)
Keep the same states. Put each state's output on every arrow that enters that state. The number of states never increases, and the resulting Mealy machine may then allow state reduction.
Mealy → Moore (May Need More States)
A Moore state can have only one output. If arrows entering a Mealy state carry different outputs, split that state into one copy per output value. Each copy has the same outgoing transitions as the original. If a Mealy machine has n states and k output values, the Moore machine needs at most n × k states.
Example. In the Mealy edge detector, S1 is entered by 1/1 (from S0) and by 1/0 (from S1). Split S1 into S1/z=1 and S1/z=0. S0 is entered only with output 0, so it stays one state. The result has 3 states: S0 (z = 0), S1 with z = 1, and S1 with z = 0. These are exactly ZERO, EDGE and ONE of the Moore design.
State Reduction
A word description often produces more states than necessary. Fewer states can mean fewer flip-flops and simpler logic.
Equivalent states: two states are equivalent if, for every possible input sequence, starting from either state gives the same output sequence. Equivalent states can be merged into one.
A practical test: two states are equivalent if they have the same outputs for every input and, for every input, their next states are equivalent (identical next states are the simplest case).
The Partition Method
Consider this Mealy table (entries are next state, output):
| State | x = 0 | x = 1 |
|---|---|---|
| A | B, 0 | C, 0 |
| B | D, 0 | E, 0 |
| C | D, 0 | E, 0 |
| D | A, 0 | F, 1 |
| E | A, 0 | G, 1 |
| F | A, 1 | B, 0 |
| G | A, 1 | C, 0 |
P0: group by outputs. Outputs (x=0, x=1): A, B, C give (0, 0); D, E give (0, 1); F, G give (1, 0). P0 = {A, B, C} {D, E} {F, G}.
P1: split groups whose members go to different groups. A goes to (B, C), both in group 1. B and C go to (D, E), group 2. So A must separate from B and C. D goes to (A, F), E to (A, G): F and G are in the same group, so D and E stay together. F goes to (A, B), G to (A, C): same groups, stay together. P1 = {A} {B, C} {D, E} {F, G}.
P2: repeat. No group splits any more (B and C have identical rows; D, E differ only by F/G which are together; F, G differ only by B/C which are together). The partition is stable.
Result: 7 states reduce to 4: A, BC, DE, FG. That is 2 flip-flops instead of 3. (This was checked with a short partition-refinement program.)
| State | x = 0 | x = 1 |
|---|---|---|
| A | BC, 0 | BC, 0 |
| BC | DE, 0 | DE, 0 |
| DE | A, 0 | FG, 1 |
| FG | A, 1 | BC, 0 |
For incompletely specified tables (with don't-care entries) states are only "compatible", not equivalent, and the merging problem is harder; the implication-chart method is used there. Exams mostly ask for the completely specified case above.
State Assignment
The codes you give the states change the size of the logic, though not the behaviour. Common choices:
| Encoding | Flip-flops for N states | Idea | Good for |
|---|---|---|---|
| Binary | ⌈log2 N⌉ | States numbered 0, 1, 2, ... | Fewest flip-flops (discrete ICs, exams) |
| Gray | ⌈log2 N⌉ | Consecutive states differ in one bit | Machines that mostly step in order; fewer bits switch, less power |
| One-hot | N | Exactly one flip-flop is 1 per state | FPGAs: flip-flops are plentiful, next-state logic becomes very simple and fast |
A useful hand rule: give adjacent codes (differing in one bit) to states that have the same next state, or that are next states of the same state. Adjacent codes make 1s land next to each other in K-maps, so groups get bigger.
Common Mistakes
Putting outputs in the wrong place. Moore: in the state. Mealy: on the arrow. If an output depends on the input, it is Mealy, no matter how the diagram is drawn.
Assuming Mealy and Moore outputs are simultaneous. The Moore output appears one clock later for the same behaviour.
Forgetting the reset state. Every FSM needs a defined starting state, implemented with a reset.
Merging states with equal outputs but different futures. State reduction needs equal outputs and equivalent next states.
Copying Mealy outputs into a Moore table. When converting Mealy to Moore, split states that are entered with different outputs.
Ignoring unused codes. As with counters, check that unused state codes lead back to legal states.
GATE and Interview Questions
Q1. An FSM has 11 states. How many flip-flops are needed with binary encoding and with one-hot encoding?
Binary: ⌈log2 11⌉ = 4. One-hot: 11.
Q2. A Mealy machine has 4 states and a binary output. What is the maximum number of states in an equivalent Moore machine?
Each state may need one copy per output value: 4 × 2 = 8 states at most.
Q3. In which model can a glitch on the input appear on the output, and why?
The Mealy model, because the output logic takes the input directly, with no flip-flop in between. In a Moore machine the input reaches the output only through the state register, which samples it at the clock edge.
Q4. A sequential circuit has DA = B, DB = x and output y = A·B̅·x. Is it Mealy or Moore? Describe what it detects.
The output uses x, so it is Mealy. B holds the input from one clock ago and A from two clocks ago. y = 1 when (two ago, one ago, now) = (1, 0, 1), so the circuit detects the sequence 101, with overlap allowed.
Q5. States P and Q have identical outputs. Under x = 0 both go to R. Under x = 1, P goes to S and Q goes to T, where S and T are equivalent. Are P and Q equivalent?
Yes. Same outputs and, for every input, equivalent next states.
Q6. Why do FPGA synthesis tools often choose one-hot encoding?
FPGAs have a flip-flop in every logic cell, so extra flip-flops are almost free, while wide logic is expensive. With one-hot, each next-state bit depends on only a few signals, giving small, fast logic.
Summary
An FSM = state register + next-state logic δ + output logic λ, formally (S, I, O, δ, λ, s0).
Moore: output = f(state); outputs in the circles; clean, one cycle later.
Mealy: output = f(state, input); outputs on the arrows; same or fewer states, reacts in the same cycle, may pass input glitches.
Rising-edge detector: Mealy needs 2 states (D = x, z = Q̅x); Moore needs 3 (D1 = x(Q1 + Q0), D0 = xQ̅1Q̅0, z = Q0).
Analysis: equations → state table → state diagram → behaviour. Design: diagram → table → reduce → assign → excitation → K-maps → circuit.
Moore → Mealy keeps the states; Mealy → Moore may split states (at most n × k).
State reduction merges equivalent states using the partition method; state assignment chooses binary, Gray or one-hot codes.
Next, Sequence Detector Design uses this whole procedure on the classic "detect 101 / 1011" problems.