Designing a sequence detector

Q: What is the difference between a Moore and a Mealy machine?

A Moore machine's output depends on the current state only (drawn inside the state bubbles), so it is glitch-free but reacts one clock later. A Mealy machine's output depends on the current state and the current input (drawn on the transition arrows), so it usually needs fewer states and asserts in the same cycle as the triggering input, at the cost of possibly glitching with the input.

Q: What is the difference between overlapping and non-overlapping detection?

In overlapping detection a bit can be part of two matches, so detecting two consecutive 1s in 1 1 1 fires twice; the target state loops back to itself on a continued match. In non-overlapping detection the machine restarts after each hit, so 1 1 1 fires once. The only difference is where the arrow leaving the accepting state points, which changes a single row of the state table.

FSM design from a spec: Moore vs Mealy

12 min read

A sequence detector is a finite state machine that watches a serial input and raises its output when a target bit pattern arrives; you design one by writing a state diagram, filling a state-transition and output table, assigning a binary code to each state, and reading the next-state and output equations off the table, choosing a Moore output (from the state alone) or a Mealy output (from the state and the current input).

Builds onFinite state machines D flip-flop Karnaugh maps

Build it in the lab →

The finite state machine you have seen so far, the ring counter, has no data inputs: it just marches T0 -> T1 -> T2 -> T3 on the clock. Real controllers branch on an input: go one way on a 1, another on a 0. This lesson does the canonical exercise that teaches that skill, a sequence detector, and walks the full design flow you will reuse for every controller (including the CPU's own control unit): take a plain-English spec, turn it into a state diagram, and grind it down to gates and flip-flops.

Two output styles: Moore and Mealy

Before designing anything, decide where the output comes from. There are two standard styles, and they are the difference between labelling the bubbles and labelling the arrows of a state diagram.

Moore machine: the output depends on the current state only. You write the output value *inside* each state bubble. It is glitch-free (a clean function of a stored state) but reacts one clock later, because the machine has to clock into the right state before the output changes.
Mealy machine: the output depends on the current state and the current input together. You write the output *on the transition arrow*. It usually needs fewer states and asserts in the same cycle as the triggering input, but it can glitch if the input glitches.

The one-line memory aid: Moore output is in the bubble, Mealy output is on the arrow. Everything else about the design flow, the state register plus next-state logic from the state machine lesson, is identical between the two.

A common trap: a data input does not make a machine Mealy

It is tempting to assume that the instant a machine has a data input it must be Mealy. It does not. Moore versus Mealy is decided by one thing only: whether the output depends on the input. If the output reads the stored state alone, the machine is Moore, no matter how many inputs steer its next state; only when the output also reads the current input is it Mealy.

Take a 2-bit up/down counter with a direction input dir. When dir = 0 it counts up (00 -> 01 -> 10 -> 11 -> 00); when dir = 1 it counts down (00 -> 11 -> 10 -> 01 -> 00). Every clock it plainly branches on the input, so dir rides the arrows of its state diagram. Yet its output is the count itself, read straight off the two flip-flops: the output bits equal Q1 Q0, with no dir term anywhere. Output from the state alone means this counter is a Moore machine, data input and all.

A one-question test settles it every time: write the output equation, then look for the input in it. If a live input variable appears, the machine is Mealy; if the output reduces to the state bits alone, it is Moore, even when you first sketched it in Mealy form with the output on the arrows. Inputs on the arrows are just branch conditions: they pick the next state, not the output style.

The design flow, step by step

Every FSM design follows the same recipe. It turns a sentence into hardware with no guessing:

Read the spec and list the situations the machine must remember (for a detector: how much of the target pattern you have matched so far). Each situation becomes a state.
Draw the state diagram: a bubble per state, and a labelled arrow for every input value out of every state. Pick a reset state to start in.
Fill the state-transition and output table: one row per (current state, input), giving the next state and the output.
Assign a binary code to each state (00, 01, 10, ...), so the state fits in flip-flops.
Read the equations off the table: the next-state bits D1, D0, ... and the output become boolean functions of the current-state bits and the input, minimised with K-maps.
Wire it: a flip-flop per state bit forms the state register; the next-state gates feed the flip-flops' D inputs; the output gates read the state (Moore) or the state and input (Mealy).

Worked example: detect two consecutive 1s

The spec: watch a serial input X, one bit per clock, and raise Z whenever the two most recent bits were both 1. Detections overlap, so the input 1 1 1 counts twice (bits 1 to 2, and bits 2 to 3). Build the Moore version first. It needs three states, named for how much of 1 1 we have matched:

S0 = the last bit was not a 1 (nothing matched, also the reset state).
S1 = we have just seen a single 1.
S2 = we have seen two-or-more 1s in a row. This is the only state where Z = 1.

The transitions read straight from the spec: any 0 throws you back to S0; a 1 advances S0 -> S1 -> S2, and S2 stays in S2 on more 1s (that is what makes detection overlap). As a state diagram:

S0 --1-

→ S1 --1-

→ S2 --1-

→ S2, and every --0-

→ goes back to S0

Now assign codes S0 = 00, S1 = 01, S2 = 10 (writing the state as Q1 Q0). The fourth code 11 is unused: the machine never reaches it from reset. Fill the table, with next state D1 D0 and the Moore output Z:

Q1	Q0	X	D1	D0	Z
0	0	0	0	0	0
0	0	1	0	1	0
0	1	0	0	0	0
0	1	1	1	0	0
1	0	0	0	0	1
1	0	1	1	0	1

State-transition and output table for the Moore detector (Q1 Q0 is the current state, X the input, D1 D0 the next state, Z the output). The two unused rows Q1 Q0 = 11 are left as don't-cares, which is what lets the equations below simplify. Z = 1 only in state S2 = 10.

Reading the D1 column: it is 1 only in rows 011 and 101, both of which have X = 1 and at least one state bit high. Reading D0: it is 1 only in row 001, where X = 1 and both state bits are 0. And Z follows Q1 exactly. Treating the 11 rows as don't-cares, the minimised equations are:

D1 = X · (Q1 + Q0), D0 = X · Q1' · Q0', Z = Q1

That is the whole point of the flow: once the table is filled, the hardware is mechanical. D1 and D0 are ordinary combinational functions (an OR feeding an AND, and a pair of NOTs feeding two ANDs), and they drive the D inputs of two flip-flops whose Q outputs feed back into them. No cleverness, no guessing: a state table always becomes gates plus flip-flops this way.

The Moore detector: two D flip-flops hold the state Q1 Q0, the gates compute D1 = X AND (Q1 OR Q0) and D0 = X AND NOT Q1 AND NOT Q0, and Z = Q1. Before the first clock the flip-flops read Z; open it in the lab, then feed X one bit per clock (try 0 1 1 0 1 1 1) and watch Z rise the cycle after each pair of 1s.

Watching it run

Feed the stream X = 0 1 1 0 1 1 1, starting reset in S0. Each clock the machine takes one transition; Z reads the state you are now in. The Mealy version (built next) is shown on the same clock so you can compare when each style fires:

Cycle	X	Moore state	Moore Z	Mealy Z
1	0	S0	0	0
2	1	S0	0	0
3	1	S1	0	1
4	0	S2	1	0
5	1	S0	0	0
6	1	S1	0	1
7	1	S2	1	1

The two 1s of the first pair land in cycles 2 and 3. Mealy Z rises in cycle 3 (the same cycle as the second 1); Moore Z rises in cycle 4 (one clock later, once the machine has clocked into S2). Moore Z is exactly Mealy Z delayed by one cycle. The final 1 1 pair (cycles 6 to 7) makes Moore fire again in cycle 8, just past the window shown.

The Mealy version: fewer states, earlier output

The identical spec as a Mealy machine needs only two states: M0 = the last bit was not a 1, M1 = the last bit was a 1. The output lives on the arrows: from M1, a 1 input asserts Z (that 1 plus the remembered 1 is two in a row); every other arrow outputs 0. Because the state just records the previous bit, the next-state logic is a single flip-flop with D = X, and the output is a single AND:

D = X, Z = Q · X (Q holds the previous input bit)

So the Mealy detector is one flip-flop that delays X by a clock, plus one AND that raises Z when the current bit and the previous bit are both 1. Same behavior, one flip-flop instead of two, and Z asserts in the very cycle the second 1 arrives (it is a direct function of the live input) rather than one clock later. That is the classic trade: Mealy is smaller and faster to respond; Moore is later but glitch-free because its output is a clean function of a stored state, never of a possibly-glitching input.

Overlapping vs non-overlapping detection

Whether detections overlap is a spec decision, and it changes exactly one arrow of the Moore diagram: the one leaving the accepting state S2. Feed the stream X = 1 1 1 and ask what the shared middle 1 may do. Overlapping detection lets a single bit belong to two matches, so S2 loops back to itself on a 1, and Z reports both the bits-1-to-2 pair and the bits-2-to-3 pair. Non-overlapping detection starts the count over after each hit, so from S2 a 1 goes to S1 (that 1 counts only as the *first* of a possible next pair), and Z reports just once.

Overlapping: S0 --1-

→ S1 --1-

→ S2 --1-

→ S2

Non-overlapping: S0 --1-

→ S1 --1-

→ S2 --1-

→ S1

In both graphs every 0 still returns to S0; only the S2 --1--> arrow moves. Clocking in the stream 1 1 1 from reset makes the split concrete (the state shown is the one entered *after* that bit, and the Moore Z is that state's output):

Bit #	X	Overlap state	Overlap Z	Non-ovlp state	Non-ovlp Z
1	1	S1	0	S1	0
2	1	S2	1	S2	1
3	1	S2	1	S1	0

Detect-11 on 1 1 1, starting from S0. The first pair (bits 1 to 2) lands the machine in S2 for both designs. On the third 1 they diverge: overlapping stays in S2 and keeps Z high (a second, overlapping pair), while non-overlapping drops to S1 and Z falls (the leftover 1 merely begins a fresh count). So 1 1 1 reports twice with overlap and once without; on 1 1 1 1 it would be three times versus twice.

Common mistakes. Putting a Moore output on an arrow, or a Mealy output in a bubble (they are the *defining* difference, so mixing them is a real error). Forgetting the overlap rule: a non-overlapping detector sends the accepting state's continued-1 arrow to S1 (starting a fresh count) instead of staying in S2, giving a different table. Being off by one about when Z asserts (Mealy same cycle, Moore next cycle). Skipping the state-assignment and K-map steps and guessing the equations. And leaving the unused 11 code truly undefined instead of treating it as a don't-care (or, in safety-critical designs, routing it explicitly back to S0).

This is the single most important sequential-design skill: any controller is built this way. The CPU's control unit is a state machine whose states are the micro-steps of fetch-decode-execute, whose input is the opcode, and whose outputs are the control lines. Master spec-to-state-diagram-to-table-to-gates here and you can design that control unit (and any traffic light, vending machine, or protocol handler) by the same recipe.

Try it

Change the spec to non-overlapping detect-11: after a hit, the detector must start over from scratch (so 1 1 1 fires only once, not twice). Which single arrow in the Moore state diagram changes, and to where?

Frequently asked

What is a sequence detector?

A sequence detector is a finite state machine that watches a serial input, one bit per clock, and raises its output when a target bit pattern appears (for example two 1s in a row). You design one by writing a state diagram, filling a state-transition and output table, encoding the states in flip-flops, and reading the next-state and output equations off the table.

What is the difference between a Moore and a Mealy machine?

A Moore machine's output depends on the current state only (drawn inside the state bubbles), so it is glitch-free but reacts one clock later. A Mealy machine's output depends on the current state and the current input (drawn on the transition arrows), so it usually needs fewer states and asserts in the same cycle as the triggering input, at the cost of possibly glitching with the input.

How do you design a finite state machine from a specification?

Follow a fixed recipe: (1) list the situations the machine must remember, one per state; (2) draw a state diagram with a labelled arrow for each input out of each state, and choose a reset state; (3) fill a state-transition and output table; (4) assign a binary code to each state; (5) read the next-state and output equations off the table and minimise them with a K-map; (6) wire a flip-flop per state bit with the next-state gates driving their D inputs.

What is the difference between overlapping and non-overlapping detection?

In overlapping detection a bit can be part of two matches, so detecting two consecutive 1s in 1 1 1 fires twice; the target state loops back to itself on a continued match. In non-overlapping detection the machine restarts after each hit, so 1 1 1 fires once. The only difference is where the arrow leaving the accepting state points, which changes a single row of the state table.

You've got the theory. Now build it from scratch and watch it work.

Build it in the lab →

Builds towardAlgorithmic state machines (ASM charts)Analyzing a sequential circuit