9
$\begingroup$

I recently realized that FFT's aren't perfect. Meaning if I take a signal and then take it's FFT, and then do an inverse FFT, the resulting output isn't exactly the same as the input. Here's an image to show you what I mean :FFT doesn't always work

I think the image is fairly self explanatory. The IFFT signal is just an inverse transform of "FFT spectrum" and the "Difference" plot is the difference between the IFFT signal and the original signal ($\text{IFFT - Original}$).

Clearly there are some artefacts, although they are really small. I'd like to know why they occur in the first place. Is this because of the finite window of the fourier transform? Or because of something in the FFT algorithm?

Note: This plot has 32 points, but I've checked with 100, 1000, 1024, 256 and 64 points, and there's always this residue in the difference of a similar magnitude (either $10^{-16}$ or $10^{-15}$).

$\endgroup$
  • 4
    $\begingroup$ All limited-precision math has these errors, not just FFTs. $\endgroup$ – endolith May 21 '13 at 23:10
15
$\begingroup$

The differences you see are due to numerical errors in floating point format. All operations needed to perform an FFT and an inverse FFT can only be done with finite precision and you've shown the result of this finite accuracy in your lower right plot.

$\endgroup$
  • $\begingroup$ Would there be a situation where this error could blow up beyond floating point precision? $\endgroup$ – Kitchi May 21 '13 at 20:14
  • 6
    $\begingroup$ And just to confirm @MattL's answer: $10^{-16} \approx 2^{-53}$ and there are 53 bits of mantissa in double-precision floating point numbers. So the rounding error you are seeing is just in the last 2 bits. That's about as good as it gets. $\endgroup$ – Wandering Logic May 21 '13 at 20:18
  • $\begingroup$ @Kitchi: yes, there are many situations where numerical errors can be a major problem, even in floating point format. Matrix inversion would be one of many examples. It all has to do with condition number. $\endgroup$ – Matt L. May 21 '13 at 20:39
  • 1
    $\begingroup$ @MattL. - Wonderful! Thanks for the reference. $\endgroup$ – Kitchi May 21 '13 at 21:25
7
$\begingroup$

In general a number can't be represented exactly in digital form. An error is introduced. If you are in Matlab you can write eps at the command, it gives you a number.

EPS, with no arguments, is the distance from 1.0 to the next larger double precision number, that is EPS = 2^(-52).

The error you see in your plot is in range returned by eps (that is 2^(-52)).

Even though you expect real values in your output from your IFFT you might see that your imaginary part is not exactly equal to zero. Same thing.

$\endgroup$

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.