Introduction to Discrete Mathematics, Fall 2000
Problem Set 9, 21-23 November

1. Determine the capacity of the binary symmetric channel BSC($p$), when (a) $p = 0.01$, (b) $p = 0.1$, (c) $p = 0.4$.

2. Show that the Hamming distance $d(x,y)$ between $n$-bit binary strings is a metric in the space $\{0,1\}^n$, i.e. for all $x, y, z \in \{0,1\}^n$ the following hold:
   1. $d(x,y) \geq 0$,
   2. $d(x,y) = 0$ if and only if $x = y$,
   3. $d(x,y) = d(y,x)$,
   4. $d(x,z) \leq d(x,y) + d(y,z)$ (``triangle inequality'').
   (Of course only condition (d) is nontrivial in this case.)

3. List all the codewords of the Hamming code ${\cal H}_4$ (4 data bits, 3 parity bits, single-error correction), when the parity check matrix $H$ is given in standard form. (``Standard form'' = the identity matrix $I_3$ corresponding to the parity bits is located in the rightmost columns of the check matrix $H$.)

4. Prove that a single-error correcting 7-bit code can have at most 16 codewords, and hence the code ${\cal H}_4$ has maximal rate within this class of codes.

5. Design a single-error correcting 5-bit binary code with 4 codewords. Is the rate of this code higher or lower than that of the Hamming code ${\cal H}_4$?

6. Mr. $K$ and Ms. $Y$ are enjoying a pleasant evening in a somewhat noisy restaurant, whose noise level is modeled by the channel BSC(0.1). Mr. $K$ would like to send Ms. $Y$ the 4-bit message ``0101''.
   1. What is the probability that the message is received correctly, if Mr. $K$ doesn't code it in any way?
   2. How does the situation change if Mr. $K$ repeats the message three times, and Ms. $Y$ chooses as the value of each bit that which occurred in the majority of repetitions? (I.e., in this case two times out of three.)
   3. How about if Mr. $K$ codes the message using the Hamming code ${\cal H}_4$? What is the coded form of the message in this case?

7. Decode the bitstring 1001010, which corresponds to a codeword of the natural ${\cal H}_4$ code with a one-bit error. (``Natural'' = the columns of the parity check matrix $H$, when interpreted as binary numbers, are in numerically increasing orded.) What are the contents of the 4 ``message bits'' in the correct 7-bit codeword.

The second Midterm Exam of the course takes place Wed 29 November at 8-11 a.m. The exam covers the material discussed in Problem Sets 6 thru 9 (graphs and coding).