FFT Processing Gain

Question

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.

Answer 1

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:

The FFT plots for different sizes in frequency domain is:

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.