2
$\begingroup$

$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

enter image description here

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

enter image description here

enter image description here

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

Just like you did, start with:

\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$

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – nexxterp
    Commented Nov 17, 2023 at 8:14
  • $\begingroup$ 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. $\endgroup$
    – Jdip
    Commented Nov 17, 2023 at 9:49
  • $\begingroup$ 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. $\endgroup$
    – nexxterp
    Commented Nov 17, 2023 at 11:40
  • $\begingroup$ 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. $\endgroup$
    – Jdip
    Commented Nov 17, 2023 at 17:54
  • $\begingroup$ I did it in my edited version of question, but still I couldn't see how we can move from here to find DFT. $\endgroup$
    – nexxterp
    Commented Nov 17, 2023 at 18:47

Your Answer

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

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