Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit


HW 1 Math 422 Winter 2022

 

Problem 1.  Let n ∈ N be odd.  Consider the code considered in the first lecture where 00 ···0 repeated n times means “no” and 11 ··· 1 repeated n times means “yes”.  Assume the messages are being transmitted in a symmetric coding channel with error probability 0 < p < .5. To decode messages, the person or device receiving messages counts the number of 0s in the received message. If there are more 0s than 1s, the receiver decodes the message as being “no”. Otherwise, the receiver decodes the message as being “yes”.

(a) Given n, give a formula for the probability that a received message is incorrectly

decoded.

(b) Prove that as n approaches infinity, the probability that a received message is incor-

rectly decoded converges to 0. Hint: Use Hoeffding’s inequality and the squeeze the- orem from elementary calculus.  See https://en.wikipedia.org/wiki/Binomial_ distribution, Section 2.5 on Tail Bounds. With this hint, your solution should be short. You’ll need the assumption that p < .5 here.

Problem 2. Let q ∈ N. Prove that

Aq(n,k) ≤ qn −k+1 .

Hint:  Let C be a (n,M,k) code.  Consider the M length n − k + 1 strings given by the first n − k + 1 letters of each codeword. Prove that these M length n − k + 1 strings are all distinct. Then M must be ≤ qn −k+1 .

Problem 3.  Let t ∈ N. Let C  ⊂ F be a code with d(C) = 2t. Prove that C cannot cor- rect t errors in general.  Thus, the bounds from a theorem proved in class are sharp.  Hint to guide you: Show that there exists x ∈ C, y ∈ F not in C such that d(x,y) = t (meaning that there were t errors made in transmitting x and y was received), and z ∈ C not equal to x with d(z,y) = t. Then nearest neighbour decoding doesn’t work. Not required for this problem: you should be able to prove a similar statement that a code C with d(C) = 2t+1 can’t correct t+1 errors in general.

Problem 4. Consider the 3-ary code (defined over Z/3Z)

Determine d(C) (you should list 6 numbers and pick the smallest one).  How many errors can C detect?  How many errors can C correct?  Suppose a codeword is transmitted and the user receives x = 01111212. Using the nearest neighbor decoding principle, can x be decoded? If so, what codeword does x decode to?