Error-correction
|
|
Template:Mergefrom In computer science and information theory, error correction consists of using methods to detect and/or 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. In general, error correction requires more redundant bits than error detection.
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 minimum amount of redundant data is one bit. A common method of error detection uses one bit of each byte of data as a parity bit. 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.
The most obvious method of error-correction is to repeat each unit of data multiple redundant times. However, it is possible to detect and correct errors with far less redundant data.
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, although this requires adding increasing amounts of redundant data to the original, which might not be practical when the error probability is very high. Shannon's theorem sets an upper bound to the error correction rate that can be achieved using a fixed amount of redundancy, but does not tell us how to construct such an optimal encoder.
Hamming codes allow any single bit error in a block to be detected and corrected. Other block error-correcting codes, such as 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.
However, in practice errors often occur in bursts rather than at random. This is often compensated for by shuffling (interleaving) the bits in the message after coding. Then any burst of bit-errors is broken up into a set of scattered single-bit errors when the bits of the message are unshuffled (de-interleaved) before being decoded.