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

Practical Bottom Line

Since we must use the DFT in practice, preferring an FFT for speed, we typically compute the sample autocorrelation function for a length $ M$ sequence $ v(n)$ , $ n=0,1,2,\ldots,M-1$ as follows:

  1. Choose the FFT size $ N$ to be a power of 2 providing at least $ M-1$ samples of zero padding ( $ N\geq 2M-1$ ):

    $\displaystyle x \isdef [v(0),v(1),\ldots,v(M-1), \underbrace{0,\ldots,0}_{\hbox{$N-M$}}].$ (7.21)

  2. Perform a length $ N$ FFT to get $ X(\omega_k)=\hbox{\sc FFT}_k(x)$ .
  3. Compute the squared magnitude $ \left\vert X(\omega_k)\right\vert^2$ .
  4. Compute the inverse FFT to get $ (x\star x)(l)$ , $ l=0,\ldots,N-1$ .
  5. Remove the bias, if desired, by dividing out the implicit Bartlett-window weighting to get

    $\displaystyle \hat{r}_{v,M}(l) \isdef \left\{\begin{array}{ll} \frac{1}{M-\vert l\vert} (x\star x)(l), & l=0,\,\pm1,\,\pm2,\,\pm (M-1)\;\mbox{(mod $N$)} \\ [5pt] 0, & \vert l\vert\geq M\; \mbox{(mod $N$)}. \\ \end{array} \right.$ (7.22)

Often the sample mean (average value) of the $ M$ samples of $ v(n)$ is removed prior to taking an FFT. Some implementations also detrend the data, which means removing any linear ``tilt'' in the data.7.6

It is important to note that the sample autocorrelation is itself a stochastic process. To stably estimate a true autocorrelation function, or its Fourier transform the power spectral density, many sample autocorrelations (or squared-magnitude FFTs) must be averaged together, as discussed in §6.12 below.

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]

``Spectral Audio Signal Processing'', by Julius O. Smith III, W3K Publishing, 2011, ISBN 978-0-9745607-3-1.
Copyright © 2022-02-28 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University