Forums

Why don't we just zero out FFT bins?

Started by bmh161 April 9, 2009
This is probably a stupid question but, well, I'm not all that smart...

Instead of going through all the trouble of designing complicated digital
filters, why don't we just pick the frequencies that we want to supress and
replace those bins in the FFT with zeros?


>This is probably a stupid question but, well, I'm not all that smart... > >Instead of going through all the trouble of designing complicated
digital
>filters, why don't we just pick the frequencies that we want to supress
and
>replace those bins in the FFT with zeros? > > >
Then, with the undesirable frequencies zeroed out, take the inverse FFT to get back to the time domain.
On Apr 9, 9:29&#2013266080;am, "bmh161" <bmh...@yahoo.com> wrote:
> >This is probably a stupid question but, well, I'm not all that smart... > > >Instead of going through all the trouble of designing complicated > digital > >filters, why don't we just pick the frequencies that we want to supress > and > >replace those bins in the FFT with zeros? > > Then, with the undesirable frequencies zeroed out, take the inverse FFT to > get back to the time domain.
Because the resulting frequency response is often quite awful. If you design a digital filter, then you have control over its response. Clay
On Thu, 9 Apr 2009 06:38:41 -0700 (PDT), clay@claysturner.com wrote:

>Because the resulting frequency response is often quite awful. If you >design a digital filter, then you have control over its response.
And so is the resulting impulse response. Here are two of the MANY ways to think about this: 1. You're falling into the classic "if I just zero the appropriate FFT bins, I'll have a perfect lowpass/bandpass/highpass/whateverpass filter" trap. Consider what happens in-between FFT bins -- you have no control over frequencies that do not correspond to FFT bins, and they will not automatically be zero just because the adjacent FFT bins are zero. If you FFT longer and longer time signals in order to be able to explicitly zero more and more of those in-between frequencies, eventually you will realize that you have to FFT an infinitely long time signal in order to actually accomplish what you desire. 2. A filter that is "rectangular" (nonzero at most frequencies and zero over a small group of frequencies, or zero at most frequencies and nonzero over a small group of frequencies) will have a sinc-like [sine(x)/x] impulse response that extends to infinite time in both directions. This is caused by the fact that multiplying by a rectangular window in the frequency domain is equivalent to convolving with a sinc window in the time domain. Greg
On 9 Apr, 15:22, "bmh161" <bmh...@yahoo.com> wrote:
> This is probably a stupid question but, well, I'm not all that smart... > > Instead of going through all the trouble of designing complicated digital > filters, why don't we just pick the frequencies that we want to supress and > replace those bins in the FFT with zeros?
What do you think the answer is? Besides a generally sadistic attitude by engineers towards students? You asked the right question, but you won't learn anything until you answer it yourself. To give some hints what to look for: - Are there any drawbacks with the 'obvious' approach? - Do the more elaborate methods address or maybe even handle such drawbacks? (Even more hints: The answer to both questions is 'yes'. But that's all the hints I will give.) Rune
Greg Berchin <gberchin@comicast.net.invalid> wrote:
(snip on filtering using FFT)
 
> 1. You're falling into the classic "if I just zero the appropriate FFT > bins, I'll have a perfect lowpass/bandpass/highpass/whateverpass > filter" trap. Consider what happens in-between FFT bins -- you have > no control over frequencies that do not correspond to FFT bins, and > they will not automatically be zero just because the adjacent FFT bins > are zero. If you FFT longer and longer time signals in order to be > able to explicitly zero more and more of those in-between frequencies, > eventually you will realize that you have to FFT an infinitely long > time signal in order to actually accomplish what you desire.
If you take the FFT on a signal that is at least as long as the source, there are no in between bins. However, FFT is O(NlogN), while FIR and IIR filters are O(N). I don't believe that the FFT has to be infinitely long, but it does have to be as long as the source signal.
> 2. A filter that is "rectangular" (nonzero at most frequencies and > zero over a small group of frequencies, or zero at most frequencies > and nonzero over a small group of frequencies) will have a sinc-like > [sine(x)/x] impulse response that extends to infinite time in both > directions. This is caused by the fact that multiplying by a > rectangular window in the frequency domain is equivalent to convolving > with a sinc window in the time domain.
Well, you can't make in infinitely sharp cutoff, but only as sharp as the bin spacing. It helps to think of the signal as periodic (possibly after zero padding), and also the transform as periodic. I did wonder once how long the longest FFT that has ever been done is. It would seem that one could FFT an entire CD, though it is a little more obvious to do each track separately. -- glen
bmh161 wrote:
>> This is probably a stupid question but, well, I'm not all that >> smart... >> >> Instead of going through all the trouble of designing complicated > digital >> filters, why don't we just pick the frequencies that we want to >> supress and replace those bins in the FFT with zeros? > > Then, with the undesirable frequencies zeroed out, take the inverse > FFT to get back to the time domain.
You might want to consider both the resulting overall frequency response and the signal to be processed. All of the general answers deal with the overall frequency response - and that's a very good start. But, the signal to be processed can make a difference as well. Here are some observations, some repeated and others new to the thread: 1) You can see the frequency response you'll get by doing this: a) put those zeros in, just as you'd suggested. I guess then you might be putting 1's everywhere else or some such thing, eh? b) IFFT the result (I don't think you have to append this sequence with zeros before you IFFT - but I could be wrong here). c) append the time sequence from the IFFT with a bunch of zeros. d) FFT the result. This will be an interpolated version of the frequency response. The zeros you put in there will still be there but now you'll be able to see in between them and in between all of the original samples in frequency. If it's a lowpass filter it will look like it's been convolved with a sinc - which corresponds to a gate which has a width the same as the non-zero length of the time sequence. OK. So much for frequency response. Now, let's say that you could create a filter with "brick wall" transitions (yes, limited by the distance between frequency samples). Assume that you apply such a filter to a signal. Assume that the signal: Case 1) Has lots of energy at the transition points. OR Case 2) Has very little engergy at the transition points. Now we have the opposite situation where the sharp transitions are in frequency. The gate is in frequency. Accordingly, there will be sinc-like convolution in the time domain. The shape of the filter transitions controls this. Since you didn't control the shape of the frequency transitions and made them as sharp as possible, there will be spreading or leakage in the time domain sequence. Well, at least for Case 1. For Case 2 there are no sharp transitions in the "output signal" in the frequency domain just because there's no energy there. So, there's much less spreading or leakage in the time domain sequence. Example of the latter: We want to interpolate in time. We decide to do this by appending zeros in frequency (around the original fs/2). There are two ways to do it: 1) Repeat the spectral sequence so it's doubled in length and creates a new fs that's 2X the old fs. So far, so good except there's a big hump of energy at the new fs/2. If we IFFT this now, with the input to the IFFT being periodic, every other output sample will be zero and there will be no effective interpolation. To get past this, we need to suppress all the energy around fs/2. We might choose to use a half-band filter to do this. 2) Another approach is to mash all the energy around fs/2 with zeros - effectively multiplying by a gate function. This is the approach you're asking about. Here the transitions are at fs/4 and 3fs/4 which used to be at fs/2 and -fs/2. Presumably the original signal was reasonably filtered before sampling so that there's no (er... little) energy around those points. So, there are no sharp transitions in the frequency sequence introduced - thus no added leakage/spreading in time. If we're really being picky and want to interpolate more than 2X then we might use a half-band filter one time and then append zeros (same as doubling the length and mashing with zeros) around current fs/2 up to the desired interpolation factor of sample points. In doing this, less and less energy is "forced" and much less and less sharp transitions occur. Fred
On Thu, 09 Apr 2009 08:22:55 -0500, "bmh161" <bmh161@yahoo.com> wrote:

>This is probably a stupid question but, well, I'm not all that smart... > >Instead of going through all the trouble of designing complicated digital >filters, why don't we just pick the frequencies that we want to supress and >replace those bins in the FFT with zeros? >
Hello bmh161, you ask a super-sensible question. I've read a few of the responses to your question here and they seem to strongly imply that frequency-domain filtering is a bad idea. However, some months ago I was playing around with, oops I mean "modeling", this process of freq-domain filtering and it seemed to work fine for me. I was adding noise to an audio signal and experimenting with freq-domain filtering the noisy signal. That is, I merely zero-out the spectral components of the noise I wanted to eliminate. Everything seemed to work OK. Now, as you know, in DSP it's easy to perform some modeling, contemplate the entire process, and decide that we know what's happening. Only to find out later that our judgement, and supposed understanding, were wildy incorrect! So bmh161, sorry I can't provide any profound always-true information on this subject. I just wanted to say that your question is sensible and that we, the DSP guys here, should investigate the process of freq-domain filtering in detail and come up with an explanation of why it sometimes works and sometimes may not work. [-Rick-]
Rick Lyons <R.Lyons@_bogus_ieee.org> wrote:
 
> I've read a few of the responses to your question here > and they seem to strongly imply that frequency-domain > filtering is a bad idea. However, some months ago > I was playing around with, oops I mean "modeling", > this process of freq-domain filtering and it seemed to > work fine for me. I was adding noise to an audio > signal and experimenting with freq-domain filtering > the noisy signal. That is, I merely zero-out the > spectral components of the noise I wanted to eliminate. > Everything seemed to work OK.
I think it should work OK, too. But you can't do it in real time as you often need for digital filters. If you wanted a graphic equalizer for your stereo system, you would find that you didn't hear each track on the CD until after it was finished, not to mention that you couldn't change the filter while the track was playing. Being O(NlogN) isn't so good, either.
> Now, as you know, in DSP it's easy to perform some > modeling, contemplate the entire process, and decide > that we know what's happening. Only to find out later > that our judgement, and supposed understanding, were > wildy incorrect!
-- glen
On Apr 9, 9:22&#2013266080;am, "bmh161" <bmh...@yahoo.com> wrote:
> This is probably a stupid question but, well, I'm not all that smart... > > Instead of going through all the trouble of designing complicated digital > filters, why don't we just pick the frequencies that we want to supress and > replace those bins in the FFT with zeros?
Actually that topic is covered as a design method in "Digital Signal Processing" by Oppenheim and Schafer. They show a lowpass filter design example where, at the band, edge they use a few transition values between the 1's (passband) and 0's (stopband) to improve performance over just 1's and 0's. The transition values are done by "trial and error", and you may (or may not, depending on your specs) get an acceptable result. I haven't used it ever to design a filter I actually used, but you might find it interesting to give it a try against a set of limited specs (PB, SB, num taps) and see how well it performs (actual PB & SB, PB and SB error, etc) against other methods. spamfree