Learn › Topic 11

Moore and Mealy state machines: a complete design

7 min read · bitGateLab Team

A finite state machine (FSM) is a sequential circuit that "remembers" which step of a process it is in. Traffic lights, combination locks, elevator controllers and serial communication receivers are all state machines. Here you will see the two classic models, Moore and Mealy, and follow a complete design from the description in words to the flip-flop equations, using a detector for the sequence 101.

Parts of a state machine

Every synchronous FSM has three blocks:

State register: n flip-flops (almost always D type) that store the current state; they are enough for up to 2ⁿ states.
Next-state logic: combinational; it computes the next state from the current state and the inputs.
Output logic: combinational; it computes the outputs.

The difference between the two models lies in the last block:

Moore: the outputs depend only on the current state. They are written inside the circle of each state (for example S3/1).
Mealy: the outputs depend on the state and on the inputs. They are written on the arrows (input/output, for example 1/1).

A Mealy machine usually needs fewer states and responds in the same cycle in which the input arrives, but its output can change at any moment if the input changes. A Moore machine responds one cycle later, and its output changes only right after the clock edge, which makes it cleaner.

The problem: a 101 sequence detector

A serial input X arrives synchronized with the clock, one bit per cycle. The output Z must be 1 every time the last three bits received are 1, 0, 1. Overlap is allowed: the string 10101 contains two detections, because the last 1 of the first sequence is the first of the next one.

The first step is to decide what the machine has to remember. Each state stands for "how much of the sequence I have so far":

S0: nothing useful so far.
S1: the last bit was 1.
S2: the last bits were 1, 0.
S3: I have just received 1, 0, 1 (Z = 1).

State diagram and state table (Moore)

For each state and each value of X, ask yourself: with this new bit, what is the longest suffix that matches the beginning of 101? That suffix defines the next state.

Moore detector for 101 with overlap. The numbers on the arrows are the value of X; the output is inside each state.

Current state	X = 0	X = 1	Z
S0	S0	S1	0
S1	S2	S1	0
S2	S0	S3	0
S3	S2	S1	1

Pay attention to two transitions that people often get wrong. In S1 another 1 arrives: the string ends in 11, and the last 1 still works as a beginning, so the machine stays in S1. In S3 a 0 arrives: the string ends in 1010, whose suffix 10 matches the beginning of 101, so it goes to S2 and not to S0. That is what makes overlap possible.

State assignment and equations

With 4 states, 2 D flip-flops (Q1 Q0) are enough. The most direct assignment is the binary one: S0 = 00, S1 = 01, S2 = 10, S3 = 11. With D flip-flops the excitation table is trivial, because D = Q⁺.

Q1	Q0	X	Q1⁺ = D1	Q0⁺ = D0
0	0	0	0	0
0	0	1	0	1
0	1	0	1	0
0	1	1	0	1
1	0	0	0	0
1	0	1	1	1
1	1	0	1	0
1	1	1	0	1

Simplification:

D0 is 1 in exactly the rows with X = 1, so D0 = X. It makes sense: in this assignment Q0 = 1 means "the last bit was 1".
D1 = Σm(2, 5, 6) with the variables in the order Q1 Q0 X. Minterms 2 (010) and 6 (110) are adjacent and form Q0·X. Minterm 5 (101) has no neighbors at 1 and stays on its own: Q1·Q0·X. D1 = Q0·X + Q1·Q0·X.
The Moore output depends only on the state: Z = Q1·Q0.

The circuit ends up with 2 D flip-flops, a 2-input AND for Z, and for D1 a 2-input AND, a 3-input AND and a 2-input OR (plus the inverters for Q0 and X).

Verification with a test sequence

Input X = 1 0 1 0 1 1 0 1, starting from S0. State after each edge:

Edge	1	2	3	4	5	6	7	8
X	1	0	1	0	1	1	0	1
State	S1	S2	S3	S2	S3	S1	S2	S3
Z	0	0	1	0	1	0	0	1

There are three detections: at bits 1 to 3, 3 to 5 (overlap) and 6 to 8. Check edge 4 with the equations: state S3 = 11 and X = 0, D1 = 1·1 + 1·0·0 = 1 and D0 = 0, next state 10 = S2. It matches.

The Mealy version

In a Mealy machine the output goes on the transition, so state S3 is no longer needed: the detection happens "when the 1 arrives while in S2". With three states A (nothing), B (last bit 1) and C (last bits 1, 0):

State	X = 0	X = 1
A	A / 0	B / 0
B	C / 0	B / 0
C	A / 0	B / 1

2 flip-flops are still needed, but the output Z = 1 appears in the same cycle in which the last 1 arrives, one cycle earlier than in the Moore version.

Common mistakes

Sending every transition that "fails" to S0, without checking which part of the sequence is still useful; that is how overlapping detections are lost.
Writing outputs on the arrows in a Moore machine or inside the states in a Mealy machine.
Forgetting the unused flip-flop combinations (for example, the code 11 in the Mealy version): you have to decide where they go, or mark them as X and verify that the machine returns to the sequence.
Reading the output of a Mealy machine at any moment: it must be sampled just before the edge, when the input is already stable.
Changing the input X right at the clock edge when testing the machine.

Try it in the simulator

Once you have the equations, building the detector takes a few minutes, and the timing diagram lets you check every transition.

Place two D flip-flops with the same clock; name their outputs Q1 and Q0.
Connect the input X directly to D0.
Build D1 = Q0·X + Q1·Q0·X with two inverters, two AND gates and an OR, and connect it to D1.
Connect an AND of Q1 and Q0 to an indicator for Z.
Change X before each edge following the sequence 1 0 1 0 1 1 0 1 and watch in the timing diagram that Z turns on after edges 3, 5 and 8.

Exercises

With overlap, how many times does the machine detect 101 in the string 1010101?
Answer
Three times: at bits 1 to 3, 3 to 5 and 5 to 7.
Redo the Moore table of the 101 detector without overlap (after a detection it starts from scratch).
Answer
Only row S3 changes: with X = 0 it goes to S0 and with X = 1 it goes to S1. The other rows stay the same.
With the Mealy-version assignment A = 00, B = 01, C = 10, find Z.
Answer
Z = 1 only in state C with X = 1: Z = Q1·Q0·X. If the code 11 never appears it can be marked as X, which leaves Z = Q1·X.
What is the minimum number of flip-flops needed by a machine with 9 states?
Answer
4, because 2³ = 8 is not enough and 2⁴ = 16 is.

To review the flip-flops that make up the state register, see latches and flip-flops.