Review Questions for Exam 1

One option is to set up an encoder plus error maker, an error corrector and a divider for a three error correcting BCH code based on a primitive polynomial of degree 7, on a spreadsheet.

If you do that that is all you have to do, and you get a perfect grade if it all works.

You may talk about problems on the exam to anyone, but please, construct all spreadsheets with your own hands.

The second option for the exam, due monday, is to do my choice of 5 of the problems below.

1. Problems 2-3 of Assignment 1. namely

Construct a 4 weighing optimum scheme with the maximum number of coins including one good coin using the procedure described. This can be done on a spreadsheet or on paper. It is easy on a spreadsheet. Build a 4 weighing automatic spreadsheet bad coin finder. It should have a column for each potentially bad coin, indicating its number and when it is to go on the balance.

If you enter a  (0,1,-1) column of length 4, it should tell you which coin is bad and if it is heavy or light.

(I use the if, or and sum functions on the spreadsheet to do this.)

2. Set up a Batcher's algorithm spreadsheet for 64 keys, so that if you input 64 numbers on the left, they come out sorted on the right.

3. Describe and analyze a procedure for finding the median (or any other rank) out of M keys in a linear number of steps by dividing the keys into blocks of size 9 instead of 5. How many comparisons do you need to sort a block of size 9?

What bound can you find of the form cM using this approach?

( how small can you get c to be?)

4. Here is a sequence of frequencies of occurrence of words in a given message.

Construct an optimal Huffman code from this data for these frequencies.

Construct an optimal order preserving code, (Hu-Tucker code) from the same data.

Compute the length of the message using each of these and also the “entropy of information defined by these frequencies. (easy to do on a spreadsheet.)

5. The largest term in the power series expansion of e^N  is N^N/N! so we can deduce that e^N is given by W(N) multiplied by  N^N/N!  where W(N) is the effective number of “largest terms” that contribute to that series.

Given the approximation formula for W(n) of

W(N) = sqrt(8*atan(1)*N) (1+ 1/(12*N) + A/N^2)

Use a spreadsheet to determine A as accurately as you can.

6. Use a spreadsheet to plot (chart x y scatter) p(k/N) vs k for binomial distributions having p=1/2 and p=1/3 for values of N from 5 to however high you can, on one sheet for each p. Here p(k/N) is to meqn the probability that the proportion of occurrences of the event in question is k/N.

7. Derive the formula for a Poisson distribution from the binomial distribution with p=m/N, for finite k as N gets large.

8. Given a class of N students with independently chosen birthdays, deduce the probability that no two have the same birthday. This can be done by deducing a formula for it and taking logs and expanding them to approximate the answer.

Another way to estimate the answer is by assuming you have a Poisson distribution of the number of pairs of students with the same birthday. How do these answers compare?

9. Suppose k persons get on an elevator in the basement of an office building one mornings and they get out each with equal probability of emerging at each floor there being m floors at which they might get out, and suppose they get out independently. Find the expected number of floors at which the elevator does not stop, because nobody gets out.

Evaluate for m=11 and k=10 and vice versa.

10. Express the Second Theorem in your own words and outline a proof of it. (both directions of same.)

11. Find a primitive polynomial of degree 7; find the equations satisfied by the remainders of its third and fifth powers.

Thus construct a three error correcting BCH code.

12. Construct a spreadsheet encoder for the two error correcting BCH code you get.

and construct a spreadsheet that finds the remainder on dividing by your primitive polynomial if the sum of the error monomials, also of the sum of their cubes.

13. Using the information from the previous question construct a spreadsheet that corrects up to two errors automatically. (By testing each monomial remainder to see if it obeys the error locator equation.)

Hint: instead of testing the monomial y to see if it obeys

remainder (y²  +s₁y + s₂)  = 0 instead test

remainder (t₁y² + t₁s₁y + t₁s₂) = 0 (this is slightly easier to form)

14. Construct a divider, that will retrieve the original message from the corrected message by dividing by the encoding polynomial.

15. Outline the steps you would have to perform if you want to correct 3 errors, both in coding and error correcting.