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

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

1 Answer 1

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$
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$
    – MBaz
    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$
    – BoltzBooz
    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$ Mar 1, 2018 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.