DSPRelated.com
Free Books
   Free Books    Mathematics of the DFT  

Correlation Theorem


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

$\displaystyle \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)... ...t 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}) \;\longleftrightarrow\;\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$.

Next Section:
Power Theorem
Previous Section:
Dual of the Convolution Theorem