0
$\begingroup$

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.

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

1 Answer 1

0
$\begingroup$

The most common alternative is overlap add/save method that leverages the FFT algorithm (https://en.wikipedia.org/wiki/Overlap%E2%80%93add_method). The break even point for most architectures is typically around 64 or 128 tap filter lengths, but that depends a lot on the properties of the computation platform.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.