18.310
First Exam due Wednesday October 16, 2002
1.
Outline a proof of Shannon's Second Theorem, on the proportion of check bits
necessary and sufficient to be able to correct a proportion p of errors, (for
p<1/2.)
2.How
many errors must you correct in a BCH code with 255 bits given a probability of
10-4 of error per bit, to reduce the probability of
an error per message getting by to 10-15, while having the
probability of having to resend because you cannot correct the error to at most
10-12 per message? Use the fact that when you make more errors than
you correct, most of the time you will have to resend. Sometimes though you
will be fooled. (estimate how much of the time this will happen ; use the fact
that the number of words per code word is 2degree coding polynomial.
and the number of decodable words per codeword is like C(N,number of errors
code can correct).
3.Given
the following list of message frequencies in order, compute optimal Hu Tucker
and Huffman codes, and compute the
average message length in each of them.
Compute the entropy of information H(p1,p2,…)
given this list.
5 4 4 6 20 8 5 6 10 40 4 3 3
4
4.
Outline in pseudo-code or in computer code in an appropriate language two of
the first few of our sorting algorithms other than Batchers. (It is not
appropriate to use the command "sort") Or, Construct a Batcher
spreadsheet sorter for 32 keys.
5.
Suppose you take the equation for two errors: rem s2 + s1y +y2 =0 at xe1 and xe2,
and divide these equations by y before evaluating them at xe1 and xe2,
then sum them.
What
do you get? This suggests that you can get a two error correcting code by
taking the product of a primitive polynomial and its reverse, and getting s2
= t1/t-1. Will this work?. Verify by trying on a degree 4
primitive polynomial. Note: to make it work you have to handle fixing 1 error
differently. How? (t-1 is the dot product of the
received message with the ordinary remainder table upside down)
(you can turn a table upside down by copying it into new rows (values only), and sorting those rows by the power, largest first, but remember to put the 0 power back on top; you can then copy back next to your original table.)