1
$\begingroup$

I'm currently reading this article and trying hard to understand it.

According to the article, DFT is as follows:

$$ X_k=\sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}nk} \\\text{where k is integer and its range is [0, N-1]} $$

And here is where my first curiosity arises. According to the sampling theorem, we can only see as many as $N/2$ frequencies if we use $N$ points to analyze a signal. If it is true, isn't a valid range for frequency (that is, $k$) is $[0, N/2 - 1]$, not $[0, N-1]$ as currently written in the article?

And my second question is that why the range of $k$ became half if we divide $x_n$ into an even part and an odd part. According to the article, $X_k$ can be rewritten as follows:

$$ X_k=\sum_{n=0}^{\frac{N}{2}-1}x_{2m}e^{-\frac{2\pi i}{N/2}mk}+e^{-\frac{2\pi i}{N}k}\cdot\sum_{n=0}^{\frac{N}{2}-1}x_{2m+1}e^{-\frac{2\pi i}{N/2}mk} \\\text{where k is integer and its range is [0, N/2-1]} $$

I suppose the reason the range of $k$ became half is because the range of $n$ became half as we divided $x_n$ into two parts. Therefore, since $n$--the number of points--became half, we end up being able to observe only half frequencies than before we divided $x_n$, due to the sampling theorem.

Thank you for reading my question and please correct me if I mistook something.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

An $N$-point DFT $$ X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} nk } ~~~,~~~ k = 0,1,...,N-1 $$

computes complex-amplitudes of the frequency-domain vector $X[k]$, associated with each distinct basis vector $e^{j \frac{2\pi k}{N}n} $ per $k$ that span the space of complex-valued discrete-time sequences of length N.

Due to integer properties and periodicity of complex exponentials, it follows that a discrete-time sequence of length $N$ permits at most $N$ distinct complex-exponential basis vectors. Therefore, there can be at most $N$ distinct frequency calculations. That's why the frequency index $k$ ranges in $0$ to $N-1$.

However, if the discrete-time sequence $x[n]$ is real-valued, then it can be seen that it's DFT will be conjugate symmetric, $X[k] = X^*[-k]$, and only half of the frequency calculations is sufficient to represent whole $X[k]$, and it can reconstruct $x[n]$, nevertheless DFT index $k$ is still considered to be ranging in $0$ to $N-1$, albeit redundantly in the second half.

Coming to your second issue, you are right, when you decompose an $N$-point DFT X[k] into its even and odd indexed sequences, then the new sequences will be of half length, and thus their own index ranging will be halved too. However, when they are combined, there will be a twiddle glue factor whose frequency index range is still $0$ to $N-1$...

Improve this answer
$\endgroup$
1
$\begingroup$

To your first question: the DFT generates also bins for negative frequency values. In the spectra you most commonly see plotted, these are left out, as their magnitude will be the exact same as the positive frequency bins for real input signals. For real input, the DFT generates a Hermetian symmetric output, the negative frequency bins are complex conjugates of their positive counterparts. So the sampling theorem is of course right in the sense, that only $N/2$ frequencies can be observed, but still the DFT generates $N$ output bins.

To your second question: the decomposition in odd and even bins is just that: a decomposition, a different way of writing down or looking at one and the same thing. It has nothing to do with the sampling theorem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.