# proof of Autocorrelation property of DFT

I am facing problem in proving the Auto-correlation property of Discrete Fourier Transform (DFT), that is

$$\mathcal{DFT}\left\{\sum_{r=0}^{N-1}x[r]x^*[r+n]\right\} = X[k]X^*[k]= |X[k]|^2$$

where $X[k]$ is the DFT of $x[n]$, and $x[n]$ is periodic with period $N$: $$x[n+N] = x[n] \qquad \forall n \in \mathbb{Z}$$ Likewise $X[k]$ is periodic with period $N$: $$X[k+N] = X[k] \qquad \forall k \in \mathbb{Z}$$

Below is my Approach:

\begin{align} \mathcal{DFT}\left\{\sum_{r=0}^{N-1}x[r]x^*[r+n]\right\} &= \sum_{n=0}^{N-1} \sum_{r=0}^{N-1}x[r] x^*[r+n] e^{- j 2 \pi n k/N} \\ \\ &= \sum_{r=0}^{N-1}x[r] \sum_{n=0}^{N-1} x^*[r+n] e^{- j 2 \pi n k/N} \\ \\ &= \sum_{r=0}^{N-1}x[r] \sum_{n=r}^{r+N-1} x^*[n] e^{- j 2 \pi (n-r) k/N} \\ \\ &= \sum_{r=0}^{N-1}x[r] \sum_{n=0}^{N-1} x^*[n] e^{j 2 \pi r k/N} e^{- j 2 \pi n k/N} \\ \\ &= \sum_{r=0}^{N-1}x[r] e^{j 2 \pi r k/N} \sum_{n=0}^{N-1} x^*[n] e^{- j 2 \pi n k/N} \\ \\ &= \sum_{r=0}^{N-1}x[r] e^{j 2 \pi r k/N} \sum_{n=0}^{N-1} x^*[n] (e^{- j 2 \pi n (-k)/N})^* \\ \\ &= \sum_{r=0}^{N-1}x[r] e^{j 2 \pi r k/N} \sum_{n=0}^{N-1} ( x[n] e^{- j 2 \pi n (-k)/N})^* \\ \\ &= \sum_{r=0}^{N-1} x[r] e^{ j 2 \pi r k/N} X^*[-k] \\ \\ &= \sum_{r=0}^{N-1} x[r] e^{ -j 2 \pi r (-k)/N} X^*[-k] \\ \\ &= X[-k] X^*[-k] = \Big| X[-k] \Big|^2 \\ \\ & \ne \ X[k] X^*[k] \quad = \Big| X[k] \Big|^2 \\ \end{align}

as $$X[k] = \mathcal{DFT} \{ x[r] \} = \sum_{r=0}^{N-1} x[r] e^{- j 2 \pi r k/N}$$

so where is my mistake? and how should I approach??

• Please have a look at how I made your post readable. Please use Latex formatting for formulas so people can actually understand what you're asking. Another thing: this is a typical homework problem, so please show us what you did and where you're stuck. – Matt L. Jan 20 '18 at 16:28
• There is a thing called Direct Proof for which you can use specific properties of the dft to start from the left and end on the right. Do you think you could have a go at this and then update the question with your progress? As this is a homework question, at the moment, it does not contain any work you may have done so far and therefore it is unclear what exactly you are stuck with (?) – A_A Jan 20 '18 at 23:18
• the result you seek appears to be true only if $x[n]$ is real. – robert bristow-johnson Mar 1 '18 at 9:07
• how the result is true if $x[n]$ is real ? please explain.... @robert bristow-johnson – Suresh Mar 1 '18 at 16:03
• if $x[n]$ is purely real (that is $\Im\{x[n]\}=0 \quad \forall n \in \mathbb{Z}$), then $X[-k]=X^*[k]$ and likewise $X[k]=X^*[-k]$ and that bottom "$\ne$" becomes "$=$". – robert bristow-johnson Mar 1 '18 at 18:18

The complex conjugate property of DFT states that $\rm{DFT}\{x^{*}[n]\} = X^{*}[-k]$. This implies that exponent in the second line of your proof should be $-k$. Which then allows for the DFT of $x[n]$ as $X[k]$. A number multiplied by its conjugate give the square of its absolute value.
• turns out that the result he needs with $X[k]$ (rather than $X[-k]$) is true only if $x[n]$ is purely real. – robert bristow-johnson Mar 1 '18 at 9:32