Error-correction

In computer science and information theory, error-correction consists of methods to detect and correct errors in the transmission or storage of data by the use of some amount of redundant data and (in the case of transmission) the selective retransmission of incorrect segments of the data.

Error-correction methods are chosen depending on the error characteristics of the transmission or storage medium, such that errors are almost always detected and corrected with a minimum of redundant data stored or sent.

The most obvious (and highly inefficient) method of error-correction is to repeat each unit of data multiple times. Another simple method is to use one bit of each byte of data as a parity bit. Note, however, that this only provides error-detection, and not error-correction: if a single bit error occurs, we do not know which bit is in error. Worse, this method will only detect about half of all errors. However, it is possible to do much better than either of these simplistic methods.

Information theory tells us that whatever be the probability of error in transmission or storage, it is possible to construct error-correcting codes in which the likelihood of failure is arbitrarily low. It gives a bound on the efficiency that such schemes can achieve.

Error-correction in practice is complicated by the fact that errors might occur in bursts rather than at random. This is often compensated for by shuffling the bits in the message after coding in such a way that a burst of bit-errors is broken up into a set of scattered single-bit errors when the bits of the message are unshuffled before being decoded.

Block error-correcting codes, like Hamming codes, and Reed-Solomon codes transform a chunk of bits into a (longer) chunk of bits in such a way that errors up to some threshold in each block can be detected and corrected.