Why don't we just zero out FFT bins?

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