# How to make the FIR convolution sum more efficient for continuously filtered signal?

So I want to continuously filter a signal with a causal FIR filter $$h$$ such that at every sample timestep, I add a new sample to my current set of samples and remove the oldest sample in that set and perform the same FIR filtering on the resulting new set of samples.

Currently I am just calculating the filter's convolution sum

$$y[n]=\sum_{k} (x[n]h[n-k])$$

by just adding the scaled and shifted elements in $$h$$, which means that $$y[0]$$ requires one term in the above summation, $$y[1]$$ requires two terms in the above summation, etc.

Despite the savings for the earlier time indices, for N samples my current implementation is still $$O(N^2)$$, so I was wondering is there any way to make the convolution sum more efficient by reusing calculations I did for the old set of samples for the very similar push-pop new sample set? Also, if there is not would it be better to just implement the LTI discrete integration? I think this is $$O(N)$$ with each of the $$N$$ sample integrations being a constant number of multiplications and additions, so I was wondering for large N if this would be better.

• There is something called "fast convolution" which uses the FFT. It changes the cost from $O(N^2)$ to $O(N \log(N))$. Apr 2 at 23:32
• Are you implementing this offline or in real-time? Apr 3 at 1:02
• Trying for real time. Apr 3 at 15:35

The major downside is latency: the algorithm has an inherent latency of $$N$$ where $$N$$ is the length of the filter . There are different "hybrids" methods to trade off latency against efficiency if needed. These are often referred to as "block convolvers" and can be done with with constant or staggered sub-block sizes.