1
$\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??

$\endgroup$
  • 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$ – Matt L. Jan 20 '18 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$ – A_A Jan 20 '18 at 23:18
  • 1
    $\begingroup$ the result you seek appears to be true only if $x[n]$ is real. $\endgroup$ – robert bristow-johnson Mar 1 '18 at 9:07
  • $\begingroup$ how the result is true if $x[n]$ is real ? please explain.... @robert bristow-johnson $\endgroup$ – Suresh Mar 1 '18 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$ – robert bristow-johnson Mar 1 '18 at 18:18
1
$\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.

$\endgroup$
  • 2
    $\begingroup$ A suggestion: your answer would be more useful if you pointed out in which step of the derivation the mistake ocurred. $\endgroup$ – MBaz Feb 28 '18 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$ – BoltzBooz Mar 1 '18 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$ – robert bristow-johnson Mar 1 '18 at 9:32

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.