# Expressing 2N point DFT in terms of N point DFT

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.

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.

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

• Thank you, I forgot about the shift in time property of DFT for solving this one. Commented Nov 25, 2018 at 12:08
• Can you explain why we use here $$e^{-j\frac{\pi}{N}n}$$ and not $$e^{-j\frac{2\pi}{N}n}$$? Commented Nov 25, 2018 at 12:18
• By elaborating on the DFT expression you can get it... Commented Nov 25, 2018 at 12:21