Time scaling in DFT?

Let $x[n]$ be a real signal whose length $N$ is even. Let $y[n]=x[2n]+jx[2n+1]$ a signal whose length is $M=\frac{N}{2}$. $X[k]$ for $k=0,...,N-1$ and $Y[k]$ for $k=0,...,M-1$ are the respective DFTs of those signals. Find $Y[k]$ as a function of $X[k]$.

I haven't been able to find a scaling time property for the DFT. I read all the Oppenheim-Schafer's discrete signals book and found nothing about the subject. I tried doing it by definition but I just can't realize what the relationship between both DFTs is.

This is a classic exercise and it shows you how to obtain the DFT of a real-valued length $N$ signal in terms of the DFT of a length $N/2$ complex-valued signal.

You have to write $X[k]$ in terms of the even and odd samples of $x[n]$. With $W_N=e^{-j2\pi /N}$ you get

\begin{align}X[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn}&=\sum_{n=0}^{N/2-1}x[2n]W_{N/2}^{kn}+W_N^k\sum_{n=0}^{N/2-1}x[2n+1]W_{N/2}^{kn}\\&=\text{DFT}_{N/2}\{y_R[n]\}+W_N^k\;\text{DFT}_{N/2}\{y_I[n]\}\\&=Y_e[k]-jW_N^kY_o[k]\tag{1}\end{align}

where $y_R[n]$ and $y_I[n]$ are the real and imaginary parts of $y[n]$, respectively, and $Y_e[k]$ and $Y_o[k]$ are the even and odd parts of $Y[k]$. Eq. $(1)$ shows that after having computed the length $N/2$ DFT $Y[k]$, you need to split it into its even an odd parts, and from them you can obtain the length $N$ DFT $X[k]$.

Obtaining $Y[k]$ from $X[k]$ is also possible, even though that's usually the less practical problem, because often you have an FFT routine that takes complex input signals, so it's more efficient to compute a lenght $N$ FFT of a real-valued sequence by computing a length $N/2$ FFT of a complex-valued sequence. Anyway, $Y[k]$ is given by

$$Y[k]=\sum_{n=0}^{N/2-1}x[2n]W_{N/2}^{kn}+j\sum_{n=0}^{N/2-1}x[2n+1]W_{N/2}^{kn}\tag{2}$$

With $W_{N/2}^n=W_N^{2n}$, the first term on the right-hand side of $(2)$ can be written as

\begin{align}\sum_{n=0}^{N/2-1}x[2n]W_{N}^{k(2n)}&=\sum_{n=0}^{N-1}x[n]W_N^{kn}\frac{1+(-1)^n}{2}\\&=\frac12\sum_{n=0}^{N-1}x[n]W_N^{kn}+\frac12\sum_{n=0}^{N-1}x[n]W_N^{nN/2}W_N^{kn}\\&=\frac12\left(X[k]+X[k+N/2]\right)\tag{3}\end{align}

where I used $(-1)^n=W_N^{nN/2}$.

Eq. $(3)$ shows that decimation in the time domain corresponds to aliasing in the frequency domain, as expected.

In a completely analogous manner, the last term in Eq. $(2)$ can be written as

$$j\sum_{n=0}^{N/2-1}x[2n+1]W_{N/2}^{kn}=\frac{j}{2}\left(X[k]-X[k+N/2]\right)W_N^{-k}\tag{4}$$

Substituting $(3)$ and $(4)$ into $(2)$ gives the final solution:

$$Y[k]=\frac12X[k]\left(1+jW_N^{-k}\right)+\frac12X[k+N/2]\left(1-jW_N^{-k}\right)\tag{5}$$

• Hello Matt, thanks for the thorough answer. Sorry for the typo in the length $M$, I already edited it. However, I have one doubt left. What you wrote seems to be $X[k]$ in terms of $Y[k]$, but how would be the other way round? I mean, how could you obtain the DFT of a length $N/2$ complex-valued signal from the DFT of a length $N$ real-valued one (i.e. $Y[k]$ in terms of $X[k]$)? Feb 7 '16 at 13:54
• @M.S.: I've added this to my answer. Feb 7 '16 at 17:06
• I don't understand some steps in equation $(3)$. When you write $\frac12\sum_{n=0}^{N-1}x[n](1+(-1)^n)W_N^{kn}$, I don't see why the last factor is $W_N^{kn}$ and not $W_N^{2kn}$. And then in the second part of that equation, I don't see where the $W_N^{nN/2}$ in the second term came from. Feb 7 '16 at 17:45
• I just realized where the $W_N^{nN/2}$ comes from, but still can't figure out the first part. Feb 7 '16 at 17:52
• @M.S.: I've added another step to (3). Note that the first two terms are equal, because in the first you only sum over even indices ($2n$) of $x[n]$, and in the second you sum over all indices ($n$), but the odd ones are zeroed out by the term $(1+(-1)^n)/2$, which equals $1$ for even $n$, and $0$ for odd $n$. Feb 7 '16 at 19:46