Correlation is a process for determining the similarity between two waveforms; if those two waveforms are identical, the process is referred to as autocorrelation. The autocorrelation function (ACF) proves useful, for instance, in detecting the presence of periodic signals buried in noise. And just as researchers developed the discrete Fourier transform to make it possible to perform frequency transformations with computers, they've come up with digital techniques for performing the ACF. However, designers should be aware that several methods exist, and selecting the wrong one for a given application can produce invalid results.

To see where these digital versions come from, first recognize that the continuous ACF contains many useful mathematical properties. Perhaps the most useful comes from the Wiener-Khnitchine relation, which states that taking the ACF's Fourier transform generates the original signal's power spectral density (PSD). Thus, you can see that a direct relationship exists between the ACF and the Fourier transform. Indeed, the ACF contains the identical information found in the Fourier transform but in a different form.

Several digital ACFs

Ideally, the ACF's discrete version should maintain as many useful properties of a continuous ACF as possible. Unfortunately, researchers haven't found a discrete ACF formula containing all the desirable properties, so selecting an ACF computing technique depends heavily on the application. This article focuses on two popular methods.

As for the first, assume you need the ACF of the squarewave in Fig 1a. One discrete ACF formula is

where N equals the total number of samples in the waveform and l corresponds to the lag value. The term lag is just a substitute for index and historically means how far one signal is delayed when compared to another. This first formula produces the ACF in Fig 1b

Fig 1 -- Given the same source signal, as in (a), two digital ACFs generate completely different results (b) and (c), which become even more striking when you take their respective FFTs (d) and (e). Note in (d) the negative values for low frequencies -- something you'll never see in nature.

To determine how well this discrete ACF performs, you can consider several criteria. One popular choice bases itself on statistical analysis, where mathematical analysis shows that if the samples come from the real world (and thus are random), this formula doesn't equal the true discrete ACF. Instead each estimated value is on average off by a bias of (N - | 1 | / N)R_x(l). Thus, this method is called a biased estimate.

To get an unbiased discrete ACF, try a second formula:

Fig 1c illustrates the unbiased ACF values it generates for the example squarewave. Note the significant difference between the two ACF shapes and that ACF bias increases as lags increase.

Because the biased ACF produces incorrect values, why would you ever implement it? Because, unlike the unbiased ACF, it does produce valid results for one large ACF application area -- spectral analysis. As readers well know, taking the inverse FFT of a digital signal in the frequency domain generates the original time-domain signal. However, the Wiener-Khnitchine relation says the ACF is equivalent to taking the inverse FFT of the frequency-domain squared magnitude signal.

To see the implications of this fact, examine Figs 1d and 1e, which show the FFT for each of the example discrete ACFs in Figs 1b and 1c. First notice the graphs display only positive frequency components (ignoring the negative frequencies). The author did so because FFT magnitude values are exactly equal for positive and negative frequencies if the time-domain signal is real, which is true in this example.

Next notice that negative magnitude values exist for the unbiased ACF's squared Fourier magnitude in Fig 1d. Because the square of any value should be non-negative, something appears to have gone terribly wrong. To find out what, consider some DSP theory. When digitizing a continuous formula, you must take care to maintain as many continuous properties as possible. It turns out that an ACF must be positive semi-definite for its Fourier transform to equal a signal's squared magnitude FFT. What does this mumbo-jumbo mean? Simply put, an ACF is positive semi-definite if and only if

Although this property appears unduly mathematical, producing nonnegative Fourier transform values requires this ACF condition. A down-to-earth explanation of positive semi-definite doesn't exist, but for whatever it's worth, it does say that the eigenvalues of the autocorrelation matrix are non-negative. Also, unbiased ACFs aren't guaranteed positive semi-definite, whereas a biased ACF always is. Thus, the unbiased ACF produces more valid ACF values (because of no bias) while generating invalid spectral densities (not guaranteed positive semi-definite). Conversely, the biased ACF produces unreliable ACF values at high lags (due to the bias) but generates valid spectral densities (because it's positive semi-definite).

The effects of filtering

Let's now take this discussion beyond theory and examine some examples where the ACF's values and shape provide signal information. Suppose you start with a sequence of

Fig 2 -- Even though the time-domain waveshapes of a random signal (a) and the results of passing it through two different FIR filters (b) and (c) don't look considerably different, taking the ACF of those three (d), (e) and (f) reveals important information.

white random values (Gaussian random signal with mean = 0 and standard deviation = 1, Fig 2a) and pass them through two FIR filters

and

which generate the results in Fig 2b and 2c, respectively.

By looking at the outputs, what can you determine about the filters? You could generate each filtered signal's PSD (by computing the signal's FFT squared magnitude) to verify that the filters remove high frequencies from the noise. However, investigating the correlation between ACF values by comparing local values provides additional information. Figs 2d, e and f illustrate the corresponding scaled ACFs for the white-noise signal and the two filtered signals (showing only the first 21 lags).

Notice that the white-noise ACF (Fig 2d) approximates an impulse function, which makes sense because white noise has a constant Fourier magnitude and because a constant's inverse Fourier transform is an impulse function.

In general, when looking at ACF graphs the author examines how the values decrease away from Lag 0. Any decrease indicates the amount of correlation existing between neighboring signal values. The first filter's ACF (Fig 2e) indicates that some correlation exists between adjacent signal values because Lag 1's value is well away from zero. ACF values beyond Lag 1 lie near zero, which indicates zero or no correlation between signal values two time units away. Recall that the filter uses one past signal value when computing the output, so it forces correlation into output at Lag 1. In turn, the second ACF (Fig 2f) indicates correlation out to Lag 2, implying that signal values separated by two time units relate to one other. Once again, the ACF and filter structure directly correspond because the second FIR filter uses two past signal values.

Uses in signal comparison

Although simple, these examples illustrate conceptually how correlation relates the ACF to signals or filters. Another popular discrete ACF application compares candidate signals to a prototype signal. To compare different signals, you extend the ACF beyond autocorrelation to the cross-correlation function (CCF).

For example, suppose you start with a prototype pulse (Fig 3a) and want to know which of four other signals (Figs 3b-e) more closely resemble it. You compare the signals by computing a CCF-like function, but before doing so, you must normalize them all to compensate for differing signal variances. Do so by computing

to scale and shift the CCF. Comparing signals using the CCF requires deciding whether or not the application determines that a shifted version of the prototype is a good or bad comparison. If you don't want to allow a shifted prototype version, set l = 0 and compute ρ_xy(0) for each candidate signal against the prototype signal.

As an example, compare the five signals in Figs 3a-e to the prototype in Fig 3a. Some quick calculations show that ρ_xy(0) equals approximately 1.0, 0.85, 0.25, 0.0 and 0.55, respectively. Note that  so that several signals -- the prototype itself, the prototype plus noise and the thinner pulse signal -- correlate highly with the prototype.

Fig 3 -- To see the effects of the CCF for signal comparison, consider the five example signals in (a) through (e). The plots in (f) through (j) show the CCF of each signal taken against that in (a). Of course, the CCF of (a) with itself is the ACF.

However, what happens with the shifted prototype? The CCF contains information concerning whether a shifted prototype exists along with the shifted amount. You can extract this information by computing ρ_xy(1) for values of l other than zero. Before computing these values, which ACF formula should you use? If you want to keep , use the biased ACF; if you want more accurate ACF values near Lag 0, then choose the unbiased ACF.

Computing the unbiased ρ_xy(1) produces the graphs in Fig 3f-j. Notice first that ρ_xy(1) > 1 at l = 6 for the shifted prototype. Thus the amount of shift is easily available because this large value indicates significant correlation and thus a near-perfect match. The main problem with an unbiased CCF occurs with large values far away from Lag 0. You can ignore these anomalies because the variance for them is high; in fact, variance increases the further away you move from Lag 0. Thus, when graphing and analyzing the CC, the author usually uses only 25% to 50% of the possible values.

As a final note, this article has hopefully shown that you can't blindly apply DSP algorithms without understanding the theoretical issues behind them. I can't tell you how many times I've seen algorithms misused due to some small idiosyncrasy. A golden rule of mine is to fully understand why a DSP algorithm produces the results it does. If you have difficulty doing so, then run the algorithm on some simple signals until you get the hang of it. As for the ACF, it's a very useful but sometimes forgotten DSP tool. As an exercise in efficiently computing the ACF (compared to directly coding the formula), how would you compute the discrete ACF using the FFT such that you minimize execution time?

This article originally appeared in Personal Engineering & Instrumentation News , Jan 1994, pgs 75-80. Reprinted with permission of PEC Inc; all rights reserved.

Matthew Perry is VP and general manager of Cirrus Logic's Embedded Processors Div (www.cirrus.com); Matt was with Motorola Inc when he wrote this article.

		Click here to get your listing up.