Loading...

​​Discussion 5B

​​Erasures

​​Alice wants to send a message of ​​$n$​ packets to Bob. She can send a number of packets through a channel; however, the channel erases ​​$k$​ packets. How many packets does Alice need to send in order for Bob to receive the message?

​​(The packets contain information about their positions, so we know which packets are lost.)

​​Solution

​​Let the ​​$n$​ packets in the message be ​​$m_1, \cdots, m_n$​. They can represented as the points ​​$(1, m_1), \cdots, (n, m_n)$​, which can be used to construct a unique polynomial ​​$P(x)$​ of degree at most ​​$n-1$​. 

​​If Bob can construct ​​$P(x)$​, then he can figure out what the original message is. In order to do so, he needs to receive ​​$n$​ points to reconstruct ​​$P(x)$​. Since the channel erases ​​$k$​, Alice must send ​​$n+k$​ points. So Alice sends the packets ​​$P(1), \cdots, P(n+k)$​, from which Bob will receive ​​$n$​ points to reconstruct the polynomial with. Once Bob has ​​$P(x)$​, he can determine the original message by evaluating ​​$P(1), \cdots, P(n)$​.

​​General Errors

​​What if the channel changes the values in ​​$k$​ packets instead of just erasing them? Can Alice still transmit a message that Bob can decode; if so, how many packets does Alice need to send?

​​Berlekamp-Welch

1. ​​Again, Alice creates ​​$P(x)$​ with degree ​​$n-1$​.

2. ​​Alice sends ​​$n+2 k$​ packets: ​​$P(1), \cdots, P(n + 2 k)$​

3. ​​Bob receives ​​$n+2 k$​ packets, ​​$k$​ of which are now changed

1. ​​Let the packets received be ​​$r_1, \cdots, r_{n+2k}$​

2. ​​Let these errors occur at positions ​​$e_1, \cdots, e_k$​

4. ​​Define ​​$E(x) = (x-e_1) \cdots (x-e_k) = x^k + b_{k-1} x^{k-1} + \cdots + b_0$​

5. ​​Then ​​$P(i) E(i) = r_i E(i)$​ for all ​​$i \in \{ 1, \cdots, n+2k \}$​ because

1. ​​if ​​$i$​ is a location of an error, then ​​$E(i)=0$​

2. ​​if ​​$i$​ is not a location of an error, then ​​$P(i) = r_i$​

6. ​​Let ​​$Q(x) = P(x) E(x) = a_{n+k-1} x^{n+k-1} + \cdots + a_0$​

7. ​​Then from (5) we know ​​$Q(i) = r_i E(i)$​ for ​​$i \in \{ 1, \cdots, n+2k \}$​

1. ​​this gives us a system of ​​$n+2k$​ equations

2. ​​​​$E(\cdot)$​ has ​​$k$​ unknown coefficients

3. ​​​​$Q(\cdot)$​ has ​​$n + k$​ unknown coefficients

8. ​​Once we find ​​$E(x)$​ and ​​$Q(x)$​, we can find ​​$P(x) = \frac{Q(x)}{E(x)}$​

​​

​​We actually do the above over a finite field ​​$GF(p)$​ instead of the reals; reason is here: Shamir’s Secret Sharing 

​​

​​