1
$\begingroup$

Inverse DFT is given as: \begin{equation} y_n=\sum_{k=0}^{N-1}Y_k e^{j\frac{2\pi nk}{N}}\tag{1} \end{equation} and knowing that Fourier transform of a real value signal has Hermitian symmetry property, i.e., $Y^*_k=Y_{N-k}$ with $\frac{N}{2}$ positive and $\frac{N}{2}$ negative frequencies, Eq. (1) can be rewritten in which of following ways:

  • Notation 1: $$ y_n=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=0}^{\frac{N}{2}-1}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}} $$

  • Notation 2: $$ y_n=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=1}^{\frac{N}{2}}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}} $$

  • Notation 3: $$ y_n=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=\frac{N}{2}}^{N}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}} $$

$\endgroup$
1
$\begingroup$

I can't see any match with the initial $y_n$ in equation $(1)$, (see update). With a slight change to the notation, you have the following results in the first two cases, for Notation 1 and 2 respectively:

  • Notation 1: \begin{align} y_{n_1}&=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=0}^{\frac{N}{2}-1}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}\tag{$\mathbf{1a}$}\\ &=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=0}^{\frac{N}{2}-1}Y_k^* \overbrace{e^{j2\pi n}}^{=1} e^{-j\frac{2\pi nk}{N}}\\ &=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\left(\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}\right)^*\\ &=y_{n/2}+y^*_{n/2}\tag{$\scriptstyle{\text{$y_{n/2}=y_n$ for $n=0, \ldots, N/2 -1$}}$}\\ &=2y_{\frac n2}\tag{$\scriptstyle{\text{if $y_n$ is real, then $y_{n/2}$ is real}}$} \end{align}

  • Notation 2: \begin{align} y_{n_2}&=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=1}^{\frac{N}{2}}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}\tag{$\mathbf{1b}$}\\ &=\underbrace{\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+Y_N+\sum_{k=1}^{\frac{N}{2}-1}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}}_{\textrm{same as notation 1}}-Y_N-Y_{N/2}\\ &=2y_{n/2}-Y_N-Y_{N/2}\\ \end{align}

For Notation 3 however, the equation would be identical to equation $(1)$ if you changed the upper limit of the second summation to $N-1$ instead of $N$, otherwise you have an additional term as a result of the $N^{\rm th}$ term as shown below:
\begin{align} y_{n_3}&=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=\frac{N}{2}}^{N}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}\tag{$\mathbf{1c}$}\\ &=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\left(\sum_{k=N/2}^{N-1}Y_k e^{j\frac{2\pi nk}{N}}\right)^*+Y_0\\ &=y_{n/2}+\left(y_{n/2}^{'}\right)^*+Y_0\tag{$\scriptstyle{\text{$y_{n/2}^{'}=y_n$ for $n=N/2, \ldots, N-1$}}$}\\ &=y_{n/2}+y_{n/2}^{'}+Y_0\\ &=y_n + Y_0 \end{align}

So, the correct notation should be:

$$ y_n=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=\frac{N}{2}}^{N-1}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}\tag{$\mathbf{2}$} $$

UPDATE:

Regardless of equation $(1)$, to test Notation 1 I will maintain my last notation and go proving if the equality below holds, i.e. if equation $(\mathbf{2})$ equals equation $(\mathbf{1a})$ in Notation 1.

\begin{align} \sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=\frac{N}{2}}^{N-1}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}&=\sum_{k=0}^{\frac{N}{2}-1}Y_k e^{j\frac{2\pi nk}{N}}+\sum_{k=0}^{\frac{N}{2}-1}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}\\ \implies\sum_{k=\frac{N}{2}}^{N-1}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}&=\sum_{k=0}^{\frac{N}{2}-1}Y_{N-k} e^{j\frac{2\pi n(N-k)}{N}}\\ \end{align}

One way could be testing if the following equalities are satisfied:

\begin{align} Y_{N/2}e^{j\frac{2\pi n(N/2)}{N}}&=Y_Ne^{j\frac{2\pi n(N)}{N}}\\ Y_{N/2-1}e^{j\frac{2\pi n(N/2-1)}{N}}&=Y_{N-1}e^{j\frac{2\pi n(N-1)}{N}}\\ Y_{N/2-2}e^{j\frac{2\pi n(N/2-2)}{N}}&=Y_{N-2}e^{j\frac{2\pi n(N-2)}{N}}\\ \vdots&=\vdots\\ Y_2e^{j\frac{4\pi n}{N}}&=Y_{N/2+2}e^{j\frac{2\pi n(N/2+2)}{N}}\\ Y_1e^{j\frac{2\pi n}{N}}&=Y_{N/2+1}e^{j\frac{2\pi n(N/2+1)}{N}}\\ \end{align}

It's neither the periodicity nor the Hermitian property of the DFT (for a real-valued signal i.e $Y_{N-k}=Y_{-k}=Y_k^*$) that we're seeing in the above equations. But let's check the first two and the last one for instance:

  • For the first equation: \begin{align} &Y_{N/2}e^{j\frac{2\pi n(N/2)}{N}}=e^{j\frac{2\pi n(N/2)}{N}}\left(\sum_{n=0}^{N-1}y[n]e^{-j\frac{2\pi(N/2)n}N}\right)=- \sum_{n=0}^{N-1}y[n]e^{-j\pi n}=\sum_{n=0}^{N-1}y[n]=Y_0\\ &Y_{N}e^{j\frac{2\pi n(N)}{N}}=e^{j\frac{2\pi n(N)}{N}}\left(\sum_{n=0}^{N-1}y[n]e^{-j\frac{2\pi(N)n}N}\right)=\sum_{n=0}^{N-1}y[n]e^{-j2\pi n}=\sum_{n=0}^{N-1}y[n]=Y_0\\ &\implies Y_{N/2}e^{j\frac{2\pi n(N/2)}{N}}= Y_{N}e^{j\frac{2\pi n(N)}{N}}\\ \end{align}

  • For the second equation: \begin{align} &Y_{N/2-1}e^{j\frac{2\pi n(N/2-1)}{N}}=e^{j\frac{2\pi n(N/2-1)}{N}}\left(\sum_{n=0}^{N-1}y[n]e^{-j\frac{2\pi(N/2-1)n}N}\right)= e^{-j\frac{2\pi n}{N}}\sum_{n=0}^{N-1}y[n]e^{j\frac{2\pi n}N}=e^{-j\frac{2\pi n}{N}}Y_1^*\\ &Y_{N-1}e^{j\frac{2\pi n(N-1)}{N}}=e^{j\frac{2\pi n(N-1)}{N}}\left(\sum_{n=0}^{N-1}y[n]e^{-j\frac{2\pi(N-1)n}N}\right)=e^{-j\frac{2\pi n}{N}} \sum_{n=0}^{N-1}y[n]e^{\frac{j2\pi n}N}=e^{-j\frac{2\pi n}{N}}Y_1^*\\ &\implies Y_{N/2-1}e^{j\frac{2\pi n(N/2-1)}{N}}=Y_{N-1}e^{j\frac{2\pi n(N-1)}{N}}\\ \end{align}

  • For the last equation:

\begin{align} &Y_1e^{j\frac{2\pi n}{N}}=e^{j\frac{2\pi n}{N}}Y_1\\ &Y_{N/2+1}e^{j\frac{2\pi n(N/2+1)}{N}}=e^{j\frac{2\pi n(N/2+1)}{N}}\left(\sum_{n=0}^{N-1}y[n]e^{-j\frac{2\pi(N/2+1)n}N}\right)=e^{j\frac{2\pi n}{N}} \sum_{n=0}^{N-1}y[n]e^{\frac{-j2\pi n}N}=e^{j\frac{2\pi n}{N}}Y_1\\ &\implies Y_1e^{j\frac{2\pi n}{N}}=Y_{N/2+1}e^{j\frac{2\pi n(N/2+1)}{N}} \end{align}

So, it looks like the initial notation in equation $(\mathbf{1a})$ is indeed identical to equation $(\mathbf{2})$. In conclusion, Notation 1 is correct for a real-valued signal. And Notation 3 need a slight change in the summation limit of the second term to be true. That's my two cents.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I am confused now....is it that from N frequencies half is positive and half is negative where negative ones are hermitian symmetric so summation over $n$ can be broken into two summations,i.e, over positive and negative side of the spectrum? If none of equations relates to Eq(1) then which one is correct notation for IDFT of real valued signal of length N? $\endgroup$ – Cali Aug 8 '16 at 19:17
  • $\begingroup$ I see your edit, I got mislead by your previous hermitian notation. I have to fix my answer. $\endgroup$ – Gilles Aug 8 '16 at 21:11
  • $\begingroup$ @Cali , please have a look to the updated answer. $\endgroup$ – Gilles Aug 9 '16 at 7:15
  • $\begingroup$ thank you very much for your answer. Just one additional question: regardless to the Eq. (1) which of the notations is the correct one for representing real-valued signal of length $N$ which has Hermitian symmetry property?Would notation 1 then be correct one since it essentially represents $\frac{N}{2}$ positive frequencies and $\frac{N}{2}$ negative frequencies which are $Y_{-k}=Y_{N-k}=Y^{*}_k$ $\endgroup$ – Cali Aug 9 '16 at 8:41
  • $\begingroup$ @Cali please see the recent update. $\endgroup$ – Gilles Aug 9 '16 at 19:03

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.