Correlation Theorem

Theorem: For all $x,y\in\mathbb{C}^N$ ,

$$\zbox {x\star y \;\longleftrightarrow\;\overline{X}\cdot Y}$$

where the correlation operation `$\star$ ' was defined in §7.2.5.

Proof:

$$\begin{eqnarray*} (x\star y)_n &\isdef & \sum_{m=0}^{N-1}\overline{x(m)}y(n+m) \\ &=& \sum_{m=0}^{N-1}\overline{x(-m)}y(n-m) \qquad (m\leftarrow -m)\\ &=& \left(\hbox{\sc Flip}(\overline{x})\circledast y\right)_n \\ &\;\longleftrightarrow\;& \overline{X} \cdot Y \end{eqnarray*}$$

The last step follows from the convolution theorem and the result $\hbox{\sc Flip}(\overline{x}) \leftrightarrow \overline{X}$ from §7.4.2. Also, the summation range in the second line is equivalent to the range $[N-1,0]$ because all indexing is modulo $N$ .