18.310 Exam #1

October 13, 2006

1. Given N coins of which all have the same weight and at most one which has a different weight. You want to locate the different weight coin or declare that all the coins are the same weight, using a balance at most k times. How large can N be for you to succeed in doing so, if you have a additional coin that you know to be good? If not? Describe the rules the weighing matrix must follow. Please indicate your reasoning in obtaining your answers.

1. State Shannon’s Second (noisy channel) Theorem, and give a brief outline of its proof, in both directions.

1. Which of the following polynomials are primitive?

1 + x2 + x7 + x9

1 + x2 + x6

1 + x3 + x6

1 + x + x7

1 + x + x5

1. A. If you use (1 + x + x6) as your primitive polynomial p(x) to define remainders, what condition must the additional factor q(x) obey so that p(x)q(x) will be a two error correcting BCH code?

B. Find q(x) here.

5. A. Suppose an experiment is repeated n times independently and an event E occurswith probability p each time. What is the probability that E occurs exactly k times?

B. Apply Stirling's formula to the exact expression under the assumption that pn and n(1-p) are large. What do you get?