DISCRETE-TIME
CORRELATION
Dr. Muhammad
Zaigham Abbas
In these lectures…
Cross-Correlation
Concepts
Relation with Convolution
Examples
Auto-Correlation
Correlation
Definition:
Correlation or “Co-Relation” is a measure of similarity/
relationship between two signals
If x[n] & y[n] are two discrete-time signals, then the
correlation of x[n] with respect to y[n] is given as,
rxy [l ] x[m] y[m l ]
m
where l is lag, indicating time-shift
Applications of Correlation
There are applications where it is necessary to compare
one reference signal with one or more signals to
determine the similarity between the pair and to
determine additional information based on the
similarity
In machine learning, a neural network called
“Convolutional Neural Network” essentially computes
correlation
You’ll see in subsequent slides that convolution and
correlation are similar algorithms
In digital communications, “correlators” can be used to
detect and demodulate signals
In RADAR systems, the principle of correlation can be
used to estimate the distance of target from the RADAR
Computing Cross-Correlation
Cross-Correlation: Correlation between two different sequences
Matlab command xcorr() can be used for this purpose
x-corr x wrt y x-corr y wrt x
rxy [l ] x[m] y[m l ] ryx [l ] y[m] x[m l ]
m m
y[n] is said to be shifted by l samples to the right with
respect to the reference sequence x[n] for positive
values of l, and shifted by l samples to the left for
negative values of l
The ordering of the subscripts xy in the definition of
rxy[l] specifies that x[n] is the reference sequence which
remains fixed in time, while y[n] is being shifted with
respect to x[n]
Relationship b/w Conv. & Corr.
Mathematically, the Convolution between x[n] & h[n] is
given as
y[n] x[k ] h[n k ]
k
Correlation of x[n] with h[n] is given as
r[n] x[k ] h[k n]
k
Replaced variable l by n, & no time
reversal
But if we “time-reversed” the second sequence of the
Convolution, we end up with Correlation
y[n] x[k ] h[ (n k )]
k
x[k ] h[ n k ]
k
r[n] x[k ] h[k n]
k
Where, r[n] is the correlation of x[n] with respect to
h[n]
So, we can say that
“Correlation, mathematically, is just Convolution,
with the second sequence, time-reversed”
r[n] x[n] * h[ n]
We can use this property to find Correlation, using the
same method we used for Convolution, albeit, the
second sequence needs to be time-reversed
This only requires that we don’t time-
reverse for convolution in the first
place!
Example 1: Find the correlation b/w the two sequences x[n] and y[n]
given by,
x[n] = [3 1 2] y[n] = [3 2 1]
m: -2 -1 0 1 2 3 4 5
x[m]: 3 1 2
y[m+2]: 3 2 1
y[m+1]: 3 2 1
y[m]: 3 2 1
y[m-1]: 3 2 1
y[m-2]: 3 2 1
y[m-3]: 3 2 1
Hint: The value of m starts from (– length of y + 1) and continues till (length
of y + length of x – 1)
Here m starts from -3 + 1 = -2 and continues till 3 + 3 – 1 = 5
m: -2 -1 0 1 2 3 4 5
x[m]: 3 1 2
y[m+2]: 3 2 1
y[m+1]: 3 2 1
y[m]: 3 2 1
y[m-1]: 3 2 1
y[m-2]: 3 2 1
y[m-3]: 3 2 1
rxy[-2] = 3 x 1
=3
m: -2 -1 0 1 2 3 4 5
x[m]: 3 1 2
y[m+2]: 3 2 1
y[m+1]: 3 2 1
y[m]: 3 2 1
y[m-1]: 3 2 1
y[m-2]: 3 2 1
y[m-3]: 3 2 1
rxy[-2] = 3 x 1 =
3
rxy[-1] = 3 x 2 + 1 x 1
=7
m: -2 -1 0 1 2 3 4 5
x[m]: 3 1 2
y[m+2]: 3 2 1
y[m+1]: 3 2 1
y[m]: 3 2 1
y[m-1]: 3 2 1
y[m-2]: 3 2 1
y[m-3]: 3 2 1
rxy[-2] = 3 x 1 = 3
rxy[-1] = 3 x 2 + 1 x 1
=7
rxy[0] = 3 x 3 + 1 x 2 + 2 x
1= 13
m: -2 -1 0 1 2 3 4 5
x[m]: 3 1 2
y[m+2]: 3 2 1
y[m+1]: 3 2 1
y[m]: 3 2 1
y[m-1]: 3 2 1
y[m-2]: 3 2 1
y[m-3]: 3 2 1
rxy[-2] = 3 x 1 = rxy[1] = 1 x 3 + 2 x 2 = 7
3
rxy[-1] = 3 x 2 + 1 x 1 =
7
rxy[0] = 3 x 3 + 1 x 2 + 2 x
1= 13
m: -2 -1 0 1 2 3 4 5
x[m]: 3 1 2
y[m+2]: 3 2 1
y[m+1]: 3 2 1
y[m]: 3 2 1
y[m-1]: 3 2 1
y[m-2]: 3 2 1
y[m-3]: 3 2 1
rxy[-2] = 3 x 1 = 3 rxy[1] = 1 x 3 + 2 x 2 = 7
rxy[-1] = 3 x 2 + 1 x 1 = rxy[2] = 2 x 3 = 6
7
rxy[0] = 3 x 3 + 1 x 2 + 2 x 1=
13
Define x & y in Matlab and use command xcorr(x,y) to
verify this answer
m: -2 -1 0 1 2 3 4 5
x[m]: 3 1 2
y[m+2]: 3 2 1
y[m+1]: 3 2 1
y[m]: 3 2 1
y[m-1]: 3 2 1
y[m-2]: 3 2 1
y[m-3]: 3 2 1
rxy[-2] = 3 x 1 = 3 rxy[1] = 1 x 3 + 2 x 2 = 7
rxy[-1] = 3 x 2 + 1 x 1 = 7 rxy[2] = 2 x 3 = 6
rxy[0] = 3 x 3 + 1 x 2 + 2 x 1= rxy[3] = 0 (no overlap)
13 rxy l {3 7 13 7 6}
Example 2: Find the correlation of y[n] with respect to x[n], with the
sequences given by,
x[n] = [3 1 2] y[n] = [3 2 1]
m: -2 -1 0 1 2 3 4 5
y[m]: 3 2 1
x[m+2]: 3 1 2
x[m+1]: 3 1 2
x[m]: 3 1 2
x[m-1]: 3 1 2
x[m-2]: 3 1 2
x[m-3]: 3 1 2
Hint: The value of m starts from (– length of y + 1) and continues till (length
of y + length of x – 1)
Here m starts from -3 + 1 = -2 and continues till 3 + 3 – 1 = 5
m: -2 -1 0 1 2 3 4 5
y[m]: 3 2 1
x[m+2]: 3 1 2
x[m+1]: 3 1 2
x[m]: 3 1 2
x[m-1]: 3 1 2
x[m-2]: 3 1 2
x[m-3]: 3 1 2
ryx[-2] = 3 x 2 =
6
m: -2 -1 0 1 2 3 4 5
y[m]: 3 2 1
x[m+2]: 3 1 2
x[m+1]: 3 1 2
x[m]: 3 1 2
x[m-1]: 3 1 2
x[m-2]: 3 1 2
x[m-3]: 3 1 2
ryx[-2] = 3 x 2 =
6
ryx[-1] = 3 x 1 + 2 x 2
=7
m: -2 -1 0 1 2 3 4 5
y[m]: 3 2 1
x[m+2]: 3 1 2
x[m+1]: 3 1 2
x[m]: 3 1 2
x[m-1]: 3 1 2
x[m-2]: 3 1 2
x[m-3]: 3 1 2
ryx[-2] = 3 x 2
=6
ryx[-1] = 3 x 1 + 2 x 2 =
7
ryx[0] = 3 x 3 + 2 x 1 + 1 x 2=
13
m: -2 -1 0 1 2 3 4 5
y[m]: 3 2 1
x[m+2]: 3 1 2
x[m+1]: 3 1 2
x[m]: 3 1 2
x[m-1]: 3 1 2
x[m-2]: 3 1 2
x[m-3]: 3 1 2
ryx[-2] = 3 x 2 = 6 ryx[1] = 2 x 3 + 1 x 1 = 7
ryx[-1] = 3 x 1 + 2 x 2 = 7
ryx[0] = 3 x 3 + 2 x 1 + 1 x 2=
13
m: -2 -1 0 1 2 3 4 5
y[m]: 3 2 1
x[m+2]: 3 1 2
x[m+1]: 3 1 2
x[m]: 3 1 2
x[m-1]: 3 1 2
x[m-2]: 3 1 2
x[m-3]: 3 1 2
ryx[-2] = 3 x 2 = ryx[1] = 2 x 3 + 1 x 1 = 7
6
ryx[-1] = 3 x 1 + 2 x 2 = ryx[2] = 1 x 3 = 3
7
ryx[0] = 3 x 3 + 2 x 1 + 1 x 2= 13
Define x & y in Matlab and use command xcorr(y,x) to
verify this answer
m: -2 -1 0 1 2 3 4 5
y[m]: 3 2 1
x[m+2]: 3 1 2
x[m+1]: 3 1 2
x[m]: 3 1 2
x[m-1]: 3 1 2
x[m-2]: 3 1 2
x[m-3]: 3 1 2
ryx[-2] = 3 x 2 = ryx[1] = 2 x 3 + 1 x 1 = 7
6
ryx[-1] = 3 x 1 + 2 x 2 = 7 ryx[2] = 1 x 3 = 3
ryx[0] = 3 x 3 + 2 x 1 + 1 x ryx[3] = 0 (no overlap)
2= 13 ryx l {6 7 13 7 3}
Example 3: Find the correlation of the two sequences x[n] and y[n]
represented by,
x[n] = {1 2 3} y[n] = [0.5 1 2 1 0.5]
Rxy [l ] R yx [ l ]
Verify
Autocorrelation
Auto-Correlation: Correlation between the same sequence
Mathematically, it is given as,
rxx [l ] x[m]x[m l ], l 0,1,2,...
m
At zero(0) lag, it returns a maximum value and the energy of the signal
rxx [0] x[m]x[m] x 2 [n] E x
n
Ambiguity in the Results!
Suppose, we have three
sequences:
Sequence a
6
a[n] = [1 2 3 4 5 6]; 4
b[n] = [2 4 6 8 10 12]; 2
c[n] = [5 10 15 20 25 30]; 0
1 2 3 4 5 6
Sequence b
15
Note here that, 10
0
b = 2*a 1 2 3 4 5 6
Sequence c
c = 5*a 30
20
10
and we want to find the correlation 0
1 2 3 4 5 6
between a[n] & b[n] and also
a[n] & c[n]
i.e. rab & rac
The results show that r ab
200
1) Correlation between a[n] 182
& b[n] has a maximum
150
value of 182 at zero lag 100
50
0
-5 -4 -3 -2 -1 0 1 2 3 4 5
2) Correlation between a[n]
r ac
& c[n] has a maximum 500
455
value of 455 at zero lag 400
300
200
These results seem 100
ambiguous 0
-5 -4 -3 -2 -1 0 1 2 3 4 5
and misleading given b[n]
and c[n] are simply
amplitude scaled versions
of a[n]
This particular ambiguity can be resolved by amplitude
normalizing a[n], b[n], and c[n] prior to compute their
correlations
Normalized Correlations
Normalized Correlation between x[n] and y[n]
rxy l
xy l
rxx 0 ryy 0
Normalized Autocorrelation
rxx l
xx l
rxx 0
Normalisation – step 1
Normalise input sequences by their maximum value
For example, a_norm = a/max(a)
Sequence a Normalised Sequence a
6
1
4
2 0.5
0 0
1 2 3 4 5 6 0 1 2 3 4 5 6
Sequence b Normalised Sequence b
15
1
10
5 0.5
0 0
1 2 3 4 5 6 0 1 2 3 4 5 6
Sequence c Normalised Sequence c
30
1
20
10 0.5
0 0
1 2 3 4 5 6 0 1 2 3 4 5 6
Unnormalised sequences Normalised sequences
Normalisation – step 1
Let’s inspect the effect of normalization
on the cross-correlation graph
r ab r ab
200 3
150
2
100
1
50
0 0
-5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 5
r ac r ac
500 3
400
2
300
200
1
100
0 0
-5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 5
Unnormalised cross- Cross-correlation with
Normalisation – step 2
rxy l
xy l
Normalise cross-correlation using
rxx 0 ryy 0
r ab r ab (normalised)
200
1
150
100
0.5
50
0 0
-5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 5
r ac r ac (normalised)
500
400 1
300
200 0.5
100
0 0
-5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 5
Unnormalised cross- Normalised cross-
