1
$\begingroup$

This question is prompted by a statement made in this response (reproduced below):

The DFT calculates spectral components up to $f_s/2$, no matter what the input signal is.

A book I'm reading explains that the DFT of a signal $x(n)$ is the result of the inner product of $x(n)$ with each of the sampled complex sinusoidal basis vectors $s_k(n)$. Here is the author's definition of the DFT:

enter image description here

The value $k$ is called the bin number and $\omega_k$ are harmonics of the sampling frequency $f_s$ (expressed in angular unit of radians, alternatively represented as $f_k = \frac{k}{N}f_s$).

Since $k$ is taken from $0$ to $N-1$, $X(\omega_k)$ is defined up to and including $f_{N-1} = \frac{N-1}{N}f_s$. Why would Deve (answer author) say $f_s/2?$

$\endgroup$
2
$\begingroup$

Depends a bit on the indexing convention, but in typically you would interpret the frequency interval as $[-f_s/2, f_s/2]$ and not as $[0,f_s]$. The DFT is periodic in N so you you have

$$X(N-1) = X(-1) $$

Keep in mind that that the sampling theorem requires the signal to be band limited to $f_s/2$ so assuming that you have actual independent information about frequencies higher than $f_s/2$ is misleading.

For real signals, it's conjugate symmetric anyway, i.e. $f_{-k} = f^*_k$ so there is only independent information on half of the spectrum anyway.

$\endgroup$
  • $\begingroup$ This was mentioned in the book, here and here but I didn't understand what author meant. Can you further explain why $k$ can be taken from $[-N/2, N/2-1]$? Are the frequencies between $[N/2, N-1]$ neglected or are they present but "wrapped around" and present at $\omega_k $ for $k \in [-N/2, 0]$? $\endgroup$ – Minh Tran Aug 5 at 17:45
  • 1
    $\begingroup$ The higher frequencies are not "neglected" they are just mirror images of the negative frequencies. Let's say you sample a single at $f_s=10kHz$ and do an FFT with $N=1000$. The FFT bins represent the frequencies of -5000, -4990,..., 4990, 5000. Since the FFT is periodic, you get the same value at -4000 Hz, 6000Hz, 16000Hz, 26000Hz, etc. However, these higher frequencies are not represented in the original signal, as this would violate the sampling theorem $\endgroup$ – Hilmar Aug 5 at 19:17
2
$\begingroup$

You are right, the DFT bins correspond to frequencies $f_k=\frac{k}{N}f_s$. In order to see this let's consider finite length signals with potentially non-zero elements in the index range $[0,N-1]$. In this case, the DFT is just a sampled version of the DTFT (discrete-time Fourier transform):

$$\textrm{DTFT:}\quad X(e^{j\omega})=\sum_{n=0}^{N-1}x[n] e^{-jn\omega}\tag{1}$$

$$\textrm{DFT:}\quad \hat{X}[k]=\sum_{n=0}^{N-1}x[n] e^{-jn\frac{2\pi k}{N}}\tag{2}$$

From $(1)$ and $(2)$ we get

$$\hat{X}[k]=X(e^{j\omega_k}),\qquad\omega_k=\frac{2\pi k}{N}\tag{3}$$

So the index $k=0$ corresponds to DC, $k=N/2$ (if $N$ is even) corresponds to Nyquist, and $k=N-1$ corresponds to just below $f_s$ (actually, $\frac{N-1}{N}f_s$).

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