Erasure codes

In coding theory, an erasure code is a forward error correction (FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of k symbols into a longer message (code word) with n symbols such that the original message can be recovered from a subset of the n symbols. The fraction r = k/n is called the code rate. The fraction k’/k, where k’ denotes the number of symbols required for recovery, is called reception efficiency.

Optimal erasure codes have the property that any k out of the n code word symbols are sufficient to recover the original message (i.e., they have optimal reception efficiency). Optimal erasure codes are maximum distance separable codes (MDS codes).

Optimal codes are often costly (in terms of memory usage, CPU time, or both) when n is large. Except for very simple schemes, practical solutions usually have quadratic encoding and decoding complexity. In 2014, Lin et al. gave an approach with ${\displaystyle O(n\log n)}$ operations.

Parity check is the special case where n = k + 1. From a set of k values ${\displaystyle \{v_{i}\}_{1\leq i\leq k}}$, a checksum is computed and appended to the k source values:

...
Wikipedia