5

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 belowenter image description here

This is the fft, with the lower frequencies towards the ends.

enter image description hereenter image description here

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.

user1084113
  • 213
  • 2
  • 7
  • 1
    This question is close to a duplicate of http://dsp.stackexchange.com/questions/6220/why-is-it-a-bad-idea-to-filter-by-zeroing-out-fft-bins/6224#6224 – hotpaw2 Nov 05 '13 at 19:06
  • Is there a reference that answers just that? –  Dec 31 '13 at 15:08

4 Answers4

12

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.

hotpaw2
  • 35,346
  • 9
  • 47
  • 90
  • 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 05 '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 05 '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 05 '13 at 22:08
  • This is a good post, but I am not sure that I agree with you. You make the argument that if you zero-out particular bins that you are adding that frequency of opposite phase, but not touching frequencies between bins. Fair enough. But how is that different from 'normal filtering'? A 'normal filter' also just shapes your frequency spectrum, but also 'doesn't touch' bins in between. How does what you said not apply to normal filtering? – TheGrapeBeyond Dec 31 '13 at 15:19
  • A "normal" (FIR, IIR) filter is not ideal, only close (leaving a non-zero stop-band ripple). A range of bins (a sufficiently large weighted bunch of nearby bins) can often be composited to produce a close (but not exact) match or cancelation of a "between-bin" sinusoid. Often much closer than zero-ing just the nearest bin or two. – hotpaw2 Dec 31 '13 at 20:12
  • @hotpaw2 "can often be composited to produce a close (but not exact)". Thats the point. Let us forget about ideal VS non-ideal for the time being. Why, is 'normal' filtering using a filter, 'touching' in-between frequencies in a better way than zeroing out co-efficients? Both methods will not ever shape those in-between frequencies. Just because a bunch of bins are zero'd out, or not zero'd out doesnt mean that in-between frequencies are going to be touched any more or less. How is that even possible? – TheGrapeBeyond Jan 01 '14 at 00:29
  • Because a properly weighted combination of a larger number of bins is usually a better match than zeroing a few. Fourier says any (reasonable) waveform of any frequency (including between bins) can be matched by using all the bins. – hotpaw2 Jan 01 '14 at 03:23
  • @hotpaw2 "Because a properly weighted combination of a larger number of bins is usually a better match than zeroing a few." We're going in circles. You are making the claim that zeroing out, say, 100 FFT coefficients will not touch in-between frequencies. However in the same vein you claim that if you weight those 100 FFT coefficients in some way, that you will be touching in-betweens. That does not make sense. – TheGrapeBeyond Jan 01 '14 at 17:50
  • Also, zeroing 100 bins will touch "in between" frequencies, especially near the center of the 100. But not as well near the edges, not 100% as in perfect filtering, and not anywhere near as smooth a response as a properly shaped filter. – hotpaw2 Jan 01 '14 at 19:24
  • 1
    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 01 '14 at 20:15
  • @hotpaw2 you said ... "ONLY with frequencies that are exactly periodic in the FFT length".. what do you mean by term exact period in the FFT lenght ? – user6363 May 31 '17 at 07:33
  • 1
    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 07:56
  • If i am correct then you mean to say ....if for example my sampling frequency is 2400hz & N=2400, then if X[n] is the FFT of the sample sequence.. then only X[1201] is not having any relation to other frequency bin.. while other bins are in conjugate pair.. have i got it right ? – user6363 May 31 '17 at 08:49
  • ok got from this link ... https://dsp.stackexchange.com/questions/8604/fft-of-sine-wave-not-coming-as-expected-i-e-single-point – user6363 May 31 '17 at 10:28
7

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.

PAK-9
  • 810
  • 4
  • 14
3

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.

Hilmar
  • 44,604
  • 1
  • 32
  • 63
  • 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 05 '13 at 17:08
  • 1
    yes. an ideal low pass filter requires infinite number or time domain samples. – Hilmar Nov 05 '13 at 19:22
3

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.

nispio
  • 842
  • 5
  • 12