2
$\begingroup$

I have an input sequence $x=\{x_1, x_2 , ... x_n\}$ of reals, where $n=2^m$ for some $m$. I wish to calculate FFT of $x$.

$X=FFT(x)$

However, before I calculate the FFT, the signal $x$ gets corrupted with noise $\eta$, so $\hat{x}=x+\eta$, and calculated FFT, $\hat{X}$ is FFT of $\hat{x}$, rather than $x$.

$\hat{X}=FFT(\hat{x})$

I wish to recover actual or approximate FFT $X$ from $\hat{X}$ under following assumption:

  1. $x$ is band limited signal; FFT spectrum dies down quickly.
  2. The noise $\eta$ is a shifted delta function, with unknown shift and magnitude, i.e. $\eta(n)= R\delta (n-l)$, where $R,\ l$ are real and integer respectively.

How will I do it in a compute efficient way?

$\endgroup$
  • $\begingroup$ Is the band limit of $x$ low enough that some upper part of the spectrum only comes from the noise? $\endgroup$ – Olli Niemitalo Jan 12 '16 at 9:24
  • $\begingroup$ It's fair to assume that. $\endgroup$ – piyush_sao Jan 12 '16 at 18:24
1
$\begingroup$

High-pass filter the input with a zero-phase filter to eliminate the signal of interest, leaving only the high-passed noise. If the signal is periodic, you can do this in the frequency domain and convert back to time domain by IFFT. Find the time of the peak and deduce the magnitude of the unfiltered delta function from the magnitude of the filtered delta function (the peak value or root mean square). Knowing the delay and magnitude, subtract the noise from the original input signal. Do FFT.

$\endgroup$
1
$\begingroup$

There is more effective method for decision of your problem. Try to use some non-linear filter in time domain before calculating of FFT. Median filter is simple and effective filter for reducing impulse noise (Median_filter). You can use simplest version with size of 3.

UPDATE

It is answer to comment of zimbra314.

Strange constraint. It is easy to reduce impulse noise in time-domain, but not in frequency-domain. But, is it your homework? If so I can give you a hint. Please do FFT of delta function. See to amplitude and phase of this spectrum. The amplitude spectrum of delta function has very simple form and there are a lot of high-frequency components. Your signal is band-limited, so there are not any high-frequency components. So you can easy estimate a amplitude spectrum of your noise . As you know, FFT of sum of 2 function ($x+\eta$) is sum of FFT of this signals. So you can calculate amplitude of $X$ very easy by subtraction amplitude spectrum of noise from $\hat{X}$

Is it possible to estimate phase spectrum of delta function. See phase for different values of shift of delta function... I think you will find method of estimation of phase spectrum yourself.

UPDATE 2

Spectrum of delta function ($\eta(n)= R\delta (n-l)$) is quite simple and well known. Spectrum of your band limiting signal $x$ does not have any high-frequency components. So high frequency components of spectrum of ($x+\eta$) equals to high frequency components spectrum of $\eta$. Algorithm is:

  1. calculate $\hat{X}=FFT(\hat{x})$
  2. estimate parameters of spectrum delta function $\eta$ from high-frequency part of $\hat{X}$
  3. calculate estimating spectrum $\Theta$ by using parameters from step 2
  4. calculate estimation of ${X}=\hat{X} - \Theta$
$\endgroup$
  • $\begingroup$ I have additional constraint that I can only do any operation in calculated fft, what do I do in this case? $\endgroup$ – piyush_sao Jan 13 '16 at 11:58
  • $\begingroup$ It's not homework problem. $\endgroup$ – piyush_sao Jan 14 '16 at 13:05
  • $\begingroup$ @zimbra314, Sorry. Do you have questions about my hint? $\endgroup$ – SergV Jan 14 '16 at 15:39
  • $\begingroup$ Well, ultimately it boils down to how to calculate fft of signal that consists of single complex exponential. And it seems the best way to do it is doing an fft, but doing so is inefficient as it takes same time as doing original fft. I'm looking for a better way. $\endgroup$ – piyush_sao Jan 14 '16 at 15:43
  • $\begingroup$ @zimbra314, I have updated my answer. $\endgroup$ – SergV Jan 15 '16 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.