# $\mathrm{FFT}$ generates non-linear noise

I followed the tutorial for generating the frequency spectrum of a signal here, and for testing I generated a sine signal with the frequency of $440 \textrm{ Hz}$. That resulted in the time domain in the following picture:

And when I convert it into the frequency domain, I get:

My question now is:

• Why is the background noise shaped like it is?
• I would have expected a more even noise, or rather a linear shaped noise. Where does this shape come from?

Edit concerning the technical data:

• Sample rate is $44100\,\textrm{Hz}$, which should be enough
• FFT length is identical to the signal length, i.e. 1323000 points.
• The absolute frequency of your signal doesn't mean anything if you're not specifying the sample rate; this is a digital system! – Marcus Müller Mar 15 '16 at 11:43
• What's your FFT length? – Marcus Müller Mar 15 '16 at 11:47
• I gave your question an upvote "in advance"; please still add information on sampling rate, FFT length, sine amplitudes, numerical type, FFT implementation… – Marcus Müller Mar 15 '16 at 12:01
• Added the sampling rate and the FFT length. Why are the sine amplitudes needed? – arc_lupus Mar 15 '16 at 12:32
• more for completeness; from the graph, I'd guess it's rougly $\sqrt 2$. – Marcus Müller Mar 15 '16 at 12:42

First of all, look at the power of what you call background noise:

It's between -150 dB and -120 dB below your peak's power. Which means that the magnitude of these FFT points is somewhere in $[10^{-7.5};10^{-6}]$ of the main peak magnitude.

That screams "numerical inaccuracy" all over the place:

Assuming your FFT was implemented using 32 bit IEEE754 floating point numbers, you'd have to realize that for each point of the FFT output, there's at least an FFT-length amount of additions taking place with a very finite numerical precision.

Now your FFT has an enormous length; $1323000\approx 1.3\cdot 10^6$ additions bring the most stable algorithm to its knees. For a bit of details on error analysis on commonly used FFT algorithms, refer to [1].

Have a look at the DFT matrix to understand the concept of how these values come to be: For the frequency of your spectral peak, signal-period ($\frac{1}{f_\text{signal}}$) spaced samples are added up; since they always have the same value (definition of "period"), the result is large; for all the others, the should cancel each other out. For example, the bin at $2\cdot f_\text{signal}$ always adds up the same absolute value, but with alternating sign. For other bins, you just take values from the sine and add them up. What happens now is that due to limited floating point math, when you add up a large and a small number, and then subtract the large number again, you won't get the same small number you had – accuracy reduces with magnitude!

Now, the FFT is an algorithm that is pretty resilient with respect to that (because it doesn't try to add up all FFT-length values at once), but there's only so much stability that an algorithm can achieve with a given machine $\epsilon$.

I would have expected a more even noise, or rather a linear shaped noise.

Why that? If anything, you're observing a process where the imperfections of the FFT are correlated with the input signal. Something like that won't have "white" PSD! Remember, the PSD of a process is the Fourier transform of its autocorrelation; in your case, it seems there's more autocorrelation at higher frequencies.

Do your understanding a favor and add a bit of as-good-as-feasible white, gaussian noise to the input, maybe with a variance of $N=10^{-3}$ of the sine's amplitude, and do your mag squared FFT again. You'll see the noise floor where you expect it, and it will be flat, because the (dominant) source of noise is actually white, and not strongly correlated.

Also, your $1.3\cdot10^6$ FFT really isn't all that helpful, unless you actually need a frequency resolution of $\frac{f_\text{sample}}{N}=\frac{4.41\cdot 10^4}{1.323\cdot10^6}=33\,\text{mHz}$ (which I dare to doubt). Try with shorter pieces of your signal!

[1] Tasche, M., and H. Zeuner, Roundoff error analysis for fast trigonometric transforms, in Handbook of Analytic-Computational Methods in Applied Mathematics, G. Anastassiou (ed.), Chapman & Hall/CRC, Boca Rota, 2000, 357–406.

• The number of fft points was just chosen due to lazyness and for first tests... – arc_lupus Mar 15 '16 at 13:10
• well, use something smaller (1024 is still plenty) and see how that improves the noise – Marcus Müller Mar 15 '16 at 17:03