# 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. Commented Jan 20, 2018 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
Commented Jan 20, 2018 at 23:18
• the result you seek appears to be true only if $x[n]$ is real. Commented Mar 1, 2018 at 9:07
• how the result is true if $x[n]$ is real ? please explain.... @robert bristow-johnson Commented Mar 1, 2018 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 "$=$". Commented Mar 1, 2018 at 18:18

You did not consider the conjugate property of the DFT.

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.

And DFT is discrete in the transform domain, hence its parameter should be in brackets rather than parentheses.

• A suggestion: your answer would be more useful if you pointed out in which step of the derivation the mistake ocurred.
– MBaz
Commented Feb 28, 2018 at 18:14
• I lost a point the other time for giving details. What stops the poster from looking up the conjugate property of DFT? Commented Mar 1, 2018 at 8:02
• turns out that the result he needs with $X[k]$ (rather than $X[-k]$) is true only if $x[n]$ is purely real. Commented Mar 1, 2018 at 9:32

I've been trying to prove the same for myself the last couple of days and ended up with the exact same result as you. Very frustrating! I mean, it should hold for both real and complex values! And not only for real $$x[n]$$ as many people point out here.

To put it short, the error is in your definition of the auto-correlation function. It should be:

$$\sum_{r=0}^{N-1}x^*[r]x[r+n]$$

Not

$$\sum_{r=0}^{N-1}x[r]x^*[r+n]$$

See for example Julius O. Smith's definition in the book Mathematics of the DFT.

If you write the auto-correlation function like that you can prove it in a similar manner as you did: \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} \\ \\ &= \left( \sum_{r=0}^{N-1}x[r] e^{- j 2 \pi r k/N}\right)^* \sum_{n=0}^{N-1} x[n] e^{- j 2 \pi n k/N} \\ \\ &= X^*[k]X[k] = \Big| X[k] \Big|^2 \\ \\ \end{align}

It took me quite a while to figure out the mistake. I did not find any proofs of the Auto-correlation property of the DFT (Or the Wiener-Khinchin Theorem which this really is) for discrete time signals. There are many proofs out there for continuous signals, see for example Mathworld: Wiener-Khinchin, and notice here the definition of the autocorrelation function! We should conjugate the non-shifted function.