---
title: "Sequence detector for 110"
subject: "Digital Logic"
chapter: 9
key: "semester_3/digital_logic:detector-110"
source: https://www.bctengineer.com/q/semester_3/digital_logic/detector-110
site: BCT Engineering
---

# Sequence detector for 110

Digital Logic · Chapter 9: Sequential Machines

- Asked in: 2070 Chaitra, 8 marks
- Video: [Design a sequence detector to detect 110 || Draw state diagram  for 110  sequence detector.](https://www.youtube.com/watch?v=yepMDN_siuU) — Sirisha Vamsi
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/digital_logic/detector-110
- Whole chapter: https://www.bctengineer.com/md/semester_3/digital_logic/chapter-9

## Question

Design a sequential machine that has one serial input and one output z. The machine is required to give an output z = 1 when the input X contains the message 110.

## Short answer

Mealy machine with states A (reset), B (1 received), C (11 received). D flip-flops, assignment A=00, B=01, C=10. Equations: D1 = Q0 X + Q1 X, D0 = Q1' Q0' X. Output Z = Q1 X'.

## Answer

No flip-flop type is specified, so D flip-flops are used (simplest: D = next state).

A **Mealy** machine is used (output depends on present state and input), so fewer states are needed. Overlapping sequences are allowed: after a detection the machine keeps the useful tail of the input. One input X and one output Z; Z = 1 in the clock period in which the last bit of **110** arrives. Flip-flops: **D**.

States (what has been received so far):

- **A**: reset / last bit 0
- **B**: "1" received
- **C**: "11" received (stays in C on more 1s)

#### State diagram (Mealy)

```text
Arc label = input/output

 A --1/0--> B --1/0--> C --0/1--> A

 A --0/0--> A  (self loop)
 B --0/0--> A
 C --1/0--> C  (self loop)
```

#### State table

| Present state | Next, X=0 | Next, X=1 | Z (X=0) | Z (X=1) |
|---|---|---|---|---|
| A | A | B | 0 | 0 |
| B | A | C | 0 | 0 |
| C | A | C | 1 | 0 |

#### State assignment

A = 00, B = 01, C = 10 (flip-flop outputs $Q_1 Q_0$). The unused code 11 is taken as don't care (x) in all K-maps. The flip-flops are cleared to 00 at power-on (start state). Checking the final equations, from 11 the machine goes to a valid state on the next clock (X=0 goes to A, X=1 goes to C), so it is self-starting.

#### Excitation table of D flip-flop

| Q | Q+ | D |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

#### Transition and excitation table

| Q1 Q0 | X | Q1+ Q0+ | D1 | D0 | Z |
|---|---|---|---|---|---|
| 0 0 | 0 | 0 0 | 0 | 0 | 0 |
| 0 0 | 1 | 0 1 | 0 | 1 | 0 |
| 0 1 | 0 | 0 0 | 0 | 0 | 0 |
| 0 1 | 1 | 1 0 | 1 | 0 | 0 |
| 1 0 | 0 | 0 0 | 0 | 0 | 1 |
| 1 0 | 1 | 1 0 | 1 | 0 | 0 |

#### K-maps and simplified equations

```text
D1          X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    1
Q1Q0=11       x    x
Q1Q0=10       0    1

D0          X=0  X=1
Q1Q0=00       0    1
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       0    0

Z           X=0  X=1
Q1Q0=00       0    0
Q1Q0=01       0    0
Q1Q0=11       x    x
Q1Q0=10       1    0
```

$$
\begin{aligned} D_1 &= Q_0 X + Q_1 X \\ D_0 &= Q_1' Q_0' X \\ Z &= Q_1 X' \end{aligned}
$$

#### Logic diagram

```text
           +-------------+     +----------+
 X  ------>| next-state  |---->| FF1, FF0 |--+--> Q1, Q0
    +----->| logic       |     |  (CLK)   |  |
    |      +-------------+     +----------+  |
    +-------------------<--------------------+
    |      +-------------+
    +----->| output      |----> Z
 X  ------>| logic       |
           +-------------+
```

Gates needed (two D flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates):

- $D_1$: a 2-input AND for $Q_0 X$; a 2-input AND for $Q_1 X$, combined in a 2-input OR gate.
- $D_0$: a 3-input AND for $Q_1' Q_0' X$.
- $Z$: a 2-input AND for $Q_1 X'$.

**Check:** input X = 0110110 gives Z = 0001001; Z = 1 at bits 4 and 7.

## Check yourself

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

1. Why is a Mealy machine used for the 110 detector?
   A. Output depends on present state and input, so fewer states are needed
   B. Mealy machines need no flip-flops
   C. Mealy output depends only on the state, so it is glitch-free
   D. It allows non-overlapping detection only
   Answer: A. A Mealy output depends on state and input, so Z can be 1 as the last bit arrives, needing only 3 states. (Key point: Mealy choice)

2. What does state C mean, and what does it do on X=1?
   A. '110' received; it goes to A on X=1
   B. '11' received; it stays in C on more 1s
   C. '1' received; it goes to B on X=1
   D. Reset; it stays in C on X=1
   Answer: B. C means two 1s received; another 1 still leaves the last two bits as 11, so it stays in C. (Key point: State meaning)

3. Which output equation results for the 110 detector (A=00, B=01, C=10)?
   A. Z = Q1 Q0 X'
   B. Z = Q1' Q0' X
   C. Z = Q1 X'
   D. Z = Q0 X
   Answer: C. Z = 1 only in state C (Q1Q0 = 10) when X = 0; with 11 as don't care this simplifies to Q1 X'. (Key point: Output equation)

4. For a D flip-flop, how is D found from the transition table?
   A. D = complement of Q+
   B. D = Q xor Q+
   C. D = 1 whenever the state changes
   D. D = Q+ (D equals the next state)
   Answer: D. The D excitation table shows D = Q+, so the D inputs are read directly from the next-state columns. (Key point: D flip-flop)

## Close variants set in other exams

- [Sequence detector for 1010](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1010) — Digital Logic, chapter 9, asked 5×
- [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×

## Related in Digital Logic

- [Sequence detector 110 using JK flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-110-jk) — Digital Logic, chapter 9, asked 3×
- [Sequence detector 1001 using D flip-flops](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-1001-d) — Digital Logic, chapter 9, asked 9×
- [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×

## Related in other subjects

- [Sequence detector 1101 FSM and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-sequence-detector-1101) — Embedded System, chapter 9
- [Input/output interface unit design factors](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Aio-interface-unit-importance) — Instrumentation II, chapter 7
- [Sequence detector 1011 state diagram and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-sequence-detector-1011) — Embedded System, chapter 9
- [Input/output matching gains at 1.0 GHz](https://www.bctengineer.com/question.md?key=semester_7%2Frf_and_microwave_engineering%3Aamplifier-matching-network-gains-1ghz) — RF and Microwave Engineering, chapter 6