Comp [34]49 Program 2        Dordal        Oct 2, 2008
Due: Oct 9, 2008

Consider Table 8.5, p 214, rows 3 and 4.
n      k     t     P(X)
1572X8 + X7 + X6 + X4 + 1
1553 X10 + X8 + X5 + X4 + X2 + X + 1

We build the (n,k) block code using the indicated generator polynomial. Error patterns E are sequences of n bits with the number of 1-bits greater than zero and less than or equal to t (the locations of the 1-bits represents the errors).
For row 3, t=2, there are 15*14/2 = 105 possible length-15 E with two 1-bits, in addition to 15 E's with a single 1-bit. For row 4, t=3, there are 15*14*13/3*2 = 455 possible E with three 1-bits, in addition to the 105 + 15 E's for row 3.

You are to calculate E mod P = S for all possible E; remember that E mod P is calculated using polynomial division (the div java program, or an alternative). You then need to save the table of <E,S> pairs, and sort it by S, so that from S we can find E. As part of sorting, you will also establish that no two S's are the same.

To do the sorting, you can either use the unix sort and uniq utilities, or load into a spreadsheet and use the sorting facilities there. If you take the latter approach, you may need to do something to make sure that the data is imported as strings, preserving leading 0's.

There is a sample method for generating all E with three 1-bits in tester.java.

Note that you will need to make sure that ZPAD is set to true in bitstring.java, so remainders have their initial zero bits.

Added October 30: for those who are still working on this, here are the complete tables of all error patterns E (all 15-bit strings with, for row 3, up to two 1-bits, or for row 4, up to three 1-bits):
E values for row 3
E values for row 4

The files are in text format, with one entry per line. Using a typical unix shell, you can calculate the syndrome S for each of these and create the file of all pairs with 

    for i in $(cat file)
    do
        java foo $i
    done
where the output of "foo 10000000" is the argument 10000000 followed by the computed syndrom (eg 01101), with the two separated by a space. This is perhaps the easiest way to get a file with both the original E and the corresponding syndrome S(E) together on the same line. The file can then be sorted with the unix sort utility, or by loading into a spreadsheet.

Added December 3: I've added a method readstrings(String filename) in tester.java; given the filename "E_row3.text", it returns an ArrayList of all 120 bitstrings in that file. This should make it easier to read in the file in java, and then generate the remainders by looping through that ArrayList, and printing out the original bitstrings and remainders.