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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\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.

Improve this answer
$\endgroup$
2
  • $\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$ Commented Aug 5, 2019 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$ Commented Aug 5, 2019 at 19:17
3
$\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$).

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.