Optimal erasure codes with arbitrary parameters

From Wikipedia, the free encyclopedia

You have new messages (last change).

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help Wikipedia by improving the introduction according to the guidelines laid out at Wikipedia:Guide to layout. You can discuss the issue on the talk page.

An erasure code is used to encode data in such a way that the original message can be decoded without receiving all the encoded data.

[edit] Err-mail

Alice wants to send her telephone number (555629) to Bob using err-mail. Err-mail works just like e-mail, except

  1. About half of all the mail sent gets lost. (Some versions of this story refer to the err-mail daemon)
  2. Messages longer than 5 characters are illegal.
  3. It is very expensive (Similar to air-mail).

Instead of asking Bob to acknowledge the messages she sends, Alice devises the following scheme :

  1. She breaks her telephone number up into two messages : "A=555" and "B=629".
  2. Now she constructs the following diagram, using her infinitely sharp pencil on a grid
  3. She measures the values for C, D, E from the grid and then transmit 3 more redundant messages : "C=703", "D=777" and "E=851"

Now suppose Bob receives "D=777" and "E=851". Then he can make the following drawing :

Because there is exactly one unique line passing through the marks he made, he can reconstruct the value of A and B.

Clearly Bob can perform this procedure using any 2 err-mails.

It is also easy to prove that Alice cannot encode her telephone number in just one err-mail. This is because Alice can have 106 possible telephone numbers, which is less than the number of possible err-mails.

Therefore this system is truly efficient.

Err-mail 2

When the err-mail 2 arrives (the upgrade), it turns out that it can only send messages with 4 characters. Alice will now start by sending "A=55", "B=56" and "C=29". She will then place markers called A through E on the floor in a configuration that is known to Bob. She will then fit a plane such that its height above A is 55, its height above B is 56 and its height above C is 29. The redundant messages is then the height of that plane above D and E. If Bob receives 3 messages he should be able to reconstruct the plane and Alice's phone number.

[edit] Implementation

This process commonly implemented in a finite field using a Vandermonde matrix.

[edit] References

Retrieved from "http://en.wikipedia.org../../../o/p/t/Optimal_erasure_codes_with_arbitrary_parameters.html"