Practical Bottom Line

Since we must use the DFT in practice, preferring the 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$):
   $$x \isdef [v(0),v(1),\ldots,v(M-1), \underbrace{0,\ldots,0}_{\hbox{$N-M$}}].$$

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
   $$\hat{r}_{v,M}(l) \isdef \left\{\begin{array}{ll} \frac{1}{M-\ver... ...)} \\ [5pt] 0, & \vert l\vert\geq M\; \mbox{(mod $N$)}. \\ \end{array}\right.$$

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

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 §5.12 below.