Near-optimal erasure codes require (1+ε)k symbols to recover the message (where ε>0). Reducing ε can be done at the cost of CPU time. Near-optimal erasure codes trade correction capabilities for computational complexity: practical algorithms can encode and decode with linear time complexity.
Fountain codes (also known as rateless erasure codes) are notable examples of near-optimal erasure codes. They can transform a k symbol message into a practically infinite encoded form, i.e., they can generate an arbitrary amount of redundancy symbols that can all be used for error correction. Receivers can start decoding after they have received slightly more than k encoded symbols.
Regenerating Codes address the issue of rebuilding (also called repairing) lost encoded fragments from existing encoded fragments. This issue arises in distributed storage systems where communication to maintain encoded redundancy is a problem.
Read more about this topic: Erasure Code
Famous quotes containing the word codes:
“... until both employers’ and workers’ groups assume responsibility for chastising their own recalcitrant children, they can vainly bay the moon about “ignorant” and “unfair” public criticism. Moreover, their failure to impose voluntarily upon their own groups codes of decency and honor will result in more and more necessity for government control.”
—Mary Barnett Gilson (1877–?)