Definition of the DFT / FFT Bin Size

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.