FIR Filter

From Hamsterworks Wiki!

Jump to: navigation, search

To give you some idea what bare-metal FPGA development can be like, here is how to implement a 999-point FIR filter using a 18x18 DSP block. I have yet to test any of this so it is going to have some errors in it!

In C this would be roughly equivalent to:

int n;
int m[1024];
int k[1024] = {... filter kernel ....};

long long filter(sample_in)
{
  int j;
  long long a = 0;

  m[n++] = sample_in;

  for(j = 0; j  < 999; j++)
    a  = a + m[(n+j)&0x3ff] * k[j];
  return a;
}

A few questions:

  • How long will this take to process each sample?
  • Can you guarantee that it always take the same length of time?
  • Would you trust this code to filter something important, like the feedback loop in a power supply?
  • If this runs at 100MHz, can you predict if this will keep up with a 48kHz stream of samples?

Here's how the it would be done in a generic HDL. First off, HDLs need you to explicitly define your data:

  • 'n' and 'j' are 10-bit registers,
  • m[]' and 'k[]' are 1024x18-bit memories - 'k[]' holds the filter kernel
  • 'a' is the 48 bit accumulator of a DSP slice.
every clock cycle
  if new_sample_in = 1 then
    m[n] <= sample_in;
    j <= 0;
    a <= 0;
    n++;	
    new_sample_out <= '0';
  else if j < 999 then
    a <= a + m[n+j] * j[j];
    j++;
    new_sample_out <= '0';
  else if j = 999 then
    filter_out <= a;
    new_sample_out <= '1';
    j++;
  else
    new_sample_out <= '0';
  end if;

And now asking the same questions again:

  • How long will this take to process each sample? 1002 cycles
  • Can you guarantee that it always take the same length of time? Yes, Always, FPGAs have no task switching, interrupts or drivers to cause jitter.
  • Would you trust this code to filter something important, like the feedback loop in a large power supply? Yes.
  • If this runs at 100MHz, will it keep up with a 48kHz stream of samples? Yes. And it will work at up to 99,800 samples per second

Because this is all fixed point calculations is no rounding errors that occur at runtime - were this implemented using floating point the round off errors are unpredictable - towards the end of the calculation small values in m[] or k[] may have no impact on the final result.

And now in VHDL, with some optimizations

This is all in one file except for "kernel_memory" which is a 1024x18-bit signal port ROM, sample_memory is a single port Block RAM.

----------------------------------------------------------------------------------
-- Engineer: Mike Field <hamster@snap.net.nz> 
-- 
-- Module: fir_filter.vdl
--
-- Description: Module to implement an 18-bit FIR filter on 18-bit data
--
-- NOTE: The FIR coefficients must be at the end of kernel_memory (i.e. last 
-- coefficient should be stored at address
----------------------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity fir_filter is
    Port ( clk             : in  STD_LOGIC;
           data_in         : in  STD_LOGIC_VECTOR (17 downto 0);
           data_in_strobe  : in  STD_LOGIC;
           data_out        : out  STD_LOGIC_VECTOR (17 downto 0);
           data_out_strobe : out  STD_LOGIC);
end fir_filter;

architecture Behavioral of fir_filter is
   constant FIR_LENGTH : natural := 300;

   COMPONENT sample_memory
      PORT (
         clk  : IN STD_LOGIC;
         we   : IN STD_LOGIC;
         addr : IN STD_LOGIC_VECTOR(9 DOWNTO 0);
         din  : IN STD_LOGIC_VECTOR(17 DOWNTO 0);
         dout : OUT STD_LOGIC_VECTOR(17 DOWNTO 0)
      );
   END COMPONENT;
    
   COMPONENT kernel_memory
      PORT (
         clk  : IN STD_LOGIC;
         addr : IN STD_LOGIC_VECTOR(9 DOWNTO 0);
         dout : OUT STD_LOGIC_VECTOR(17 DOWNTO 0)
      );
   END COMPONENT;
 
   signal data_index     : unsigned(9 downto 0)          := (others => '0');
   signal write_address  : unsigned(9 downto 0)          := (others => '0');
   signal kernel_data    : std_logic_vector(17 downto 0) := (others => '0');
   signal memory_data    : std_logic_vector(17 downto 0) := (others => '0');
   signal memory_address : std_logic_vector(9 downto 0)  := (others => '0');
   signal kernel_address : std_logic_vector(9 downto 0)  := (others => '0');
   signal reset_total    : std_logic                     := '0';

   signal total : signed (41 downto 0) := (others => '0');
begin

  -- a read-only memory block to hold the filter kernel
kernel : kernel_memory
  PORT MAP (
    clk  => clk,
    addr => kernel_address,
    dout => kernel_data
  );

  -- a r/w memory block to hold the incoming samples.
memory : sample_memory
  PORT MAP (
    clk  => clk,
    we   => data_in_strobe,
    addr => memory_address,
    din  => data_in,
    dout => memory_data
  );
  
   -- THIS SHIFT WILL NEED TO BE ADJUSTED FOR YOUR FILTER.
   -- for zero gain the total of all the kernel constants should 
   -- be scaled to match the divison-by-shifting you choose here.
   data_out       <= std_logic_vector(total(34 downto 17));
   
   memory_address <= std_logic_vector(write_address + data_index);
   kernel_address <= std_logic_vector(data_index);

process(clk)

   begin
      if rising_edge(clk) then
         -- accmulate the running total unless the reset flag is seen
         if reset_total = '1' then
            total <= (others => '0');
         else
            total <= total + signed(memory_data) * signed(kernel_data);
         end if;
         
         -- Set defaults
         data_out_strobe <= '0';
         reset_total     <= '0';
         
         if data_in_strobe = '1' then
            -- if new data has arrived then move write the pointer to the next 
            -- address and reset the accumulator
            reset_total     <= '1';
            write_address <= write_address+1;

            -- we're going to use the last 'FIR_LENGTH' values written to memory
            data_index    <= TO_UNSIGNED(1024-FIR_LENGTH,10);

         elsif data_index = 0 then
            if reset_total = '0' then
               -- As we have processed the sample, but have yet to reset 
               -- the accumulator then we should output the total to
               -- the downstream logic
               data_out_strobe <= '1';
            end if;
            
            -- when data_index comes back to zero we have processed all the data
            reset_total     <= '1';
         else
            data_index <= data_index + 1;
         end if;
      end if;
   end process;
end Behavioral;

And here is a sample filter kernel:

----------------------------------------------------------------------------------
-- Engineer: Mike Field <hamster@snap.net.nz> 
-- 
-- Module: kernel_memory.vhd
--
-- Description: Kernel for a low pass FIR filter
----------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity kernel_memory is
    Port ( clk  : in  STD_LOGIC;
           addr : in  STD_LOGIC_VECTOR (9 downto 0);
           dout : out STD_LOGIC_VECTOR (17 downto 0));
end kernel_memory;

architecture Behavioral of kernel_memory is
begin
process(clk)
   begin
      if rising_edge(clk) then
         case addr is
            -- Low pass filter, @ 0.01fc (480Hz)
            when "1111111111" => dout <= "000000000000000010"; --          2
            when "1111111110" => dout <= "000000000000000010"; --          2
            when "1111111101" => dout <= "000000000000000010"; --          2
            when "1111111100" => dout <= "000000000000000010"; --          2
            when "1111111011" => dout <= "000000000000000010"; --          2
            when "1111111010" => dout <= "000000000000000010"; --          2
            when "1111111001" => dout <= "000000000000000011"; --          3
            when "1111111000" => dout <= "000000000000000011"; --          3
            when "1111110111" => dout <= "000000000000000011"; --          3
            when "1111110110" => dout <= "000000000000000011"; --          3
            when "1111110101" => dout <= "000000000000000011"; --          3
            when "1111110100" => dout <= "000000000000000100"; --          4
            when "1111110011" => dout <= "000000000000000100"; --          4
            when "1111110010" => dout <= "000000000000000100"; --          4
            when "1111110001" => dout <= "000000000000000100"; --          4
            when "1111110000" => dout <= "000000000000000100"; --          4
            when "1111101111" => dout <= "000000000000000100"; --          4
            when "1111101110" => dout <= "000000000000000100"; --          4
            when "1111101101" => dout <= "000000000000000100"; --          4
            when "1111101100" => dout <= "000000000000000100"; --          4
            when "1111101011" => dout <= "000000000000000100"; --          4
            when "1111101010" => dout <= "000000000000000011"; --          3
            when "1111101001" => dout <= "000000000000000011"; --          3
            when "1111101000" => dout <= "000000000000000010"; --          2
            when "1111100111" => dout <= "000000000000000001"; --          1
            when "1111100110" => dout <= "000000000000000000"; --          0
            when "1111100101" => dout <= "111111111111111111"; --         -1
            when "1111100100" => dout <= "111111111111111101"; --         -3
            when "1111100011" => dout <= "111111111111111011"; --         -5
            when "1111100010" => dout <= "111111111111111001"; --         -7
            when "1111100001" => dout <= "111111111111110111"; --         -9
            when "1111100000" => dout <= "111111111111110100"; --        -12
            when "1111011111" => dout <= "111111111111110001"; --        -15
            when "1111011110" => dout <= "111111111111101110"; --        -18
            when "1111011101" => dout <= "111111111111101010"; --        -22
            when "1111011100" => dout <= "111111111111100110"; --        -26
            when "1111011011" => dout <= "111111111111100010"; --        -30
            when "1111011010" => dout <= "111111111111011101"; --        -35
            when "1111011001" => dout <= "111111111111011000"; --        -40
            when "1111011000" => dout <= "111111111111010011"; --        -45
            when "1111010111" => dout <= "111111111111001110"; --        -50
            when "1111010110" => dout <= "111111111111001000"; --        -56
            when "1111010101" => dout <= "111111111111000010"; --        -62
            when "1111010100" => dout <= "111111111110111011"; --        -69
            when "1111010011" => dout <= "111111111110110101"; --        -75
            when "1111010010" => dout <= "111111111110101110"; --        -82
            when "1111010001" => dout <= "111111111110100111"; --        -89
            when "1111010000" => dout <= "111111111110100000"; --        -96
            when "1111001111" => dout <= "111111111110011001"; --       -103
            when "1111001110" => dout <= "111111111110010010"; --       -110
            when "1111001101" => dout <= "111111111110001011"; --       -117
            when "1111001100" => dout <= "111111111110000100"; --       -124
            when "1111001011" => dout <= "111111111101111101"; --       -131
            when "1111001010" => dout <= "111111111101110111"; --       -137
            when "1111001001" => dout <= "111111111101110001"; --       -143
            when "1111001000" => dout <= "111111111101101100"; --       -148
            when "1111000111" => dout <= "111111111101100111"; --       -153
            when "1111000110" => dout <= "111111111101100010"; --       -158
            when "1111000101" => dout <= "111111111101011111"; --       -161
            when "1111000100" => dout <= "111111111101011100"; --       -164
            when "1111000011" => dout <= "111111111101011010"; --       -166
            when "1111000010" => dout <= "111111111101011010"; --       -166
            when "1111000001" => dout <= "111111111101011010"; --       -166
            when "1111000000" => dout <= "111111111101011100"; --       -164
            when "1110111111" => dout <= "111111111101011111"; --       -161
            when "1110111110" => dout <= "111111111101100100"; --       -156
            when "1110111101" => dout <= "111111111101101011"; --       -149
            when "1110111100" => dout <= "111111111101110011"; --       -141
            when "1110111011" => dout <= "111111111101111101"; --       -131
            when "1110111010" => dout <= "111111111110001001"; --       -119
            when "1110111001" => dout <= "111111111110010111"; --       -105
            when "1110111000" => dout <= "111111111110100111"; --        -89
            when "1110110111" => dout <= "111111111110111010"; --        -70
            when "1110110110" => dout <= "111111111111001111"; --        -49
            when "1110110101" => dout <= "111111111111100110"; --        -26
            when "1110110100" => dout <= "000000000000000000"; --          0
            when "1110110011" => dout <= "000000000000011100"; --         28
            when "1110110010" => dout <= "000000000000111011"; --         59
            when "1110110001" => dout <= "000000000001011101"; --         93
            when "1110110000" => dout <= "000000000010000010"; --        130
            when "1110101111" => dout <= "000000000010101001"; --        169
            when "1110101110" => dout <= "000000000011010011"; --        211
            when "1110101101" => dout <= "000000000011111111"; --        255
            when "1110101100" => dout <= "000000000100101111"; --        303
            when "1110101011" => dout <= "000000000101100000"; --        352
            when "1110101010" => dout <= "000000000110010101"; --        405
            when "1110101001" => dout <= "000000000111001100"; --        460
            when "1110101000" => dout <= "000000001000000110"; --        518
            when "1110100111" => dout <= "000000001001000001"; --        577
            when "1110100110" => dout <= "000000001001111111"; --        639
            when "1110100101" => dout <= "000000001011000000"; --        704
            when "1110100100" => dout <= "000000001100000010"; --        770
            when "1110100011" => dout <= "000000001101000110"; --        838
            when "1110100010" => dout <= "000000001110001011"; --        907
            when "1110100001" => dout <= "000000001111010011"; --        979
            when "1110100000" => dout <= "000000010000011011"; --       1051
            when "1110011111" => dout <= "000000010001100100"; --       1124
            when "1110011110" => dout <= "000000010010101111"; --       1199
            when "1110011101" => dout <= "000000010011111010"; --       1274
            when "1110011100" => dout <= "000000010101000101"; --       1349
            when "1110011011" => dout <= "000000010110010000"; --       1424
            when "1110011010" => dout <= "000000010111011100"; --       1500
            when "1110011001" => dout <= "000000011000100110"; --       1574
            when "1110011000" => dout <= "000000011001110001"; --       1649
            when "1110010111" => dout <= "000000011010111010"; --       1722
            when "1110010110" => dout <= "000000011100000010"; --       1794
            when "1110010101" => dout <= "000000011101001001"; --       1865
            when "1110010100" => dout <= "000000011110001110"; --       1934
            when "1110010011" => dout <= "000000011111010001"; --       2001
            when "1110010010" => dout <= "000000100000010010"; --       2066
            when "1110010001" => dout <= "000000100001010000"; --       2128
            when "1110010000" => dout <= "000000100010001100"; --       2188
            when "1110001111" => dout <= "000000100011000101"; --       2245
            when "1110001110" => dout <= "000000100011111010"; --       2298
            when "1110001101" => dout <= "000000100100101100"; --       2348
            when "1110001100" => dout <= "000000100101011011"; --       2395
            when "1110001011" => dout <= "000000100110000110"; --       2438
            when "1110001010" => dout <= "000000100110101100"; --       2476
            when "1110001001" => dout <= "000000100111001111"; --       2511
            when "1110001000" => dout <= "000000100111101101"; --       2541
            when "1110000111" => dout <= "000000101000000111"; --       2567
            when "1110000110" => dout <= "000000101000011100"; --       2588
            when "1110000101" => dout <= "000000101000101100"; --       2604
            when "1110000100" => dout <= "000000101000111000"; --       2616
            when "1110000011" => dout <= "000000101001000000"; --       2624
            when "1110000010" => dout <= "000000101001000010"; --       2626
            when "1110000001" => dout <= "000000101001000000"; --       2624
            when "1110000000" => dout <= "000000101000111000"; --       2616
            when "1101111111" => dout <= "000000101000101100"; --       2604
            when "1101111110" => dout <= "000000101000011100"; --       2588
            when "1101111101" => dout <= "000000101000000111"; --       2567
            when "1101111100" => dout <= "000000100111101101"; --       2541
            when "1101111011" => dout <= "000000100111001111"; --       2511
            when "1101111010" => dout <= "000000100110101100"; --       2476
            when "1101111001" => dout <= "000000100110000110"; --       2438
            when "1101111000" => dout <= "000000100101011011"; --       2395
            when "1101110111" => dout <= "000000100100101100"; --       2348
            when "1101110110" => dout <= "000000100011111010"; --       2298
            when "1101110101" => dout <= "000000100011000101"; --       2245
            when "1101110100" => dout <= "000000100010001100"; --       2188
            when "1101110011" => dout <= "000000100001010000"; --       2128
            when "1101110010" => dout <= "000000100000010010"; --       2066
            when "1101110001" => dout <= "000000011111010001"; --       2001
            when "1101110000" => dout <= "000000011110001110"; --       1934
            when "1101101111" => dout <= "000000011101001001"; --       1865
            when "1101101110" => dout <= "000000011100000010"; --       1794
            when "1101101101" => dout <= "000000011010111010"; --       1722
            when "1101101100" => dout <= "000000011001110001"; --       1649
            when "1101101011" => dout <= "000000011000100110"; --       1574
            when "1101101010" => dout <= "000000010111011100"; --       1500
            when "1101101001" => dout <= "000000010110010000"; --       1424
            when "1101101000" => dout <= "000000010101000101"; --       1349
            when "1101100111" => dout <= "000000010011111010"; --       1274
            when "1101100110" => dout <= "000000010010101111"; --       1199
            when "1101100101" => dout <= "000000010001100100"; --       1124
            when "1101100100" => dout <= "000000010000011011"; --       1051
            when "1101100011" => dout <= "000000001111010011"; --        979
            when "1101100010" => dout <= "000000001110001011"; --        907
            when "1101100001" => dout <= "000000001101000110"; --        838
            when "1101100000" => dout <= "000000001100000010"; --        770
            when "1101011111" => dout <= "000000001011000000"; --        704
            when "1101011110" => dout <= "000000001001111111"; --        639
            when "1101011101" => dout <= "000000001001000001"; --        577
            when "1101011100" => dout <= "000000001000000110"; --        518
            when "1101011011" => dout <= "000000000111001100"; --        460
            when "1101011010" => dout <= "000000000110010101"; --        405
            when "1101011001" => dout <= "000000000101100000"; --        352
            when "1101011000" => dout <= "000000000100101111"; --        303
            when "1101010111" => dout <= "000000000011111111"; --        255
            when "1101010110" => dout <= "000000000011010011"; --        211
            when "1101010101" => dout <= "000000000010101001"; --        169
            when "1101010100" => dout <= "000000000010000010"; --        130
            when "1101010011" => dout <= "000000000001011101"; --         93
            when "1101010010" => dout <= "000000000000111011"; --         59
            when "1101010001" => dout <= "000000000000011100"; --         28
            when "1101010000" => dout <= "000000000000000000"; --          0
            when "1101001111" => dout <= "111111111111100110"; --        -26
            when "1101001110" => dout <= "111111111111001111"; --        -49
            when "1101001101" => dout <= "111111111110111010"; --        -70
            when "1101001100" => dout <= "111111111110100111"; --        -89
            when "1101001011" => dout <= "111111111110010111"; --       -105
            when "1101001010" => dout <= "111111111110001001"; --       -119
            when "1101001001" => dout <= "111111111101111101"; --       -131
            when "1101001000" => dout <= "111111111101110011"; --       -141
            when "1101000111" => dout <= "111111111101101011"; --       -149
            when "1101000110" => dout <= "111111111101100100"; --       -156
            when "1101000101" => dout <= "111111111101011111"; --       -161
            when "1101000100" => dout <= "111111111101011100"; --       -164
            when "1101000011" => dout <= "111111111101011010"; --       -166
            when "1101000010" => dout <= "111111111101011010"; --       -166
            when "1101000001" => dout <= "111111111101011010"; --       -166
            when "1101000000" => dout <= "111111111101011100"; --       -164
            when "1100111111" => dout <= "111111111101011111"; --       -161
            when "1100111110" => dout <= "111111111101100010"; --       -158
            when "1100111101" => dout <= "111111111101100111"; --       -153
            when "1100111100" => dout <= "111111111101101100"; --       -148
            when "1100111011" => dout <= "111111111101110001"; --       -143
            when "1100111010" => dout <= "111111111101110111"; --       -137
            when "1100111001" => dout <= "111111111101111101"; --       -131
            when "1100111000" => dout <= "111111111110000100"; --       -124
            when "1100110111" => dout <= "111111111110001011"; --       -117
            when "1100110110" => dout <= "111111111110010010"; --       -110
            when "1100110101" => dout <= "111111111110011001"; --       -103
            when "1100110100" => dout <= "111111111110100000"; --        -96
            when "1100110011" => dout <= "111111111110100111"; --        -89
            when "1100110010" => dout <= "111111111110101110"; --        -82
            when "1100110001" => dout <= "111111111110110101"; --        -75
            when "1100110000" => dout <= "111111111110111011"; --        -69
            when "1100101111" => dout <= "111111111111000010"; --        -62
            when "1100101110" => dout <= "111111111111001000"; --        -56
            when "1100101101" => dout <= "111111111111001110"; --        -50
            when "1100101100" => dout <= "111111111111010011"; --        -45
            when "1100101011" => dout <= "111111111111011000"; --        -40
            when "1100101010" => dout <= "111111111111011101"; --        -35
            when "1100101001" => dout <= "111111111111100010"; --        -30
            when "1100101000" => dout <= "111111111111100110"; --        -26
            when "1100100111" => dout <= "111111111111101010"; --        -22
            when "1100100110" => dout <= "111111111111101110"; --        -18
            when "1100100101" => dout <= "111111111111110001"; --        -15
            when "1100100100" => dout <= "111111111111110100"; --        -12
            when "1100100011" => dout <= "111111111111110111"; --         -9
            when "1100100010" => dout <= "111111111111111001"; --         -7
            when "1100100001" => dout <= "111111111111111011"; --         -5
            when "1100100000" => dout <= "111111111111111101"; --         -3
            when "1100011111" => dout <= "111111111111111111"; --         -1
            when "1100011110" => dout <= "000000000000000000"; --          0
            when "1100011101" => dout <= "000000000000000001"; --          1
            when "1100011100" => dout <= "000000000000000010"; --          2
            when "1100011011" => dout <= "000000000000000011"; --          3
            when "1100011010" => dout <= "000000000000000011"; --          3
            when "1100011001" => dout <= "000000000000000100"; --          4
            when "1100011000" => dout <= "000000000000000100"; --          4
            when "1100010111" => dout <= "000000000000000100"; --          4
            when "1100010110" => dout <= "000000000000000100"; --          4
            when "1100010101" => dout <= "000000000000000100"; --          4
            when "1100010100" => dout <= "000000000000000100"; --          4
            when "1100010011" => dout <= "000000000000000100"; --          4
            when "1100010010" => dout <= "000000000000000100"; --          4
            when "1100010001" => dout <= "000000000000000100"; --          4
            when "1100010000" => dout <= "000000000000000100"; --          4
            when "1100001111" => dout <= "000000000000000011"; --          3
            when "1100001110" => dout <= "000000000000000011"; --          3
            when "1100001101" => dout <= "000000000000000011"; --          3
            when "1100001100" => dout <= "000000000000000011"; --          3
            when "1100001011" => dout <= "000000000000000011"; --          3
            when "1100001010" => dout <= "000000000000000010"; --          2
            when "1100001001" => dout <= "000000000000000010"; --          2
            when "1100001000" => dout <= "000000000000000010"; --          2
            when "1100000111" => dout <= "000000000000000010"; --          2
            when "1100000110" => dout <= "000000000000000010"; --          2
            when "1100000101" => dout <= "000000000000000010"; --          2
            when others       => dout <= (others => '0');
         end case;
      end if;
   end process;
end Behavioral;

Speed

When constricted for 48 MHz the following Fmax is given.

 Design statistics: 
    Minimum period:   6.756ns{1}   (Maximum frequency: 148.017MHz) 

It takes n+2 cycles to process each sample with a FIR kernel of length n - so a single DSP block implementing a 999 point FIR filter could process 147kS per second.

Personal tools