11
$\begingroup$

When transforming a noisy signal via Fast Fourier Transform from time to frequency domain there is a "Processing gain" of the FFT which increases as number of bins increases. I.e. the more bins I have the more the noise floor in the freqeuency domain is reduced.

1. Actually I don't understand completely, from where this gain is coming from. Does this mean that I need just sample the signal with higher sampling rate in order to have more bins, hence a higher FFT processing gain?

2. What is about the inverse FFT? Do I have a "Processing lost"? When starting in frequency domain does this mean, the more frequency samples I have, the more noise will appear in the time domain signal? However, this would be counter-intuitive since this would also lead to big distortion of signals when applying padding (of the frequency-domain data) for time-domain interpolation purposes.

$\endgroup$
6
  • 2
    $\begingroup$ Short answer: one way of looking at the DFT is a uniformly-spaced bank of bandpass filters. As you increase the number of bins in your DFT, each filter has a narrower bandwidth (and therefore passes less noise). If you're searching for a narrowband signal, it pays to have the DFT bin width close to the signal of interest's bandwidth. That way, you still pass through the signal unchanged while also passing as little noise as possible. I may expand this later if I get a chance. $\endgroup$
    – Jason R
    May 19, 2014 at 12:08
  • $\begingroup$ I would appreciate an expanded explanation. $\endgroup$
    – Frank
    May 19, 2014 at 13:06
  • 3
    $\begingroup$ designnews.com/… $\endgroup$ May 19, 2014 at 19:41
  • $\begingroup$ @Frank: The link provided by Seth has a slightly more detailed explanation. Increasing the FFT size to "push down the noise floor" is analogous to turning down the resolution bandwidth on a spectrum analyzer. $\endgroup$
    – Jason R
    May 19, 2014 at 22:07
  • 1
    $\begingroup$ ESCHEW OBFUSCATION The FFT SNR increases with the number of FFT points because of the very DEFINITION of the FFT SNR. The FFT SNR is defined as the SNR in a BW equal to the size of the Frequency BIN and the BIN size decreases as the number of FFT points increases. $\endgroup$ Nov 17, 2016 at 22:23

6 Answers 6

7
$\begingroup$

I think the easiest way to wrap around a concept is to have a simple example:

% example of FFT of a very noisy sin wave
f0 = 1000;     % sinusoid frequency
Fs = 10000;    % sampling frequency 
n = 0:1/Fs:1; % one second worth of sample index
N = length(n);
SNR = -20;    % signal to noise ratio is -20dB
Pn  = 0.5*10^(-SNR/10); % signal power is 0.5 for sin wave
NFFT = round([N/8 N/4 N/2 N]); % FFT size to see how it effects the gain


%% signal and generation
sx = sin(2*pi*f0*n);
sn = sqrt(Pn)*randn(1, N);
%% adding noise
xn = sx + sn;
%% signal with and w/o noise in time
figure(1);
plot(n(1:100), xn(1:100)); hold on;
plot(n(1:100), x(1:100), 'r');
legend('noisy', 'clean');
%% FFT of different sizes
figure(2); 
Xf = fft(xn, NFFT(4));
plot(Fs*(0:NFFT(4)-1)/NFFT(4), abs(Xf)/N, '.-'); hold on;
Xf = fft(xn, NFFT(3));
plot(Fs*(0:NFFT(3)-1)/NFFT(3), abs(Xf)/N, 'r.-');
Xf = fft(xn, NFFT(2));
plot(Fs*(0:NFFT(2)-1)/NFFT(2), abs(Xf)/N, 'g.-'); 
Xf = fft(xn, NFFT(1));
plot(Fs*(0:NFFT(1)-1)/NFFT(1), abs(Xf)/N, 'k.-');
legend('FFT size = N', 'FFT size = N/2', 'FFT size = N/4', 'FFT size = N/8');

The plot of noisy and clean sin wave in time domain looks like this: Noisy vs clean sin wave

The FFT plots for different sizes in frequency domain is: enter image description here

i.e., increasing the FFT size means adding more signal samples in the calculation, and therefore easier for FFT to determine the frequency, as the signal information gets added on, while the noise information does not. Here you can see the "relative" noise floor w.r.t signal has decreased.

As for inverse Fourier, I won't say it is a loss, I'd say we went back where we came from.

hth.

$\endgroup$
5
  • 2
    $\begingroup$ While not necessarily rigorous, this is the type of answer that the OP was looking for. The other answers that describe the constant gains inherent in many DFT implementations are not wrong, but they just aren't answering the question that was asked. See the link provided in Seth's comment on the question above as well. $\endgroup$
    – Jason R
    May 21, 2014 at 2:18
  • $\begingroup$ I cannot entirely agree to the statement "there is no sense of IFFT, if we did not do the FFT in the first place." Think about a vector network analyzer providing frequency-domain values. In this case no (forward) FFT is applied a priori. Hence, applying the inverse FFT on these original data would lead to "Processing lost" while transforming to time-domain?! $\endgroup$
    – Frank
    May 21, 2014 at 11:42
  • $\begingroup$ @Frank this means in spread spectrum, we introduce a processing loss at transmitter, to apply processing gain at receiver! In the end we did not gain anything. $\endgroup$
    – learner
    May 21, 2014 at 12:57
  • $\begingroup$ @learner: Spread spectrum is some kind of artificial example since a narrowband signal is "man made" spread at the transmitter in order to achieve some gain at the receiver. However, when using a vector network analyzer there is no step before obtaining the frequency-domain data. Hence, there is no source of artificial "degenerating SNR" in order to gain SNR at some other point in the processing chain. $\endgroup$
    – Frank
    May 21, 2014 at 14:54
  • $\begingroup$ @Frank Actually, whenever I used network analyzer I always did the IFFT of a spectrum sweep (3GHz-11GHz), in that case, I was not able to observe an IFFT processing loss. However, your point is valid. That made me think that FFT gain and IFFT loss are relative to the properties of the signal being considered. Consider a dirac delta function in time, if we do FFT, instead of gain we'll have a loss. Do you agree? $\endgroup$
    – learner
    May 22, 2014 at 5:52
3
$\begingroup$

The "'Processing gain' of the FFT which increases as number of bins increases" is due solely to an issue of definition. the FFT is a "fast" algorithm to compute the DFT. usually the DFT (and inverse DFT) is defined as:

$$ X[k] \triangleq \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N} $$

and

$$ x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{+j 2 \pi n k/N} $$

but it could have been defined as

$$ X[k] \triangleq \frac{1}{N} \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N} $$

and

$$ x[n] = \sum_{k=0}^{N-1} X[k] e^{+j 2 \pi n k/N} $$

and can even be defined as

$$ X[k] \triangleq \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k/N} $$

and

$$ x[n] = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} X[k] e^{+j 2 \pi n k/N} $$

in the latter form, there is no "processing gain" of either the DFT nor iDFT.

$\endgroup$
7
  • $\begingroup$ I don't understand why this answer is downvoted. It doesn't address part 2 of the question, but it's definitely not wrong. $\endgroup$
    – Phonon
    May 19, 2014 at 23:30
  • 3
    $\begingroup$ and it answers the issue of gain of the inverse FFT just as much as it answers the issue of the gain of the forward FFT. such is life. $\endgroup$ May 19, 2014 at 23:44
  • 1
    $\begingroup$ For the "processing gain" the other answers talk about, it does not matter what the normalisation is. The important part is how far down your noise floor is in relation to your signal. $\endgroup$
    – oystein
    May 16, 2017 at 17:26
  • $\begingroup$ so @oystein, "processing gain" applies only to signal-to-noise ratio? $\endgroup$ May 17, 2017 at 1:03
  • 1
    $\begingroup$ This is not the processing gain the OP is referring to. $\endgroup$
    – rbell
    Dec 1, 2021 at 23:23
3
$\begingroup$

Let's look at the effect of an FFT on a coherent signal, and then compare it to the effect it has on a random Gaussian noise sequence. First, consider a coherent signal, such as $x[n] = \sigma_{s} \sin[\omega_{0} n]$. The N-point DFT of the signal is $$ X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2 \pi n k / N}. $$ Suppose $\omega_{0} = 2\pi (10) / N$, so the $X[10]$ is the bin corresponding to our signal. That is $$X[10] = \sum_{n=0}^{N-1} \sigma_{s} \sin(2 \pi 10n/N ) e^{-j 2 \pi 10 n/ N} =\sigma_{s} \sum_{n=0}^{N-1} \sin(2 \pi 10 n/N ) (\cos{2 \pi 10 n/ N} - j \sin{2 \pi 10 n/ N}) , $$ where I used Euler's formula and $\cos(-x) = \cos(x)$ and $\sin(-x) = -\sin(x)$.

Now use $\sin^{2}(x) =1$ and $ 2 \sin x \cos x = \sin 2x$ to get $$ X[10] = \sigma_{s} \sum_{n=0}^{N-1} \frac{1}{2}\sin{ 4 \pi 10 n/ N} - j \sigma_{s} \sum_{n=0}^{N-1} 1 . $$ The real part of $X[10]$ (the first sum) is just the sum of an oscillating series, and so it's value will be small as long as $N$ is of reasonable size. The imaginary part of $X[10]$ is equal to $ - \sigma_{s} N $.

The power corresponding to our signal is then $$|X[10]|^{2} = Re(X[10])^{2} + Im(X[10])^{2} \approx \sigma_{s}^{2} N^{2}.$$

Now let's see what happens to an incoherent sequence of uncorrelated random values with variance $\sigma_{n}^{2}$, $y[n]\sim\mathcal{N}(0, \sigma_{n}^{2})$. The N-point FFT is now $$ Y[k] = \sum_{n=0}^{N-1} y[n] e^{-j 2 \pi kn / N} . $$ Of course, $Y[k]$ is also a random variable. Let's look at the expected value of its power. $$ E(|Y[k]|^{2}) = E\left[\left(\sum_{n=0}^{N-1} y[n] e^{-j 2 \pi nk / N}\right)\left(\sum_{n=0}^{N-1} y[n]^{*} e^{j 2 \pi nk / N}\right)\right] = \left(\sum_{n=0}^{N-1} E(|y[n]|^{2}) \right) + \left( \sum \sum _{i \neq j} E(y[i] y[j]^{*}) e^{j 2\pi (j-i)/N} \right) $$ (I factored the product into two sums, and used linearity of expectation).

Now, $E(|y[n]|^{2}) = \sigma_{n}^{2}$, and since $y[n]$ is assumed uncorrelated from sample to sample, $E(y[i]y[j]$, with $i\neq j$, is simply 0.

Therefore, $$ E(|Y[k]|^{2}) = \sigma_{n}^{2} N $$.

SNR is the ratio of signal power to noise power. Since the noise is described statistically, the SNR is also a random variable. Its expected value increases as the FFT length increases. This is because the FFT coherently sums the signal, while it randomly sums the noise. Specifically, $$ SNR = \frac{|X[10]|^{2}}{|Y[10]|^{2}} = \frac{\sigma_{s}^{2}}{\sigma_{n}^{2}} N .$$ We can see that the SNR increases as N. If we define the input SNR to be, in decibels, $SNR_{input} = 10 \log_{10}\frac{\sigma_{s}^{2}}{\sigma_{n}^{2}}$ we get that, in dB, $$ SNR_{db} = SNR_{input} + 10 \log_{10} N .$$ This is the $10 \log_{10} N$ gain that an FFT has on a coherent signal over a random noise signal.

$\endgroup$
3
  • $\begingroup$ I think your equations may be missing some lowercase n's, and sin(-x) = -sin(x) not sin(x). $\endgroup$
    – DavidG25
    Oct 27, 2021 at 16:42
  • $\begingroup$ Thank you for pointing those out David. I believe I corrected all the missing n's and fixed the sin(-x) typo. $\endgroup$ Oct 28, 2021 at 19:11
  • $\begingroup$ This is close, but not quite right. 1) $\sin^2(x) \neq1$ and 2) The SNR should be the ratio of powers, but a sine wave, $A \sin(x)$ has a power of $A^2/2$. $\endgroup$
    – Ash
    Apr 16 at 18:13
2
$\begingroup$

The FFT processing gain comes from the fact that the DFT (of which FFT is simply a fast implementation) is a non-normalized linear transformation. This is a mouthful, so let's look at what this means.

I'm going to assume that you know what a linear transformation is. Namely, given vectors $\mathbf{x}$ and $\mathbf{y}$ and a matrix $A$ we have

$$\mathbf{y} = A \mathbf{x}.$$

DFT is just such a transformation. In fact, you can use MATLAB dftmtx command to generate this matrix for you based on the length of vector $\mathbf{x}$. This this case,

$$\mathbf{y} = \text{DFT}(\mathbf{x}).$$

This matrix $A$ has some properties. First of all, it's a square matrix, which means that it's probably invertible (and indeed it is!). It also tells us that we're essentially taking components of x and performing a change of basis given by the columns of $A$ to get its DFT. So far so good.

Now, let's get to some more important properties. Matrix $A$ is orthogonal. This means that every column of $A$ is perpendicular to every other column, or more mathematically, $A^TA$ is a diagonal matrix (you may have to think a little about why this is true). This is a very nice property, since simply transposing the matrix gives us something very close to its inverse.

To make this Transpose $\leftrightarrow$ Inverse relationship strict, we want the matrix $A$ to also be normal. This is a matrix whose every column vector has length 1. In other words, if $a$ is a column of $A$, then $\sqrt{a^Ta} = 1.$ If a matrix is both orthogonal and normal, we call it orthonormal, and in this case $A^TA = I$, so $A^T$ is in fact the inverse of $A$. Neat!

The usual DFT matrix (or the usual DFT transform) is orthogonal, but not orthonormal. In fact, if $D$ is the DFT matrix, then $D^TD = N$ where $N$ is the number of columns (or rows, it's square!) in $D$. To make it orthonormal, we should use $\frac{D}{\sqrt{N}}$ instead. If you look at it long enough, you realize that is we scale both forward and inverse transforms by $\frac{1}{\sqrt{N}}$, we're doing extra work in performing the calculations, so we usually just scale by $\frac{1}{N}$ at the inverse.

There are better theoretical reasons for doing it on one side rather than of both. See my answer here for more information.

$\endgroup$
1
$\begingroup$

The processing gain of the FFT refers to increased SNR for a sinusoid. You can think of the DFT or the FFT as a bank of matched filters. The matched filter maximizes the SNR at the output. Another way to look at the processing gain, if you have sinusoid in noise in the time domain at a given SNR and then take the FFT and look at the Sinsoid power vs the noise power in the FFT bin (assuming the frequency corresponds exactly with a FFT bin) then you will see a higher SNR or processing gain. You can think of the FFT as bandwidth filters and the noise in each frequency bin is spread out in comparison to the time-domain signal where the noise is through out the signal.

The processing gain comes about because it coherently adds the components of the sinusoid together. So you will also see this called coherent gain. This coherent addition is also why when you have a longer signal you get more processing gain i.e. more samples add together coherently. By coherent I mean that it assumes you have knowledge of the phase of the signal - in this case the frequency. Alternatively you can think of a longer matched filter as having a narrower bandwidth, so less noise gets through the filter. Thus giving you better SNR or processing gain.

Note that if the sinusoid does not exactly align with a frequency of an FFT bin, then there will still be a peak at near by FFT bins, but then a few of the neighbouring FFT bins will also contain significant magnitudes. There will be a peak at the nearest FFT bin but it will be less than the processing gain. This effect is often callled spectral leakage. You can use windows to reduce the spectral leakage, but you decrease the processing gain as well. The worst case loss is when your signal sits exactly between two FFT bin frequencies.

I would suggest you read the Harris paper on windows. It explains a lot of the details I am talking about.

So if you have a sinusoid in white noise you will get the processing gain by taking the DFT/FFT. By taking the IFFT/IDFT you will suffer a processing loss because you are spreading your signal back into the noise.

$\endgroup$
-1
$\begingroup$

The "gain" is in terms of desired (and easy to see) knowledge. If you transform to the frequency domain, you gain more explicit/visible (as can see it in a graphic plot) knowledge of particular frequency bands, but lose visible (can no longer see it in the FFT plot) knowledge of exact timing information. If you transform back to the time domain, then you gain more explicit knowledge of timing (impulse time and transient changes, etc.), but lose visible knowledge (if you throw away the previous FFT plot) of what frequency bands that that time-domain waveform stimulates.

There is no actual gain in the inherent information present in either the time or frequency vector, more likely some tiny loses due to numerical precision within the FFT.

Increase the sampling rate of an already band-limited signal (already below Nyquist at the lower sample rate) adds no new information (except possibly moving the sample data farther from anti-alias filter distortions, and spreading out quantization noise). There's nothing new to which to add more "gain".

But increasing the total sample vector time (not with zero-padding, but with more actual relevant data) can add fresh new information, which may allow processing "gain" to lower the noise floor, especially given a stationary signal.

$\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.