Lab 4. Pseudo-Random Binary Sequences and Data Scramblers#

Aim of the experiment#

In this experiment, you will generate pseudo-random binary sequences using linear feedback shift registers. You will use the generated sequence for a data scrambler and descrambler.

Reading assignment#

Lab 4 instructions#

Linear-feedback shift register for psuedonoise sequence generation#

In this exercise, we will implement a \(m=14\) bit LFSR with \(h_1=h_3=h_4=\cdots=h_{11}=0\) and \(h_2=h_{12}=h_{13}=h_{14}=1.\) This will generate a maximal length PN sequence with period \(N=2^{14}-1=16,383\).

  1. In lab.c, create a variable to act as the ‘shift register’. Since we will be using the right shift >> operation later, use an unsigned datatype such as uint32_t. Initialize it with a nonzero value.

    uint32_t s = 1;
    
  2. In lab.c, create an array to store the generated PN sequence and initialize it to zero. Make the array large enough to store one full period plus an additional 14 (or more) bits to verify that the sequence repeats after the expected period.

    If we use a 32-bit datatype, then the PN sequence would require \(\frac{2^{14} \text{ bits}}{32 \text{ bits per word}}=512\) words. We want to store slightly more elements to check the periodicity, so give the array a length of at least 513.

    uint32_t PN[513] = {0};
    
  3. Implement the LFSR. Since we will not need any I/O functionality for this exercise, you can put all of your code inside the lab_init() function in lab.c.

    1. Since each iteration of the LFSR corresponds to generating a single bit, we need to keep track of (1) our bit position in the current word and (2) the current word in the array. Create two variables corresponding to the current location in our PN array:

      uint32_t i_bit = 0;
      uint32_t i_word = 0;
      
    2. Create a for loop with index variable \(n\) representing the current time. Since we want to generate one period plus several additional samples to verify that the sequence repeats, allow the for loop to stop after \(2^m - 1 + 32 = 16415\) iterations.

      for (uint32_t n = 0; n<16415; n+=1)
      {
          .
          .
          .
      }
      
    3. Inside the for loop, add a statement that saves the most recent value generated by the LFSR in the PN array. Recall that the most recent value will be the \(m=14\)th most significant bit, so the expression (s>>13) & 1 would be one one way to isolate it. The variables you created in (3a) track the bit position and current word; use them to update your PN array with the new value.

      Warning: the following line of C code is dense and contains multiple bitwise operations. Read it carefully and take time to parse its meaning!

      PN[i_word] |= (
                      (s>>13) & 1
                    ) << i_bit;
      
    4. Inside the for loop, update the variables that track the current position. Every 32 bits, you should move to the next word in the array.

      i_bit += 1;
      if (i_bit == 32)
      {
      	i_word += 1;
      	i_bit = 0;
      }
      
    5. Inside the for loop, update the state of the LFSR.

      Warning: the following line of C code is dense and contains multiple bitwise operations. Read it carefully and take time to parse its meaning!

      s = ( s|(
                (1<<14) & (
                            (s<<2)^(s<<12)^(s<<13)^(s<<14)
                          )
              )
          ) >> 1;
      
    6. Put a breakpoint after the for loop and run the code. Examine the ‘PN’ array and confirm that the sequence has a period of \(N=2^{14}-1=16,383\). Include the explanation for the periodicity in the discussion section in your lab report.

Data scrambler / descrambler#

In this exercise, we will use the generated PN sequence to scramble and descramble a binary image.

  1. In lab.c create an array containing the binary ‘tree.png’ image. Please see the instructions on managing data between MATLAB and C. (you can copy and paste the variable declaration from this page.)

  2. In lab.c, call the provided ‘display_image’ function to show the tree image on the display. Put breakpoint after this function so that you have an oppurtinity to see it before the code resumes.

    display_image(tree, 128, 128);
    
  3. In lab.c, call the provided ‘display_image’ function to show the PN sequence on the display. Put breakpoint after this function so that you have an oppurtinity to see it before the code resumes.

    display_image(PN, 129, 128);
    
  4. Scramble each bit of the tree image by taking the XOR with the PN sequence. You may perform the operation in-place by overwriting the existing ‘tree’ array.

    for (i_word = 0; i_word < 512; i_word+=1)
    {
        tree[i_word] ^= PN[i_word];
    }
    

    Call the display_image function again (with a breakpoint) to examine the result.

    display_image(tree, 128, 128);
    
  5. Descramble the image by again taking the XOR, and display the result. It should exactly match the original image.

    for (i_word = 0; i_word < 512; i_word+=1)
    {
        tree[i_word] ^= PN[i_word];
    }
    display_image(tree, 128, 128);
    

Include your scrambler/descrambler code in the lab report

Autocorrelation#

This exercise will help you understand the properties of PN sequences by calculating their auto correlation in MATLAB.

  1. Fill out the MATLAB code which implements the autocorrelation for a periodic signal represented by an array x containing one period.

    \[R_{xx}[n] \text{ for periodic signal} = \frac{1}{N}x[n]\star x[n] = \frac{1}{N}\sum_{k=1}^{N}\overline{x[k]}x[n+k]\]
    function autocorr = R(x,n)
        N = length(x);
        autocorr = 0;
        for k = 1:N
            k1 = k;
            k2 = k + n;
            .
            .
            .
            autocorr = autocorr + x(k1)*x(k2);
        end
        autocorr = autocorr/N;
    end
    
  2. Load the PN sequence generated earlier into MATLAB. You can either export it from the STM IDE, or load the precomputed sequence from a text file.

    pn = readmatrix('pn_16384.txt')'; pn = pn(:);
    pn = fliplr(dec2bin(pn))'; pn = str2num(pn(:));
    pn = pn*2-1; pn(end) = [];
    
  3. Generate an autocorrelation graph for the PN sequence. Make the extent of the autocorrelation plot large enough to show two periods.

    n = -16384:16384;
    func = @(n) R(pn,n);
    figure; stem(n, arrayfun(func,n));
    

Include the autocorrelation plot in your lab report

Lab report contents#

Be sure to include everything listed in this section when you submit your lab report. The goal of the report is to help cement what you learned in memory. For sections I, II, and IV, imagine your audience is a student who is your peer but who has not yet completed the lab.

I. Introduction#

Briefly explain the theory and algorithms behind the programs that you wrote. The slides and reading material might help you in writing this section.

II. Methods#

Describe the steps you took to implement the algorithms in your own words.

III. Results from lab exercise#

Present the results you obtain for each task on the assignment sheet. This section should include illustrative oscilloscope screenshots of the DSP algorithms in action. Also include any code that you wrote or modified. Please do not include all of the boilerplate code from the textbook.

  • Code for data scrambler and descrambler

  • Autocorrelation graph

IV. Discussion#

In this section, discuss the takeaway from each lab. You can mention any intuition that you developed. Also mention any problems that you faced and how you rectified them.