Finding Discrete Fourier Transform (DFT) for different DFT size

$$N$$ is an even integer, $$x[n]$$ is a finite length signal over the interval $$n \in [0,N-1]$$, and $$X[k]$$ is the $$N$$-point DFT of $$x[n]$$. Analytically find the DFT of sequence below in terms of $$X[k]$$. DFT size is $$2N$$ and

So, I did this (note: below, in $$Y[k]=X[k/2]$$, $$k$$'s being odd creates indefiniteness.)

I found the exponential terms in terms of sine appears on both nominator and denominator.

This exercise is aimed at showing that zero-padding in the time domain interpolates the frequency domain. Since this is homework, I'll give you the beginning of the solution.

\begin{align} Y[k] &= \sum_{k=0}^{N-1}x[n]e^{-j2\pi k\frac{n}{2N}}\\ &= \sum_{k=0}^{N-1}x[n]e^{j2\pi k\frac{n}{2N}}e^{-j2\pi k\frac{n}{N}}\\ &= \mathcal{F}\left\{x[n]e^{j2\pi k\frac{n}{2N}}\right\} \end{align} where $$\mathcal{F}$$ denotes the DFT operator.

Next, we know that multiplication in the time domain is convolution in the frequency domain, so: $$Y[k] = X[k] * \mathcal{F}\left\{e^{j\pi k\frac{n}{N}}\right\}\tag{1}$$

The next step is to compute $$\mathcal{F}\left\{e^{j\pi k\frac{n}{N}}\right\}$$:

\begin{align} \mathcal{F}\left\{e^{j\pi k\frac{n}{N}}\right\} &= \sum_{k=0}^{N-1}e^{j\pi k\frac{n}{N}}e^{-j2\pi k\frac{n}{N}}\\ &= \sum_{k=0}^{N-1}e^{-j\pi k\frac{n}{N}} \end{align}

Now here is a crucial result for geometric series: $$\sum_{k=0}^{N-1}a^n = \frac{1-a^N}{1-a}$$ So now we have: $$\mathcal{F}\left\{e^{j\pi k\frac{n}{N}}\right\} = \frac{1-e^{-j\pi k}}{1-e^{-j\pi\frac{k}{N}}}\tag{2}$$

Using Euler’s formula to modify $$(2)$$, the final expression for $$(1)$$ is:

$$Y[k] = X[k] * \underbrace{e^{-j\omega_k\big(\frac{N-1}{2}\big)}\frac{\sin(N\omega_k/2)}{\sin(\omega_k/2)}}_{G[\omega_k]}$$ where $$\omega_k = \frac{\pi k}{N}$$ for simplicity.

$$G[\omega_k]$$ is an interpolation function. When you convolve this function with $$X[k]$$, you interpolate $$X[k]$$. So by zero padding $$x[n]$$, we interpolated its spectrum $$X[k]$$.

If you want to take it a step further, here is the convolution sum:

$$Y[l] = \sum_{k=0}^{L-1}X[k]G[\omega_l-\omega_k] = \sum_{k=0}^{N-1}X[k]G[\pi l/2N - \pi k/N]$$

$$l = 0, \cdots, 2N-1$$

with $$L = 2N, \omega_l = \pi l/L, \omega_k = \pi k/N$$

• I unfortunately could not do it. For Y[2m], I got the desired result but I cannot get it for Y[2m+1]=X[in terms of m]. Even though I take the fourier transform of exponential you write, I do not think its convolution with X[k] will be easy. Commented Nov 17, 2023 at 8:14
• 1. Forget about Y[2m] and Y[2m+1]. 2. You do not have to compute the convolution of $X[k]$ and $\mathcal{F}\left\{e^{j\pi k n/N}\right\}$. Just try to compute $\mathcal{F}\left\{e^{j\pi k n/N}\right\}$ and we’ll go from there.
– Jdip
Commented Nov 17, 2023 at 9:49
• By using the DFT formula I found it as (1-(-1)^k)/(1-exp(-jπk/N)), but I could not visualize how I can use this result. Commented Nov 17, 2023 at 11:40
• That's right, but you went a step too far. As you work your way through these, please edit your question with what you're doing so I can help correct you. I'll give you a couple more hints, and as you work your way through the problem I'll help.
– Jdip
Commented Nov 17, 2023 at 17:54
• I did it in my edited version of question, but still I couldn't see how we can move from here to find DFT. Commented Nov 17, 2023 at 18:47