# Does the DFT calculate spectral components up to half the sampling frequency, $f_s/2$?

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:

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?$$

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.

• 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]$? – Minh Tran Aug 5 '19 at 17:45
• 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 – Hilmar Aug 5 '19 at 19:17

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