3

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.

Tendero
  • 5,020
  • 6
  • 27
  • 46

1 Answers1

5

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

Matt L.
  • 89,963
  • 9
  • 79
  • 179
  • 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]$)? – Tendero Feb 07 '16 at 13:54
  • @M.S.: I've added this to my answer. – Matt L. Feb 07 '16 at 17:06
  • I don't understand some steps in equation $(3)$. When you write $\frac12\sum_{n=0}^{N-1}xnW_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. – Tendero Feb 07 '16 at 17:45
  • I just realized where the $W_N^{nN/2}$ comes from, but still can't figure out the first part. – Tendero Feb 07 '16 at 17:52
  • @M.S.: First you have $x[2n]W_N^{2nk}$ inside the sum, and by substituting $2n$ by $n$, this is equivalent to the sum I showed, where the factor $1+(-1)^n$ makes sure that only even indices are summed up. And, as you already figured out, $W_N^{nN/2}$ is simply $(-1)^n$. – Matt L. Feb 07 '16 at 18:03
  • Excuse me, but I still don't get it. As I see it, there is no variable substitution there, it's just the same expression rewritten, with the same variable being used. If a substitution was done (for example, if we replaced $2n=m$), then the factor that discriminates even indices would never appear. I think that what you did is just a very smart way of making $X[k]$ appear but the final result I get using the method you explained above is that $\sum_{n=0}^{N/2-1}x[2n]W_{N/2}^{kn}=\frac{1}{2}(X[2k]+X[2k-\frac{N}{2}])$ – Tendero Feb 07 '16 at 18:54
  • 1
    @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$. – Matt L. Feb 07 '16 at 19:46
  • Now I saw it! Thank you very much for your thoroughness and patience, Matt! :) – Tendero Feb 07 '16 at 20:06
  • @M.S.: Great, I hope you learned something. – Matt L. Feb 07 '16 at 20:27
  • Matt, sorry to bother you again with this, but I can't get to eq. $(4)$. What I'm doing is $$j\sum_{n=0}^{N/2-1}x[2n+1]W_{N}^{k(2n)}=j\sum_{n=0}^{N-1}x[n]W_N^{kn}\frac{1+(-1)^{n+1}}{2}=j\frac{1}{2}\sum_{n=0}^{N-1}x[n]W_N^{kn}+j\frac{1}{2}\sum_{n=0}^{N-1}x[n]W_N^{nN/2}W_N^{kn}e^{-j\pi}=\frac{j}{2}(X[k]-X[k+N/2])$$. So the last factor you wrote, W_N^{-k} is missing. What did I do wrong? – Tendero Feb 07 '16 at 21:32
  • @M.S.: In your first sum in order to do index substitution, you need also $W_N^k$ to have the power $2n+1$ (and not just $2n$). If you do this you get the missing term outside the sum to compensate for it. – Matt L. Feb 08 '16 at 09:01