AA: Autocorrelation and Autocovariance

Assignment Summary

If your last (family) name begins with A-N, please complete the "Appl. Assignment 5 Quiz" on WebCT PRIOR TO STARTING work on this assignment. If your last (family) name begins with O-Z, please complete the "Appl. Assignment 5 Quiz" on WebCT after finishing work on this assignment. The quiz is found in the "Assessments" tab of the WebCT page.

Last Name Begins With When To Take the Quiz
A-N BEFORE STARTING the assignment
O-Z After completing the assignment

In Application Assignment 4, we studied how to decorrelate the stream of measured RSS values (the fading signal) at a node. However, we never quantified the temporal correlation or covariance of the fading signal. In this assignment, you will perform this quantification.

There are two parts to this assignment:

  1. Compute and plot the autocorrelation and autocovariance functions for the temporal fading signal. Turn in: A plot of either the autocorrelation or autocovariance function.
  2. Determine the highest sampling rate if the correlation coefficient must be below a given threshold. Turn in: Your threshold value of the correlation coefficient, and how often you find that samples may be used in secret generation if the correlation coefficient must be lower than than your threshold.
    1. You will need Matlab, a text file from an RSS measurement experiment, and some way to produce a document (eg., Word, OpenOffice). Create one PDF containing the outputs of your assignment, and the Matlab code you used to generate them. Turn it into the WebCT assignment drop box, by midnight on the due date.


      We've shown that temporal correlation can be avoided by using a decorrelation transformation. This assignment provides another way to get rid of (at least, approximately) the temporal correlation, before it enters our secret key.

      High covariance between bits in our secret key would be a bad thing. Then, if we guessed one value, it would help us better guess several future values. But subsequent RSS numbers have a high covariance, so if we just used every RSS measurement to come up with the bits for the secret (as we did in Application assignment 1), we'd have a key with high covariance between subsequent bits.

      This assignment has you take the following, intuitively pleasing approach: Just don't use every RSS sample! Encode one RSS measurement into a bit, then skip several RSS measurements; encode another RSS measurement into a bit, then skip several measurements again; etc., until we have enough bits. If you skip several samples, the measurements that you do encode will have a lower covariance.

      But how many should you skip? What we've been studying in class is autocovariance, which tells us the covariance between one sample of a random process and another sample at a certain delay, as a function of that delay. What we're going to do is to assume the process is wide-sense-stationary (WSS) and then estimate the autocovariance from the samples. Then, looking at the autocovariance as a function of delay, you can tell how big of a delay you need in order to get two RSS measurements with a low covariance. "Delay" and "number of samples to skip" have the same meaning here. In sum, the autocovariance is used as a tool to determine how to pick a "delay" to achieve some particular (low) covariance between the RSS measurements used to encode subsequent bits in the secret key.

      Assignment Description

      Load the data as you did in Application Assignment 2. This involves loading, separating, and interpolating the data so that you have data vectors "interpa" and "interpb" in memory. Also, correct for the mean in each vector as you did previously.

      1. Compute the autocorrelation and autocovariance functions

      The autocovariance function is the covariance between two samples of a wide-sense stationary (WSS) random process $\{X_{n}\}_{n}$ as a function the time delay between two samples. For a time delay $i$, we write the autocovariance function $C_X[i]$ as
      $$ C_X[i] = \mbox{Cov} ( X_{n}, X_{n+i}) $$
      in other words,
      $$ C_X[i] = \mbox{E}[ ( X_{n} - \mu_X)(X_{n+i} -\mu_X )] $$
      where $\mu_X$ is the mean of $X_{n}$.

      The autocorrelation function simply does not correct for the mean. It is the expected value of the product of two samples of the random process, one delayed by $i$ compared to the other.
      $$ R_X[i] = \mbox{E}[ X_{n} X_{n+i}] $$

      Computationally, finding the autocorrelation function from data is like convolution. However, an autocorrelation function is an expected value. Experimentally, to find $C_X[i]$ we will take the mean of what is inside of the expected value for all possible values $n$. First, find the mean:

      meanVal = mean(interpa);

      Then, if the delay I'm interested in is delay, then my Matlab code is

      values = len - delay;
      i = delay + 1;
      autocovariance(i) = sum((interpa(1:values)-meanVal) .* (interpa((1+delay):len)-meanVal))/values;
      autocorr(i) = sum(interpa(1:values) .* interpa((1+delay):len))/values;

      Note that I had to do i=delay+1 because Matlab will not accept an index of zero, but computing the autocorrelation for $i=0$ is very important. Also, notice that as delay increases, there are fewer values to use to estimate the functions. We need to divide by values in both computations in order to account for this fact.

      The Matlab code above uses interpa; you could have just as well studied interpb.

      Calculate the autocorrelation and autocovariance functions for delay=0 to 2000 (in a for loop, for example), and plot one of the results. Since we had previously made interpa and interpb zero-mean, the autocorrelation should be identical to the autocovariance.

      2. Design the sampling rate.

      Let's assume that we are not going to use a decorrelation transform like we did in Application Assignment 4. Instead, we will simply take every $k$th sample (call them the secret key samples) and encode each to one bit (zero or one) using the censoring scheme we studied in Application Assignment 2.

      How often should we sample? There is a tradeoff (represented by the autocovariance function) between $k$ and the correlation coefficient between subsequent secret key samples. To design your system, pick a "low" value of correlation coefficient (say, 0.1, or 0.05) as a threshold. Based on your autocovariance function, you can find the correlation coefficient as a function of delay (How do you do this?). Next, determine what value of delay $k$ ensures that subsequent secret key samples will have correlation coefficient less than your threshold. Turn in your threshold and your secret key sampling rate, that is, $1/k$.


      Submit your results as described above.

      If your last (family) name begins with O-Z, please complete the "Appl. Assignment 5 Quiz" on WebCT now.