Unbiased Cross-Correlation
Recall that the cross-correlation operator is cyclic (circular)
since is interpreted modulo
. In practice, we are normally
interested in estimating the acyclic cross-correlation
between two signals. For this (more realistic) case, we may define
instead the unbiased cross-correlation
![$\displaystyle \zbox {{\hat r}^u_{xy}(l) \isdef \frac{1}{N-l}\sum_{n=0}^{N-1-l} \overline{x(n)} y(n+l),\quad
l = 0,1,2,\ldots,L-1}
$](http://www.dsprelated.com/josimages_new/mdft/img1555.png)
![$ L\ll N$](http://www.dsprelated.com/josimages_new/mdft/img1556.png)
![$ L\approx\sqrt{N}$](http://www.dsprelated.com/josimages_new/mdft/img1557.png)
![$ \overline{x(n)} y(n+l)$](http://www.dsprelated.com/josimages_new/mdft/img1558.png)
![$ L-1$](http://www.dsprelated.com/josimages_new/mdft/img1218.png)
![$ n=N-l-1$](http://www.dsprelated.com/josimages_new/mdft/img1559.png)
![$ n$](http://www.dsprelated.com/josimages_new/mdft/img80.png)
![$ N$](http://www.dsprelated.com/josimages_new/mdft/img35.png)
![$ {\hat r}^u_{xy}(l)$](http://www.dsprelated.com/josimages_new/mdft/img1560.png)
![$ r_{xy}(l)$](http://www.dsprelated.com/josimages_new/mdft/img1552.png)
![$ x$](http://www.dsprelated.com/josimages_new/mdft/img25.png)
![$ y$](http://www.dsprelated.com/josimages_new/mdft/img26.png)
An unbiased acyclic cross-correlation may be computed faster via DFT (FFT) methods using zero padding:
![$\displaystyle \zbox {{\hat r}^u_{xy}(l) = \frac{1}{N-l}\hbox{\sc IDFT}_l(\overline{X}\cdot Y), \quad
l = 0,1,2,\ldots,L-1}
$](http://www.dsprelated.com/josimages_new/mdft/img1561.png)
![\begin{eqnarray*}
X &=& \hbox{\sc DFT}[\hbox{\sc CausalZeroPad}_{N+L-1}(x)]\\
Y &=& \hbox{\sc DFT}[\hbox{\sc CausalZeroPad}_{N+L-1}(y)].
\end{eqnarray*}](http://www.dsprelated.com/josimages_new/mdft/img1562.png)
Note that and
belong to
while
and
belong to
. The zero-padding may be causal (as defined in
§7.2.8)
because the signals are assumed to be be stationary, in which case all
signal statistics are time-invariant. As usual when embedding acyclic
correlation (or convolution) within the cyclic variant given by the
DFT, sufficient zero-padding is provided so that only zeros are ``time
aliased'' (wrapped around in time) by modulo indexing.
Cross-correlation is used extensively in audio signal processing for applications such as time scale modification, pitch shifting, click removal, and many others.
Next Section:
Autocorrelation
Previous Section:
Cross-Correlation