11
$\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}$).

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ All limited-precision math has these errors, not just FFTs. $\endgroup$
    – endolith
    May 21, 2013 at 23:10

2 Answers 2

Reset to default
19
$\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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Would there be a situation where this error could blow up beyond floating point precision? $\endgroup$
    – Kitchi
    May 21, 2013 at 20:14
  • 9
    $\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, 2013 at 20:18
  • 1
    $\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, 2013 at 20:39
  • 1
    $\begingroup$ @MattL. - Wonderful! Thanks for the reference. $\endgroup$
    – Kitchi
    May 21, 2013 at 21:25
8
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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