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 sequence , as follows:

1. Choose the FFT size to be a power of 2 providing at least samples of zero padding ( ):
   

2. Perform a length FFT to get .
3. Compute the squared magnitude .
4. Compute the inverse FFT to get , .
5. Remove the bias, if desired, by inverting the implicit Bartlett-window weighting to get
   

Often the sample mean (average value) of the samples of is removed prior to taking the FFT. Some implementations also detrend the data, which means removing any linear ``tilt'' in the data.^6.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 §5.12 below.

---

Previous: Cyclic Autocorrelation
Next: Why an Impulse is Not White Noise

Order a Hardcopy of Spectral Audio Signal Processing

---

About the Author: Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.