Erasure code

From Wikipedia, the free encyclopedia

 It has been suggested that Optimal_erasure_codes_with_arbitrary_parameters be merged into this article or section. (Discuss)

In computer science, an erasure code transforms a message of n blocks into a message with more than n blocks, such that the original message can be recovered from a subset of those blocks. The fraction of the blocks required is called the rate, denoted r. Erasure codes are used in some forms of forward error correction.

Optimal erasure codes produce n/r blocks where any n blocks is sufficient to recover the original message. Unfortunately optimal codes are costly (in terms of memory usage, CPU time or both) when n is large, and so near optimal erasure codes are often used. These require (1+ε)n blocks to recover the message. Reducing ε can be done at the cost of CPU time.

Fountain codes (also known as rateless erasure codes) transform an n block message into a practically infinite encoded form. Encoded symbols can be generated ad infinitum and some number of them is enough to recover the message.

Contents

[edit] Examples

[edit] Near optimal erasure codes

[edit] Near optimal fountain (rateless erasure) codes

[edit] Optimal erasure codes

[edit] References

  • Software FEC in computer communications by Luigi Rizzo describes optimal erasure correction codes.
  • Feclib is a near optimal extension to Luigi Rizzo's work that uses band matrices. Many parameters can be set, like the size of the width of the band and size of the finite field. It also successfully exploits the large register size of modern CPUs. How it compares to the near optimal codes mentioned above is unknown.