CS 70 SPRING 2008 — DISCUSSION #7 ON EARTHLUQMAN HODGKINSON, AARON KLEINMAN, MIN XU1. Error-Correcting Code (Earth Version)Exercise 1. Your are on Earth. Your mission in this exercise is to successfully transmit an outgoingmessage to the Moon with corruption, and to repair and reconstruct an incoming message that has beencorrupted. As the Berlekamp-Welsh method is complex, we will just encode our message in (mod 5) andour message will only be two digits long. Also, assume that the channel will only corrupt 1 digit in ourmessage. In another words, let N = 2 and k = 1. How long should our transmission be?First, find a student in class who is on the Moon and pair up. You must transmit the message[c0= 1, c1= 3] to your partner. Find a polynomial of degree at most 1 P (x) such that P (0) = c0, P (1) = c1,then construct the full message you would send. Now, corrupt one of the numbers in your message, you maychoose which ever, but I recommend sending setting the second packet c1to 1 to save your partner somecomputation time.Now, receive the corrupted message from your partner and perform the Berlekamp-Welsh method toreconstruct the original message. DON’T TELL YOUR PARTNER WHAT YOU RECONSTRUCTEDYET! Move on to the next exercise after you have the message.2. FingerprintingExercise 2. Take what you think is the message that your partner on the Moon has sent you and calculateits fingerprint. In our fingerprinting scheme, we will enco de our message into a polynomial of degree 1(mod 23) by the following method: if you received the message [m0, m1], then construct the polynomialT (x) = 3m2x + 2m1+ 9 (mod 23). Now, agree with your partner upon a random r between 0 and 22 andevaluate the fingerprint T (r). Give the fingerprint to your partner, did it work?If your partner handed you a fingerprint, calculate the finger print of the correct message using the abovescheme and compare the two. If they are not the same, (politely) scold your partner and ask him/her tore-try. If they are the same, with what probability are you certain that your partner has deciphered themessage correctly?3. Erasure codesExercise 3. Min sends you a message in the alphabet R = 0, F = 1, A = 2, U = 3, and N = 4 using thepolynomial scheme discussed in class. The message size is 3. You receive the following packets.• clearly corrupted• U• N• NAssuming the three decipherable packets arrive uncorrupted, what is the value in the corrupted packet?4. More FingerprintingExercise 4. We sent the message 00001 to the Moon, but the Moon received 01010. We use the polynomialfingerprinting scheme discussed in class with P (x) = sn−1xn−1+. . .+s1x+s0(where s0is the least significantbit of the message) to verify that the data was received correctly. Our prime q = 101. Is r = 25 a lucky orunlucky value?Date: March 12, 2008.The authors gratefully acknowledge the TA’s of CS70 Past for the use of their previous notes: Chris Crutchfield, AlexFabrikant, David Garmire, Assane Gueye, Amir Kamil, Lorenzo Orecchia, Vahab Pournaghshband, Ben Rubinstein. Theirnotes form the basis for this handout.15. A Few Bits of Big-OExercise 5. Fill in the following chart:You may assume that x, y are already reduced mod p when considering operation performed (mod p).operationnumber of bit-ops in big-O runtime when performed mod px + yxyx/yx mod y n/axnSuppose we are given a polynomial P (x) = anxn+ an−1xn−1+ ...a0where an, an−1, ...a0are all naturalnumbers between 0 and q − 1. Let r be a natural number between 0 and q − 1, we wish to evaluate P (r)mod q.Exercise 6. Suppose we use the following pseudo-code for our program, how many bit operations will weperform? Express your answers in big-O notation.funct poly-eval:val_so_far = a_0for i from 1 to n:val_so_far = val_so_far + a_i * r^ireturn val_so_far mod qExercise 7. Can you think of a better algorithm that will bring the run-time down to O(n
View Full Document
Unlocking...