CS代写 CS 70 Discrete Mathematics and Probability Theory Fall 2021 – cscodehelp代写
CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Berlekamp- Up
Let P(i), a polynomial applied to the input i, be the original encoded polynomial before sent, and let ri be the received info for the input i which may or may not be corrupted.
(a) When does ri = P(i)? When does ri not equal P(i)?
(b) If you want to send a length-n message, what should the degree of P(x) be? Why?
(c) If there are at most k erasure errors, how many packets should you send? If there are at most k general errors, how many packets should you send? (We will see the reason for this later.) Now we will only consider general errors.
(d) What do the roots of the error polynomial E(x) represent? Does the receiver know the roots of E(x)? If there are at most k errors, what is the maximum degree of E(x)? Using the information about the degree of P(x) and E(x), what is the degree of Q(x) = P(x)E(x)?
(e) Why is the equation Q(i) = P(i)E(i) = riE(i) always true? (Consider what happens when P(i) = ri, and what happens when P(i) does not equal ri.)
(f) In the polynomials Q(x) and E(x), how many total unknown coefficients are there? (These are the variables you must solve for. Think about the degree of the polynomials.) When you receive packets, how many equations do you have? Do you have enough equations to solve for all of the unknowns?
CS 70, Fall 2021, DIS 5B 1
(Think about the answer to the earlier question – does it make sense now why we send as many packets as we do?)
(g) If you have Q(x) and E(x), how does one recover P(x)? If you know P(x), how can you recover the original message?
2 Berlekamp- with Fewer Errors
In class we derived how the Berlekamp-Welch algorithm can be used to correct k general errors, given n + 2k points transmitted. In real life, it is usually difficult to determine the number of errors that will occur. What if we have less than k errors? This is a follow up to the exercise posed in the notes.
Suppose Alice wants to send 1 message to Bob and wants to guard against 1 general error. She decides to encode the message with P(x) = 4 (on GF(7)) such that P(0) = 4 is the message she want to send. She then sends P(0), P(1), P(2) = (4, 4, 4) to Bob.
CS 70, Fall 2021, DIS 5B 2
(a) Suppose Bob receives the message (4,5,4). Without performing Gaussian elimination explicitly, find E(x) and Q(x).
(b) Now, suppose there were no general errors and Bob receives the original message (4,4,4). Show that the Q(x),E(x) that you found in part (a) still satisfies Q(i) = riE(i) for all i = 0,1,2.
(c) Verify that E(x) = x, Q(x) = 4x is another possible set of polynomials that satisfies Q(i) = riE(i) for all i = 0,1,2.
(d) Suppose you’re actually trying to decode the received message (4, 4, 4). Based on what you showed in the previous two parts, what will happen during row reduction when you try to solve for the unknowns?
(e) Prove that in general, no matter what the solution of Q(x) and E(x) are though, the recovered P(x) will always be the same.
CS 70, Fall 2021, DIS 5B 3
3 Secret Sharing with Spies
An officer stored an important letter in her safe. In case she becomes unreachable in battle, she decides to share the password (which is a number) with her troops. However, everyone knows that there are 3 spies among the troops, but no one knows who they are except for the three spies themselves. The 3 spies can coordinate with each other and they will either lie and make people not able to open the safe, or will open the safe themselves if they can. Therefore, the officer would like a scheme to share the password that satisfies the following conditions:
• When M of them get together, they are guaranteed to be able to open the safe even if they have spies among them.
• The 3 spies must not be able to open the safe all by themselves.
Please help the officer to design a scheme to share her password. What is the scheme? What is the smallest M? Show your work and argue why your scheme works and any smaller M couldn’t work. (The troops only have one chance to open the safe; if they fail the safe will self-destruct.)
CS 70, Fall 2021, DIS 5B 4
