2
$\begingroup$

Does there exist a discrete low-pass filter algorithm that is greatly more computationally efficient for high-order (e.g. greater than 10) low-pass filters than straightforward methods like series of IIR Butterworth filters?

$\endgroup$
  • $\begingroup$ You generally don't want to put low pass filter designs in series to increase the order. It is better to design the filter directly at the intended order and then split it up into second order sections and put those in series. And that only because it improves the numerical precision and is often even required to get something stable. $\endgroup$ – Jazzmaniac Nov 20 '13 at 13:01
3
$\begingroup$

You can implement very efficient high order low pass filter using cumulative summing. The theory is as follows. A perfect integrator has the recursive definition

$$y[n] = y[n-1]+x[n]$$

If you take the delayed difference of the output as in $$y'[n] = y[n] - y[n-d]$$

you are realizing a boxcar filter of length $d-1$, as can be seen from explicitly resolving the recursion for $y[n]$ in $y'[n]$:

$$ y'[n] = (y[n-1]+x[n]) - y[n-d]$$

$$ y'[n] = ((y[n-2] + x[n-1]) + x[n]) - y[n-d]$$

$$ \dots$$

$$ y'[n] = y[n-d] + \sum_{k=1}^{d-1}x[n-k] - y[n-d] = \sum_{k=1}^{d-1}x[n-k]$$

That means you have a low pass filter of effective order $d-1$ from just one addition and one subtraction per sample.

Of course, boxcars are only useful up to a certain point. But the same idea can be generalized to a larger class of filters with a trade off between filter shape and computational effort. And that is done by concatenating several integrator-difference stages.

Two in series will generate a triangular impulse response, three a parabolic one, and so on. Each stage convolves the output with yet another boxcar. In the frequency domain the original sinc() shaped response is taken to the n-th power (or if you have different delay lengths for the different stages, multiplied by other differently scaled sincs).

But both response sequences in time and frequency domain behave very predictably, because the central limit theorem of statistics predicts that the time domain response quickly approaches a Gaussian distribution. And because the fourier transform of a Gaussian is also Gaussian, you'll get a very good approximation of a Gaussian frequency response low pass filter after only a few stages.

One note about numerical precision though. Because you are integrating, the content of the delay buffer can be become very large and the difference precision suffers. This can be resolved by making the integrator leaky, so that it doesn't accumulate a constant function up to infinity. The leaky integrator difference equation is

$$ y[n] = (1-\epsilon) y[n-1] + x[n] $$

for some sufficiently small positive $\epsilon$.

$\endgroup$
  • $\begingroup$ You can also implement a recursive boxcar filter by just keeping a windowed accumulator. For an $N$-point average, at each input sample you add the new one, subtract the one $N$ samples before it, and then divide by $N$ to get the filtered output. This has the advantage that the accumulator won't blow up to large values, but over time, floating-point roundoff errors can accumulate and become significant. Therefore, it is advisable to, every so often, reinitialize the accumulator value by summing the last $N-1$ samples. $\endgroup$ – Jason R Nov 20 '13 at 14:30
  • $\begingroup$ I'm not sure I follow. I don't see any term in those equations that controls the cutoff frequency. $\endgroup$ – Justin Olbrantz Nov 20 '13 at 17:44
  • $\begingroup$ @JustinOlbrantz, the cutoff frequency is inversely related to the length of the boxcar, i.e. the delay $d$. The exact 3dB point depends on the number of stages, so you best calculate the filter response for whichever order you want and read off the cutoff frequency as it appears to you. $\endgroup$ – Jazzmaniac Nov 20 '13 at 18:11
  • $\begingroup$ I'm guessing this is what you were thinking of? embedded.com/design/configurable-systems/4006446/… I'm currently reading it. Much thanks for pointing it out. $\endgroup$ – Justin Olbrantz Nov 21 '13 at 6:18
  • $\begingroup$ To be honest I didn't know this had a name, but it seems to be what I had in mind! $\endgroup$ – Jazzmaniac Nov 21 '13 at 10:07
1
$\begingroup$

Depends on the requirement for your low pass filter. For anything that needs to be steep, an IIR filter is the way to go. Typically you get the lowest order with an elliptic filter: you can trade off pass band ripple, stop band attenuation and steepness. Let's say you want a audio (sample rate = 44100 Hz) filter that's not more than 1 dB down at 1kHz but 60 dB down at 2 kHz and above. With a Butterworth that requires roughly 11th order. You can get the same thing with a 5th order elliptic filter. Reducing the passband ripple to 0.1dB increases the elliptic order to 6.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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