Implementing a digital filter - via convolution or difference equation?

Question

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:

• Apple's accelerometer filter code implements a difference equation.

• This Stackoverflow question of How to implement a LowPass Filter? suggests the use of a difference equation.

• The Wikipedia article on low-pass filter provides an algorithm using a difference equation.

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?

Answer 1

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.