Checklist: Linear Feedback Shift Register

Frequently Asked Questions

What preparations do I need to do before beginning this assignment? Review the Lecture 16 slides to reacquaint yourself with the basic ideas behind LFSRs.

Do I need to follow the prescribed API? Yes, we will be testing the methods in the API directly. If your method has a different signature or does not behave as specified, you will lose a substantial number of points.

How should I represent the LFSR? There are several possible approaches. We recommend that you use an int[] array of size N, each entry of which is either 0 or 1. If you follow this approach, the init method amounts to creating the array and converting the char values in the string to int values for the array. Alternatively, you could use a char array, each entry of which is either '0' or '1'.

In the seed argument to init(), seed.charAt(0) is the leftmost bit. But in the Lecture 16 slides and the assignment page, bit 0 is the rightmost bit. Do I have to arrange the bits in my register array that way? Strings are always indexed from left to right (the way we read English). Traditionally, binary digits are indexed from right to left, with bit 0 as the lowest order or rightmost bit. You are welcome to use either approach in your internal representation—just be careful to do it correctly and consistently, and ensure that the effect is as specified in the assignment.

How do I convert the char values in the string to int values for the array? The number zero is represented by the char value '0'. The char data type is a Java primitive type, so you can compare two of them with if (c == '0'). You can also perform arithmetic on chars, so c - '0' means "subtract the number that encodes the character '0' from the number that encodes the character c. If c is the character '0' or '1', c - '0' will therefore give you the number 0 or 1.

My step() method is producing 19 for the binary number 11001. What am I doing wrong? You are calculating the bits in reverse order. 19 is the decimal value of the binary number 10011.

My generate() works with the 11 bit seed and the tap at position 8, but when I try generate()with the 20 bit seed and the tap at position 16, I get a different answer from the one shown in the example. What am I doing wrong? Make sure you are not hardwiring 11 or 8 in your LFSR code. The LFSR.init() arguments should set the size of the register and the tap position.

I get an ArrayOutOfBounds or NullPointerException error. What could cause this? Do you initialize all of the instance variables (e.g., N, reg, and tap)? Did you allocate memory for your array with new? Did you inadvertently redeclare int N or int[] reg in a method, thereby hiding the instance variable with the same name?

How do I do exclusive or (XOR) in Java? Use the ^ Java symbol. The operation a ^ b, where a and b are int values, does a bit-by-bit exclusive or of the values.

Why are we using the .png format isntead of .jpg? It is a lossless format that preserves the precise bits in the colors. Even at the highest quality settings, JPEG compression changes the image data in ways that are designed to be (nearly) imperceptible to the human eye. But any change in the encrypted version of the image will greatly affect the decrypted version.

Sometimes my encrypted picture looks like a shadowy version of the original. How do I pick a good tap number? Here are suggested tap numbers for maximizing the cycle of different size linear feedback shift registers: 5-bit (tap 2), 6-bit (tap 4), 9-bit (tap 4), 10-bit (tap 6), 11-bits (tap 8), 20-bit (tap 16), 30-bit (tap 22), 36-bit (tap 24), 48-bit (tap 42), 60 bits (tap 58), 100 bits (tap 62), and 150 bits (tap 96).

Testing

Be sure to thoroughly test each piece of your code as you write it. We offer some suggestions in the assignment specification. You should also test your data type with other parameters.

• Use the following code to test generate() with a 20-bit seed and a tap of 16.

  LFSR.init("01101000010100010000", 16);
  for (int i = 0; i < 10; i++) {
      int r = LFSR.generate(8);
      StdOut.println(LFSR.string() + " " + r);
  }
  

  It should output:

  01010001000000101010 42
  00000010101011011001 217
  10101101100100010111 23
  10010001011111000001 193
  01111100000100011010 26
  00010001101010011100 156
  10101001110010011100 156
  11001001110011100111 231
  11001110011110000111 135
  01111000011110111101 189
  

• PhotoMagic. Here are a few sample executions of PhotoMagic.java along with the desired output.

  % java PhotoMagic pipe.png 01101000010100010000 16
  [ compare against the picture on the assignment ]
  
  % java PhotoMagic Xpipe.png 01101000010100010000 16
  [ Magritte's painting of a pipe ]
  

  Here are three more encrypted images. The filename of each gives the seed and tap position:

• Challenge for the bored. This image was encrypted using a seed of at most 16 bits. Can you decrypt it? If you're still bored, try and figure out what it's a picture of.

  

• PhotoMagicDeluxe. Here is a sample execution of PhotoMagicDeluxe.java along with the desired output.

  % java PhotoMagicDeluxe Xjava.png OPENSESAME 58
  [ Java logo ]
  

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

• Download ImageData.java, Picture.java, pipe.png (Magritte's pipe), and Xpipe.png (Magritte's encrypted pipe) to your system, and put them in the same folder where you create LFSR and PhotoMagic.

• Reread the slides for Lecture 16 (to reacquaint yourself with the basic ideas behind LFSRs).

• We recommend defining the instance variables as follows:

  public class LFSR {
      // seedArray[i] = ith least significant (rightmost) bit of the LFSR
      private static char[] seedArray = { '0' };
      private static int    tapPosition; // index of the tap bit
  }
  

• Write the init function. LFSR.init() will initialize all the class variables to the specified state. Use new to create an array array. Don't assign it to the seedArray class variable until you've verified that the specified seed and tap parameters are actually valid.

• Write the string() method.

  As you fill in the methods for LFSR, use the test code described in the assignment.

• Write the step() method. Test.

• Write the generate() method. Test.

• PhotoMagic. Your PhotoMagic class is a client of the ImageDataand LFSR classes. Place ImageData.java, LFSR.java, and Picture.java (ImageData is a client of Picture) files in the same directory with PhotoMagic.java, so the compiler will be able to find all of them.

• Check back here during the course of the assignment for more test images. We also recommend sharing images with classmates &emdash; you should be able to decrypt images that other students have encrypted. This is an excellent way to help each other debug.

Enrichment

• Read more about Linear Feedback Shift Registers.