Programming Assignment Checklist: LFSR

Frequently Asked Questions

What are the goals of this assignment? To introduce you to object-oriented programming and to reinforce the message of Lecture 1.

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 code like if (c == '0').

In the initial register, fill.charAt(0) is the leftmost bit. But in the Lecture 1 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. However, it is possible to assign each element in your register array the same index that the corresponding 1 or 0 has in the initial String fill argument. Just make sure to adjust your tap position accordingly.

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.

I notice that toString() is not explicitly called in the test client code. What is the explanation?

      LFSR test1 = new LFSR("01101000010", 8);
      StdOut.println(test1);

When a Java object is passed to any of the print methods, a call is made to that object's toString() method if such a method exists.

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 fill and the tap at position 8, but when I try generate()with the 20 bit fill 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 constructor arguments should be used to set the size of the register and the tap position.

I get an ArrayOutOfBounds or NullPointerException error. What could cause this? Do your constructors initialize all of the data members (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 or constructor, thereby hiding the instance variable with the same name?

How do I read in the .png files? Use our Picture.java data type, described in Section 3.1 of the textbook. You will only need the constructors and methods of the Picture API summarized on page 330.

To see it in action, look at the program Grayscale.java which takes the name of a picture file as a command line argument, converts all pixels to gray, and displays all those pixels. If you download Grayscale.java, you will also want to download Luminance.java. Look at Luminance.java to see how to retrieve the r, g, and b values for the Color.

Testing

Be sure to thoroughly test each piece of your code as you write it. We offer some suggestions below.

LFSR. Start with this test client for your constructor and toString() method:
LFSR test1 = new LFSR("01101000010", 8); StdOut.println(test1);
- Add a printing loop to the client to test the step() method.
  LFSR test1 = new LFSR("01101000010", 8); StdOut.println(test1); for (int i = 0; i < 10; i++) { test1.step(); StdOut.println(test1); }
  With this test client, once your implementation is working, you will get this output, which matches the example given in lecture:
```
0 1 1 0 1 0 0 0 0 1 0 
1 1 0 1 0 0 0 0 1 0 1 
1 0 1 0 0 0 0 1 0 1 1  
0 1 0 0 0 0 1 0 1 1 0  
1 0 0 0 0 1 0 1 1 0 0  
0 0 0 0 1 0 1 1 0 0 1  
0 0 0 1 0 1 1 0 0 1 0 
0 0 1 0 1 1 0 0 1 0 0 
0 1 0 1 1 0 0 1 0 0 1 
1 0 1 1 0 0 1 0 0 1 0 
0 1 1 0 0 1 0 0 1 0 0 
```
- To test generate(), note that the numbers in red of the table above are the first 5 return values of step(), when using the sample fill string. So, putting a print statement in each iteration of generate() should yield the 5 values (1, 3, 6, 12, 25). Make sure to only call generate() once when testing for this intermediate result, and not in a loop as illustrated below. Remember to remove the print statement from the generate() method when you have finished testing this section.
- Once you have one call of generate() working, test generate() by using the code
  LFSR test2 = new LFSR("01101000010", 8); for (int i = 0; i < 10; i++) StdOut.print(test2.generate(8) + " "); StdOut.println();
  as your test client, which should result in the following sequence:
```
201 61 185 107 152 191 72 77 47 50
```
- Now let's test generate() with a 20-bit fill and a tap of 16. Use the code
  LFSR test3 = new LFSR("01101000010100010000", 16); for (int i = 0; i < 10; i++) StdOut.print(test3.generate(8) + " "); StdOut.println();
  as your test client, which should result in the following sequence:
```
42 217 23 193 26 156 156 231 135 189
```
PhotoMagic. To test PhotoMagic.java use
```
    java PhotoMagic pipe.png 01101000010100010000 16
```
and compare with the pictures on the assignment page.
```
    java PhotoMagic Xpipe.png 01101000010100010000 16
```
should retrieve the original picture.

Submission

Your programs must be named LFSR.java and PhotoMagic.java. Use the following readme file template. Don't forget to hit the "Run Script" button on the submission system to test that it compiles cleanly.

Possible Progress Steps

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

Download the directory lfsr to your system.
Reread the slides for Lecture 1 (to reacquaint yourself with the basic ideas behind LFSRs), the lecture slides for "Using Data Types" and "Creating Data Types", and pages 316-335 and 370-377 in the text (to learn the basics of object-oriented programming).
The design of your program should look like the template LFSR.java, except that you will need to fill in all of the constructors and methods.

We recommend defining the instance variables as follows:

public class LFSR {
    private int N;         // number of fill bits provided
    private int[] reg;     // array of integers representing the register bits
    private int tap;       // index of the tap bit
}

Make the constructor. Your constructor for LFSR will initialize all the instance variables. Use new to allocate memory for the int[] array. Observe that you must do this in the constructor (and not when you declare the instance variables) since otherwise you wouldn't know how big to make the array.
Write the toString() method.
As you fill in the methods for LFSR, use the test clients described in the test section above.
Write the step() method. Test.
Write the generate() method. Test.
PhotoMagic. Your PhotoMagic class is a client of the Picture, Color, and LFSR classes. By placing the line
```
 import java.awt.Color;
```
above the line where you declare public class PhotoMagic, the compiler will know that you are going to use the Color class. Place Picture.java and LFSR.java in the same directory with PhotoMagic.java, so the compiler will be able to find both of them.

Enrichment
- Read more about Linear Feedback Shift Registers.
COS 126 Home Page