What are the problems with designing an FIR filter using FFT?

Question

I'm trying to get an understanding of the relationship between an FIR filter designed from "first principles" using a filter kernel with convolution, and a filter designed in one of two ways using FFT (see below).

As far as I understand, the impulse response of an FIR filter is the same thing as the filter's convolution kernel. (Correct me if I'm wrong.)

Also, in my understanding, the component frequencies (i.e. Fourier transform) of an FIR filter's impulse response is the same thing as the filter's frequency response. And, therefore, the inverse fourier transform will give me back the impulse response.(Again, correct me if I'm wrong).

This leads me to two conclusions (ignoring phase response, or assuming linear phase response):

1. I should be able to design an FIR filter of arbitrary frequency response by "drawing" my desired frequency response, taking an IFFT to get the impulse response, and using that as my convolution kernel.

2. Alternatively, I should be able to create a filter by taking the FFT of the input signal, multiplying by my desired arbitrary frequency response in the frequency domain, and taking an IFFT of the result to produce the output signal.

Intuitively, it feels like 1 & 2 are equivalent, but I'm not sure if I could prove that.

It seems like people (and DSP literature) go to great lengths to design FIR kernels with predefined responses, using complicated (to me) algorithms like Chebyshev or Remez (I'm throwing out some names I've read, without really understanding them).

• Why go to these lengths, when an FFT/IFFT transform exists for every possible FIR kernel?
• Why not simply draw the exact frequency response you desire, take an IFFT, and there's your FIR kernel (method 1 above)?

Answer 1

One reason you see people designing FIR filters, rather than taking a direct approach (like both 1 and 2) is that the direct approach usually fails to take into account the periodicity in the frequency domain, and the fact that convolution implemented using an FFT is circular convolution.

What does this mean?

Suppose you have a signal $x = [ 1, 2, 3, 4]$ and a filter impulse response (convolution kernel; you are correct they are the same) $h = [ 1, 1 ]$.

The convolution $y = x *h$ is $[1, 3, 5, 7, 4]$, a 5-length vector. If you use the FFT (of the wrong length, 4) then the answer you get is $[3, 5, 7, 5]$. The reason for the difference is that the result of linear convolution of these two is length 5, but the result of circular convolution is whatever the FFT length was.

If the FFT length is greater than or equal to the length of the result of linear convolution, then the two are the same. Otherwise, the two are not the same (unless the data somehow conspires to make it so, e.g. if one signal was zero).

Answer 2

One problem is dealing with infinite length transforms that wrap-around when using a finite length FFT. The Fourier transform of a finite length frequency response is an infinite length impulse response or filter kernel. Most people would like their filter to finish before they die or run out of computer memory, so need tricks to produce shorter FIR filters. Just letting the tail of the infinite impulse response wrap-around the FFT, or truncating it short to some generic length, may produce an inferior FIR filter for your desired frequency spec compared against one of the "classical" filter prototypes.

Another problem is that a random "drawn" frequency response very often has an awful response (wild overshoots) between the drawn points at any finite resolution. Convert to a FIR filter, and it rings like crazy. The classical filter prototypes are designed to have frequency response functions that are smooth between the sample points.

Your (2) is called fast convolution, and commonly used if the FFT is longer than the length of the data window plus the filter kernel combined, and proper overlap add/save is used to take care of the start/end of each convolution segment or window (since FFTs are usually blocky in length).

Answer 3

Re 1): Yes, you can design an FIR filter by "drawing" the frequency response (in both magnitude and phase. However, this tends to be very inefficient: the length of the impulse response (and the filter order) is simply pre-determined by your FFT length. If you chose a 128 point FFT you get 128 taps for impulse response and if you chose 4096 point FFT you get 4096 filter taps.

Re 2): Yes, you can filter by multiplication in the frequency domain and that's indeed the only way to do it efficiently for large impulse responses. However, as Peter K has pointed out, multiplication in the frequency domain corresponds to circular convolution. The most common way to implement linear convolution are "overlap add" or "overlap save" algorithms (easily googled).

Answer 4

I am not sure I understand everything that was said here, but I would like to make the case for the Fourier Transform method.

First, it is an incredibly flexible and straightforward way to design FIR filters. As you said, all that needs to be done is to define the magnitude and phase responses. However, as was said, you do need to be a bit careful how you define the response. An arbitrary response may require an inordinately large number of taps to implement and give a terrible time domain response. So be careful how you define it.

Secondly, it is truly the case that the Parks McClellan method for example, can generate a better filter than the Fourier method for some specific requirements, but its not easy to control tap count and also define the magnitude, phase, and step response with that method.

For example, suppose you want to design an FIR filter with characteristics similar to a 10 pole IIR Bessel, but you want to narrow up the transition band a bit (at the expense of step response overshoot). Then the Fourier method makes this an easy problem to solve with about 22 taps, depending on how much the transition band is narrowed.

If you want to see what the Fourier method is capable of, try this FIR program http://www.iowahills.com/5FIRFiltersPage.html (it's free). It can, for example, design IIR equivalents to the Gauss, Bessel, Butterworth, and Inverse Chebyshev filters. In general, it allows you to adjust a filter's response to almost anything, which is the Fourier method's strong point. On the down side, the filters are probably not optimal for some specific requirements.

Answer 5

AFAIK this is so called "naive filtering approach". You can influence spectral content at certain points in frequency space, but you don't do anything useful for frequency content between those points. If you design proper FIR filter, you actually take into account also points in between those principal points and such filter is much better then the first one..

Regards, Bul.

Answer 6

For method 1, by taking IFFT of desired $H[\omega]$, you will likely get a impulse response $h[n]$ in complex numbers, which means the output of the filter $y[n]$ will be complex numbers too.