DSPRelated.com
Forums

Why don't we just zero out FFT bins?

Started by bmh161 April 9, 2009
steve wrote:
> > 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 certainly can, an N point FFT is just bank of N notch filters, > with frequency response controlled by the window. It's just that, in > most cases, a simple 20 tap FIR or 6 pole IIR filter will do the job > instead of performing a 4096 point FFT/IFFT.
To use the FFT directly as N filters (narrow-band, not 'notch') you would have to do one FFT for each incoming time-domain sample, which means a horrendous amount of calculation. You would be getting 4096 FIR narrow-band filters. Each of these filters has exactly 4096 taps (not 20 taps. You would not have to do an IFFT. If you do use the FFT/IFFT approach, typically with a 4096 point FFT/IFFT you can implement any FIR filter up to a limit of 2048 taps. There is an enormous gain in efficiency because each FFT/IFFT computation yields 2048 time-domain output samples. Regards, John
SG wrote:
> On 9 Apr., 15:22, "bmh161" <bmh...@yahoo.com> wrote: >> 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? > > It's equivalent to circular convolution with a brickwall lowpass > filter (infinite impulse response). The issue is you need to fight the > "wrap-around error". This becomes easy if the filter's impulse > response is finite and known ... > > Cheers! > SG
Actually, it isn't. You might think that it's equivalent to *multiplication* with a brickwall filter (not necessarily lowpass) - which corresponds to some convolution in time. Is the convolution in time circular? well, sure. Is it necessarily overlapping? - no. That depends on whether the time sequences are long enough / have enough zeros in them (both filter and data) OR that the overlap is tolerable which implies more gradual transitions in frequency or low signal energy at the transition frequencies. How to get zeros appended to the time function? 1) Start with them. But the filter being used hasn't been expressed in time has it? . OR 2) Interpolate in frequency before multiplying. This might be a bit tougher. If one were to postulate a brick wall lowpass discrete filter and then interpolate it then one would want to have a timelimited sinc that corresponds in its IFFT. The timelimited sinc would demand some sinc/Dirichlet convolution in frequency - so the interpolation of the filter would be complicated by that. The interpolated filter wouldn't be 1's and 0's Anyway, the point is that one should practically satisfy the sampling theorem in frequency in order to avoid much aliasing in time .. which is the wrap-around mentioned. If one picks a discrete filter in frequency made up of 1's and 0's then it will surely have a finite (periodic if you will) IFFT. The filter's impulse response is always finite in that sense. Fred
On 12 Apr., 20:52, "Fred Marshall" <fmarshallx@remove_the_x.acm.org>
wrote:
> SG wrote: > > On 9 Apr., 15:22, "bmh161" <bmh...@yahoo.com> wrote: > >> 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? > > > It's equivalent to circular convolution with a brickwall lowpass > > filter (infinite impulse response). The issue is you need to fight the > > "wrap-around error". This becomes easy if the filter's impulse > > response is finite and known ... > > > Cheers! > > SG > > Actually, it isn't. > [...] > If one picks a discrete filter in frequency made up of 1's and 0's > then it will surely have a finite (periodic if you will) IFFT. The > filter's impulse response is always finite in that sense.
Well, I didn't pay much attention to what subset of coefficients we were talking about and just assumed a lowpass filter. Apart from that we seem to agree for the most part. I could have made a bigger errort explaining it. Discrete circular convolution = extend a finite sequence to form a periodic sequence with period P, convolve this periodic signal with another one sequence, cut out a finite part of length P of the result. (more or less -- insert missing details here that should be ovbious). Obviously, such a periodic sequence can only be a superposution of sinusoids with wavelengths that exactly divide P. That's why there are infinitely many filters we can apply on this periodic sequence (including those with infinite impulse response) that lead to the exact same result. These filters only differ in the frequency response for those frequencies that are not present in the periodic sequence. Some kind of "brickwall" filter will also work. Some filter with an impulse response of at most P samples will always work, too. The important point here -- and I'm sure you agree with this -- is that one has to deal with wrap-around errors because in practice one usually doesn't work with periodic signals with the right period P=FFT_size. Since careless zeroing of FFT bins will in general correspond to a filter with a rather large impulse response (not significantly less than P) you can hardly avoid wrap-around errors even if zero padding is done. Cheers! SG
>>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. >
Others have already mentioned some of the problems with the method you describe. One approach to implementing a filter this way is to use the window method of FIR design without ever working in the time domain. With the window method, the desired frequency response is plugged into the appropriate FFT bins. A brick wall filter would be typical (zeroing many FFT bins). The iFFT is then taken to create the impulse response of the desired length and the result is then multiplied by a window function (see Kaiser, Von Hann, Hamming, etc). This impulse response is the coefficients for your FIR filter. However, since multiplication in the time domain is synonymous with convolution in the frequency domain, you can take your original FFT bin values, and convolve them with the frequency response of the desired window function. You should be able to adapt this to a overlap-add implementation . I'm pretty sure this works correctly, but you should investigate and work it out for yourself. This is just coming off the top of my head and may have oversights or just plain gross errors... Jacob
I believe MIPS is also a concern when you do FFT/IFFT just for filtering.


"hariharan.gk" <hariharan1983@yahoo.com> writes:

> I believe MIPS is also a concern when you do FFT/IFFT just for
> filtering. MIPS are less than time-domain convolution - that's really the reason we use it. -- % Randy Yates % "With time with what you've learned, %% Fuquay-Varina, NC % they'll kiss the ground you walk %%% 919-577-9882 % upon." %%%% <yates@ieee.org> % '21st Century Man', *Time*, ELO http://www.digitalsignallabs.com
On Apr 9, 9:22&#4294967295;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?
Well, that's just a particular type of filter called a notch. It's not that it doesn't work, it just has so many overused strange side effects, it's one of the reasons Optical Computers, Fiber Optics Signalling, Holograms, HDTV, CD, and DVD were invented.
On Thu, 9 Apr 2009 18:49:35 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>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
Could you give a practical numerical example, or more detail about what you mean here? I guess that's different then when all frequencies of the sampled signal are an integer multiple of the bin size (so fall exactly on an FFT bin).
a@b.com wrote:
(snip, I wrote)

>>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
> Could you give a practical numerical example, or more detail about > what you mean here? I guess that's different then when all > frequencies of the sampled signal are an integer multiple of the bin > size (so fall exactly on an FFT bin).
Well, say you FFT one track on a CD, maybe five minutes. (So not a Mahler symphony, for example.) Five minutes is 5*60*44100 samples, or 13230000 samples. FFT is O(N logN), so it shouldn't take all that long on most current machines. The bin spacing is then 1/(5 minutes) or about 0.00333 Hz. In FFT terms, the signal is periodic. Even if you don't believe that, the quantization noise will be enough that you can't detect frequencies closer than 0.00333Hz, anyway, in a 5 minute signal. Interesting question for those building 60Hz notch filters, how accurate is the power line frequency over short time scales? Is it better than 0.00333Hz? -- glen

glen herrmannsfeldt wrote:

> Well, say you FFT one track on a CD, maybe five minutes. > (So not a Mahler symphony, for example.) > > Five minutes is 5*60*44100 samples, or 13230000 samples. > FFT is O(N logN), so it shouldn't take all that long on most > current machines. The bin spacing is then 1/(5 minutes) or > about 0.00333 Hz.
FFT with the size of up to ~100M points is no problem as it takes ~minutes on PC. However beware of the numeric artifacts.
> In FFT terms, the signal is periodic. Even if you don't believe > that, the quantization noise will be enough that you can't > detect frequencies closer than 0.00333Hz, anyway, in a 5 minute > signal.
This is not so obvious to me. Can you justify that.
> Interesting question for those building 60Hz notch filters, > how accurate is the power line frequency over short time scales? > Is it better than 0.00333Hz?
According to my measurements, the short term accuracy of AC frequency is about 1e-4. But the fluctiation of the waveform sets the limit to the usefulness of the comb filters before the frequency instability comes into play. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com