DSPRelated.com
Free Books
   Free Books    Spectral Audio Signal Processing  

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 inverting 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 Section:
Why an Impulse is Not White Noise
Previous Section:
Cyclic Autocorrelation