# Why don't we just zero out FFT bins?

Started by 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
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&#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?

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

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

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.