Expressing 2N point DFT in terms of N point DFT

Question

I have a problem with expressing odd samples of X2 in terms of X1. I understand that the resulting DFT will be more precise in terms of expressing the exact spectrum of signal x[n], due to more samples. Moreover I know that even samples of X2(k) are copy of the spectrum of X1(k), however I do not know how to mathematically compute the odd ones.

The task is as follows:

Let $x[n]$ be a periodic sequence with period $N_1$ . Thus $x[n]$ is also periodic for period $N_2 = 2 N_1$ . We may compute $X_1[k]$: $N$-point DFT of $x[n]$ and $X_2[k]$: $2N$-point DFT of $x[n]$.

• Express $X_2$in terms of $X_1$ Hint: it is easy with even samples $X_2[2m]$ , harder with odd ones $X2_[2m+ 1]$ , for $m$ integer.

Answer 1

Consider N-point sequence $x[n]$ whose N-point DFT is $X[k]$. To compute 2N-point DFT, $X_2[k]$, of $x[n]$, one should append N-zeroes to $x[n]$, and make it a 2N-point sequence, denoted $x_2[n]$. Obviously, first N-samples of $x[n]$ and $x_2[n]$ are identical, and last N-samples of $x_2[n]$ are just zeroes.

Write 2N-point DFT of $x_2[n]$:

$$ X_2[k] = \sum_{n=0}^{2N-1} x_2[n] e^{-j \frac{2 \pi}{2N} n k } ~~,~~ k=0,1,...,2N-1 \tag{1}$$

which is identical to: $$ X_2[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n (k/2) } ~~,~~ k=0,1,...,2N-1 \tag{2}$$

Now, the even indexed samples of $X_2[k]$ can be shown to be $X[k/2]$, by setting $k_e=2m$ in Eq.2, $m=0,1,...,N-1$ :

$$ X_2[2m] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n (2m/2) } = X[m] \tag{3}$$

The odd indexed samples of $X_2[k]$ can also be obtained similarly by setting $k_o = 2m+1$, in Eq.2:

$$ X_2[2m+1] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n (\frac{2m+1}{2}) } = X[m+0.5] \tag{4}$$

Eq.4 is an interpolation statement; i.e., the sample $X[m+0.5]$ implies (but does not perform) interpolation between $X[m]$ and $X[m+1]$. However, it's not proper to set $k=m+0.5$ into the argument of a sequence, which is a mathematical array of numbers indexed by an integer; fractional indices make no literal sense. Nevertheless, Eq.4 means that taking 2N-point DFT of an N-point sequence, effectively, interpolates between samples of N-point DFT of the N-point sequence.

On the other hand, one can manipulate Eq.4 to see that:

$$ X_2[2m+1] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi}{N} n (\frac{2m+1}{2}) } = X[m+0.5] \tag{5}$$

$$ X_2[2m+1] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{ \pi}{N} n} e^{-j \frac{2 \pi}{N} n m } \tag{6}$$

denoting $x_o[n] = x[n] e^{-j \frac{ \pi}{N} n}$ yields $$ X_2[2m+1] = \sum_{n=0}^{N-1} x_o[n] e^{-j \frac{2 \pi}{N} n m} = X_o[m]\tag{7}$$

Where $X_o[m]$ is the N-point DFT of the sequence $x_o[n]$. Time-domain modulation of $x[n]$ by $ e^{-j \frac{ \pi}{N} n}$, performs half-sample shift of its N-point DFT $X[k]$, thus describe the so called interpolated values $X[k+0.5]$.