DFT sample point k < N has negative frequency

Question

(From: Schaum's DSP outline, 2nd edition, page 254, problem 6.35)

A signal $x_a(t)$ that is bandlimited to 10 kHz is sampled with a sampling frequency of $f_s = 20$ kHz. The DFT of N=1000 samples of x[n] is then computed, that is:

$$ X[k]=\sum_{n=0}^{N-1} x[n] e^{-j(2\pi / N)nk} $$

with N=1000.

(a) to what analog frequency does the index … k=150, and k=800 correspond?

---

A few equations:

$$ \omega_k = \frac{2 \pi k}{N} $$

$$ f_k = \frac{\omega_k f_s}{2 \pi} $$

For k=150:

$$ \omega_k = \frac{2 \pi}{1000} 150 = \frac{3}{10}\pi $$

$$ f_k= \frac{3\pi 20000}{2 \pi 10} = 3000\ \ hz $$

Ok no problem so far:

For k=300:

$$ \omega_k = \frac{2 \pi}{1000} 800 = \frac{4}{5}\pi $$

Here's where i hit a problem:

book says, for k=800, we need to be careful. Because $X(e^{j\omega})$ is periodic:

$$X(e^{j\omega}) = X(e^{j\omega + 2\pi}) $$

Therefore, k=800 corresponds to the frequency:

$$ \omega_k = \frac{2\pi}{N}k = \frac{2\pi}{N}(k - N) = -200\frac{2\pi}{N} $$

My question is this:

what's the reason we need to use a negative frequency here? Since k=800 < N=1000? Wouldn't it just be:

$$ \omega_k = \frac{2 \pi 800}{1000} = \frac{8\pi}{5} = 5.02... $$

Is this just the book being strange or am i missing some understanding of DFT? I would have thought you wouldn't need to worry about $2\pi$ unless k > 1000?

Answer 1

The DTFT frequency $\omega_k$ corresponding to the $N$-point DFT index $k$ is given by (frequency sampling relation)

$$ \omega_k = \frac{2 \pi}{N} k ~~~,~~~ k = 0,1,...,N-1.$$

The confusion might arise with the interpretation that the, on the continuous-time domain these frequencies correspond to:

$$ f_k = \frac{f_s}{N} k ~~~,~~~ k = 0,1,...,N-1 ?$$

But no. Because, after about $k = N/2$ which corresponds to $\omega = \pi$ and $f = f_s/2$, you will be sampling the negative portion of the shifted spectrum: $X(e^{j (\omega-2\pi)})$, which corresponds to negative discrete-time frequencies of $X(e^{j \omega})$ due to the periodicity of DTFT $X(e^{j\omega})$.

A more relevant (eventually the same) interpretation of the CTFT, DTFT, DFT frequency relation can be given by the following.

Let $x_c(t)$ be bandlimited to $-B \leq f <B$ and sampled at $F_s = 2B$ samples per second. The base period of the spectrum of $x[n]$ is between $-\pi \leq \omega < \pi$. Note that only the left member is included and the right member is discluded.

Now assume an $N$-point DFT $X[k]$ of $x[n]$ is computed. According to the frequency sampling interpretation of DFT, samples of $X[k]$ are given by :

$$ X[k] = X(e^{j \frac{2\pi}{N} k}) ~~~~ , k = ...-3,-2,-1,0,1,2,3... $$

Note very carefully, that eventhough most of the time we restrict our attention of the DFT index $k$ into the range of $0 \leq k < N$, indeed, the relation is valid for all $k$ which is a manifestation of DFT $X[k]$ and DTFT $X(e^{j \omega})$ being periodic by $N$ and $2\pi$.

Hence, instead of taking the range of $k$ in $[0,N-1]$, we can also take it in the range: $[-N/2 , N/2-1]$ (assuming $N$ even for the moment).

So, if you take $k = -N/2,-N/2+1,...,-1,0,1,2,...,N/2-1$ as the range of $k$ for DFT $X[k]$, then the mapping into the negative frequencies become obvious.

Note that, conventional FFT software always take the range of $k$ in $[0,N-1]$. Therefore, one has to relate them too which is simple: for $k$ in $[-N/2,-1]$ it corresponds to $k'$ in $[N/2,N-1]$ in the conventional DFT range, and for $k$ in $[0,N/2-1]$ it corresponds to the $k'$ in $[0,N/2-1]$ range in the conventional range.

Answer 2

The inverse DTFT to which the $\omega$ refers to when sampling DTFT to create an N-point DFT maybe taken over any $2\pi$ interval, since the sampling rate for the DTFT is always normalized to $\omega_s=2\pi$:

$$ f[n] = \frac{1}{2\pi} \int_{2\pi} F(e^{j\omega})e^{j\omega n} d\omega $$

While we could take the inverse DTFT over $\omega=0$ to $2\pi$, it is more conventional to use $\omega$ over the range $\omega=-\pi$ to $\pi$ so that its easier to see complex conjugate relationships between poles and zeros. Thus, the inverse DTFT becomes:

$$ f[n] = \frac{1}{2\pi} \int_{-\pi}^{\pi} F(e^{j\omega})e^{j\omega n} d\omega $$

Also, note due to periodic nature of DTFT:

$$ X(e^{j\omega}) = X(e^{j\omega + 2\pi}) $$

The range $\omega=\pi$ to $2\pi$ is an alias of:

the range $\omega=-\pi$ to $0$

Next, if we consider expressing a discrete frequency $\omega$ as a continuous frequency $\Omega$ then you need to convert $\omega$ into the range $-\pi$ to $\pi$ because CTFT is not periodic like the DTFT, thus we take the lowest range of values of $\omega$ before converting to $\Omega$.