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.

Answer

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