Why don't we just zero out FFT bins?

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

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