Determining Delay with Cross Correlation

11 replies · 13K views · last reply
Evo8
Messages
168
Reaction score
0

Homework Statement


Let x(t) be a transmitted radar pulse. The received radar pulse is y(t).

[itex]y(t)=ax(t-t_{d})+v(t)[/itex]

Where v(t) is the additive noise and td is the time delay. The signals x(t) and y(t) are sampled and processed digitally to determine the delay

The discrete time signals are:
x(n) = x(nT)
y(n) = ax(n − D) + v(n)

where v(n) is the noise in the received signal, T is the sampling time of the
receiver, and D is the number of samples the received pulse is delayed by
the round trip to the target.

1. Explain how we can use cross correlation to determine the delay

2.Let x(n) be the 13-point Barker sequence
x(n) = [11111 − 1 − 111 − 11 − 11]

and let v(n) be a Gaussian zero mean sequence with variance [itex]σ^{2} = .01[/itex]
A Gaussian random variable array with σ2 = 1 can be generated using randn(m,n). To convert the sequence to another value of σ2, just multiply the entire sequence by σ. Write a program that generates the sequence y(n), for 0 ≤ n ≤ 199 for variable parameters a and D. Choose D to be the last two digits of your birth year + the day of your birth. If your birthday was August 21, 1989, D = 89 + 21 = 110. Thus, in y(n), there will be D zeros prior to the beginning of the Barker sequence and enough zeros afterwards to increase the length of y(n) to 200.

D=94
a=0.8814

3. Plot the signals x(n) and y(n) for 0≤n≤199

4. Compute and plot the cross correlation. 0≤l≤185. Estimate the delay from the plot

Homework Equations


See code below.


The Attempt at a Solution



For #1 this is what I think. -The cross correlation can be used to determine the degree that two series are related or correlated. When the two signals are calculated and cross correlated the result can be graphed and analyzed for the delay. The bounds that the cross correlation is calculated to will indicate how much correlation at certain delays. If an area of interest is at the positive bound this shows a high correlation, if at the lower bound this indicated no correlation. If below the lower bound this can indicate a negative correlation.

Ok so I thought I had this one down but my results just don't match up to my original delay of 94. I get almost exactly double my original delay. Am I missing something here?

#3
Here is my code:
clear all
n=0:199;
a=0.8814;
D=94;
v=randn(1,200)*.01;
x=[zeros(1,94) 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13+D))];
y=a*x+v;
subplot(2,1,1); plot(x); grid
xlabel('...'); ylabel('...');
title('x(n) Plot');
subplot(2,1,2); plot(y); grid
xlabel('...'); ylabel('...');
title('y(n) Plot');

The plots from this code
Two stacked line plots of digital signals over a common time axis: the upper trace is a short coded pulse with alternating positive and negative segments, and the lower trace shows the same pattern shifted later with added noise.



For #4 I reused the code and added the cross correlation:

clear all
n=0:185;
a=0.8814;
D=94;
v=randn(1,200)*.01;
x=[zeros(1,94) 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13+D))];
y=a*x+v;
z=xcorr(x,y);
subplot(1,1,1); plot(z); grid
xlabel('Delay'); ylabel('Amplitude');
title('Cross Correlation');

The plot of my calculated cross correlation
Line graph of a cross-correlation output over lags, showing one tall central peak near lag 94 with smaller side lobes on either side of a flat baseline.


From looking at this plot of the cross correlation I would say the delay is at 200. The delay I used in the data was 94 though? Where am I going wrong?

Thanks for any help on this and sorry for the super long post.
 
Attachments
  • Two stacked plots titled x(n) Plot and y(n) Plot, each showing a sequence of values from -1 to 1 against sample index 90 to 115; x(n) is a rectangular-looking bipolar pulse train, and y(n) is a similar pattern shifted later with added noise.
    Lab5_3.jpg
    23.9 KB · Views: 995
  • Plot titled Cross Correlation showing amplitude against delay from 185 to 216. A tall peak reaches about 11.47 at delay 200, with small side peaks near 0.9 on either side and a flat baseline near zero.
    Lab5_4.jpg
    27.1 KB · Views: 1,382
Ive looked over the code again and I have a feeling I am on the right track. Maybe I am just not understanding how the cross correlation in MATLAB works?

Im using the function xcorr

does anyone have experience using this function?
 
Hey Evo8! :smile:

If you look at you graphs of x and y, you can see that there is no delay.
The vector y only has a little noise.

You should define x without the delay zeroes in front, and y with the delay zeroes.

Now, your cross correlation gives you a peak at 200.
Since your vector is 200 entries long, this corresponds to a delay of 0, which is what you have now (it wraps around).
 
Hi ILS!

I did notice that there is no delay. However I don't think defining my x without the delay zeros in front is the correct approach. The x is supposed to be a 200 elements array with the barker sequence given D zeros (94 in my case) in and then enough zeros after to complete the 200 element.

However I am looking at it again now and I think I see a problem with my y definition. In the problem statement it is defined as follows y(n) = ax(n − D) + v(n). I didnt seem to include that -D in my y definition.

I changed my code to the following: (See changes in bold)

clear all
n=0:185;
a=0.8814;
D=94;
v=randn(1,200)*(.01)^2;
x=[zeros(1,94) 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13+D))];
y=a*(x-D)+v;
z=xcorr(x,y);
subplot(1,1,1); plot(z); grid
xlabel('Delay'); ylabel('Amplitude');
title('Cross Correlation');


See the associated plot here:
Line plot titled Cross Correlation with Delay on the x-axis from about 50 to 330 and Amplitude on the y-axis from -450 to 0; the curve sits near 0, drops sharply near delay 94 to a flat plateau near -415 until about 295, then rises back to 0 with spikes near 300.


No you can see that I've placed a data cursor where the plot drops out. This happens to be right at 94 which is my delay. Does this look a little better? Why does it go back up at 300? I also see a very small spike at 200. This is where my array ends I assume?

For reference here are the input vs. output signals
Two stacked line plots titled x(n) Plot and y(n) Plot, each with n from 0 to 200 on the horizontal axis. The x(n) plot is zero except for a short burst of values between about 94 and 108 that swing between -1 and 1. The y(n) plot is near -82.8 except for a burst between about 94 and 108 that dips to roughly -83.7 and reaches about -82.


I feel like I am getting close but the data my not be as clean as it should be?

Thanks for your response
 
Attachments
  • Line plot titled Cross Correlation, Delay on the x-axis from about 50 to 330 and Amplitude on the y-axis from -450 to 0. The curve sits at 0, drops steeply near delay 94 to about -415, stays flat across the middle, then rises back to 0 near delay 300, with noisy spikes at both transitions.
    Lab5_3a.jpg
    29 KB · Views: 2,373
  • Two stacked line plots titled x(n) Plot and y(n) Plot, n from 0 to 200. x(n) is zero except a short burst of +1 and -1 values near n=94 to 107. y(n) sits near -82.8 with a similar burst near n=94 to 107, dipping to about -83.7 and rising to -82.
    Lab5_3b.jpg
    28.2 KB · Views: 2,397
x=[zeros(1,94) 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13+D))];
y=a*(x-D)+v;

I think your y is not quite right yet.
You have subtracted D from the amplitude of x (vertically) and not from the index of x (horizontally), which you can see in your graphs or x and y.

Perhaps you could try something like:
undelayed_x=[1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13))];
y=a*undelayed_x+v;
 
hmmm I am not sure this is quite right either though. First the delay D is not used at all in either x or y. So how could I see a delay of D if its not used? This is what I get for plots if I use this code:

clear all
n=0:185;
a=0.8814;
D=94;
v=randn(1,200)*.01;
x=[1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13))];
y=a*x+v;
z=xcorr(x,y);
subplot(1,1,1); plot(z); grid
xlabel('Delay'); ylabel('Amplitude');
title('Cross Correlation');

Two stacked line plots titled x(n) Plot and y(n) Plot over n from 0 to 200: x(n) is a short burst of ±1 values near n=0 to 14 then zero; y(n) shows a similar burst at 0.9 and -0.9 amplitude, then near-zero noise.


Cross-correlation plot titled Cross Correlation, with Delay on the x-axis from about 90 to 310 and Amplitude on the y-axis from 0 to about 10. A tall narrow spike reaching about 8.5 sits near delay 200, with a smaller cluster of oscillating peaks of about 1 between delays 185 and 212, and near-zero values elsewhere.


Also I am quite confident that my X is correct. My y however I believe is my issue.

See this text taken from the problem statement
Choose D to be the last two digits of your birth year + the day of your birth. If your birthday was August 21, 1989, D = 89 + 21 = 110. Thus, in y(n), there will be D zeros prior to the beginning of the Barker sequence and enough zeros afterwards to increase the length of y(n) to 200.

This one is stumping me. I am not sure how to go about it. The closes I've come is the previous set of plots. But as you said I am affecting the amplitude not the correct delay?
 
Attachments
  • Cross-correlation plot titled Cross Correlation, with Delay on the x-axis from about 90 to 310 and Amplitude on the y-axis from 0 to about 10; a tall narrow spike peaks near 8.5 at delay 200, with a smaller ringing cluster of lower amplitude around delays 185 to 212 and near-zero noise elsewhere.
    test.jpg
    28.8 KB · Views: 2,267
  • Two stacked line plots titled x(n) Plot and y(n) Plot, each with a y-axis from -1 to 1 and an x-axis from 0 to 200; both show brief spikes near n = 0 to 15 and are flat near zero afterward, with y(n) showing small noise.
    test2.jpg
    28.9 KB · Views: 2,363
As you can see in the graph, y is still not shifted in time.

Perhaps you can try with:

x=[zeros(1,D) 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13+D))];
undelayed_x=[1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13))];
y=a*undelayed_x+v;
 
I could try this. However it is not different then what is tried in the above post.So my result will not change.

This is from your previous post:
Perhaps you could try something like:
undelayed_x=[1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13))];
y=a*undelayed_x+v;

This is from my code in the previous post:
x=[1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13))];
y=a*x+v;

And this is from the last post:
x=[zeros(1,D) 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13+D))];
undelayed_x=[1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13))];
y=a*undelayed_x+v;

The y definition has not changed and is still using the "undelayed_x." Did you mean to try plotting the delayed X vs the undleayed x in your post above? This might work however i don't think its what's intended. The received signal is y not x. I am not sure where to go on this one.
 
Reading your problem statement again, I must modify my statement, since the delay is the wrong way around.

It should be:

x=[1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13))];
delayed_x=[zeros(1,D) 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13+D))];
y=a*delayed_x+v;

Either way, your result will change, since your x and y will be shifted in time, as they are supposed to.

You should not do anything else with the "delayed_x".
I only introduced it to construct the proper y, which can also be done in other (and better) ways.
 
Ok now i think i may see where you were going with this. I was a bit confused.

So this is what i have for code: Note this is only the parts of interest right now.


x=[1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13))];
delayed_x=[zeros(1,D) 1 1 1 1 1 -1 -1 1 1 -1 1 -1 1 zeros(1,200-(13+D))];
y=a*delayed_x+v;
z=xcorr(x,y);

The plots below are ordered as follows. Cross correlation on y and x. x and then delayed_x. Where i think i didnt really understand was that the y is using the delayed x, when computing the cross correlation I am using the non delayed x and the y which has the delayed x within. Now I get a time shift.

Three stacked plots: top, cross correlation of y and x vs delay with a single sharp peak near 106 and small ripples around 94 to 118; middle, x sequence of +1/-1 values over samples 0 to 200, nonzero only near the start; bottom, delayed_x sequence nonzero from about sample 94 to 110.


The cross correlation shows a peak at 106. This is somewhat close to my delay of 94? How does this look now? where does this discrepancy come from? The nature of computing cross correlation?

Thanks for the help ILS
 
Attachments
  • Three stacked plots: top, cross correlation of amplitude against delay with a single peak near delay 106; middle, a sequence of +1 and -1 values over indices 0 to 200 that is nonzero only near the start; bottom, a similar sequence nonzero only around indices 95 to 110.
    test3.jpg
    21.5 KB · Views: 2,264
Good! :)

The discrepancy is because the shift is counted as negative (it is y[t-D]).
Since your vector has length 200, it wraps around and 200-94=106.
 
Ah this makes sense!

Thanks so much. I apologize for not understanding where you were going with this. The gears were turning but it took a little bit for them to get up to speed.

Thanks again!