3
$\begingroup$

When reconstructing the frequency domain for an FFT, what is the most self-consistent way to do this -- i.e. how is it best to define the bin width, $\Delta f$?

For example, previously I thought it a simple matter of saying, $$\Delta f = span / N_{points,FFT}$$ where the span is the size of the window you want to look at and $N_{points,FFT}$ is the number of points that should appear in the final FFT result. This makes very clear sense especially when you deal with some FFT spectrum analyzer where you set the span and the number of points in the final FFT (some times called the number of FFT lines) can also be set but tends to have some upper value for that device.

However I have also seen definitions attached to the sampling rate for the incoming transient signal to be FFT'd, as $$\Delta f = f_{sr} / N_{points,FFT}$$ or even as $$\Delta f = 2 f_{sr} / N_{points,FFT}$$ depending on how you define $N_{points,FFT}$. I.e. the number of points that goes into making the FFT or the number of points that will appear in the final FFT result because half the spectrum is thrown away due to mirroring.

Maybe it doesn't matter and it just depends on the way you choose to define things. But if anyone has any insight that would be helpful!


I am adding a little more to clarify my confusion.

Suppose you have some FFT spectrum analyzer that can process at maximum 2048 points in a time transient. That then means The final FFT would have 1024 points -- as we discard the mirror image. I then (again this is all in the context of making an FFT with some FFT spectrum analyzer device) say I want to set my span of this FFT to $50\ \rm{Hz}$. This would give a resultant FFT with a bin width of $\Delta f = 50 / 1024 = 0.049\ \rm{Hz}$. To me this must imply that the sample rate, $f_{sr}$, must vary according to the desired span.

So is this is all question of what your free parameters are, whether the maximum number of points in a transient signal is fixed, or the maximum sample rate you can take, and so on?

$\endgroup$
  • $\begingroup$ I appended my answer before I saw your clarification. It should answer your questions. I would recommend that you use "point" for your sample values and "bin" for your DFT values. A "DFT point" is misleading. Typically you set two parameters, the sampling rate and the sampling interval (frame), everything else gets set from those. Longer intervals give you bigger "bin spacing" and thus higher resolution (the ability to distinguish tones). Higher sampling rates don't improve resolution, but they do increase the frequency range before aliasing occurs. $\endgroup$ – Cedron Dawg Jul 15 at 13:50
3
$\begingroup$

I don't think Hilmar's answer is very good as it interprets the DFT within a specific application context. That confuses issues.

The DFT is a tranform that works on a set of N samples. The samples are presumed to be evenly spaced in their domain on a finite interval of samples is called a frame. It may be time, it may be distance, or it could even be another dimension. The bin values tell you how close your samples are to corresponding to that bin. The important thing to remember is each bin corresponds to a sinusoidal which has a frequency of the bin index measured in units of cycles per frame. What happens outside the frame is out of scope for the DFT. Saying "The DFT assumes the interval is infinitely repeating" is misleading without any constructive benefit. What is true is that an inverse DFT can be extended, and it will form a repeating pattern.

The concept of "energy" is only valid is a subset of applications. "Leakage" is not about energy at all, it is about representation of points in multidimensional coordinate systems. But that discussion is a bit mathematical.

What it seems you are stuggling with having to do with definitions on particular applications and what is the significance of the number of sample points on your frequency values and the possible resolutions. Those concepts are straightforward with a understanding of the DFT devoid of application details.

Suppose you have a given signal over a fixed interval. If that signal has three cycles in the frame, the parameters of the fundamental will be found in bin 3 (zero based indexing), and its harmonics will be in bin 6, 9, 12, etc. The number of sample points you use will determine the number of bins there are. The more bins there are the higher up your halfway point (called Nyquist) is. If the frequency of your signal (or one of its harmonics) exceeds the Nyquist value, then it will "wrap around" and look like a different frequency. This is called an alias.

For instance, suppose you had N=16. Then the Nyquist bin is 8. A signal will 10 cycles per frame will land in bin 10, but its mirror image value lands in bin 6, so if you are looking at the DFT you would say, "Hey there is a 6 cycles per frame signal in there", when in fact it is 10. Increasing your sample count would fix that. For N=32, the 10 bin would still have a value, but now the mirror image is in 22. That's why you have to sample at least twice the rate of the highest frequency you want to find to have it land in the lower half.

BTW, every DFT is exact, aka lossless.


The sampling rate is what ties the units of the DFT to the units of your application. N has units of samples per frame. $f_s$ is the conventional symbol for samples per application unit, usually seconds, so the unit is samples per second, designated with Hz. This is a little misleading as the sampling is better thought of as a rate instead of a frequency. Anyway, using T for your interval length, measured in seconds, you have.

$$ f_s \left(\frac{samples}{second}\right) = \frac{ N \left(\frac{samples}{frame}\right) }{ T \left(\frac{seconds}{frame}\right) } $$

Of course, you can switch that around, say:

$$ N = f_s \cdot T $$

To interpret the bin values, $k$ is usually used for the bin index, so the frequency associated with a bin is $k$ cycles per frame. Hence:

$$ \frac{ k \left(\frac{cycles}{frame}\right) }{ T \left(\frac{seconds}{frame}\right) } = k/T \left(\frac{cycles}{second}\right) $$

Therefore the "bin spacing", i.e. the difference in frequency between two adjacent bins, is $1/T$, but the units are still cycles per second.

Now, from above, $ T = N / f_s $, so the bin spacing can also be called $ f_s / N $.


And just a bit more insight...

Your Nyquist frequency is always going to be 2 samples per cycle for any N.

$$ \frac{ 2\pi \left(\frac{radians}{cycle}\right) }{ 2 \left(\frac{samples}{cycle}\right) } = \pi \left(\frac{radians}{sample}\right) $$

It is also helpful to picture the DFT bins arranged around the unit circle in the complex plane. The DC bin on the 1, and the Nyquist is on the -1. The Nyquist is the same distance from the DC whether you go clockwise or counter-clockwise. The bins are indexed from 0 to N/2 across the top for even N, and 0 to (N-1)/2 for odd N. There is only a Nyquist bin for even N. The bottom half is better indexed with negative values($-k$), but usually comes back as the upper part of the results($N-k$). The definition doesn't care and they are aliases.

The mirror image, aka conjugate symmetry, is only true for real valued signals. Ultimately it works the way it does because:

$$ \cos( \theta ) = \frac{ e^{i\theta} + e^{-i\theta} }{2} $$

But that's a longer story.

$\endgroup$
  • $\begingroup$ okay now this is a much better answer and is getting closer to what I am trying to understand. I still feel there is somehow an intrinsic relation between the span of an FFT and the sampling rate. I'm going to add a bit more in my question if you don't mind taking a look? $\endgroup$ – Q.P. Jul 15 at 13:21
  • $\begingroup$ @QuantumPenguin, I've updated my answer for you. You might also want to check out dsprelated.com/showarticle/768.php for a "physical meaning" of the bin values. $\endgroup$ – Cedron Dawg Jul 15 at 13:43
  • $\begingroup$ Thanks for expanding on your answer! Also nice discussions in the link you provide. Really the last piece for me is to somehow relate, or show the interconnection of the span and the sample rate. $\endgroup$ – Q.P. Jul 15 at 16:18
  • 2
    $\begingroup$ @QuantumPenguin The frame is the span, or perhaps better said: The DFT frame covers a span. The sample rate is independent. It is the conversion factor between the length of your span and the sample count N. $\endgroup$ – Cedron Dawg Jul 15 at 16:48
  • 2
    $\begingroup$ @QuantumPenguin Sample rate, span length, or sample count? You get to choose 2. $\endgroup$ – Cedron Dawg Jul 15 at 17:00
5
$\begingroup$

Let's assume we have a sample rate of $f_s=10 kHz$ and FFT size of $N=1000$

  1. Your bin spacing is $\delta f = 10 Hz$. It's simply the sample rate divided by the FFT size. That's all there is to it.
  2. Keep in mind that the FFT requires both the time domain and the frequency domain signal to be perodic. Most signals are not, so there needs to be some sort "accommodation" that's specific to the needs for your application.
  3. A real-valued sine wave with a frequency that is an integer multiple of the bin spacing will only show up in two bins symmetric around zero. I.e. a 100 Hz sine wave will show up in bins +10 and -10 (assuming we index the bins from $[-N/2,N/2-1]$
  4. A complex exponential with a frequency that is integer multiple of the bin spacing will only show up in one bin. I.e. a +100 Hz complex exponential will show up bin +10.
  5. A cosine wave with a frequency that's NOT an integer multiple of the bin spacing (e.g. 105Hz) will spread out over all bins. The bulk of the energy will be in the neighborhood of 105 Hz but there will be energy in ALL bins. This is a direct consequence of bullet 2): the FFT assumes periodicity with $N/f_s$. In essence the FFT doesn't calculate the spectrum of the sine wave, but the spectrum of a signal that consists of 1000 sample long snippet of a 105Hz cosine that gets repeated infinite times. At the splice point there is a massive discontinuity and that causes the energy to spread over all bands
  6. In order to minimize this spreading effect, one can apply a window, that tapers down the edges of the time domain frame and reduces the discontinuity. On the other hand, the window also smears out the energy in the frequency domain, so you can't get any sharp lines any more.
  7. Many people think that the FFT will give you an "exact" representation of the signal's frequency content. That's not the case unless the time domain signal is either periodic with the FFT length or if it's finite in time. For all other signals the results will depend heavily on the exact process and parameters chosen.

EDIT: reworded item 7 per the comment

$\endgroup$
  • $\begingroup$ Thanks for the answer. While a very nice anser and a good overview of an FFT in general. I am not convinced by point 1. For example. If I have make an FFT with a $50 \rm{Hz}$ span, and that finall FFT will have 1000 points or FFT lines then $\delta f = 0.05 \rm{Hz}$. This implies that the span of your FFT window and sample rate are some how the same -- I struggle with this! $\endgroup$ – Q.P. Jul 15 at 12:55
  • $\begingroup$ Hilmar, I suggest you check out my latest blog article: dsprelated.com/showarticle/1284.php Your #7 is completely false. $\endgroup$ – Cedron Dawg Jul 15 at 13:13
  • 1
    $\begingroup$ @QuantumPenguin: your span is ALWAYS determined by the sample rate. You can't choose it independently. $\endgroup$ – Hilmar Jul 15 at 15:50
  • $\begingroup$ @CedronDawg: I agree it's poorly worded. The FFT gives you always an exact result as per it's definition. It's just not the result that most inexperienced people want or expect $\endgroup$ – Hilmar Jul 15 at 15:53
  • $\begingroup$ @Hilmar That's exactly what I wanted to check that the sampling rate and the span are somehow coupled/the same. Are you able to provide a reference? $\endgroup$ – Q.P. Jul 15 at 16:03
2
$\begingroup$

FFT result bin spacing is proportional to sample rate and inversely proportional to the length of the FFT. Any two of the three (deltaF, SRate, N) can be independant parameters (within the range your equipment allows). That will determine the third. e.g. the maximum range of the two free variables in your spectrum analyzer settings will determine the maximum range of the third dependent variable.

You have to sample longer (or use samples from a longer window) to tell closer spaced frequency spectra apart. You can't tell a 440 Hz note "A" from a 441 Hz note in fast music. But with a constant concert-A tone for a minute, you can just count the zero crossings in a waveform plot, and see a clear difference of over 100 more zero crossings. Either a longer FFT, or wider bin spacing due to less samples used. And you have to sample faster if you want to see faster changing input (higher maximum frequencies). A higher sample rate.

$\endgroup$
  • $\begingroup$ You're kind of conflating resolution (telling two tones apart) with precision (variance of your measurement) there in your second paragraph. You don't need longer intervals for higher precision, but it sure helps with resolution. $\endgroup$ – Cedron Dawg Jul 15 at 21:19
  • $\begingroup$ The extra (left out above) parameter is length vs. S/N. With zero noise and/or interference, specifying a sinewave requires only 3 (or 4?) non-aliased samples. Approaching zero S/N, length for statistical significance goes to infinity. In actual use, the term "resolution" has multiple meanings. $\endgroup$ – hotpaw2 Jul 15 at 22:18
  • $\begingroup$ @QuantumPenguin, Clarifying, common usage and technical word usage issues aside, increasing the interval moves tones up the DFT scale and thus they separate more and are easier to tell apart, independent of N. Keeping the interval the same and changing N, leaves the tones in the same spot on the DFT scale, but shifts where the wraparound point (Nyquist) is. Noise is a side issue, and of course more samples at the same noise level will yield better results. Another side issue, the interval choice for real world applications is also heavily dependent on the expected duration of the sounds. $\endgroup$ – Cedron Dawg Jul 15 at 22:43
2
$\begingroup$

Your confusion is very much understandable because it took me a while to understand the frequency axis spacing issue. Finally after digging for years, I found that your question is answered by the theorem of Cooley (the man who made FT possible on computers) in 1967. It is sad that no textbook addresses this as a theorem but casually mentions in passing.

More details here: https://chemistry.stackexchange.com/questions/117901/zero-filling-fourier-transform-in-nmr/117919#117919

The frequency axis spacing issue is a result of a beautiful theorem. I found in Cooley's original paper from 1967 [1, p. 80].

Theorem 1

If $x(t), -∞ < t < ∞,$ and $a(f), -∞ < f < ∞,$ are a Fourier integral transform pair,

$$x(t) ↔ a(f),$$

then $Tx_p(jΔt), j = 0, 1, \cdots, N - 1,$ and $a_p(nΔf), n = 0, 1, 2, \cdots, N - 1,$ are a finite Fourier transform pair,

$$ \begin{align} Tx_p(jΔt) &= T\sum_{l = -∞}^∞{x(jΔt + lT)} ↔ \sum_{k = -∞}^∞{a(nΔf + kF)} \\ &= a_p(nΔf) \end{align} $$

where $Δf = 1/(NΔt) = 1/T.$

It is to be remembered that the finite Fourier transform pair

$$X(j) ↔ A(n)$$

is defined by

$$X(j) = \sum_{n = 0}^{N - 1}{A(n)W_N^{jn}}, \quad W_N = e^{2πi/N}$$

Thus, if two functions are Fourier transforms of one another, then the sequences obtained from them by aliasing and sampling in this fashion are finite Fourier transforms of one another.

Cooley & Tukey are the key persons who made Discrete Fourier Transform (DFT) possible by computers for lowly mortals like us, otherwise it was an elitist subject among the mathematicians. However, math researchers told me this was known in 1754. Full discussion here: History of Integral Transform Theorem

References

  1. Cooley, J.; Lewis, P.; Welch, P. Application of the Fast Fourier Transform to Computation of Fourier Integrals, Fourier Series, and Convolution Integrals. IEEE Transactions on Audio and Electroacoustics 1967, 15 (2), 79–84. https://doi.org/10/bmw8z8.
$\endgroup$
  • $\begingroup$ Nice answer! The one thing I would really like to see is a relation between the sampling rate and the span. $\endgroup$ – Q.P. Jul 15 at 16:04
  • $\begingroup$ The sampling frequency of the experimental data determines the maximum value of the frequency axis in the Fourier domain. For example, if my sampling frequency was 250 Hz, after fft the frequency axis will end at 125 Hz. This is another theorem or criteria attributed to Nyquist. Although you will find ten other names associated with the same concept. This assumes the number of data point are even. I have asked similar questions like these at length in this forum and MATLAB forums. Search FFT and DFT even and odd. It was a good discussion. $\endgroup$ – M. Farooq Jul 15 at 16:55
0
$\begingroup$

In a real spectrum analyzer the input sample rate may be wider than the pass band of the upstream filters. After the FFT, only the frequencies in the passband of the filter are shown in the span. So the first equation you showed is for you don't crop anything in the frequency domain, the other equations are more general.

Also real spectrum analyzers will apply a window function to the time domain to give the frequency domain a nice shape this typically makes the actual resolution bandwidth several bins wide, so the FFT bin spacing is not as relevant.

$\endgroup$
0
$\begingroup$

Just a quick note, thanks to all for the contributions. Together you helped me understand my problem. Essentially what we can say is that the size of the final FFT window or the span, is simply $$span = \Delta f \left( \frac{N_s}{2} - 1 \right)$$ or in context of the sample frequency, $f_s$, $$ span = f_s \left( \frac{1}{2} - \frac{1}{N_s} \right)$$. Where $N_s$ is the number of samples to be FFT's ($N_s / 2$ is the number of points left in the final FFT result as we throw half away because of mirroring), and $\Delta f = f_s / N_s$ is the line width resolution.

$1/\Delta_f$ is the amount of time required to take a transient signal due to the Fourier limit.

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