COS 126: Assignments (Fall 2019) - Linear-Feedback Shift Register COS126 Syllabus Meetings Lectures Precepts Assignments Exams Help! Linear-Feedback Shift Register Checklist Files Submit Introduction What are the goals of this assignment? To introduce you to object-oriented programming and to re-reinforce the message of Lecture 0. Where can I review the concepts involved? Review Lecture 0 to reacquaint yourself with the basic ideas behind LFSRs. Read Sections 3.1 and 3.2 of the textbook to learn the basics of object-oriented programming and how to use Color and Picture data types. LFSR.java Does the API that I define for LFSR need to be exactly the same as the one prescribed? 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. Producing undocumented side effects (such as printing to standard output in any of the constructor or instance methods) is also an API violation. You may not add public methods to the API; however, you may add private methods (which are accessible only in the class in which they are declared). How should I represent the LFSR? There are several possible approaches. For example, you can use an int[] array of length n + 1, each entry of which is either 0 or 1, with entry i corresponding to bit i for each i from 1 to n. If you follow this approach, the constructor amounts to creating the array and converting the char values in the string to int values for the array (and initializing your other instance variables). However, you are allowed to use any efficient representation that you like. How do I create an instance variable that is an array if I don't know its length at compile time? Declare it as an instance variable, but initialize it in constructor (where you will know its length). For example, see Program 3.2.3 in the textbook. What extra comments should I include when writing object-oriented programs? You must comment the purpose of every method, using the names of the argument variables in your description. Additionally, you must comment the purpose of each instance variable. In the initial register, seed.charAt(0) is the leftmost bit. However, in both Lecture 0D and the assignment specification, bit 1 is the rightmost bit. Do I have to arrange the bits in my register array that way? Traditionally, strings are indexed from left to right, while binary numbers are indexed from right to left. You are welcome to use either approach here—just be careful to do it correctly and consistently. How do I convert the char values in the String argument to int values for the array? The characters zero and one are represented by the char literals '0' and '1'. The char data type is a Java primitive type, so you can compare two of them with if (c == '0'). Why am I getting 48s and 49s when I print out values for debugging? Internally, characters are represented as integers. The code for '0' is 48, and the code for '1' is 49. (Read about ASCII or Unicode for more information.) When you perform arithmetic operations on values of type char, they are promoted to type int. So, the expressions '0' + 1 and '1' ^ '1' ^ '1' both evaluate to the value 49 of type int. We recommend converting from the characters '0' and '1' to the integers 0 and 1, so that you don't have to deal with such type conversion anomalies. In toString(), I loop the right number of times, but the returned String looks too short. What can cause this? This can be the reverse of the problem above. If you take the integer 0 or 1 and cast it to a char, it is a special control character that may appear blank when printed. My generate() 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 9, but when I try generate()with the 20-bit seed and the tap at position 17, I get a different answer from the one shown in the example. What am I doing wrong? Make sure you are not hardwiring 9 or 11 in your code. The LFSR constructor arguments must set the size of the register and the tap position. The toString() is not explicitly called in the test client code, but it still gets called. How does this work?
LFSR lfsr = new LFSR("01101000010", 9);
StdOut.println(lfsr);
Every object in Java has a toString() method, which is automatically called by StdOut.println(). I get an ArrayOutOfBounds or NullPointerException error. What could cause this? Do your constructors initialize all of the instance variables (e.g., n, reg, and tapPosition)? Did you allocate memory for your array with new? Did you inadvertently re-declare int n or int[] reg in a method or constructor, thereby hiding the instance variable with the same name? How do I perform the exclusive or (xor) operation in Java? Use the ^ operator. If a and b are of type int, the expression a ^ b evaluates to an int whose value is the bit-by-bit exclusive or of the two operands. If a and b are of type boolean, the expression a ^ b evaluates to a boolean whose value is the exclusive or of the two operands. PhotoMagic.java Does the API that I define for PhotoMagic need to be exactly the same as the one prescribed? 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. Producing undocumented side effects (such as printing to standard output or mutating the Picture argument to transform()) is also an API violation. You may not add public methods to the API; however, you may add private methods (which are accessible only in the class in which they are declared). Why must I create a new Picture object in transform(), instead of mutating the one passed in as argument? The API does not specify this is an allowable side effect, so it is not permitted. In practice, a client might be very annoyed if an object they passed to a method was mutated with proper documentation. Why are we using the PNG format instead of JPEG? PNG is a lossless format that preserves the precise bits in the colors. How do I read and process PNG files? Use the Color and Picture data types described in Section 3.1 of the textbook. Review Program 3.1.3 (Luminance.java) for using the Color data type; review either Program 3.1.4 (Grayscale.java) or ColorSeparation.java for using the Picture data type. 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 3), 6-bit (tap 5), 9-bit (tap 5), 10-bit (tap 7), 11-bit (tap 9), 20-bit (tap 17), 30-bit (tap 23), 36-bit (tap 25), 48-bit (tap 43), 60 bit (tap 59), 100 bit (tap 63), and 150 bit (tap 97). How can I save an Picture that is displayed in a window? Select File -> Save -> filename.png from the menu in the window where the image is displayed, where filename is whatever name you want to give the image. What is a java.awt.HeadlessException and how did I cause it? The assignment specifies that you should call show() only once, in PhotoMagic.main(). Calling it in other places can give this error. Using Color The Color data type is built into Java in the "Abstract Window Toolkit" package. To access it, type the following at the top of your program:
import java.awt.Color;
Now, you can create Color variables and objects:
// constructor arguments are red, green, and blue components
Color princetonOrange = new Color(245, 128, 37);
This abbreviated API documents all of the methods that you will need for this assignment. Using Picture The Picture data type was created for this course. If you used the autoinstaller, the Picture data type should already be available in Java (and you will not need to use an import statement). To check if it is available, type the following command into the terminal: > java-introcs Picture https://introcs.cs.princeton.edu/java/31datatype/baboon.png If it's working (and you have an Internet connection), you will see an image of a baboon displayed in a window and the text output 298-by-298 at the command line. If Picture does not seem to be installed correctly, one solution is to copy Picture.java to the same directory as your other files for this assignment. You can create Picture variables and objects as follows:
// create a picture from a URL (Internet connection required)
Picture picture1 = new Picture("http://introcs.cs.princeton.edu/java/31datatype/baboon.png");
// create a picture from a file (baboon.png must be in working directory)
Picture picture2 = new Picture("baboon.png");
// display pictures in separate windows
picture1.show();
picture2.show();
This abbreviated API documents all of the methods that you will need for this assignment. 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. LFSR. Use the following code to test generate() with a 20-bit seed and a tap of 17.
LFSR lfsr20 = new LFSR("01101000010100010000", 17);
StdOut.println(lfsr20);
for (int i = 0; i < 10; i++) {
int r = lfsr20.generate(8);
StdOut.println(lfsr20 + " " + r);
}
It outputs:
01101000010100010000
01010001000000101010 42
00000010101011011001 217
10101101100100010111 23
10010001011111000001 193
01111100000100011010 26
00010001101010011100 156
10101001110010011100 156
11001001110011100111 231
11001110011110000111 135
01111000011110111101 189
PhotoMagic. Here are the (red, green, blue) values of the first 4 pixels, both before and after encoding. Add debugging statements in your code to check that you are getting the same values:
> java-introcs PhotoMagic pipe.png 01101000010100010000 17
Before: 135 98 80
After: 173 187 71
Before: 141 104 86
After: 76 114 202
Before: 146 109 91
After: 14 138 220
Before: 146 109 91
After: 47 214 254
PhotoMagic. Here are a few sample executions of PhotoMagic.java along with the desired output.
> java-introcs PhotoMagic pipe.png 01101000010100010000 17
> java-introcs PhotoMagic Xpipe.png 01101000010100010000 17
> java-introcs PhotoMagic Xpipe-gray.png 10010111101011101111 17
> java-introcs PhotoMagic Xbaboon-gray.png 01101000010100010000 17
> java-introcs PhotoMagic Xbaboon-red.png 01101000010100010000 17
> java-introcs PhotoMagic Xbaboon-green.png 01101000010100010000 17
> java-introcs PhotoMagic Xbaboon-blue.png 01101000010100010000 17
> java-introcs PhotoMagic Xshield.png 010101010101010101010101010101 23
> java-introcs PhotoMagic Xscarpet-cookies.png 01101000010100010000 17
[ picture of something delicious ]
> java-introcs PhotoMagic Xjava.png 001110001111000100001101010010000100010010000000001100000100 59
[ picture of something you could drink with cookies ]
Possible Progress Steps These are purely suggestions for how you might make progress. You do not have to follow these steps. Do the reading specified at the top of this page. Download the profile files, which includes the template LFSR.java. You will need to specify the instance variables and complete the constructor and methods. One reasonable way to represent the LFSR is to use an int[] array and the following instance variables:
private int n; // number of bits in the LFSR
private int[] reg; // reg[i] = ith bit of LFSR, reg[1] is rightmost bit
private int tapPosition; // tap position
Implement 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. Test the constructor. In the LFSR main method, instantiate several different LFSR objects, varying the values for the seed and tap position. Implement the length() method. Test the length method. In the LFSR main method, invoke the length method on the LFSR objects (from step 4) and print the resulting value. Are your results correct? Implement the bitAt() method. Test the bitAt method. In the LFSR main method, invoke the bitAt method using different values for the argument i on the LFSR objects (from step 4) and print the resulting value. Are your results correct? Is the value of your tap correct? Implement the toString() method. Test the toString method. In the LFSR main method, invoke StdOut.println on the LFSR objects you instantiated (from step 4). Are your results correct? Implement the step() method. Test the step method. In the LFSR main method, invoke the step method on the the LFSR objects you instantiated (from step 4). Are your results correct? You should also use the test code provided in the assignment. Implement the generate() method. Test the generate method. Use the test code provided in the assignment. PhotoMagic. Your PhotoMagic class is a client of the Picture, Color, and LFSR classes. Place LFSR.java in the same directory as PhotoMagic.java, so the compiler will be able to find both of them. See also the sections on using the Color and Picture data types. Optional: Enrichment Read more about linear-feedback shift registers.
