Correlation

Step-by-step illustration of correlation between two signals with all intermediate plots

Correlation is a foundation over which the whole structure of digital communications is built. In fact, correlation is the heart of a digital communication system, not only for data detection but for parameter estimation of various kinds as well. Throughout, we will find recurring reminders of this fact.

As a start, consider from the article on Discrete Fourier Transform that each DFT output S[k] is just a sum of term-by-term products between an input signal and a cosine/sine wave, which is actually a computation of correlation. Later, we will learn that to detect the transmitted bits at the receiver, correlation is utilized to select the most likely candidate. Moreover, estimates of timing, frequency and phase of a received signal are extracted through judicious application of correlation for synchronization, as well as channel estimates for equalization. Don’t worry if you did not understand the last sentence, as we will have plenty of opportunity on this website to learn about these topics.

By definition, correlation is a measure of similarity between two signals. In our everyday life, we recognize something by running in our heads its correlation with what we know. Correlation plays such a vital and deep role in diverse areas of our life, be it science, sports, economics, business, marketing, criminology or psychology, that a complete book can be devoted to this topic.


"The world is full of obvious things which nobody by any chance ever observes."

Holmes to Watson – The Hound of the Baskervilles

For all of Sherlock Holmes’ inferences, his next step after observation was always correlation. For example, he accurately described Dr James Mortimer’s dog through correlating some observations with templates in his mind:


"\cdots and the marks of his teeth are very plainly visible. The dog’s jaw, as shown in the space between these marks, is too broad in my opinion for a terrier and not broad enough for a mastiff. It may have been — yes, by Jove, it is a curly-haired spaniel."

Sherlock Holmes – The Hound of the Baskervilles

As in the case of convolution, we start with real signals and the case of complex signals will be discussed later.

Correlation of Real Signals


The objective of correlation between two signals is to measure the degree to which those two signals are similar to each other. Mathematically, correlation between two signals s[n] and h[n] is defined as

(1)   \begin{equation*}         r_{sh}[n] = \sum \limits _{m = -\infty} ^{\infty} s[m] h[m-n]     \end{equation*}

where the above sum is computed for each n from -\infty to +\infty and the subscript s and h represent the order in which the signals appear on right hand side. We denote correlation operation by "\text{corr}" as

(2)   \begin{equation*}       r_{sh}[n] = s[n] ~\text{corr}~ h[n]     \end{equation*}

Note that unlike convolution,

(3)   \begin{equation*}         s[n] ~\text{corr}~ h[n] \neq  h[n] ~\text{corr}~ s[n]     \end{equation*}

This can be verified by plugging p = m-n in Eq (1) which yields m = n+p and hence

    \begin{align*}       \sum \limits _{p = -\infty} ^{\infty} s[n+p] h[p]  &= \sum \limits _{p = -\infty} ^{\infty}  h[p] s[p+n] \\                                                          & \neq \sum \limits _{m = -\infty} ^{\infty} h[m] s[m-n]     \end{align*}

Nevertheless, it can be deduced that Eq (1) is equivalent to

(4)   \begin{equation*}              r_{sh}[n] = \sum \limits _{m = -\infty} ^{\infty} s[m+n] h[m]     \end{equation*}

Now we can say that

    \begin{equation*} r_{sh}[n] = r_{hs}[-n] \end{equation*}

In terms of conveying information, there is not much difference and one is just a flipped version of the other.

Correlation computation


Comparing Eq (1) with convolution Eq, it is evident that

(5)   \begin{equation*}         r_{sh}[n] = s[n] * h[-n]     \end{equation*}

Therefore, from a viewpoint of conventional method, computing correlation between two signals is very similar to their convolution, except that there is no flipping of one signal. This is because h[-n] flips the signal once and convolution flips it again, hence bringing the original signal back.

From the viewpoint of intuitive method, it is clear that a negative sign with the NOW, -n, turns the future into past, and the past into future. Consequently, the last sample of the original signal arrives first, since it has become the farthest past.

Except this difference, correlation of real signals is very similar to convolution and the discussion on convolution accordingly applies here as well. For complex signals, there is another remarkable difference between the two, which we discuss next.

An example of correlation between the same two signals as in convolution example, s[n] = [2\hspace{1mm}-\hspace{-1mm}1\hspace{2mm} 1] and h[n] = [-1\hspace{2mm} 1\hspace{2mm} 2], is shown in Figure below, where the result r[n] is shown for each n.

Step-by-step illustration of correlation between two signals with all intermediate plots

Correlation of Complex Signals


Correlation between two complex signals s[n] and h[n] can be understood through writing Eq (1) in IQ form. However, another difference from convolution is that one signal is conjugated as

(6)   \begin{align*}         r_{sh}[n] &= s[n] ~\text{corr}~ h^*[n] \nonumber \\                   &= \sum \limits _{m = -\infty} ^{\infty} s[m] h^*[m-n]       \end{align*}

where conjugate of a signal was defined in the article on complex numbers. The above equation can be decomposed as in this Eq,

(7)   \begin{align*}          (r_{sh}[n])_I\: &= s_I[n] ~\text{corr}~ h_I[n] + s_Q[n] ~\text{corr}~ h_Q[n] \\         (r_{sh}[n])_Q &= s_Q[n] ~\text{corr}~ h_I[n] - s_I[n] ~\text{corr}~ h_Q[n]       \end{align*}

The actual computations can be written as

(8)   \begin{align*}          (r_{sh}[n])_I\: &= \sum \limits _{m = -\infty} ^{\infty} s_I[m] h_I[m-n] + \sum \limits _{m = -\infty} ^{\infty} s_Q[m] h_Q[m-n] \\         (r_{sh}[n])_Q &= \sum \limits _{m = -\infty} ^{\infty} s_Q[m] h_I[m-n] - \sum \limits _{m = -\infty} ^{\infty} s_I[m] h_Q[m-n]       \end{align*}

Due to the identity \cos A \cos B + \sin A \sin B = \cos (A-B), a positive sign in I term indicates that phases of the two aligned-axes terms are actually getting subtracted. Obviously, the identity applies in above equations only if magnitude can be extracted as common term, but the concept of phase-alignment still holds. Similarly, the identity \sin A \cos B - \cos A \sin B = \sin (A-B) implies that phases of the two cross-axes terms are also getting subtracted in Q expression. Hence, a complex correlation can be described as a process that

  • computes 4 real correlations: I ~\text{corr}~ I, Q ~\text{corr}~ Q, Q ~\text{corr}~ I and I ~\text{corr}~ Q
  • subtracts by phase anti-aligning the 2 aligned-axes correlations (I \diamond I + Q \diamond Q) to obtain the I component
  • subtracts the 2 cross-axes correlations (Q ~\text{corr}~ II ~\text{corr}~ Q) to obtain the Q component.

Now it can be inferred why a conjugate was required in the definition of complex correlation but not complex convolution. The purpose of correlation is to extract the degree of similarity between two signals, and whenever A is close to B,

    \begin{align*}       \cos(A-B) &\approx 1 \\       \sin(A-B) &\approx 0     \end{align*}

thus maximizing the correlation output.

Correlation and Frequency Domain


Just like convolution, there is an interesting interpretation of correlation in frequency domain. As before, DFT works with circular shifts only due to the way both time and frequency domain sequences are defined within a range 0 \le n, k \le N-1.

As always, we utilize the definition of DFT by applying Eq (1) to DFT definition. The derivation is similar to convolution.

Circular correlation between two signals in time domain is equivalent to multiplication of the first signal with conjugate of the second signal in frequency domain because

    \begin{equation*}         s[n] ~\boxed{\text{corr}}~ h[n] = s[n] \circledast h^*[-n]     \end{equation*}

which leads to

(9)   \begin{equation*}         s[n] ~\boxed{\text{corr}}~ h[n]  ~\xrightarrow{\text{\large{F}}} ~ S[k] \cdot H^*[k]      \end{equation*}

and the relation between h^*[-n] and H^*[k] can be established through the DFT definition.

Cross and Auto-Correlation


The correlation discussed above between two different signals is naturally called cross-correlation. When a signal is correlated with itself, it is called auto-correlation. It is defined by setting h[n] = s[n] in Eq (6) as

(10)   \begin{align*}         r_{ss}[n] &= s[n] ~\text{corr}~ s^*[n] \nonumber \\                   &= \sum \limits _{m = -\infty} ^{\infty} s[m] s^*[m-n]      \end{align*}

An interesting fact to note is that

(11)   \begin{align*}         r_{ss}[0] &= \sum \limits _{m = -\infty} ^{\infty} s[m] s^*[m] \nonumber \\                   &= \sum \limits _{m = -\infty} ^{\infty} |s[m]|^2 \nonumber \\                   &= E_s      \end{align*}

which is the energy of the signal s[n].

Remember that another signal can have a large amount of energy such that the result of its cross-correlation with s[n] can be greater than the auto-correlation of s[n], which intuitively should not happen. Normalized correlation \overline{r}_{sh}[n] is defined in Eq (12) in a way that the maximum value of 1 can only occur for correlation of a signal with itself.

(12)   \begin{align*}         \overline{r}_{sh}[n] &= \frac{\sum \limits _{m = -\infty} ^{\infty} s[m] h^*[m-n]}{\sqrt{\sum \limits _{m = -\infty} ^{\infty} |s[m]|^2} \cdot \sqrt{\sum \limits _{m = -\infty} ^{\infty} |h[m]|^2}} \nonumber \\         &= \frac{1}{\sqrt{E_s} \cdot \sqrt{E_h}} ~~ \sum \limits _{m = -\infty} ^{\infty} s[m] h^*[m-n]      \end{align*}

In this case, regardless of the energy in the other signal, its normalized cross-correlation with another signal cannot be greater than the normalized auto-correlation of a signal due to both energies appearing in the denominator.

Spectral Density


Taking the DFT of auto-correlation of a signal and utilizing Eq (9), we get

(13)   \begin{equation*}         r_{ss}[n] ~\xrightarrow{\text{\large{F}}} ~ S[k] \cdot S^*[k] = |S[k]|^2     \end{equation*}

The expression |S[k]|^2 is called Spectral Density, because from Parseval relation in the article on DFT Examples that relates the signal energy in time domain to that in frequency domain,

    \begin{equation*}         E_s = \sum _{n=0} ^{N-1} |s[n]|^2 = \frac{1}{N} \sum _{n=0} ^{N-1} |S[k]|^2     \end{equation*}

Thus, energy of a signal can be obtained by summing the energy |S[k]|^2 in each frequency bin (up to a normalizing constant 1/N). Accordingly, |S[k]|^2 can be termed as energy per spectral bin, or spectral density.

From the above discussion, there are two ways to find the spectral density of a signal:

  1. Take the magnitude squared of the DFT of a signal.
  2. Take the DFT of the signal auto-correlation.

If you found this article useful, you might want to subscribe to my email list below to receive new articles.


Leave a Comment

Your email address will not be published. Required fields are marked *