Erasure code

Rateless erasure codes are a form of erasure codes. In general, an erasure code transforms a message of n blocks, into one 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) 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.

Rateless erasure codes transform an n block message into a pratically 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: Tornado codes
• Rateless erasure codes: Online codes, LT codes, Raptor codes