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

# Sequence detector for 1010

Digital Logic · Chapter 9: Sequential Machines

- Asked in: 2079 Bhadra, 12 marks; 2068 Chaitra, 12 marks (asked 2 times)
- Video: [VLSI : sequence detector 1010 || sequence detector 1011 overlapping mealy FSM](https://www.youtube.com/watch?v=EUosQBSw2qQ) — 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-1010
- Whole chapter: https://www.bctengineer.com/md/semester_3/digital_logic/chapter-9

## Question

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

## Short answer

Design as an overlapping Mealy detector with two JK flip-flops. State encoding: A=00, B=01, C=10, D=11. The inputs are J1 = Q0 X', K1 = Q0 X + Q0' X'; J0 = X, K0 = X'; output Z = Q1 Q0 X'.

## Answer

The machine has one serial input X and one output Z; Z = 1 when the last four bits received are 1, 0, 1, 0. Since no flip-flop type is specified, JK 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 JK 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 (X=0) | Next (X=1) | Z (X=0) | Z (X=1) |
|---|---|---|---|---|---|
| A | reset / no useful bits | A | B | 0 | 0 |
| B | "1" received | C | B | 0 | 0 |
| C | "10" received | A | D | 0 | 0 |
| D | "101" received | C | B | 1 | 0 |

#### Step 2: State diagram
```text
 Main path (label = X/Z):
 A -1/0-> B -0/0-> C -1/0-> D -0/1-> C
 Other transitions:
 A -0/0-> A    B -1/0-> B
 C -0/0-> A    D -1/0-> B
```

#### Step 3: State assignment
| State | A | B | C | D |
|---|---|---|---|---|
| Q1 Q0 | 0 0 | 0 1 | 1 0 | 1 1 |

#### Step 4: Excitation table
JK excitation: 0→0: J=0, K=X; 0→1: J=1, K=X; 1→0: J=X, K=1; 1→1: J=X, K=0.

| Q1 Q0 | X | Q1+ Q0+ | J1 | K1 | J0 | K0 | Z |
|---|---|---|---|---|---|---|---|
| 0 0 | 0 | 0 0 | 0 | X | 0 | X | 0 |
| 0 0 | 1 | 0 1 | 0 | X | 1 | X | 0 |
| 0 1 | 0 | 1 0 | 1 | X | X | 1 | 0 |
| 0 1 | 1 | 0 1 | 0 | X | X | 0 | 0 |
| 1 0 | 0 | 0 0 | X | 1 | 0 | X | 0 |
| 1 0 | 1 | 1 1 | X | 0 | 1 | X | 0 |
| 1 1 | 0 | 1 0 | X | 0 | X | 1 | 1 |
| 1 1 | 1 | 0 1 | X | 1 | X | 0 | 0 |

#### Step 5: K-maps (rows $Q_1$, columns $Q_0X$)
| J1: Q1 / Q0X | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 1 | X | X | X | X |

| K1: Q1 / Q0X | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | X | X | X | X |
| 1 | 1 | 0 | 1 | 0 |

| J0: Q1 / Q0X | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 1 | X | X |
| 1 | 0 | 1 | X | X |

| K0: Q1 / Q0X | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | X | X | 0 | 1 |
| 1 | X | X | 0 | 1 |

| Z: Q1 / Q0X | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |

#### Step 6: Equations
$$
\begin{aligned} &J_1 = Q_0\overline{X},\quad K_1 = Q_0X + \overline{Q_0}\overline{X} \\ &J_0 = X,\quad K_0 = \overline{X} \\ &Z = Q_1Q_0\overline{X} \end{aligned}
$$

#### Step 7: Logic diagram
```text
   +-----+       +-----+
J0>|J   Q|-Q0 J1>|J   Q|-Q1
   | FF0 |       | FF1 |
K0>|K    |    K1>|K    |
   +--^--+       +--^--+
      |             |
CLK---+-------------+
X = serial input, common to the gates
J1 = Q0.X'   K1 = Q0.X + Q0'.X'
J0 = X   K0 = X'
Z = Q1.Q0.X'
```
The gates for each flip-flop input are built from the equations; the output gate gives Z directly (Mealy output).

#### Check with an input stream
| X | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|
| State | A | A | B | C | D | C | D | C | D | C |
| Z | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |

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

Note: $K_1 = \overline{Q_0 \oplus X}$ (an XNOR gate), and FF0 simply follows the input ($J_0 = X$, $K_0 = \overline{X}$).

## Check yourself

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

1. Why does the 1010 Mealy detector use 2 flip-flops?
   A. It has 4 states (A, B, C, D) and 2 flip-flops give 4 codes
   B. It has 5 states and 2 flip-flops are enough for 5
   C. Each bit of 1010 needs its own flip-flop
   D. JK flip-flops always come in pairs
   Answer: A. A Mealy machine for a 4-bit sequence needs 4 states, and 2 flip-flops give exactly 4 codes. A Moore machine would need 5 states. (Key point: Number of states and flip-flops)

2. In state D ("101" received), what happens when X = 0?
   A. Go to A with Z = 0
   B. Go to C with Z = 1
   C. Go to B with Z = 1
   D. Stay in D with Z = 0
   Answer: B. 101 followed by 0 completes 1010, so Z = 1. The tail "10" is useful for overlap, so the next state is C. (Key point: Overlap handling)

3. What is the output equation of this machine?
   A. Z = Q1 Q0 X
   B. Z = Q1 Q0' X'
   C. Z = Q1' Q0 X'
   D. Z = Q1 Q0 X'
   Answer: D. Z = 1 only in state D (Q1Q0 = 11) with X = 0, so Z = Q1 Q0 X'. (Key point: Output equation)

4. The equations J0 = X and K0 = X' mean that FF0:
   A. Always toggles
   B. Always holds its value
   C. Simply follows the input X
   D. Always resets to 0
   Answer: C. If X = 1, J=1,K=0 sets Q0 to 1; if X = 0, J=0,K=1 resets it to 0. So Q0 takes the value of X. (Key point: FF0 equations)

## Close variants set in other exams

- [Sequence detector for 110](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Adetector-110) — 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 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×
- [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 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