Why not set unnecessary frequency components to zero in freq domain?

The answer to this one may be obvious, I dont know, but I still couldnt
figure it out, so I had to post.

To remove an interfering frequency from a noisy signal, why don't we
simply take the FFT and set the interfering frequency value to zero (in
the amplitude spectrum), and then take IFFT again? Something similar seems
to be done in JPEG (DCT) compression, where the higher frequencies are
simply set to zero before the compression.
 
I see a few negatives with this:
 
1> To implement a running filter, you need to keep taking the FFT and IFFT
repeatedly, which may be an unacceptable computation overhead.
 
2> A finite-length sine wave actually does not produce a single sample in
the FFT, but also spills over to adjacent frequencies due to finite length
effects.

Can someone please clarify on this?
 
thanks in advance,

"adolf123" <karthickng@ieee.org> writes:

> The answer to this one may be obvious, I dont know, but I still couldnt
> figure it out, so I had to post.
>
> To remove an interfering frequency from a noisy signal, why don't we
> simply take the FFT and set the interfering frequency value to zero (in
> the amplitude spectrum), and then take IFFT again? Something similar seems
> to be done in JPEG (DCT) compression, where the higher frequencies are
> simply set to zero before the compression.
>  
> I see a few negatives with this:
>  
> 1> To implement a running filter, you need to keep taking the FFT and IFFT
> repeatedly, which may be an unacceptable computation overhead.

Yes, you've got part of the idea. 

To use the FFT for linear filtering, you have to take steps to ensure there
is no aliasing due to the inherently circular convolution you get with the FFT. 
Generally, that means you have to ensure a certain number of zero samples in
either the impulse response, the input signal, or both. 

Simply setting a bin to zero is (I think) going to result in a very wide
equivalent impulse response, which means it will alias. 

And if you want to filter indefinitely-lengthed signals using the FFT, you
have to split the input into blocks and use a technique like overlap/add or
overlap/save.

> 2> A finite-length sine wave actually does not produce a single sample in
> the FFT, but also spills over to adjacent frequencies due to finite length
> effects.

I know what you mean, but I wouldn't use the terminology you use. For
example, it's not the "finited-ness" of the sine wave that causes the
"spilling" but rather the relationship of its frequency to the sample
rate and FFT length. In just the right situation, the FFT will yield a
perfect "spike" for a finite-lengthed sine wave. 

To step back a little, notch-filtering an interferer is a filtering
operation.  If you use an FIR filter, then it can be implemented in
the time domain (using a standard convolution sum) or in the frequency
domain using FFTs and, e.g., overlap/add.
-- 
%  Randy Yates                  % "Bird, on the wing,
%% Fuquay-Varina, NC            %   goes floating by
%%% 919-577-9882                %   but there's a teardrop in his eye..."
%%%% <yates@ieee.org>           % 'One Summer Dream', *Face The Music*, ELO
http://www.digitalsignallabs.com

Randy Yates <yates@ieee.org> writes:
> [...]

PS: Proakis and Manolakis have a very thorough section on the circular
convolution property of the DFT and the overlap add/save methods.

@BOOK{proakis,
  title = "{Digital Signal Processing: Principles, Algorithms, and Applications}",
  author = "John~G.~Proakis and Dimitris~G.~Manolakis",
  publisher = "Prentice Hall",
  edition = "third",
  year = "1996"}

PSS: I think there is a more recent edition.
-- 
%  Randy Yates                  % "Rollin' and riding and slippin' and
%% Fuquay-Varina, NC            %  sliding, it's magic."
%%% 919-577-9882                %  
%%%% <yates@ieee.org>           % 'Living' Thing', *A New World Record*, ELO
http://www.digitalsignallabs.com

On Oct 11, 7:47 pm, "adolf123" <karthic...@ieee.org> wrote:
> The answer to this one may be obvious, I dont know, but I still couldnt
> figure it out, so I had to post.
>
> To remove an interfering frequency from a noisy signal, why don't we
> simply take the FFT and set the interfering frequency value to zero (in
> the amplitude spectrum), and then take IFFT again? Something similar seems
> to be done in JPEG (DCT) compression, where the higher frequencies are
> simply set to zero before the compression.

But note that JPEG (quantized DCT) compression can leave quite
visible artifacts in some cases (mosquito noise).

> I see a few negatives with this:
...
> 2> A finite-length sine wave actually does not produce a single sample in
> the FFT, but also spills over to adjacent frequencies due to finite length
> effects.

That is exactly the problem.  A finite-length FFT will
chop the sine wave into a finite length by sort-of an inherent
rectangular window.  A rectangular window of a non-exactly
periodic (in that window) sinusoid will appear as a sampled
Sinc in the FFT result, e.g. portions of the energy will spill
into side lobes.  If you zero a bin which contains these side
lobes, you end up distorting portions of those other non-bin
frequencies in addition to the one you are trying to null.
e.g. you get distortion.

And if the frequency you want to remove isn't exactly periodic
in the FFT aperture, then the problem doubles.  You end up
only remove a portion of the interfering frequencies sampled
Sinc spillage by zeroing one bin.  So you both distort other
frequencies and only partially remove the interfering frequency.

When you try to plot the continuous frequency response of
zeroing one bin, these effects will cause the response curve
to look quite un-flat and very ringy near the bin of interest.
A wider, less abrupt, filter will usually cause much less of this
type of distortion, contrary to what some DSP novices might
first assume.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

Randy Yates wrote:

> "adolf123" <karthickng@ieee.org> writes:
(snip)

>>2> A finite-length sine wave actually does not produce a single sample in
>>the FFT, but also spills over to adjacent frequencies due to finite length
>>effects.

> I know what you mean, but I wouldn't use the terminology you use. For
> example, it's not the "finited-ness" of the sine wave that causes the
> "spilling" but rather the relationship of its frequency to the sample
> rate and FFT length. 

A finite length sine as a time domain signal (zero outside the specified
time) has a width in frequency space inversely proportional to the
length of the sine.  More usual are sines multiplied by Gaussians,
wave packets, which have a Gaussian width in frequency space.

> In just the right situation, the FFT will yield a
> perfect "spike" for a finite-lengthed sine wave. 

The FFT of a finite length signal that is not zero padded
gives the result for a periodic infinitely long signal.
For sines with the right period, yes, a delta in frequency
space.

> To step back a little, notch-filtering an interferer is a filtering
> operation.  If you use an FIR filter, then it can be implemented in
> the time domain (using a standard convolution sum) or in the frequency
> domain using FFTs and, e.g., overlap/add.

Sounds good to me.

-- glen

On 12 Okt, 04:47, "adolf123" <karthic...@ieee.org> wrote:
> The answer to this one may be obvious, I dont know, but I still couldnt
> figure it out, so I had to post.
>
> To remove an interfering frequency from a noisy signal, why don't we
> simply take the FFT and set the interfering frequency value to zero (in
> the amplitude spectrum), and then take IFFT again? Something similar seems
> to be done in JPEG (DCT) compression, where the higher frequencies are
> simply set to zero before the compression.

There is one fundamental difference between image processing
and analysis of time-series data: In image procesing you have
all the data available when you do the processing. One image
is all there is, and that's what you have to deal with.

In most applications in time series analysis the available
data is only a random sample of a stochastic process, which
means that one can always aqcuire more data by leaving the
recorder running for a bit longer. Of course, one has to
stop the recording at one point, which in turn means one
always deals with an incomplete data set.

Since DSP deals with discrete-time data where one in many
applications really is interested in continuous-time data,
one ends up with two problems:

- One has a finite sample of an infinitely long process
- One has discrete-time data and discrete spectra where
  one really is interested in continuous-time data
  and contionuous spectra.

Since the setting is far more complex in the case of
time series analysis, one have to be a lot more careful
than one needs to be with image processing.

> I see a few negatives with this:
>
> 1> To implement a running filter, you need to keep taking the FFT and IFFT
> repeatedly, which may be an unacceptable computation overhead.

No, you don't have to. There are other ways of doing things.

> 2> A finite-length sine wave actually does not produce a single sample in
> the FFT, but also spills over to adjacent frequencies due to finite length
> effects.

That's part of the explanation; you just don't know exactly
what to remove. In view of what I explained above, that most
time series data sets are random samples of stochastic
processes, the exact ferquency component available to you
depend on the length of the discrete-time data sequence.
Remember, with a sequence of length N the Fourier coefficients
are located at w_n = 2*pi/(N*T) where T is the sampling period.
Change the length of the data sequence from N to N+1 and the
Fourier component change with it.

There is also a famous theorem (Wiener-Kinchine?) which
states that if a spectrum is zero over some non/vanishing
bandwidth the time-domain signal will be infinitely long.
Which causes all sorts of problems with ringing and
wrap-around, if one tries to emulate it in discrete
spectra.

Rune

I use it all the time in the lab on cyclic signals. But there are a couple
of pitfalls in the general case, one of them is ringing in the time
domain. 

Here is an example on an audio file, for experiments.
Treating the whole audio file as a cyclic signal means that one has to
push the "repeat" button on the CD player after processing, otherwise the
spectrum will spill :)

http://www.elisanet.fi/mnentwig/webroot/FFT_filter_example/index.html

Cheers

Markus

adolf123 wrote:
> To remove an interfering frequency from a noisy signal, why don't we
> simply take the FFT and set the interfering frequency value to zero (in
> the amplitude spectrum), and then take IFFT again?

(Disclaimer : I know little about noise removal) If you're trying to
get rid of noise, there's a way to do (pretty much) this. Just
characterise your noise in the frequency domain (get a sample of pure
noise, FFT it, take the magnitude of it, smooth it if necessary) then
substract the FFT of your signal you want to de-noise with that, and
IFFT. I believe it will yield better results than if you arbitrarily
set bins to zero in the frequency domain.

> Something similar seems
> to be done in JPEG (DCT) compression, where the higher frequencies are
> simply set to zero before the compression.

Yes, but I believe it's done in order to get rid of the least
significant frequency-domain information, in order to make the amount
of information to save less important.

"adolf123" <karthickng@ieee.org> wrote in message 
news:4rWdnQyuJODBfZPanZ2dnUVZ_jqdnZ2d@giganews.com...
> The answer to this one may be obvious, I dont know, but I still couldnt
> figure it out, so I had to post.
>
> To remove an interfering frequency from a noisy signal, why don't we
> simply take the FFT and set the interfering frequency value to zero (in
> the amplitude spectrum), and then take IFFT again? Something similar seems
> to be done in JPEG (DCT) compression, where the higher frequencies are
> simply set to zero before the compression.
>
> I see a few negatives with this:
>
> 1> To implement a running filter, you need to keep taking the FFT and IFFT
> repeatedly, which may be an unacceptable computation overhead.

***Actually this can be faster than time domain convolution.

>
> 2> A finite-length sine wave actually does not produce a single sample in
> the FFT, but also spills over to adjacent frequencies due to finite length
> effects.

Correct.  Another way to look at the operation you suggest is that it 
identically subtracts a sinusoid of an integral number of cycles in the time 
domain - without spectral leakage.  So, whether that's what you want, that's 
what you get!

Note that you would have to subtract from both the positive and negative 
frequency values; i.e. a term between 0 and fs/2 and another term between fs 
and fs/2 by the same distance.  Otherwise it doesn't have the desired 
affect - if then.

Fred