---
title: "Sequence detector 1001 using D flip-flops"
subject: "Digital Logic"
chapter: 9
key: "semester_3/digital_logic:detector-1001-d"
source: https://www.bctengineer.com/q/semester_3/digital_logic/detector-1001-d
site: BCT Engineering
---

# Sequence detector 1001 using D flip-flops

Digital Logic · Chapter 9: Sequential Machines

- Asked in: 2078 Kartik, 12 marks
- Video: [sequence detector 1000 || sequence detector 1001 overlapping mealy FSM](https://www.youtube.com/watch?v=mhGRxCXUDfY) — VLSI-LEARNINGS
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/digital_logic/detector-1001-d
- Whole chapter: https://www.bctengineer.com/md/semester_3/digital_logic/chapter-9

## Question

A sequential machine which has one input, A and one output, Y. The machine is required to give the output high when the input contains a serial message of 1001, use only D flip-flops for realizing the design.

## Short answer

Mealy machine with 2 D flip-flops; states S0(00), S1(01), S2(10), S3(11). D1 = (Q1 xor Q0) A', D0 = Q1 Q0' + A, Y = Q1 Q0 A.

## Answer

The machine has one input A and one output Y; Y = 1 when the last four bits received on A are 1, 0, 0, 1. Only D flip-flops are used.

A **Mealy** machine is used (output depends on the present state and the present input), and overlapping sequences are detected. Since the sequence has 4 bits, 4 states are needed, so **2 D flip-flops** ($Q_1Q_0$) are used, clocked on the positive edge. (A Moore machine would need 5 states.)

#### Step 1: States
| Present state | Meaning | Next (A=0) | Next (A=1) | Y (A=0) | Y (A=1) |
|---|---|---|---|---|---|
| S0 | reset / no useful bits | S0 | S1 | 0 | 0 |
| S1 | "1" received | S2 | S1 | 0 | 0 |
| S2 | "10" received | S3 | S1 | 0 | 0 |
| S3 | "100" received | S0 | S1 | 0 | 1 |

#### Step 2: State diagram
```text
 Main path (label = A/Y):
 S0 -1/0-> S1 -0/0-> S2 -0/0-> S3 -1/1-> S1
 Other transitions:
 S0 -0/0-> S0    S1 -1/0-> S1
 S2 -1/0-> S1    S3 -0/0-> S0
```

#### Step 3: State assignment
| State | S0 | S1 | S2 | S3 |
|---|---|---|---|---|
| Q1 Q0 | 0 0 | 0 1 | 1 0 | 1 1 |

#### Step 4: Excitation table
D excitation: $D = Q^+$ (D equals the next state).

| Q1 Q0 | A | Q1+ Q0+ | D1 | D0 | Y |
|---|---|---|---|---|---|
| 0 0 | 0 | 0 0 | 0 | 0 | 0 |
| 0 0 | 1 | 0 1 | 0 | 1 | 0 |
| 0 1 | 0 | 1 0 | 1 | 0 | 0 |
| 0 1 | 1 | 0 1 | 0 | 1 | 0 |
| 1 0 | 0 | 1 1 | 1 | 1 | 0 |
| 1 0 | 1 | 0 1 | 0 | 1 | 0 |
| 1 1 | 0 | 0 0 | 0 | 0 | 0 |
| 1 1 | 1 | 0 1 | 0 | 1 | 1 |

#### Step 5: K-maps (rows $Q_1$, columns $Q_0A$)
| D1: Q1 / Q0A | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 |

| D0: Q1 / Q0A | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 |

| Y: Q1 / Q0A | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |

#### Step 6: Equations
$$
\begin{aligned} &D_1 = Q_1\overline{Q_0}\overline{A} + \overline{Q_1}Q_0\overline{A} \\ &D_0 = Q_1\overline{Q_0} + A \\ &Y = Q_1Q_0A \end{aligned}
$$

#### Step 7: Logic diagram
```text
   +-----+       +-----+
D0>|D   Q|-Q0 D1>|D   Q|-Q1
   | FF0 |       | FF1 |
   |     |       |     |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
A = serial input, common to the gates
D1 = Q1.Q0'.A' + Q1'.Q0.A'
D0 = Q1.Q0' + A
Y = Q1.Q0.A
```
The gates for each flip-flop input are built from the equations; the output gate gives Y directly (Mealy output).

#### Check with an input stream
| A | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|
| State | S0 | S1 | S2 | S3 | S1 | S2 | S3 | S1 | S1 | S2 |
| Y | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |

Y = 1 appears exactly on the clock in which the last bit of 1001 arrives; overlapping sequences are also detected.

Note: $D_1 = \overline{A}\,(Q_1 \oplus Q_0)$, so FF1 needs one XOR and one AND gate.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. For a D flip-flop, what are the inputs D1, D0?
   A. Equal to the present state Q1, Q0
   B. Equal to the next state Q1+, Q0+
   C. Equal to Q xor Q+
   D. Always the complement of the input A
   Answer: B. D = Q+, so the excitation table is simply a copy of the next-state columns. (Key point: D excitation)

2. In state S2 ("10" received), what happens on A = 1?
   A. Go to S3
   B. Go to S0
   C. Go to S1, since 101 ends with a new 1
   D. Stay in S2
   Answer: C. 101 breaks the 1001 pattern, but the last 1 may begin a new one, so the machine goes to S1. (Key point: Overlap in S2)

3. In S3 ("100") with A = 1, what is the result?
   A. Y = 1, next state S1 (last 1 can start a new 1001)
   B. Y = 1, next state S0
   C. Y = 0, next state S1
   D. Y = 0, next state S3
   Answer: A. 100 plus 1 completes 1001, so Y = 1. The last 1 is reused, so the next state is S1. (Key point: Detection and overlap)

4. Which equation gives the output?
   A. Y = Q1 Q0' A
   B. Y = Q1 Q0 A'
   C. Y = Q1' Q0 A
   D. Y = Q1 Q0 A
   Answer: D. Y = 1 only in S3 (Q1Q0 = 11) with A = 1. (Key point: Output equation)

## Close variants set in other exams

- [Sequence detector 1010 using T flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1010-t) — Digital Logic, chapter 9, asked 7×
- [Sequence detector 1001 using SR flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1001-sr) — Digital Logic, chapter 9, asked 7×
- [Sequence detector 1101 using SR flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1101-sr) — Digital Logic, chapter 9, asked 7×
- [Sequence detector 1101 using T flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1101-t) — Digital Logic, chapter 9, asked 7×
- [Sequence detector 001 using JK flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-001-jk) — Digital Logic, chapter 9, asked 7×
- [Sequence detector 011 using JK flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-011-jk) — Digital Logic, chapter 9, asked 7×
- [Sequence detector 1110 using T flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1110-t) — Digital Logic, chapter 9, asked 7×

## Related in Digital Logic

- [Sequence detector 1011 using T flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1011-t) — Digital Logic, chapter 9, asked 2×
- [Sequence detector 101 using T flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-101-t) — Digital Logic, chapter 9
- [Sequence detector 1011 using JK flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1011-jk) — Digital Logic, chapter 9, asked 3×
- [Sequence detector 011 using T flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-011-t) — Digital Logic, chapter 9
- [Sequence detector 011 using RS flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-011-rs) — Digital Logic, chapter 9