Sequence detector 1101 FSM and VHDL

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.

FSM (state diagram), arc label = input / output

 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

VHDL implementation

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).