REMINDER: Ms. Newman should be coming to PHS after school
- Simulate one step. The step() method simulates one step of the LFSR and returns the rightmost bit as an integer (0 or 1). For example,
// LFSR lfsr1 = new LFSR("01101000010", 9); // for this assignment the seed and tap can be hardcoded or input String lfsr1 = "01101000010"; int tap = 9; StdOut.println(lfsr1); for (int i = 0; i < 10; i++) { // int bit = lfsr1.step(); // code to create a sequence of 0s and 1s like the example below StdOut.println(lfsr1 + " " + bit); }
outputs
01101000010
11010000101 1
10100001011 1
01000010110 0
10000101100 0
00001011001 1
00010110010 0
00101100100 0
01011001001 1
10110010010 0
01100100100 0
- Extracting multiple bits. The method generate() takes a positive integer k as an argument and returns a k-bit integer obtained by simulating k steps of the LFSR. This task is easy to accomplish with a little arithmetic:
- initialize a variable to zero
- for each bit extracted, double the variable
- add the bit returned by step()
For example, extracting (from left to right) each bit from the sequence 1 1 0 0 1, the variable takes on the values 1, 3, 6, 12, and 25, ending with the binary representation of the bit sequence.
gen = 0
gen = gen * 2 + new_bit = 0 * 2 + 1 = 1
gen = gen * 2 + new_bit = 1 * 2 + 1 = 3
gen = gen * 2 + new_bit = 3 * 2 + 0 = 6
gen = gen * 2 + new_bit = 6 * 2 + 0 = 12
gen = gen * 2 + new_bit = 12 * 2 + 1 = 25
For example,
// LFSR lfsr2 = new LFSR("01101000010", 9); // for this assignment the seed and tap can be hardcoded or input String lfsr2 = "01101000010"; int tap = 9; StdOut.println(lfsr2); for (int i = 0; i < 10; i++) { // int r = lfsr2.generate(5); // code to generate a number like 25 in the example above StdOut.println(lfsr2 + " " + r); }
outputs
01101000010
00001011001 25
01100100100 4
10010011110 30
01111011011 27
01101110010 18
11001011010 26
01101011100 28
01110011000 24
01100010111 23
01011111101 29
Classwork:
Write a java program, YI_LFSRSim.java to generate an output like the one right above for a given seed.
NOTE: It doesn’t have to be OOP.