In computer science, an erasure code transforms a message of n blocks into a message with > 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.
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.
Examples
Near optimal erasure codes
Near optimal fountain (rateless erasure) codes
Optimal erasure codes
- Parity: used in redundant array of independent disks
- Optimal erasure codes with arbitrary parameters are surprisingly simple.
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.