Free Books

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