--- title: "Sequence detector 1101 FSM and VHDL" subject: "Embedded System" chapter: 9 key: "semester_6/embedded_system:vhdl-sequence-detector-1101" source: https://www.bctengineer.com/q/semester_6/embedded_system/vhdl-sequence-detector-1101 site: BCT Engineering --- # Sequence detector 1101 FSM and VHDL Embedded System · Chapter 9: Microcontrollers in Embedded Systems - Asked in: 2070 Magh, 7 marks - Video: [0111 Sequence Detector-Using Mealy and Moore FSM](https://www.youtube.com/watch?v=OVTjSu1jK48) — Easy Electronics - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/embedded_system/vhdl-sequence-detector-1101 - Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-9 ## Question Design a sequence detector for the string "1101", that outputs a one when the input matches this string, show the FSM and its VHDL implementation. ## Short answer A Mealy FSM with states S0, S1, S11, S110. Transitions: S0-1->S1, S1-1->S11, S11-0->S110, S110-1->S1 with z=1 (overlap allowed), S110-0->S0. VHDL uses a state register and a combinational process for next state and output based on input. ## Answer The detector watches a serial input x, one bit per clock, and gives z = 1 when the last four bits received are 1101. Overlap is allowed (the last 1 of a detected string may start the next one). A Mealy FSM with four states is used. | State | Bits matched so far | |---|---| | S0 | none | | S1 | "1" | | S11 | "11" | | S110 | "110" | #### FSM (state diagram), arc label = input / output ```text main path: (S0) -1/0-> (S1) -1/0-> (S11) -0/0-> (S110) | back to (S1) <---- 1/1 ----+ other arcs: S0 --0/0--> S0 S1 --0/0--> S0 S11 --1/0--> S11 S110 --0/0--> S0 ``` Notes: S11 loops on 1 because 111 still ends with "11". From S110 the input 1 completes 1101 (z = 1); the last 1 can start a new match, so the next state is S1. #### State table | Present state | x = 0: next / z | x = 1: next / z | |---|---|---| | S0 | S0 / 0 | S1 / 0 | | S1 | S0 / 0 | S11 / 0 | | S11 | S110 / 0 | S11 / 0 | | S110 | S0 / 0 | S1 / 1 | #### VHDL implementation ```vhdl library ieee; use ieee.std_logic_1164.all; -- Mealy detector for the serial pattern 1101 (overlapping allowed) entity seq_1101 is port ( clk : in std_logic; rst : in std_logic; x : in std_logic; z : out std_logic ); end entity seq_1101; architecture fsm of seq_1101 is type state_t is (S0, S1, S11, S110); signal state, next_state : state_t; begin process (clk, rst) begin if rst = '1' then state <= S0; elsif rising_edge(clk) then state <= next_state; end if; end process; process (state, x) begin z <= '0'; case state is when S0 => -- nothing matched if x = '1' then next_state <= S1; else next_state <= S0; end if; when S1 => -- seen 1 if x = '1' then next_state <= S11; else next_state <= S0; end if; when S11 => -- seen 11 if x = '0' then next_state <= S110; else next_state <= S11; end if; when S110 => -- seen 110 if x = '1' then z <= '1'; -- 1101 detected next_state <= S1; -- last 1 starts a new match else next_state <= S0; end if; end case; end process; end architecture fsm; ``` Two processes are used: one for the state register (with asynchronous reset) and one for the next-state and output logic. The code was analysed and simulated with GHDL; for the input 1011011010110111101101 the output was 1 at bit positions 6, 9, 14, 19 and 22, each the last bit of a 1101 (overlaps included). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the 1101 detector, from S110 with input x = 1, what happens? A. z = 0 and next state S0 B. z = 1 and next state S1 C. z = 1 and next state S0 D. z = 0 and next state S11 Answer: B. S110 + 1 completes 1101, so z = 1; the last 1 can start a new match, so the next state is S1. (Key point: Mealy detection) 2. Why does S11 stay in S11 when x = 1? A. Because 111 still ends with '11', which is a matched prefix B. Because the detector is stuck waiting for a reset C. Because an error has occurred D. Because the output must stay 0 Answer: A. Input 111 ends in '11', so the longest matching prefix is still '11'; the machine remains in S11. (Key point: Self-loop on S11) 3. What does state S110 record? A. No bits matched B. The last three bits received are 110 C. The pattern 1101 has been received D. The last bit received was 0 and the one before it 0 Answer: B. S110 means the last three bits are 110, so one more 1 will complete 1101. (Key point: State meaning) 4. How is the FSM split into processes in the VHDL code? A. One process for the state register with asynchronous reset, one for next-state and output logic B. One process per state C. One process for z only and none for state D. A single process with no sensitivity list Answer: A. The first process (clk, rst) updates state; the second (state, x) is combinational and computes next_state and z. (Key point: Two-process FSM coding) ## Related in Embedded System - [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 - [Use of VHDL; decoder design](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-use-decoder) — Embedded System, chapter 9 - [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 - [VHDL models; full adder structural](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-models-full-adder-structural) — Embedded System, chapter 9 - [VHDL architectures; elevator controller](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-architectures-elevator) — Embedded System, chapter 9 ## Related in other subjects - [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 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 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×