3
$\begingroup$

Given some frequency-domain representation of an impulse response.

How does the number of frequency-domain sampling points influence the outcome of an inverse FFT, if I keep the sampling frequency constant?

Example 1 Take x(t) = e^(-t)*sin(t) for t in (0,10). Sample the signal, take its fft. Omit every second point of the fft and on the result do an inverse fft. Here is the result:

enter image description here

So it looks as if the frequency-domain downsampling had removed the second portion of my signal, while dividing the first part by two. (Indeed multiplying the result by two results in a curve lying exactly above the first part of the original signal.)

  • Why did it remove the second part and not some arbitrary other part? I guess this is related to the second part being nearly zero everywhere, but I can't seem to find the exact reason.
  • Why is the result divided by two?
  • How does this generalize to other time signals?

Example 2 (pathological) Same as above, this time with a signal that is linearly decreasing from 1 to 0.1.

enter image description here

Now what is that?

Edit There was a mistake here: I accidentally used an uneven number of sampling points, which resulted in a complex signal after the ifft. Here is the fixed plot.

enter image description here

I'm interested in mathematical/theoretical as well as intuitive explanations of what's going on, as well as pointers on where to read on. I even had trouble finding a correct term for what I am doing.


Here's the R code that produced the above plots.

# First plot
t <- seq(0.01, 10, 0.01)
z <- exp(-t)*sin(t)
Z <- fft(z)/length(z)
Z2 <- Z[seq(1,length(Z),2)]
z2 <- fft(Z2, inverse=T)
plot(z)
points(Re(z2), col="red")
legend("topright", legend=c("original", "half-sampled"), fill=c("black", "red", "blue"))

# Second plot
x <- seq(1,0.101, -0.001)
X <- fft(x)/length(x)
X2 <- X[seq(1,length(X),2)]
x2 <- fft(X2, inverse=T)
plot(x)
points(Re(x2), col="red")     
legend("topright", legend=c("original", "half-sampled"), fill=c("black", "red", "blue"))
$\endgroup$
  • 2
    $\begingroup$ By throwing away every other FFT coefficient, you introduce aliasing in the time domain. This is what you see in the first example. Here the shape of the signal remains virtually unchanged, because the second half of the original signal is almost zero. What you see in the second example is an artefact because X2 is not a valid FFT of a real-valued signal. If you check you'll see that the imaginary part of ifft(X2) is much greater than what you'd expect due to numerical effects. This has to do with the fact that the signal length is odd. I'll write a more detailed answer later. $\endgroup$ – Matt L. Aug 14 '14 at 16:58
  • $\begingroup$ OK, I see now that @ThP already answered your question correctly, so I won't add another redundant answer. $\endgroup$ – Matt L. Aug 14 '14 at 17:07
  • $\begingroup$ Thanks for the comment! I had already fixed that problem with the uneven number of sampling points before, must have somehow slipped through my fingers again... Apart of that, the time domain aliasing really answers the question! This also perfectly explains what I got in the second example. $\endgroup$ – jhin Aug 14 '14 at 17:22
  • $\begingroup$ What I'm actually trying to do is to obtain a good estimate of my impulse response with as few evaluations of my frequency domain expressions as possible (since evaluating it is very costly). So a valid strategy would be to choose the number of sampling points in the frequency domain such that I obtain an impulse response that's essentially zero for at least several samples towards one end, right? Does anyone have a better suggestion on how to do this effectively? $\endgroup$ – jhin Aug 14 '14 at 17:38
  • $\begingroup$ I think it would make a lot of sense if you formulated another question about this. It would be helpful if you explained how exactly (and based on what data) you want to estimate the impulse response. $\endgroup$ – Matt L. Aug 14 '14 at 19:40
6
$\begingroup$

Regarding example 1:
first of all, either the fft or the ifft needs to be normalised by the number of sampling points as you have done (actually you can normalise each by a factor of the square root of the number of points, it is just a meter of definition). However, in your case the ifft is half the length of the fft you performed. Hence your signal is divided by 2. If you would perform the normalisation when calling the ifft (using half the original number of samples) you should get the correct height.
Now, regrading the second part of the signal, it is not truncated. What you see is some kind of aliasing. Since you downsampled without filtering, you get aliasing. This is the same concept as frequency aliasing (DFT and IDFT are basically the same). You should try to flip the input signal in the time domain and witness the results.

Next, regarding example 2:
Your problem is with the number of sampling points. Let me start by mentioning that since your signal is real, the frequency domain is symmetric.
In your first example you had even number of points. when you downsampled the frequency you still got a symmetric signal. In the second example you have odd number of samples. Therefore your decimated frequencies are not symmetric and the result is a complex signal. If you try it with one less (or more) sample it should give a similar result to example 1. On the other hand you can perform the frequency decimation while keeping the signal symmetric.

$\endgroup$
  • $\begingroup$ That problem with the uneven number of sampling points was accidental; I had already fixed that before but must somehow have missed it once again. Thanks for the hint! Time domain aliasing is a good point, though. Do you have any solid references on the topic? I don't recall that being mentioned in my DSP classes... $\endgroup$ – jhin Aug 14 '14 at 17:25

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.