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

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)?
• My area of interest is digital audio / digital music, in case it's relevant. – bryhoyt Sep 3 '13 at 10:26

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).

• Sure, but why couldn't someone then just make sure the FFT/IFFT sizes are commensurate with the final convolution length? For example, the convolution length is N + M - 1, so just make sure you 'draw' a frequency response in the fourier domain, with length M-1. Why wouldnt that work? Interesting stuff btw. :) – TheGrapeBeyond Sep 3 '13 at 18:49
• @TheGrapeBeyond: No reason at all! It's just that free-hand drawing of the response with only $M-1$ points probably doesn't do what you think it does (in between the points). – Peter K. Sep 3 '13 at 19:07
• A frequency response of length M-1 still has an infinite length impulse response. Which means when you IFFT to get your filtered result, the tail of the filter's impulse response will wrap around (multiple times) and cruft up your final time domain result. Perhaps a little. Perhaps a lot. – hotpaw2 Sep 4 '13 at 1:13

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).

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).

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.

• That does look interesting. I'll have to try the software to really get my head around what's happening -- the webpage doesn't really seem to describe its method in too much detail. From what I can tell, though, it seems like kindof a hybrid where you manipulate the frequency response of a filter prototype generated in a more traditional way. Is that correct? I think what you say is right -- you need to be careful how you define the response, or you'll end up with a huge number of taps. AFAIU, this is the big problem with designing a filter exclusively with the frequency response. – bryhoyt Sep 11 '13 at 20:25

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.