2
$\begingroup$

I was reading a couple of these threads and I was wondering: Is it possible for an FFT signal to include frequencies less than $1/N$?

Consider a time-series of length $N$, and I perform an FFT on it. In the zero-th bin of the FFT is the DC signal, and first bin is frequency $1/N$, in the second bin is frequency $2/N$ etc.

Does this mean that the smallest frequency accounted for is a signal where one full period fits in the data length? Or can there also exist frequency where only half/quarter periods will fit in the given length?

$\endgroup$
  • $\begingroup$ Does zero frequency a.k.a. DC count as a frequency less than $1/N$? $\endgroup$ – Dilip Sarwate Jul 12 '13 at 22:30
4
$\begingroup$

A DFT will convert a segment of a periodic waveform of any frequency (uniquely below Nyquist) into an orthogonal set of frequency results. The problem is that if the signal is not periodic in the FFT length, the result will not be in one result bin, but be smeared into all the FFT result bins, due to convolution with the transform of the rectangular or other window function, making it difficult to separate the periodic signal from narrowband + wideband noise (or DC + ramp + noise for spectrum below the 1st bin).

Another potential problem with estimating non-periodic real spectrum very near DC (or Fs/2) is interference from its own negative frequency image in the DFT/FFT result, which can be constructive or destructive depending on phase, and thus non-trivial to account for.

So yes, the low frequency, below Fs/N, will "exist" in the DFT/FFT complex result, but be more difficult to impossible to find or estimate, depending on the signal to noise ratio. But in zero noise, you theoretically need only 3 or 4 non-aliased samples to find a single pure sinusoid of any frequency, so it will be represented in the transformed N samples, for N >= 4, just not clearly in only 1 or 2 DFT/FFT result bins.

$\endgroup$
  • $\begingroup$ So if I understand you correctly, I can reconstruct a signal which has a frequency of less than $1/N$, but each bin individually will be of an integral frequency? $\endgroup$ – Kitchi Jul 12 '13 at 19:46
  • $\begingroup$ All the bins together will be a vector space representing any frequency. Any single bin will contain only a fraction of information, and thus be ambiguous. Could be an integral frequency, or a portion of some other windowed non-integral frequencies, or some mix of both. Yes, the windowed fraction of a very low frequency signal can be reconstructed. $\endgroup$ – hotpaw2 Jul 12 '13 at 20:14
1
$\begingroup$

Each bin in the FFT actually corresponds to energy in a range of frequencies, so while the notional center frequency of bin i corresponds to a frequency Fs * i / N, the bin will represent energy either side of this notional center frequency. So to answer you question, energy below a frequency of Fs / N will be represented in bin 0.

Note that N just determines the resolution of your FFT, i.e. how close together in frequency two distinct components can be while still appearing in two different FFT output bins.

Note also that a suitable window function is assumed to have been applied prior to the FFT, which is nearly always the case in practical FFT-based applications.

$\endgroup$
  • $\begingroup$ I was actually wondering if all the frequencies in the FFT represent signals which have an integral number of cycles in the N samples, or if it is possible for them to have a less than integral number of cycles? $\endgroup$ – Kitchi Jul 12 '13 at 10:50
  • $\begingroup$ I think I already answered that, but to clarify - the center frequency of each bin corresponds to an integer number of periods, but components above and below this integer value will also appear in the same bin. $\endgroup$ – Paul R Jul 12 '13 at 10:54
  • $\begingroup$ Not energy in just bin 0, but mostly in multiple bins around bins 0 and 1, depending of the frequency response of the window function. Given a non-zero stop-band, a tiny amount will appear in every bin. $\endgroup$ – hotpaw2 Jul 12 '13 at 16:04
  • $\begingroup$ True - I was assuming a reasonable window function and that spectral leakage could therefore be ignored for the purposes of this discussion. $\endgroup$ – Paul R Jul 12 '13 at 17:00
1
$\begingroup$

If you are really asking about the discrete fourier transform (DFT) then the answer is no, because it is not possible for a signal that repeats every $N$th sample to contain a frequency of less than $1/N$. If your original signal was longer than $N$ samples and you are chopping it to $N$ samples to do the DFT then what you are DFTing is not the original signal, it is a signal that repeats every $N$th sample.

The DFT converts your $N$ samples into the exact set of $N$ complex exponentials that when added together will reproduce your $N$ samples. But if you extend those complex exponentials beyond the $N$ samples you will see that you get an exact repeat of the original $N$ samples. So the DFT really only tells you something about the frequencies of signals that are infinitely repeating with a period of $N$.

Example: Suppose you had a triangle wave of period 8 samples: $[-1, -\frac{1}{2}, 0, \frac{1}{2}, 1, \frac{1}{2}, 0, -\frac{1}{2}]$, but you take the DFT of only the first 4 samples. You will get:

$$ -\frac{1}{4} (1 + (1 + i) e^{-\frac{1}{2} i \pi k} + e^{-i \pi k} + (1 - i) e^{-\frac{3}{2} i \pi k}) $$

But this function produces the sequence: $[-1, -\frac{1}{2}, 0, \frac{1}{2}, -1, -\frac{1}{2}, 0, \frac{1}{2}]$. That's a sawtooth not a triangle wave, and has a large discontinuity every 4th sample.

When you took the DFT of $N$ samples you were implicitly stating that you wanted the transform of a signal that repeats every $N$th sample.

$\endgroup$
  • $\begingroup$ I understand your point, but coming it at it from a pragmatic standpoint I am underwhelmed. Suppose you start out with an analog signal that is a very low-rate tone. You sample the signal. You FFT the signal with $N$ such that the frequency of the tone is less than $\frac{1}{N}$. Will the tone still show up in the FFT? Absolutely. It won't be in a single bin like a tone at $\frac{1}{N}$ would have been, but it will show up. $\endgroup$ – Jim Clay Jul 12 '13 at 17:33
  • $\begingroup$ I just demonstrated exactly that: I showed you a tone with frequency 1/8, then I took a 4-point DFT and it showed up: smeared across the entire spectrum. Because what I actually DFT'd was a completely different function that repeats every 4th sample and has a large discontinuity. $\endgroup$ – Wandering Logic Jul 12 '13 at 17:56
  • $\begingroup$ Then I suggest changing the first sentence of your answer. At best it is misleading/ambiguous. $\endgroup$ – Jim Clay Jul 12 '13 at 19:39
  • $\begingroup$ I changed it as you suggested. $\endgroup$ – Wandering Logic Jul 13 '13 at 17:52

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.