# Designing a sequence detector

*FSM design from a spec: Moore vs Mealy*

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).

Group: Processor
URL: https://digiwleea.wleeaf.dev/learn/sequence-detector/

The [finite state machine](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/control/)): take a plain-English spec, turn it into a state diagram, and grind it down to gates and [flip-flops](https://digiwleea.wleeaf.dev/learn/dff/).

## 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.

> **TIP:** 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](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/dff/): 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.

> **TIP:** 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:

1. **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**.
2. **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.
3. **Fill the state-transition and output table:** one row per (current state, input), giving the next state and the output.
4. **Assign a binary code** to each state (`00`, `01`, `10`, ...), so the state fits in flip-flops.
5. **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](https://digiwleea.wleeaf.dev/learn/karnaugh/).
6. **Wire it:** a [flip-flop](https://digiwleea.wleeaf.dev/learn/dff/) 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 `1`s 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 `1`s (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
```

> **KEY:** 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](https://digiwleea.wleeaf.dev/learn/or/) feeding an [AND](https://digiwleea.wleeaf.dev/learn/and/), and a pair of [NOT](https://digiwleea.wleeaf.dev/learn/not/)s feeding two ANDs), and they drive the `D` inputs of two [flip-flops](https://digiwleea.wleeaf.dev/learn/dff/) whose `Q` outputs feed back into them. No cleverness, no guessing: a state table always becomes gates plus flip-flops this way.

_Circuit diagram: 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](https://digiwleea.wleeaf.dev/learn/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._

> **WARN:** **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`).

> **KEY:** This is the single most important sequential-design skill: **any** controller is built this way. The CPU's [control unit](https://digiwleea.wleeaf.dev/learn/control/) 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.

**Q (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?

**A:** The self-loop on `S2`. In the overlapping design, `S2 --1--> S2` (a third `1` immediately counts as another pair). For non-overlapping, that arrow becomes `S2 --1--> S1`: after reporting a hit you treat the new `1` as only the *first* of a possible next pair, so `1 1 1` reports just once. (The `S2 --0--> S0` arrow is unchanged.) Everything else, the table rows for `S0` and `S1`, the state codes, and the design flow, stays the same; only that one transition, and therefore the `D1 D0` equations, differ.

### FAQ

**Q:** What is a sequence detector?

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

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

**A:** 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:** How do you design a finite state machine from a specification?

**A:** 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](https://digiwleea.wleeaf.dev/learn/karnaugh/); (6) wire a flip-flop per state bit with the next-state gates driving their `D` inputs.

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

**A:** In **overlapping** detection a bit can be part of two matches, so detecting two consecutive `1`s 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.