FFT and Nyquist frequency - higher frequencyresolution with lesser samples

[sodemus]

So, let's say you have a signal, bandpass filtered between 10Hz and 1000Hz. The signal is then sampled at 2000Hz. A window of 20 samples is then FFT:d. You then get a frequency resolution of 2000/20 = 100Hz (the FFT contains 20 points). One consequently doesn't know anything about any other frequencies.

However, Shannon Nyquists Sampling Theorem (SNST) states that all information about a signal with maximum frequency f_m is preserved through sampling at 2*f_m. If the entire signal can be reconstructed at a specific sampling rate, why shouldn't you then be able to reconstruct a FFT with better frequency resolution than 100Hz even if the sample size only is 20 points?

Let's start with the ideal assumption with no limitations due to technology and than move on to what can be done in the real world.

Hope I have expressed myself clear enough. I realize this should be a very simple question with a simple answer (stationary assumptions of the signal perhaps... what do I know?) but I don't see the catch.

 

[dlgoff]

You then get a frequency resolution of 2000/20 = 100Hz (the FFT contains 20 points).

Wouldn't this be true for the lower frequencies also?
From this wikipedia page on Discrete Fourier Transforms they mention that the output of a DFT is, for real inputs, half redundant.

If x_0,..., x_{N-1} are real numbers, as they often are in practical applications, then the DFT obeys the symmetry:

X_k = X_{N-k}^*.

The star denotes complex conjugation. The subscripts are interpreted modulo N.

Therefore, the DFT output for real inputs is half redundant, and one obtains the complete information by only looking at roughly half of the outputs X_0,..., X_{N-1}. In this case, the "DC" element X0 is purely real, and for even N the "Nyquist" element XN / 2 is also real, so there are exactly N non-redundant real numbers in the first half + Nyquist element of the complex output X.

Using Euler's formula, the interpolating trigonometric polynomial can then be interpreted as a sum of sine and cosine functions.

http://en.wikipedia.org/wiki/Discrete_Fourier_transform#The_real-input_DFT"

 

[sodemus]

Wouldn't this be true for the lower frequencies also?
From this wikipedia page on Discrete Fourier Transforms they mention that the output of a DFT is, for real inputs, half redundant.

Oh yeah. I have filtered it below 10Hz for a different reason. That aside, I would imagine the problem is in principle numerically ill-conditioned at lower frequencies.

 

[chroot]

The DFT is half-redundant for real inputs because it its right half is a mirror image of its left half. The Nyquist frequency is in the middle; frequencies below Nyquist are on the left.

If you take a 20-point DFT at 2 kHz, you get only 10 points between DC and the Nyquist frequency, 1 kHz. That's a "real" frequency resolution of 50 Hz, not 100 Hz.

- Warren

 

[sodemus]

The DFT is half-redundant for real inputs because it its right half is a mirror image of its left half. The Nyquist frequency is in the middle; frequencies below Nyquist are on the left.

If you take a 20-point DFT at 2 kHz, you get only 10 points between DC and the Nyquist frequency, 1 kHz. That's a "real" frequency resolution of 50 Hz, not 100 Hz.

- Warren

Thank you for the correction.

I don't think I get that entirely. How is that a real frequency resolution of 50 Hz? 10 points between 0 and 1000Hz should yield a resolution of 100Hz, no? And shouldn't 50Hz resolution contra 100Hz resolution be better (which I feel shouldn't be the case)?

But to return to the original question: how does this compare with SNST about reconstructing the signal in its entirety?

 

[chroot]

Er, excuse me, heh. I need to proof-read my posts. You're right, it's 100 Hz resolution no matter how you slice it.

The sampling frequency determines the Nyquist frequency. Any signal content at higher frequencies will be aliased into the Nyquist band, and the signal will be corrupted. Assuming you have alias-free data, you can take an FFT of as many or as few points as you like to obtain as much resolution as you want. You can zero-pad your original 20 samples and obtain a more detailed DFT with higher resolution.

The number of points you choose for your DFT is independent of your sampling frequency.

- Warren

 

[sodemus]

Er, excuse me, heh. I need to proof-read my posts. You're right, it's 100 Hz resolution no matter how you slice it.

The sampling frequency determines the Nyquist frequency. Any signal content at higher frequencies will be aliased into the Nyquist band, and the signal will be corrupted. Assuming you have alias-free data, you can take an FFT of as many or as few points as you like to obtain as much resolution as you want. You can zero-pad your original 20 samples and obtain a more detailed DFT with higher resolution.

The number of points you choose for your DFT is independent of your sampling frequency.

- Warren

Thanks for your reply! Well, the lowpass-part I mentioned earlier is just there to avoid folding.

Hm, I don't think I understand how that could improve resolution. In view of the SNST, something would make sense, I just didn't expect it to be that.

However, when I read here http://zone.ni.com/devzone/cda/tut/p/id/4880 I read the opposite. Under the heading "Distinguishing Resolutions" one can read:
"Zero padding does not improve the resolution associated with your input signal -- the only way to do this is to increase the time duration of the block of signal that you examine."

So what would then help me increase frequency-resolution? I could use same length of window but higher sampling frequency or I have to increase window length because the required windowlength for a prescribed frequency resolution is related to what frequency content the signal actually has?

But then again(!), how does this compare to the SNST (which I'm getting a little tired of writing so from now on it is SNST for short. Edit: abbreviation implemented in earlier posts as well)?

 

[chroot]

Well, your NI source is ambiguous. Certainly, zero-padding does increase the resolution of the resulting DFT, but it does not actually contain more information. You are indeed better off actually using more samples in your DFT.

I really don't know what you're asking for in relation to the SNST. All the SNST tells you is that you need to sample at 2*f_max, if f_max is the largest frequency component of your signal. When it comes time to figure out what resolution you need in your DFT, you have to make another, completely unrelated decision -- how many samples do you want to use?

- Warren

 

[sodemus]

I really don't know what you're asking for in relation to the SNST.

See my first post. As I also say there, apart from numerical limitations, what is the theoretical catch?

 

[chroot]

I'm sorry, I really just don't understand what you're asking. If you take the range 0-2 kHz and select 20 points along it, then the points are 100 Hz apart. How could they be anything else?

- Warren

 

[sodemus]

I'm sorry, I really just don't understand what you're asking. If you take the range 0-2 kHz and select 20 points along it, then the points are 100 Hz apart. How could they be anything else?

- Warren

Yes, using the FFT you will not get more information than that. However, the signal is sampled at a rate of 2000 Hz and hence you should in principle be able to reconstruct the entire signal (if it doesn't contain any energy in frequencies higher than or equal to 1000Hz). Having complete knowledge of the signal should imply complete knowledge of it's spectrum as well.

But ok, to take a counter example we could take it to an extreme and say that you have only 2 samples (say [x_1,y_1] = [0,0], [x_2,y_2] = [0.005,1] yet only 1/2000 seconds apart. There is then obviously more than one sinusoid with period longer than 1/1000 seconds that goes through the points, e.g. y=sin(50*pi*x) and y=2*sin(100*pi*x/6) obviously with different spectra. So obviously it's not only the sampling frequency that determines whether or not you can reconstruct the entire signal. So again, perhaps the signal needs to be sampled over an infinite time interval for SNST to be valid or something. It's that "exclusion clause" I would like to know. =)

 

[chroot]

Whoever said that a 20-sample DFT of a windowed piece of the signal would let you reconstruct the whole signal for all time? That isn't true!

- Warren

 

[sodemus]

Whoever said that a 20-sample DFT of a windowed piece of the signal would let you reconstruct the whole signal for all time? That isn't true!

- Warren

No, obviously not. But what then is the requirement/clause/condition? Assuming the signal is periodic and with a limited bandwidth.

 

[chroot]

If you have the DFT of twenty points, then you can only reconstruct those twenty points -- no more. The rest of the signal is effectively unknown to you, except perhaps via its statistics.

- Warren