2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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]$)? $\endgroup$ – Tendero Feb 7 '16 at 13:54
  • $\begingroup$ @M.S.: I've added this to my answer. $\endgroup$ – Matt L. Feb 7 '16 at 17:06
  • $\begingroup$ 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. $\endgroup$ – Tendero Feb 7 '16 at 17:45
  • $\begingroup$ I just realized where the $W_N^{nN/2}$ comes from, but still can't figure out the first part. $\endgroup$ – Tendero Feb 7 '16 at 17:52
  • 1
    $\begingroup$ @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$. $\endgroup$ – Matt L. Feb 7 '16 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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