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 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."
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:
" 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."
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 and is defined as
This can be verified by plugging in Eq (1) which yields and hence
Nevertheless, it can be deduced that Eq (1) is equivalent to
Now we can say that
In terms of conveying information, there is not much difference and one is just a flipped version of the other.
Comparing Eq (1) with convolution Eq, it is evident that
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 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, , 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, and , is shown in Figure below, where the result is shown for each .
Correlation of Complex Signals
Correlation between two complex signals and can be understood through writing Eq (1) in form. However, another difference from convolution is that one signal is conjugated as
where conjugate of a signal was defined in the article on complex numbers. The above equation can be decomposed as in this Eq,
Due to the identity , a positive sign in 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 implies that phases of the two cross-axes terms are also getting subtracted in expression. Hence, a complex correlation can be described as a process that
- computes real correlations: , , and
- subtracts by phase anti-aligning the aligned-axes correlations ( + ) to obtain the component
- subtracts the cross-axes correlations ( – ) to obtain the 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 is close to ,
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 .
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
and the relation between and 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 in Eq (6) as
which is the energy of the signal .
Remember that another signal can have a large amount of energy such that the result of its cross-correlation with can be greater than the auto-correlation of , which intuitively should not happen. Normalized correlation is defined in Eq (12) in a way that the maximum value of can only occur for correlation of a signal with itself.
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.
Taking the DFT of auto-correlation of a signal and utilizing Eq (9), we get
The expression 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,
Thus, energy of a signal can be obtained by summing the energy in each frequency bin (up to a normalizing constant ). Accordingly, 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:
- Take the magnitude squared of the DFT of a signal.
- Take the DFT of the signal auto-correlation.