# Removing values from FFT result same as filtering?

I don't quite understand why the textbooks say it is impossible to implement an ideal low pass filter.

If I was to take the FFT of a discrete signal x[n], with Matlab's fft function I'd be returned with a complex sequence X[n] which represents the magnitude of each frequency from 0 to n/2 and is repeated. If I was to then say simply make all the lower frequency bins equal to zero and keep the remaining the same aren't I applying an ideal low pass filter. I am excluding all the frequencies I don't want and keeping the ones I do.

For example say I have the signal below This is the fft, with the lower frequencies towards the ends.  I selectively remove the bins I do not want and keep the ones I do, note I don't actually have Matlab all the images are from a html page.

• This question is close to a duplicate of dsp.stackexchange.com/questions/6220/… – hotpaw2 Nov 5 '13 at 19:06
• Is there a reference that answers just that? – user7426 Dec 31 '13 at 15:08

If you only have a finite number of samples and are using a finite length FFT, then you will end up with a finite number of FFT frequency result bins. Each bin has a one-to-one relationship ONLY with frequencies that are exactly integer periodic in the FFT length. Any other spectrum frequencies that are not exactly periodic in the FFT aperture will not have that one-to-one relationship, but instead will have their energy spattered across the entire FFT result (a sampled periodic Sinc or Dirichlet function). Thus, zero-ing just the nearest neighbor frequency bin will not have the effect you think.

Zero-ing a bin is the same as adding an exactly periodic sinusoid of the same magnitude but of the opposite phase. If what you are trying to filter out is spectrum of a very slightly different frequency from that of the bin center, then instead of zero-ing it out by exact cancellation, the result will be an added beat pattern. Which is not the same as (FIR, IIR) filtering.

ADDED (in regards to ideal filtering) :

The basis vectors of a DFT are all orthogonal to one another. Any other sinusoid (non-periodic-in-aperture) will be orthogonal to none of the basis vectors. Which means it that that sinusoid will be represented, or have some energy end up in every DFT bin (because of not being orthogonal to any bin).

Therefore no subset of all the bins (a sequence of lower FFT/DFT bins for example) can exactly represent that signal. Therefore zero-ing only a sequence of lower bins in an attempt to create a canceling signal will be imperfect, or non-ideal for that signal. Thus a filter created by such a method cannot be ideal.

One might be able to get close for a signal near the center of a large sequence of filter bins. But not for a signal near the edges of any sequence of bins, as a large portion of the signal's energy will be represented by those bins just outside the sharp edge of the filter rectangle.

• It seems like the negative effect would be much more exaggerated when attempting to use the FFT to implement an "ideal" notch filter. Do you think that the negative effects would be less noticeable when suppressing a large portion of the spectrum this way as opposed to a single bin? – nispio Nov 5 '13 at 20:08
• @nispio : Depends. It is true that a larger groups of bins in the vicinity of a signal that one wants to cancel will give one more degrees of freedom in approximating it, and thus likely to be able to be made closer to canceling out the signal. However the problem still remains at the edge of a rectangle of zeros, as any non-periodic-in aperture signal near the edge of the rectangle in the frequency domain will have a large fraction of it's energy just outside the rectangle, possibly of the same sign and thus likely to be amplified instead of cancelled by zeroing a nearby set of bins. – hotpaw2 Nov 5 '13 at 21:46
• This is a very insightful explanation! I agree with you that the effects on the spectrum will be fundamentally different than FIR/IIR filtering, but I had never thought about it in these terms before. – nispio Nov 5 '13 at 22:08
• Also note that, technically, zero-ing bins is in fact a filter, just a very bad filter, with lots of ripples in the stop and pass band response, especially near the edges of those bands. Other weights can be much better for a flatter (closer to zero on average) stop band. – hotpaw2 Jan 1 '14 at 20:15
• A pure unmodulated sinusoid whose period is an exact integer submultiple of an DFTs length will correspond to exactly 1 basis vector, and thus appear in only one FFT result bin (and in the complex conjugate image for strictly read signals). – hotpaw2 May 31 '17 at 7:56

Is removing values from FFT result same as filtering?

Yes, as one would expect intuitively. Taking the FFT of a signal will give you a frequency domain interpretation of the signal, if you then modify the magnitude of frequency bins and take the inverse FFT you will have a signal which is 'filtered'.

Why is this not an 'ideal' (low pass) filter?

Consider the time domain representation of a brick wall (rectangular) filter in the frequency domain. If we take the inverse Fourier transform of a perfectly rectangular frequency response we get a time domain signal which stretches from -inf to +inf. We cannot take the FFT of a signal which has infinite length, or if we did we would have a frequency domain representation with an infinite number of bins - therefore a rectangular signal that is described by a finite number of bins in the frequency domain is not an 'ideal' filter.

The more samples we have in our original time domain signal the better our frequency resolution will become when we take the Fourier transform, so a brick wall filter will be increasingly close to an ideal filter as the number of time domain samples approaches infinity.

Every FFT has only limited frequency resolution. An ideal lowpass filter requires an FFT of infinite length. Along the same lines: the impulse response of an ideal lowpass filters is a sin(x)/x function which is also infinitely long in time.

• Could you explain what you mean "requires an FFT of infinite length" do you mean I need an infinite number of data samples? – user1084113 Nov 5 '13 at 17:08
• yes. an ideal low pass filter requires infinite number or time domain samples. – Hilmar Nov 5 '13 at 19:22

In practice, I think you will find that you can in fact implement a low-pass filter in the way you specify, and that it will do quite well in terms of filtering out high frequency content. The main reason that this approach is not practical is that it is not suited for real-time processing. In order to even attempt this in real time, I would have to take my signal in chunks, which inherently adds high-frequency content. You could mitigate this effect to some degree with clever windowing, but you can not avoid the fact that a finite-length window has high-frequency content.

The other major setback is computational complexity. Imagine the number of floating-point operations required to do an N-FFT followed by an N-IFFT, with an N as small as 1024. Compare that to the performance you will get out of a much simpler IIR filter which can be run in real time and requires many orders of magnitude less compute power.