Correlation
Correlation (Linear)
In many applications in Digital Signal Processing, it is necessary to determine the similarity between two signals. A common example of such an example is that of a RADAR in which the received and transmitted signals are correlated to determine the delay and from that the distance. Another instance where one might need to find similarity is to ‘look’ for a specific pattern with in a signal. This ‘similarity’ can be determined using the correlation operation. Given x[n] is one of the signals and h[n] is the other signal. A formulation of the correlation operation can be made in a manner similar to convolution. The idea is to multiply the corresponding samples (samples having same value of time index) of the two signals and summing the values up. This is done by keeping one of the signals stationary while moving across the other signal across it by delaying the signal by one time index each time. The product between the aligned samples is computed and the values are summed up to form the correlation coefficient for that delay lag (also called the correlation lag). The correlation operation is given by the equation
Where is the result from the correlation between x[n] and h[n]. is the Correlation lag and describes the lag of h[n]at which the current correlation coefficient ( at a specific ) has been computed. Given that x[n] has length l and h[n] has length m, the length of the output is (l+m-1). The peak value (positive) represents a very high similarity and a negative value represents a negative relation (inversion). Computationally, the only difference between convolution and convolution is that the signal h[n] is not time reversed before carrying out the delaying the signal, multiplying and adding the aligned signal samples.
The correlation operation described above is computed for two different signals and is thus called Cross-Correlation. If the correlation operation is computed for the same signal, i-e h[n]=x[n], then it is called the Auto-Correlation operation. The equation for Auto-correlation can be written as
One application of the auto-correlation function is to determine whether a signal contains periodic components or not.
In order to demonstrate correlation, we consider two signals x[n] = [1 2 3] and a signal h[n] = [1 2 3](this is effectively auto-correlation). The signals x[n] and h[n] are shown in the figure below.
For correlation, we need to change the index to k, therefore,
Note that we do not need to time reverse the signal h[n] as we need to determine the similarity. The computation of the correlation between x[n] and h[n] is depicted in the figures below.
For =-2
Multiplying and adding the aligned samples gives, y[-2]=3.
For =-1
Multiplying and adding the aligned samples gives, y[-1]=8.
For =0
Multiplying and adding the aligned samples gives, y[0]=14.
For =1
Multiplying and adding the aligned samples gives, y[1]=8.
For =2
Multiplying and adding the aligned samples gives, y[2]=3. The complete correlation output is
The output is shown graphically in the figure below
As can be seen from the output that the highest value is found to be for a lag value of zero which signifies maximum similarity.
Normalised Correlation
One can also normalise the correlation coefficients to provide invariance to signal energy. The motivation to carry out the normalising comes from the fact that the value of the Auto-Correlation of a signal at zero lag is equal to the energy of the signal. The normalised Cross-Correlation is given as
The Auto-Correlation function as
A value of 1 represents maximum similarity, -1 represents an inverse relationship and 0 represents no similarity.
Circular Correlation
Like circular convolution, the circular correlation operation is used for signals which are periodic. The circular correlation operation is given as
Where is the result of the circular correlation between the periodic input signal xper[n] and the periodic system impulse response hper[n]. N is the period of the signals. If one of the signal has a smaller period than the other, the first signal is padded with trailing zeros. The length of the output signal is equal to N.