Implementing a digital filter - via convolution or difference equation?

3
votes

I'm a very experienced software engineer, and I've taken some EE classes in college. I'm programming on iPhone and Android, and I want to implement digital filters (e.g. low-pass, band-pass, band-stop, etc.) for real-time microphone and accelerometer data.

I know that there are multiple, equivalent ways to implement a digital filter on a window of time-domain samples. Two approaches I'm looking at are:

  1. Implementing a difference equation directly in C/Java code (e.g. y[i] = y[i-1] + 2 * x[i]). I believe this can run in O(N) time, where N is the length of the sample window, e.g. N=512.

  2. Implementing the convolution between the sample window and the time-domain representation of an FIR filter, typically some form of sinc function. I asked this question awhile ago. This can be done in O(N lg N) if you use fast-convolution involving FFT and IFFT.

Now, from reading various online resources, I've found that the preferred, conventional-wisdom approach for C/Java programming is (1) above, implementing a difference equation. Is this a correct conclusion?

Here is what I've found:

So in summary, my questions really are:

  1. Is implementing a difference equation (rather than through fast convolution) the way to go for writing filters in C/Java?

  2. None of the references above say how to design a difference equation given specific cut-off frequencies or band-stop frequencies. I know I studied this awhile ago. Are there are any filter references for programmers with this kind of information?

3
androidiphoneaudiosignal-processingfft
Three questions: 1. If you implement your filter as y[n] = x[n] + 2*x[n-1] + 3*x[n-2] + 1*x[n-3], would you call that a difference equation or convolution? 2. Do you want to do an IIR or FIR filter? 3. Fixed point or floating point implementation? - mtrw
1. I would think that's a difference equation, right? A convolution operation uses the typical multiply-and-add operation between the signal and FFT values, while a fast convolution uses FFT and IFFT. 2. IIR or FIR doesn't matter as long as it's fast, but if I remember correctly, FIR is alway stable but requires more coefficients. 3. I guess floating-point since the microphone and accelerometer data can be floats? - stackoverflowuser2010

3 Answers

3
votes

The time domain difference equation is convolution. What you're thinking of with the FFT-based approach is frequency domain convolution aka fast convolution, which is really just a performance optimisation - it's mathematically equivalent to time domain convolution. Typically direct time domain convolution is faster for small filter lengths while the frequency domain approach wins when the filter length is large. As a rule of thumb, for 1D filtering "large" means, say, N > 50.

In the above paragraph we're just talking about FIR filters. For IIR filters frequency domain convolution is not an option (unless you truncate the impulse response at some arbitrary point), but typically IIR filters tend to be relatively short compared to FIR filters.

In order to generate filter coefficients (ie. design a filter) you typically start with a filter specification and then use one of many existing software packages to generate coefficients. You can implement your own filter design routine if you really want to - look at algorithms such as Remez exchange.

3
votes

Low-order IIR filters (using short difference equations) can be computationally much faster than either FIR convolution, or fast convolution using FFTs, if they meet your filter specification. They are also similar to low-component-count analog filters with which a circuit designer might be familiar.

If you don't have a sophisticated filter specification or requirement (one that can't be approximated closely enough in a small number of poles and zeros), why burn more CPU cycles on a FIR or FFT? But if you do need a more specialized filter, then you do.

Here is a very commonly used recipe for determining IIR coefficients for biquads. biquad IIR filters can also be cascaded for higher order filtering.

0
votes

I'll second the suggestion to use traditional time-domain digital filters, i.e., using delays, adders, and multipliers. For simple real-time filtering, this approach is likely faster and less complex.

Using FFTs in a real-time application is fine depending on the goal. For example, if you want to do real-time spectral analysis (say, for a machine learning task involving audio), then FFTs work well because they are fast, easy, and can give high spectral resolution.

Your comment is correct about FIR vs. IIR. If you give some (example) filter specifications, then we may be able to give more help as to which filter type to choose, and how to define the filter taps (i.e., coefficients). For example, if you have access to Matlab or Python-Scipy, you could use those to design your filters.

(Check out dsp.stackexchange for more on signal processing.)