7
$\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$
  • 1
    $\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 '14 at 12:08
  • $\begingroup$ I would appreciate an expanded explanation. $\endgroup$ – Frank May 19 '14 at 13:06
  • 3
    $\begingroup$ designnews.com/… $\endgroup$ – Seth May 19 '14 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 '14 at 22:07
  • $\begingroup$ The more samples you have, the more accurate is the frequency analysis of the FFT algorithm. Real signal adds up coherently in frequency domain, whereas noise adds up incoherently. Hence your SNR of the frequency peaks will increase if you have more samples. $\endgroup$ – M529 Mar 9 '16 at 11:18
4
$\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$
  • 1
    $\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 '14 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 '14 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 '14 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 '14 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 '14 at 5:52
1
$\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$
  • $\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 '14 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$ – robert bristow-johnson May 19 '14 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 '17 at 17:26
  • $\begingroup$ so @oystein, "processing gain" applies only to signal-to-noise ratio? $\endgroup$ – robert bristow-johnson May 17 '17 at 1:03
  • $\begingroup$ @robert bristow-johnson, yes that is my understanding at least. It does not matter if you scale your DFT result by $\sqrt{N}$, $N$ or $1$, since you scale both 'signal' and 'noise'. $\endgroup$ – oystein May 17 '17 at 15:22
1
$\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, privacy policy and cookie policy

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