Content deleted Content added
m fix double redirect |
m for small n, optimal codes are cheap |
||
Line 1:
In general, 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 code]]s (also known as '''Rateless erasure codes''', e.g., see [http://www.ewh.ieee.org/soc/icss/advances4.html#Item4 here]) 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.
| |||