Why don't we just zero out FFT bins?

[bmh161]

This is probably a stupid question but, well, I'm not all that smart...

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

[bmh161]

Post by bmh161
This is probably a stupid question but, well, I'm not all that smart...
Instead of going through all the trouble of designing complicate

digital

Post by bmh161
filters, why don't we just pick the frequencies that we want to supres

and

Post by bmh161
replace those bins in the FFT with zeros?

Then, with the undesirable frequencies zeroed out, take the inverse FFT t
get back to the time domain.

[c***@claysturner.com]

Post by bmh161

Post by bmh161
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

Post by bmh161
filters, why don't we just pick the frequencies that we want to supress

and

Post by bmh161
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

[Greg Berchin]

Post by c***@claysturner.com
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

[glen herrmannsfeldt]

Greg Berchin <***@comicast.net.invalid> wrote:
(snip on filtering using FFT)

Post by Greg Berchin
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.

Post by Greg Berchin
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

[a***@b.com]

On Thu, 9 Apr 2009 18:49:35 +0000 (UTC), glen herrmannsfeldt

Post by glen herrmannsfeldt
(snip on filtering using FFT)

Post by Greg Berchin
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).

[glen herrmannsfeldt]

***@b.com wrote:
(snip, I wrote)

Post by a***@b.com

Post by glen herrmannsfeldt
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

[Vladimir Vassilevsky]

Post by glen herrmannsfeldt
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.

Post by glen herrmannsfeldt
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.

Post by glen herrmannsfeldt
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

[steve]

Post by c***@claysturner.com

Post by bmh161

Post by bmh161
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

Post by bmh161
filters, why don't we just pick the frequencies that we want to supress

and

Post by bmh161
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

you have control over an FFT frequency response via windowing, an FFT
is a digital filter

[Fred Marshall]

Post by bmh161

Post by bmh161
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

Post by bmh161
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

[John Monro]

Post by bmh161

Post by bmh161
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

Post by bmh161
filters, why don't we just pick the frequencies that we want to supress

and

Post by bmh161
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.

Something like this is done in 'overlap-save' and
'overlap-add' FFT / IFFT filters, but a little more care
need so be taken in specifying the frequency response.

A requirement of these techniques is that the impulse
response of the filter must be shorter than the number of
bins in the FFT. (N/2 samples long for example.)

If you simply zero-out particular frequency bins in the FFT
you are effectively specifying a filter that has a very
steep response in the frequency domain. This filter will
have an impulse response that is certain to be too long. In
this situation, severe noise and distortion will be
introduced into the filter output.

You need to ensure that the frequency response that you are
specifying implies a filter with an acceptably short impulse
response. Unfortunately, to do this you must do a FIR
filter design even though you end up using the number of
coefficients in the filter, but not the coefficients themselves.

Regards,
John

[steve]

Post by bmh161

Post by bmh161
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

Post by bmh161
filters, why don't we just pick the frequencies that we want to supress

and

Post by bmh161
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.

[John Monro]

Post by steve

Post by bmh161

Post by bmh161
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

Post by bmh161
filters, why don't we just pick the frequencies that we want to supress

and

Post by bmh161
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

[foxcob]

Post by bmh161

Post by bmh161
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

Post by bmh161
filters, why don't we just pick the frequencies that we want to supress

and

Post by bmh161
replace those bins in the FFT with zeros?

Then, with the undesirable frequencies zeroed out, take the inverse FF

to

Post by bmh161
get back to the time domain.

Others have already mentioned some of the problems with the method yo
describe. One approach to implementing a filter this way is to use th
window method of FIR design without ever working in the time domain. Wit
the window method, the desired frequency response is plugged into th
appropriate FFT bins. A brick wall filter would be typical (zeroing man
FFT bins). The iFFT is then taken to create the impulse response of th
desired length and the result is then multiplied by a window function (se
Kaiser, Von Hann, Hamming, etc). This impulse response is the coefficient
for your FIR filter.
However, since multiplication in the time domain is synonymous wit
convolution in the frequency domain, you can take your original FFT bi
values, and convolve them with the frequency response of the desired windo
function. You should be able to adapt this to a overlap-add implementatio

[Rune Allnor]

Post by bmh161
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

[Rick Lyons]

Post by bmh161
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-]

[glen herrmannsfeldt]

Post by Rick Lyons
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.

Post by Rick Lyons
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

[Rune Allnor]

Post by bmh161
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?

...

 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

Rick, did we read the same post? The question is not why
frequency domain filtering is a bad idea, but why one doesn't
use the naive, 'obvious' specs for the filters. I commented on
a similar question not too long ago:

http://groups.google.no/group/comp.dsp/msg/2d4bd5dfb25b5a23

Such questions are covered in most DSP texts - I wouldn't be
surprised if you touched on the subject already. If not, the issue
might be worth half a page's comments in your 3rd edition, as
your book is the first entry point into DSP for lots of users.

Teachning students how to think 'right' is an admirable (and
difficult!) task; warning against how to think 'wrong' can only
help the effort.

Rune

[Rick Lyons]

On Fri, 10 Apr 2009 02:08:18 -0700 (PDT), Rune Allnor

Post by Rune Allnor

Post by bmh161
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?

...

 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

Rick, did we read the same post? The question is not why
frequency domain filtering is a bad idea, but why one doesn't
use the naive, 'obvious' specs for the filters. I commented on
http://groups.google.no/group/comp.dsp/msg/2d4bd5dfb25b5a23
Such questions are covered in most DSP texts - I wouldn't be
surprised if you touched on the subject already. If not, the issue
might be worth half a page's comments in your 3rd edition, as
your book is the first entry point into DSP for lots of users.
Teachning students how to think 'right' is an admirable (and
difficult!) task; warning against how to think 'wrong' can only
help the effort.
Rune

Hi Rune,
Oh shoot. Maybe I misunderstood the poster's
question. For whatever reason, I thought he was
asking: "Can we perform an N-point FFT on an N-point
time sequence, zero-out the spectral components
that we wish to attenuate, and then perform an
N-point inverse FFT to obtain a "filtered"
time-domain sequence.

If the original poster was asking about ways to
design a time-domain digital filter, then I
completely missed the point of his question.
(That wouldn't be the first time for me.)

[-Rick-]
PS. Rune, I wish you "calm seas."

[s***@gmail.com]

Post by bmh161
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

[hariharan.gk]

I believe MIPS is also a concern when you do FFT/IFFT just for filtering.

[Randy Yates]

Post by hariharan.gk
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.

[R.Nicholson]

Post by bmh161
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?

Because any real frequency in which you are likely to be interested
in suppressing is very probably not represented by any bin in your
FFT.


imho. ymmv.
http://www.nicholson.com/fftmisconceptions.html

[Robert Lacoste]

Post by bmh161
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?

Doing what you propose (FFT of the signal, multiplying with a frequency
mask, IFFT) gives EXACTLY the same result mathematically speaking than a FIR
filter, its just another way to calculate it. In a nutshell :

output = IFFT (FFT(input) x MASK) = convol (IFFT(FFT(input) x IFFT(MASK)) =
convol (input x IMPULSEREPONSE) = FIR(input, IMPULSERESPONSE)...

However, as explained by the other posts, if the frequency mask is just
rectangular then your actual frequency response may not be adequate between
the frequency FFT bins, that's why windowing techniques are welcome. You can
read an article I've published in 2007 in Circuit Cellar for more
explanations on links between FFT and FIR (#207, october 2007, p. 70, "The
Darker Side : No Fear with FIR").

Friendly,
Robert Lacoste
www.alciom.com

[Rick Lyons]

On Fri, 10 Apr 2009 08:13:48 +0200, "Robert Lacoste"

Post by Robert Lacoste

Post by bmh161
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?

Doing what you propose (FFT of the signal, multiplying with a frequency
mask, IFFT) gives EXACTLY the same result mathematically speaking than a FIR

[snipped by Lyons]

Hi Robert,
are you sure about that? Let's say I have a
1024-sample time sequence on which I perform a 1024-pt
FFT. Next, I zero-out the FFT bins (samples) for the
freqs I want to attenuate. Finally I perform a 1024-pt
inverse FFT. My resultant "filtered" time sequence
is 1024 samples in length (just as was the original
time sequence).

Now ...what kind of time-domain digital filtering can
I perform on the original 1024-sample time sequence
where the filter output sequence is EXACTLY the same
1024 samples as the above freq-domain filtering output?
I believe the answer is: "There *IS* no such time-domain
digital filter."

As far as I know, the freq-domain filtering I discussed in
my first paragraph above is equivalent to time-domain circular
convolution, and time-domain filtering does
not perform circular convolution.

Robert, if I'm mistaken, then I'd sure like to
know about it.

See Ya',
[-Rick-]

[Neu]

Post by bmh161
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?

A subtle point here (which is implicit in alot of the criticism
mentioned above), is that the frequency resolution and center
frequencies of your method is changes with your FFT size. Consider for
example, the case of designing a notch filter. Lets say you want to
cancel a 60 Hz sinuisoid component. Then for different FFT sizes you
will be cancelling the following frequency bands as well (assuming Fs
=44100):

N= 128 -> 0<= f < 344 Hz frequencies set to 0

N= 256 -> 0<= f < 172 Hz set to 0

N=1024 -> 43<= f < 86 Hz set to 0


The alternative is do desing a notch filter whos resolution is
"independent" of the sample size ie,

cW = cos(2*pi*60/44100);
b=[1 -2*cW 1];


This can be important in case you want to make the sample size
variable on some applications (ie, say you are processing speech
signals and the speech segments are of different lengths) but you want
the filter to be fixed.

[s***@gmail.com]

Post by Neu

Post by bmh161
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?

A subtle point here (which is implicit in alot of the criticism
mentioned above), is that the frequency resolution and center
frequencies of your method is changes with your FFT size. Consider for
example, the case of designing a notch filter. Lets say you want to
cancel a 60 Hz sinuisoid component. Then for different FFT sizes you
will be cancelling the following frequency bands as well (assuming Fs
N= 128  ->  0<= f <  344 Hz    frequencies set to 0
N= 256   ->  0<= f < 172 Hz   set to 0
N=1024   ->  43<= f < 86 Hz   set to 0

These bands will not actually be set to 0; one frequency within these
bands will and rest will be attenuated to some extent.

Post by Neu
The alternative is do desing a notch filter whos resolution is
"independent" of the sample size ie,
cW = cos(2*pi*60/44100);
b=[1 -2*cW 1];

Really horrible filter response; much worse than zeroing one point in
the FFT. Plot the response. You will see.

Post by Neu
This can be important in case you want to make the sample size
variable on some applications (ie, say you are processing speech
signals and the speech segments are of different lengths) but you want
the filter to be fixed.

spamfree

[glen herrmannsfeldt]

Post by Neu

Post by bmh161
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?

A subtle point here (which is implicit in alot of the criticism
mentioned above), is that the frequency resolution and center
frequencies of your method is changes with your FFT size. Consider for
example, the case of designing a notch filter. Lets say you want to
cancel a 60 Hz sinuisoid component. Then for different FFT sizes you
will be cancelling the following frequency bands as well (assuming Fs
N=1024 -> 43<= f < 86 Hz set to 0

At 44100 Hz, 1024 points is about 1/40th of a second, which
doesn't sound very realistic.

Consider a five minute CD track, 5*60*44100, 13230000 points,
maybe zero pad up to the next power of two or more.

Then the bins are much smaller.

-- glen

[SG]

Post by bmh161
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

[Fred Marshall]

Post by SG

Post by bmh161
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

[SG]

Post by Fred Marshall

Post by SG

Post by bmh161
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

[z***@netscape.net]

Post by bmh161
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.

[a***@gmail.com]

bmh161於 2009年4月9日星期四 UTC+8下午9時22分55秒寫道：

Post by bmh161
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?

You may be interested in the simple experiment using matlab.

https://poweidsplearningpath.blogspot.com/2019/04/dftidft.html