# Derive DFT of $x((n+1)/2)$

If $$X(k)$$ is the $$N$$-point DFT of $$x(n)$$, and $$y(n)= x\left(\frac {n+1}{2}\right)$$ for odd $$n$$, and $$0$$ for even $$n$$.

What is the $$2N$$ point DFT of $$y(n)$$ in terms of $$X(k)$$?

So far, I've noticed that $$y(2n+1)=x(n+1)$$, but I'm not sure what to do with that information in terms of the DFT summation. Can someone help me out here?

• Hint: Write down explicitly, using numbers and not symbols such as $n$ or $N$, the six elements of the sequence $y$ for the case $N=3$. You can have $y$ and $x$ in your answer but no symbol $n$ or $N$. Then write down the six-point DFT of $y$, (no summation signs $\displaystyle\Sigma$ allowed) and replace each $y$ by the corresponding value from your first answer. You should be having six equations here. Then write the 3-point DFT of $x$ using the same rules. Finally stare very hard at the results. – Dilip Sarwate Oct 19 at 3:32
• @DilipSarwate, I got the answer, but I want to know how to derive it directly. – S'Danc Oct 19 at 5:15
• @S'Danc: Dilip's suggestion was supposed to help you derive it yourself. Have you tried it? – Matt L. Oct 19 at 6:51

I would follow a signal block diagram based solution for this problem.

First as suggested in the comments, it's very helpful to investigate a few values of $$y[n]$$ and $$x[n]$$ for some $$n$$ :

\begin{align} y &= 0 ~~~,~~~ y = x \\ y &= 0 ~~~,~~~ y = x \\ y &= 0 ~~~,~~~ y = x \\ y &= 0 ~~~,~~~ y = x \\ \end{align}

with some experience, or by a direct investigation of this above sequence it can be seen that the system that produce $$y[n]$$ from $$x[n]$$ is the folowing :

$$x[n] \longrightarrow \boxed{ \uparrow 2} \longrightarrow w[n] \longrightarrow \boxed{ z^1} \longrightarrow y[n]$$

where the up arrow indicates an expansion by $$2$$ and the $$z^1$$ indicates a left shift (advance) by one sample.

Write down the DTFT relations between those signals $$x[n]$$,$$w[n]$$ and $$y[n]$$ :

\begin{align} W(\omega) &= X(2\omega) \\ Y(\omega) &= e^{j\omega} W(\omega) \\ \\ Y(\omega) &= e^{j\omega} X(2\omega) \\ \end{align}

And relate $$2N$$ point DFT $$Y[k]$$ of $$y[n]$$ to $$N$$ point DFT $$X[k]$$ of $$x[n]$$.

\begin{align} Y[k] &= Y(\omega_k) = Y(\frac{2\pi}{2N} k) &, ~~ k=0,1,...,2N-1\\ Y[k] &= e^{j \frac{2\pi}{2N} k} X(\frac{2\pi}{N} k) &, ~~ k = 0,1,...,2N-1\\ Y[k] &= e^{j \frac{\pi}{N} k} X[k] &, ~~ k = 0,1,...,2N-1 \end{align}

It can be seen that the length $$2N$$ DFT sequence $$Y[k]$$ consists of two fold replica of length $$N$$ DFT sequence $$X[k]$$ weighted by $$e^{j \frac{\pi}{N} k}$$. Note that $$X[k]$$ is periodic in $$k$$ by $$N$$, hence repeats twice during $$k = 0,1,...,2N-1$$.