Contents 1 Definitions 2 History 3 Introduction 4 Implementation 5 Error detection schemes 5.1 Repetition codes 5.2 Parity bits 5.3 Checksums 5.4 Cyclic redundancy checks (CRCs) 5.5 Cryptographic hash functions 5.6 Error-correcting codes 6 Error correction 6.1 Automatic repeat request (ARQ) 6.2 Error-correcting code 6.3 Hybrid schemes 7 Applications 7.1 Internet 7.2 Deep-space telecommunications 7.3 Satellite broadcasting (DVB) 7.4 Data storage 7.5 Error-correcting memory 8 See also 9 References 10 Further reading 11 External links

Definitions The general definitions of the terms are as follows: Error detection is the detection of errors caused by noise or other impairments during transmission from the transmitter to the receiver. Error correction is the detection of errors and reconstruction of the original, error-free data.

History The modern development of error-correcting codes in 1947 is due to Richard W. Hamming.[1] A description of Hamming's code appeared in Claude Shannon's A Mathematical Theory of Communication[2] and was quickly generalized by Marcel J. E. Golay.[3]

Introduction The general idea for achieving error detection and correction is to add some 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 or non-systematic: In a systematic scheme, the transmitter sends the original data, and attaches a fixed number of check bits (or parity data), which are derived from the data bits by some deterministic algorithm. If only 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. In a system that uses a non-systematic code, the original message is transformed into an encoded message 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 models include memory-less models where errors occur randomly and with a certain probability, and dynamic models where errors occur primarily in 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 capacity cannot be determined, or is 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.

Implementation Error correction may generally be realized in two different ways: Automatic repeat request (ARQ) (sometimes also referred to as backward error correction): This is an error control technique whereby an error detection scheme is combined with requests for retransmission of erroneous data. Every block of data received is checked using the error detection code used, and if the check fails, retransmission of the data is requested – this may be done repeatedly, until the data can be verified. Forward error correction (FEC): The sender encodes the data using an error-correcting code (ECC) prior to transmission. The additional information (redundancy) added by the code is used by the receiver to recover the original data. In general, the reconstructed data is what is deemed the "most likely" original data. ARQ and FEC may be combined, such that minor errors are corrected without retransmission, and major errors are corrected via a request for retransmission: this is called hybrid automatic repeat-request (HARQ).

Error detection schemes Error detection is most commonly realized using a suitable hash function (or checksum algorithm). A hash function adds a fixed-length tag to a message, which enables receivers to verify the delivered message by recomputing the tag and comparing it with the one provided. There exists a vast variety of different hash function designs. However, some are of particularly widespread use because of either their simplicity or their suitability for detecting certain kinds of errors (e.g., the cyclic redundancy check's performance in detecting burst errors). A random-error-correcting code based on minimum distance coding can provide a strict guarantee on the number of detectable errors, but it may not protect against a preimage attack. A repetition code, described in the section below, is a special case of error-correcting code: although rather inefficient, a repetition code is suitable in some applications of error correction and detection due to its simplicity. Repetition codes Main article: Repetition code A repetition code is a coding scheme that repeats the bits across a channel to achieve error-free communication. Given a stream of data to be transmitted, the data are divided into blocks of bits. Each block is transmitted some predetermined number of times. For example, to send the bit pattern "1011", the four-bit block can be repeated three times, thus producing "1011 1011 1011". However, if this twelve-bit pattern was received as "1010 1011 1011" – where the first block is unlike the other two – it can be determined that an error has occurred. A repetition code is very inefficient, and can be susceptible to problems if the error occurs in exactly the same place for each group (e.g., "1010 1010 1010" in the previous example would be detected as correct). The advantage of repetition codes is that they are extremely simple, and are in fact used in some transmissions of numbers stations.[4][5] Parity bits Main article: Parity bit A parity bit is a bit that is added to a group of source bits to ensure that the number of set bits (i.e., bits with value 1) in the outcome is even or odd. It is a very simple scheme that can be used to detect single or any other odd number (i.e., three, five, etc.) of errors in the output. An even number of flipped bits will make the parity bit appear correct even though the data is erroneous. Extensions and variations on the parity bit mechanism are horizontal redundancy checks, vertical redundancy checks, and "double," "dual," or "diagonal" parity (used in RAID-DP). Checksums Main article: Checksum A checksum of a message is a modular arithmetic sum of message code words of a fixed word length (e.g., byte values). The sum may be negated by means of a ones'-complement operation prior to transmission to detect errors resulting in all-zero messages. Checksum schemes include parity bits, check digits, and longitudinal redundancy checks. Some checksum schemes, such as the Damm algorithm, the Luhn algorithm, and the Verhoeff algorithm, are specifically designed to detect errors commonly introduced by humans in writing down or remembering identification numbers. Cyclic redundancy checks (CRCs) Main article: Cyclic redundancy check A cyclic redundancy check (CRC) is a non-secure hash function designed to detect accidental changes to digital data in computer networks; as a result, it is not suitable for detecting maliciously introduced errors. It is characterized by specification of what is called a generator polynomial, which is used as the divisor in a polynomial long division over a finite field, taking the input data as the dividend, such that the remainder becomes the result. A cyclic code has favorable properties that make it well suited for detecting burst errors. CRCs are particularly easy to implement in hardware, and are therefore commonly used in digital networks and storage devices such as hard disk drives. Even parity is a special case of a cyclic redundancy check, where the single-bit CRC is generated by the divisor x + 1. Cryptographic hash functions Main article: Cryptographic hash function The output of a cryptographic hash function, also known as a message digest, can provide strong assurances about data integrity, whether changes of the data are accidental (e.g., due to transmission errors) or maliciously introduced. Any modification to the data will likely be detected through a mismatching hash value. Furthermore, given some hash value, it is infeasible to find some input data (other than the one given) that will yield the same hash value. If an attacker can change not only the message but also the hash value, then a keyed hash or message authentication code (MAC) can be used for additional security. Without knowing the key, it is infeasible for the attacker to calculate the correct keyed hash value for a modified message. Error-correcting codes Main article: Forward error correction Any error-correcting code can be used for error detection. A code with minimum Hamming distance, d, can detect up to d − 1 errors in a code word. Using minimum-distance-based error-correcting codes for error detection can be suitable if a strict limit on the minimum number of errors to be detected is desired. Codes with minimum Hamming distance d = 2 are degenerate cases of error-correcting codes, and can be used to detect single errors. The parity bit is an example of a single-error-detecting code.

See also Computer science portal Berger code Burst error-correcting code Link adaptation List of algorithms for error detection and correction List of error-correcting codes List of hash functions Reliability (computer networking)

References ^ Thompson, Thomas M. (1983), From Error-Correcting Codes through Sphere Packings to Simple Groups, The Carus Mathematical Monographs (#21), The Mathematical Association of America, p. vii, ISBN 0-88385-023-0  ^ Shannon, C.E. (1948), "A Mathematical Theory of Communication", Bell System Tech. Journal, p. 418, 27  ^ Golay, Marcel J. E. (1949), "Notes on Digital Coding", Proc.I.R.E. (I.E.E.E.), p. 657, 37  ^ Frank van Gerwen. "Numbers (and other mysterious) stations". Retrieved 12 March 2012.  ^ Gary Cutlack (25 August 2010). "Mysterious Russian 'Numbers Station' Changes Broadcast After 20 Years". Gizmodo. Retrieved 12 March 2012.  ^ a b A. J. McAuley, Reliable Broadband Communication Using a Burst Erasure Correcting Code, ACM SIGCOMM, 1990. ^ Ben-Gal I.; Herer Y.; Raz T. (2003). "Self-correcting inspection procedure under inspection errors" (PDF). IIE Transactions on Quality and Reliability, 34(6), pp. 529-540.  ^ K. Andrews et al., The Development of Turbo and LDPC Codes for Deep-Space Applications, Proceedings of the IEEE, Vol. 95, No. 11, Nov. 2007. ^ Huffman, William Cary; Pless, Vera S. (2003). Fundamentals of Error-Correcting Codes. Cambridge University Press. ISBN 978-0-521-78280-7.  ^ My Hard Drive Died. Scott A. Moulton ^ "Using StrongArm SA-1110 in the On-Board Computer of Nanosatellite". Tsinghua Space Center, Tsinghua University, Beijing. Archived from the original on 2011-10-02. Retrieved 2009-02-16.  ^ Jeff Layton. "Error Detection and Correction". Linux Magazine. Retrieved 2014-08-12.  ^ "EDAC Project". bluesmoke.sourceforge.net. Retrieved 2014-08-12.  ^ "Documentation/edac.txt". Linux kernel documentation. kernel.org. 2014-06-16. Archived from the original on 2009-09-05. Retrieved 2014-08-12.

Further reading Shu Lin; Daniel J. Costello, Jr. (1983). Error Control Coding: Fundamentals and Applications. Prentice Hall. ISBN 0-13-283796-X.

External links The on-line textbook: Information Theory, Inference, and Learning Algorithms, by David J.C. MacKay, contains chapters on elementary error-correcting codes; on the theoretical limits of error-correction; and on the latest state-of-the-art error-correcting codes, including low-density parity-check codes, turbo codes, and fountain codes. Compute parameters of linear codes – an on-line interface for generating and computing parameters (e.g. minimum distance, covering radius) of linear error-correcting codes. ECC Page SoftECC: A System for Software Memory Integrity Checking A Tunable, Software-based DRAM Error Detection and Correction Library for HPC Detection and Correction of Silent Data Corruption for Large-Scale High-Performance Computing Retrieved from "https://en.wikipedia.org/w/index.php?title=Error_detection_and_correction&oldid=810663727" Categories: Error detection and correctionComputer errorsHidden categories: Articles needing additional references from August 2008All articles needing additional referencesAll articles with unsourced statementsArticles with unsourced statements from January 2012Pages using RFC magic links