1
$\begingroup$

Let's say the N-Point DFT of $x[n]$ is $X(k)$.

Now from this question, I know how to compute the 2N-Point DFT of the same $x[n]$ in terms of $X(k)$

However, this idea doesn't translate well if I have to compute the 2N-Point DFT of $x_1[n]$, for example, where:

$$x_1[n] = \begin{cases} x[n], & \text{if } n \in [0, N-1]\\ x[n-N], & \text{if } n\in [N, 2N-1]\\ 0 & \text{else} \end{cases}$$

Or for example, $x_2[n]$, where:

$$x_2[n] = \begin{cases} x[n], & \text{if } n \in [0, N-1]\\ 0 & \text{else} \end{cases}$$

Although for $x_2[n]$, I can intuitively tell that $X(k) = X_2(k)$ since there is just zero padding past N. For the case $x_1[n]$ it is rather difficult to compute the 2N-Point DFT in terms of Even indexed and Odd indexed samples. So is there a more general way to compute the 2N-Point DFT in terms of N-Point DFT?

$\endgroup$

1 Answer 1

3
$\begingroup$

The sequence $x_1[n]$ is just a concatenation of two periods of $x[n]$, which corresponds to upsampling in the frequency domain. I.e., half of the values of the length $2N$ DFT of $x_1[n]$ will be the (scaled) original values of the length $N$ DFT of $x[n]$, and the other half will be zero. Of course, this can be shown by writing out the DFT sum:

$$\begin{align}X_1[k]&=\sum_{n=0}^{2N-1}x_1[n]e^{-j\frac{2\pi}{2N}nk}\\&=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{2N}nk}+\sum_{n=N}^{2N-1}x[n-N]e^{-j\frac{2\pi}{2N}nk}\\&=\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{2N}nk}+\sum_{n=0}^{N-1}x[n]e^{-j\frac{2\pi}{2N}(n+N)k}\\&=\sum_{n=0}^{N-1}\big(x[n]+x[n]e^{-jk\pi}\big)e^{-j\frac{2\pi}{2N}nk}\\&=\sum_{n=0}^{N-1}\big(x[n]+(-1)^kx[n]\big)e^{-j\frac{2\pi}{N}n\frac{k}{2}}\\&=\begin{cases}2X\left[\frac{k}{2}\right],&k\textrm{ even}\\0,& k\textrm{ odd}\end{cases}\end{align}$$

$\endgroup$
1
  • 2
    $\begingroup$ Thanks for the step-by-step solution! So I shall continue to always consider such a question in two halves. $\endgroup$ Mar 30 at 12:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.