Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search


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) \\
&=& \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$ .


Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]

``Mathematics of the Discrete Fourier Transform (DFT), with Audio Applications --- Second Edition'', by Julius O. Smith III, W3K Publishing, 2007, ISBN 978-0-9745607-4-8.
Copyright © 2014-04-06 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA