1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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