1
$\begingroup$

I am studying DFT/FFT and I'm very confused about one thing. I read online that the frequencies we can sample with DFT must be integer (Why does the frequency in the DFT have to be an integer?). Later I found out that the frequency bins in frequency domain in FFT can be non-integer numbers, since they are calculated like this:

delta f = sampling frequency / number of samples

Why can the frequency bins be the non-integer number here? Can we also sample non-integer frequencies using DFT/FFT?

Thank you for your help.

$\endgroup$
3
$\begingroup$

Frequencies in DFT, $\omega = \frac{2\pi}{N}k, \ k = 0,1,2,...,N-1 $, only depends on the Length $N$ of DFT, and nothing else.

$$X[k] = \sum^{N-1}_{n=0}x[n]e^{-j\frac{2\pi}{N} nk}, \qquad k = 0,1,2,...,N-1$$

It is very important to understand this expression as the projection of time-domain finite length sequence $x[n], n=0,1,2,3,...,N-1$, of length $N$, onto orthogonal Discrete Fourier Basis Vectors $W_k^{N} = e^{j\frac{2\pi}{N}nk}, k=0,1,2,...,N-1$. And, the DFT Coefficients $X[k]$ are the projection coefficients actually on the $k^{th}$ basis vector. So, with this idea in mind, we can say $x[n]$ is actually a vector $\vec{x}$ in an $N$-Dimensional vector space. And, this $N$-D vector space has a set on $N$ Fourier Basis which reveals the frequency information of that $\vec{x}$. We know that projection of a vector onto another depends on dot-product (inner-product), $\langle\vec{x},\vec{y} \rangle$. The projection coefficient of a vector $\vec{x}$ onto a vector $\vec{y}$ :

$$P_{\vec{x}} = \frac{\langle\vec{x}, \vec{y}\rangle}{\langle\vec{y}, \vec{y}\rangle} = \frac{\sum^{N-1}_{n=0}x[n]y^{*}[n]}{\sum^{N-1}_{n=0}y[n]y^{*}[n]}$$ And, if we are projecting a vector $\vec{x}$ onto a unit length vector $\hat{y}$, then the Projection coefficient is exactly the dot-product, because, the denominator of the above expression will become 1.

$$P_{\vec{x}} = \langle\vec{x}, \hat{y}\rangle$$ That is exactly what the DFT Coefficient is. Projection Coefficient of time-domain sequence $\vec{x}$ onto $\vec{W_k^N}$ $$X[k] = \langle\vec{x}, \vec{W_{k}^{N}}\rangle = \sum^{N-1}_{n=0}x[n]\,W_k^{N}[n] = \sum^{N-1}_{n=0}x[n]e^{-j\frac{2\pi}{N} nk}$$

Now, notice that the $N$ Fourier Basis vectors are each at a digital frequency $\omega = \frac{2\pi}{N}k, k=0,1,2,...,N-1$. So, the DFT/FFT frequency bins just depend on the DFT Length and nothing else. DFT by itself is a perfectly fine operation on an $N$-dimensional vector. It is a linear transformation, just a change of basis from canonical basis set to Fourier Basis set, so as to reveal frequency information in that signal $\vec{x}$.

It reveals frequency information because projection(inner-product) of one vector onto another actually is a measure of similarity between the two vectors. So, each of the $X[k]$ is telling us how much similarity is between the time-domain sequence $\vec{x}$ and $k^{th}$ Fourier Basis, and, $k^{th}$ Fourier Basis is a sequence of digital frequency $\omega = \frac{2\pi}{N}k$.

As I said, DFT by itself is perfectly fine operation on any vector of finite length. You do not have to link these digital frequencies with sampling frequency. But if you want to, then, it is enough to know that when we sample a signal at sampling frequency $f_s$, then the maximum frequency that can be represented in the sampled signal is $f_s/2$. And the maximum digital frequency is $\pi$. Hence, $f_s/2$ maps to $\pi$. And therefore the digital frequency of $k^{th}$ Fourier Basis, $\omega = \frac{2\pi}{N}k$ maps to $f = \frac{f_s}{N}k$.

| improve this answer | |
$\endgroup$
0
$\begingroup$

This is shorter.

You have integer indexing of spectral lines. But your spectral resolution will be non-integer. The spacing between frequencies, delta-f, is ratio of sample rate and blocksize.

Delta-f = Fs/B

| improve this answer | |
$\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.