2
$\begingroup$

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??

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Jan 20, 2018 at 16:28
  • $\begingroup$ 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 (?) $\endgroup$ Commented Jan 20, 2018 at 23:18
  • 1
    $\begingroup$ the result you seek appears to be true only if $x[n]$ is real. $\endgroup$ Commented Mar 1, 2018 at 9:07
  • $\begingroup$ how the result is true if $x[n]$ is real ? please explain.... @robert bristow-johnson $\endgroup$ Commented Mar 1, 2018 at 16:03
  • 1
    $\begingroup$ 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 "$=$". $\endgroup$ Commented Mar 1, 2018 at 18:18

2 Answers 2

Reset to default
2
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.