--- title: "Sequence detector 1011 state diagram and VHDL" subject: "Embedded System" chapter: 9 key: "semester_6/embedded_system:vhdl-sequence-detector-1011" source: https://www.bctengineer.com/q/semester_6/embedded_system/vhdl-sequence-detector-1011 site: BCT Engineering --- # Sequence detector 1011 state diagram and VHDL Embedded System · Chapter 9: Microcontrollers in Embedded Systems - Asked in: 2078 Chaitra - 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-1011 - Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-9 ## Question Draw the state diagram for a sequence detector for the sequence 1011 and then develop a VHDL code based on the state diagram. ## Short answer A Mealy FSM with states S0, S1, S10, S101. Transitions: S0-1->S1/z=0, S1-0->S10/z=0, S10-1->S101/z=0, S101-1->S1/z=1 (overlap allowed), S101-0->S10/z=0. VHDL implements state register and next-state/output logic using a case statement. ## Answer A sequence detector reads a serial bit stream x (one bit per clock) and sets output z = 1 when the last four bits are 1011. Overlapping sequences are allowed (1011011 contains two). A Mealy machine with four states is used: | State | Meaning (bits matched so far) | |---|---| | S0 | none | | S1 | "1" | | S10 | "10" | | S101 | "101" | #### State diagram (Mealy, arc label = input / output) ```text main path: (S0) -1/0-> (S1) -0/0-> (S10) -1/0-> (S101) | back to (S1) <---- 1/1 ----+ other arcs: S0 --0/0--> S0 S1 --1/0--> S1 S10 --0/0--> S0 S101 --0/0--> S10 ``` Notes: from S101 the input 1 completes 1011 (z = 1) and the final 1 is the start of a new match, so the next state is S1. From S101 the input 0 gives 1010, whose last two bits "10" are a prefix, so the next state is S10. #### State table | Present state | x = 0: next / z | x = 1: next / z | |---|---|---| | S0 | S0 / 0 | S1 / 0 | | S1 | S10 / 0 | S1 / 0 | | S10 | S0 / 0 | S101 / 0 | | S101 | S10 / 0 | S1 / 1 | #### VHDL code ```vhdl library ieee; use ieee.std_logic_1164.all; -- Mealy detector for the serial pattern 1011 (overlapping allowed) entity seq_1011 is port ( clk : in std_logic; rst : in std_logic; -- asynchronous, active high x : in std_logic; -- serial input, one bit per clock z : out std_logic -- '1' when 1011 has just been received ); end entity seq_1011; architecture fsm of seq_1011 is type state_t is (S0, S1, S10, S101); signal state, next_state : state_t; begin -- state register process (clk, rst) begin if rst = '1' then state <= S0; elsif rising_edge(clk) then state <= next_state; end if; end process; -- next-state and output logic (Mealy) 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 = '0' then next_state <= S10; else next_state <= S1; end if; when S10 => -- seen 10 if x = '1' then next_state <= S101; else next_state <= S0; end if; when S101 => -- seen 101 if x = '1' then z <= '1'; -- 1011 detected next_state <= S1; -- last 1 can start a new pattern else next_state <= S10; -- 1010: the last "10" is still a prefix end if; end case; end process; end architecture fsm; ``` Simulation with GHDL for the input 1011011010110111101101 gave z = 1 at bit positions 4, 7, 12, 15 and 20, each the last bit of a 1011 (positions 4 and 7 overlap: 1011011). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the 1011 detector, what does state S10 mean? A. No bits matched yet B. The last two received bits are '10', a prefix of 1011 C. The pattern 1011 has just been detected D. The last bit received was 0 only Answer: B. Each state remembers the longest suffix of the input that matches a prefix of 1011; S10 means '10' is matched. (Key point: State meaning) 2. From S101, input 1 completes 1011. Why is the next state S1 and not S0? A. Because the reset is applied after a detection B. Because the final 1 can be the start of a new 1011 match (overlap allowed) C. Because the detector must wait for a 0 D. Because Moore machines never return to S0 Answer: B. Overlap is allowed (1011011), so the last 1 already counts as a matched '1' for the next pattern. (Key point: Overlap handling) 3. From S101, input 0 gives 1010. What is the next state? A. S0 B. S1 C. S10 D. S101 Answer: C. The last two bits of 1010 are '10', which is a prefix of 1011, so the machine goes to S10. (Key point: S101 on input 0) 4. Why is this a Mealy machine, and when is z = 1? A. Output depends only on the state; z = 1 in S101 B. Output depends on state and input; z = 1 in S101 when x = 1 C. Output depends on the clock only; z = 1 on each rising edge D. Output is registered; z = 1 in S0 Answer: B. In the Mealy machine z is set in the next-state process for state S101 with x = 1 (arc 1/1), so it depends on both state and input. (Key point: Mealy output) ## Related in Embedded System - [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 - [GCD processor algorithm and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-gcd-processor) — Embedded System, chapter 9, asked 3× - [LCM processor algorithm and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-lcm-processor) — Embedded System, chapter 9, asked 2× - [Use of VHDL; decoder design](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-use-decoder) — 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 - [VHDL entity, architecture; D flip-flop](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-entity-architecture-dff) — Embedded System, chapter 9 ## Related in other subjects - [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 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× - [Map sequence diagram to pseudo code](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Aorder-model-mapping-pseudocode) — Object Oriented Analysis and Design, chapter 4 - [(7,4) cyclic code with g(x) = x³ + x² + 1 for 1011](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Acyclic-code-7-4-1011-x3x2) — Communication Systems, chapter 8, asked 2×