Error detection and correction: Difference between revisions

Revision as of 16:31, 5 March 2024

Revision as of 15:47, 26 March 2024

Line 18:

The modern development of [[error correction code]]s is credited to [[Richard Hamming]] in 1947.<ref name=Thompson>{{citation|first=Thomas M.|last=Thompson|title=From Error-Correcting Codes through Sphere Packings to Simple Groups|publisher=The Mathematical Association of America|year=1983|series=The Carus Mathematical Monographs (#21)|isbn=0-88385-023-0|page=vii}}</ref> A description of [[Hamming code|Hamming's code]] appeared in [[Claude Shannon]]'s ''A Mathematical Theory of Communication''<ref>{{citation|first=C.E.|last=Shannon|title=A Mathematical Theory of Communication|journal=Bell System Technical Journal|volume=27|issue=3|pages=379–423|year=1948|doi=10.1002/j.1538-7305.1948.tb01338.x|pmid=9230594|hdl=10338.dmlcz/101429|hdl-access=free}}</ref> and was quickly generalized by [[Marcel J. E. Golay]].<ref>{{citation|first=Marcel J. E.|last=Golay|title=Notes on Digital Coding|journal=Proc.I.R.E. (I.E.E.E.)|volume=37|year=1949|page=657}}</ref>

Good error control performance requires the scheme to be selected based on the characteristics of the communication channel. Common [[channel model]]s include [[memoryless]] models where errors occur randomly and with a certain probability, and dynamic models where errors occur primarily in [[burst error|bursts]]. Consequently, ==error-detecting and correcting codes can be generally distinguished between ''random-error-detecting/correcting'' and ''burst-error-detecting/correcting''. Some codes can also be suitable for a mixture of random errors and burst errors.

== Principles ==

All error-detection and correction schemes add some [[Redundancy (information theory)|redundancy]] (i.e., some extra data) to a message, which receivers can use to check consistency of the delivered message and to recover data that has been determined to be corrupted. Error detection and correction schemes can be either [[systematic code|systematic]] or non-systematic. In a systematic scheme, the transmitter sends the original (error-free) data and attaches a fixed number of ''check bits'' (or ''parity data''), which are derived from the data bits by some encoding algorithm. If error detection is required, a receiver can simply apply the same algorithm to the received data bits and compare its output with the received check bits; if the values do not match, an error has occurred at some point during the transmission. If error correction is required, a receiver can apply the decoding algorithm to the received data bits and the received check bits to recover the original error-free data. In a system that uses a non-systematic code, the original message is transformed into an encoded message carrying the same information and that has at least as many bits as the original message.

Good error control performance requires the scheme to be selected based on the characteristics of the communication channel. Common [[channel model]]s include [[memoryless]] models where errors occur randomly and with a certain probability, and dynamic models where errors occur primarily in [[burst error|bursts]]. Consequently, error-detecting and correcting codes can be generally distinguished between ''random-error-detecting/correcting'' and ''burst-error-detecting/correcting''. Some codes can also be suitable for a mixture of random errors and burst errors.

If the channel characteristics cannot be determined, or are highly variable, an error-detection scheme may be combined with a system for retransmissions of erroneous data. This is known as [[automatic repeat request]] (ARQ), and is most notably used in the Internet. An alternate approach for error control is [[hybrid automatic repeat request]] (HARQ), which is a combination of ARQ and error-correction coding.