VHDL FSM pattern checker

Question

I'm trying to write some vhdl that detects a given pattern in a string of bits. The circuit should output 1 when it finds the pattern "110" in the input stream. My input is "X" and my output is "Z".

I'm not sure how to check for an input pattern of "110".

This is what I have so far:

library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity checker is
     Port ( clk : in  STD_LOGIC;
       x : in  STD_LOGIC;
       z : out  STD_LOGIC);
end checker;

architecture Behavioral of checker is

   type state_type is (S0, S1, S2);
   signal pr_state: state_type := S0;
   signal nx_state: state_type := S0;

 begin

process(clk) begin
  if (rising_edge(clk)) then
      pr_state <= nx_state;
  end if;
end process;

process(pr_state, nx_state) begin

case (pr_state) is 

    when S0 =>  
        z <= '0';
        nx_state <= S1;

    when S1 => 
        z <= '0';
        nx_state <= S2;

    when S2 => 
        z <= '1';
        nx_state <= S0;

end case;

end process;

end Behavioral;

Any thoughts? Appreciate your feedback.

Answer 1

If the FSM is required, the simplest might just be to walk through the possibilities:

achictecture behavior of checker is
   types states is (SEARCHING, SAW_1, SAW_11, SAW_110);
   signal state : states := SEARCHING;

begin
   process (clk) begin
      if rising_edge(clk) then
         case (state) is
         when SEARCHING:
            if (z = '1') then
               state <= SAW_1;
            else
               state <= SEARCHING;
            end if;
            z <= '0';

         when SAW_1:
            if (z = '1') then
               state <= SAW_11;
            else
               state <= SEARCHING;
            end if;
            z <= '0';

         when SAW_11:
            if (z = '0') then
               state <= SAW_110;
            else
               state <= SEARCHING;
            end if;
            z <= '0';

         when SAW_110:
            state <= SEARCHING;
            z <= '1';

         end case;

      end if;
   end process;
end architecture behavior;

This uses a different FSM structure than your original code and can be improved a bit (at least 1 state can be removed), but I think it illustrates the point.

Answer 2

A state machine over complicates this (unless there is some requirement to use sate logic). Its reasonable to just use a shift register and a comparitor. Assuming "110" means that the '1' is the first bit received, you could do something like the following (Warning! I didn't test this code.):

architecture Behavioral of checker is
   signal shift_reg : std_logic_vector(2 downto 0) := "000";

begin
  process(clk) begin
      if rising_edge(clk) then

         -- Assert the output signal if the pattern is found
         if (shift_reg = "110") then
            z <= '1';
         else
            z <= '0';
         end if;

         -- Keep a 3-bit deep buffer for comparison.
         shift_reg(2 downto 0) <= shift_reg(1 downto 0) & x;

      end if;
   end process;
end architecture Behavioral;