--- title: "Sequence detector 101 using T flip-flops" subject: "Digital Logic" chapter: 9 key: "semester_3/digital_logic:detector-101-t" source: https://www.bctengineer.com/q/semester_3/digital_logic/detector-101-t site: BCT Engineering --- # Sequence detector 101 using T flip-flops Digital Logic · Chapter 9: Sequential Machines - Asked in: 2079 Bhadra, 10 marks - Video: [101 Sequence detector design - moore FSM](https://www.youtube.com/watch?v=HYBxoz6yGOQ) — sridevi sriadibhatla - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_3/digital_logic/detector-101-t - Whole chapter: https://www.bctengineer.com/md/semester_3/digital_logic/chapter-9 ## Question A synchronous machine has 1-bit input 'X'. The output 'Y' goes high when input contains the message '101'. Draw the state diagram, derive the transition table (state table), excitation table and design circuit. Use only T flip-flops. ## Short answer A Mealy machine with states A(00), B(01), C(10) detects overlapping '101'. T flip-flop excitation gives T1 = Q0 X' + Q1, T0 = Q0 X' + Q0' X, output Z = Q1 X. ## Answer Output Y of the question is written Z (Y = Z). 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 **101** arrives. Flip-flops: **T**. States (what has been received so far): - **A**: reset / no useful bits - **B**: "1" received - **C**: "10" received #### State diagram (Mealy) ```text Arc label = input/output A --1/0--> B --0/0--> C --1/1--> B A --0/0--> A (self loop) B --1/0--> B (self loop) C --0/0--> A ``` #### State table | Present state | Next, X=0 | Next, X=1 | Z (X=0) | Z (X=1) | |---|---|---|---|---| | A | A | B | 0 | 0 | | B | C | B | 0 | 0 | | C | A | B | 0 | 1 | #### 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 B), so it is self-starting. #### Excitation table of T flip-flop | Q | Q+ | T | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | #### Transition and excitation table | Q1 Q0 | X | Q1+ Q0+ | T1 | T0 | Z | |---|---|---|---|---|---| | 0 0 | 0 | 0 0 | 0 | 0 | 0 | | 0 0 | 1 | 0 1 | 0 | 1 | 0 | | 0 1 | 0 | 1 0 | 1 | 1 | 0 | | 0 1 | 1 | 0 1 | 0 | 0 | 0 | | 1 0 | 0 | 0 0 | 1 | 0 | 0 | | 1 0 | 1 | 0 1 | 1 | 1 | 1 | #### K-maps and simplified equations ```text T1 X=0 X=1 Q1Q0=00 0 0 Q1Q0=01 1 0 Q1Q0=11 x x Q1Q0=10 1 1 T0 X=0 X=1 Q1Q0=00 0 1 Q1Q0=01 1 0 Q1Q0=11 x x Q1Q0=10 0 1 Z X=0 X=1 Q1Q0=00 0 0 Q1Q0=01 0 0 Q1Q0=11 x x Q1Q0=10 0 1 ``` $$ \begin{aligned} T_1 &= Q_0 X' + Q_1 \\ T_0 &= Q_0 X' + 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 T flip-flops with a common clock; complements are taken from the $Q'$ outputs or NOT gates): - $T_1$: a 2-input AND for $Q_0 X'$; direct line $Q_1$, combined in a 2-input OR gate. - $T_0$: a 2-input AND for $Q_0 X'$; a 2-input AND for $Q_0' X$, combined in a 2-input OR gate. - $Z$: a 2-input AND for $Q_1 X$. **Check:** input X = 0101011 gives Z = 0001010; Z = 1 at bits 4 and 6 ("10101" contains two overlapping 101s) and 0 at bit 7. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Why does C --1/1--> B? A. The final 1 can start another 101 B. C is the reset state C. The 1 returns to A D. Overlap is not allowed Answer: A. The last 1 of 101 can be the first 1 of the next 101, so B (1 received) is the next state. (Key point: Overlap) 2. Which equation gives T0? A. T0 = Q0 X B. T0 = Q0 X' + Q0' X C. T0 = Q1 D. T0 = Q0' X' Answer: B. T0 = Q0 xor X, from the toggling pattern. (Key point: T0 equation) 3. For X = 0101011, where is Z = 1? A. Bits 3 and 5 B. Bit 4 only C. Bits 4 and 6 D. Bits 4, 6 and 7 Answer: C. Z = 0001010; 10101 contains two overlapping 101s. (Key point: Check) 4. Why does Z depend on X in the output equation Z = Q1 X? A. Z must be 1 in state C always B. Moore outputs depend on X C. Z is the clear input D. It is a Mealy output; Z=1 in C only when X=1 Answer: D. Z is 1 only when in C (10) and the next input is 1, so it depends on state and input. (Key point: Output) ## Related in Digital Logic - [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 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 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 - [VHDL entity declaration; T flip-flops circuit](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-entity-two-tff-inverter) — Embedded System, chapter 9 - [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