Let N be an even integer, and $x[n]$ be a finite length signal over the interval $n\in [0,N-1]$; let $X[k]$ be the N-pt DFT of $x[n]$.

Find the 2N-Pt DFT of $x_1[n]$ in terms of $x[n]$, where:

$$x_1[n] = \begin{cases} x[\frac{n}{2}], & \text{if } n \text{ is even}\\ 0 & \text{else} \end{cases} $$

Now, the idea I had in mind was to write out the DFT sum and then change the summing variable $n\rightarrow 2n$ but that doesn't work:

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

$$\downarrow n \text{ to } 2n$$

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

This doesn't work for two reasons, 1) The form of the DFT is not correct and 2) the fact that $x_1[n] = x[n/2]$ for only even $n$'s is not reflected in the sum!

Any help would be appreciated!


1 Answer 1


You're very close. We have

$$\begin{align}X_1[k]&=\sum_{{n=0,\;n\textrm{ even}}}^{2N-1}x[n/2]e^{-j\frac{2\pi} {2N}nk}\\&=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{N}nk}\\&=X[k],\qquad k=0,1,\ldots, 2N-1\end{align}$$

Naturally, the DFTs of $x[n]$ and $x_1[n]$ have the same values. The only difference is that $X_1[k]$ has length $2N$, i.e., the values of $X[k]$ are simply repeated. This is what upsampling (insertion of zeros) does: the period in the other domain is multiplied by the number of inserted zeros plus $1$, i.e., one inserted zero results in twice the period, two zeros result in three times the period, etc.

The dual problem (concatenating two periods in the sample domain) was discussed in this question.

  • 1
    $\begingroup$ So basically $X_1(k)$ is just two periods of $X(k)$. This is a cool result! $\endgroup$
    – user64710
    Apr 2, 2023 at 19:51
  • $\begingroup$ Matt, it's the fencepost or telephone pole kinda issue. But if you have valid values for $$X_1[k] \qquad\forall \ k\in\mathbb{Z} \ \ 0 \le k \le 2N-1$$ isn't the length of $X_1[k]$ equal to $2N$? $\endgroup$ Apr 3, 2023 at 19:53
  • $\begingroup$ @robertbristow-johnson: Yes, $X_1[k]$ has $2N$ values. Was there any misunderstanding about this? $\endgroup$
    – Matt L.
    Apr 3, 2023 at 20:04
  • $\begingroup$ I wouldn't call it length $2N-1$, that's all. I think that might lead to a misunderstanding. $\endgroup$ Apr 4, 2023 at 2:01
  • 1
    $\begingroup$ @robertbristow-johnson: Oh, I see now that you've edited out my $2N-1$. I meant to write $2N$, it was just a silly mistake. Thx for editing. $\endgroup$
    – Matt L.
    Apr 4, 2023 at 9:20

Your Answer

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