Editing Error detection and correction (section)

== Types of error detection ==
Error detection is most commonly realized using a suitable [[hash function]] (or specifically, a [[checksum]], [[cyclic redundancy check]] or other 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 error]]s).

=== Minimum distance coding ===
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]].

=== Repetition codes ===
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 {{mono|1011}}, the four-bit block can be repeated three times, thus producing {{mono|1011 1011 1011}}. If this twelve-bit pattern was received as {{mono|1010 1011 1011}} – where the first block is unlike the other two – 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., {{mono|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 station]]s.<ref>{{cite web
|url=http://www.cisquet.nl/numbers.htm
|title=Numbers (and other mysterious) stations
|author=Frank van Gerwen
|access-date=12 March 2012
|archive-date=12 July 2017
|archive-url=https://web.archive.org/web/20170712053335/http://www.cisquet.nl/numbers.htm
|url-status=dead
}}</ref><ref>{{cite web
|url=http://www.gizmodo.com.au/2010/08/mysterious-russian-numbers-station-changes-broadcast-after-20-years/
|website=Gizmodo
|access-date=12 March 2012
|date=25 August 2010
|author=Gary Cutlack
|title=Mysterious Russian 'Numbers Station' Changes Broadcast After 20 Years
|archive-date=5 July 2017
|archive-url=https://web.archive.org/web/20170705131816/https://www.gizmodo.com.au/2010/08/mysterious-russian-numbers-station-changes-broadcast-after-20-years/
|url-status=dead
}}</ref>

=== Parity bit ===
{{Main|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.

Parity bits added to each ''word'' sent are called [[transverse redundancy check]]s, while those added at the end of a stream of ''words'' are called [[longitudinal redundancy check]]s.  For example, if each of a series of m-bit ''words'' has a parity bit added, showing whether there were an odd or even number of ones in that word, any word with a single error in it will be detected. It will not be known where in the word the error is, however. If, in addition, after each stream of n words a parity sum is sent, each bit of which shows whether there were an odd or even number of ones at that bit-position sent in the most recent group, the exact position of the error can be determined and the error corrected. This method is only guaranteed to be effective, however, if there are no more than 1 error in every group of n words.  With more error correction bits, more errors can be detected and in some cases corrected.

There are also other bit-grouping techniques.

=== Checksum ===
{{Main|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 unintentional all-zero messages.

Checksum schemes include parity bits, [[check digit]]s, and [[longitudinal redundancy check]]s. 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 check ===
{{Main|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. It is not suitable for detecting maliciously introduced errors. It is characterized by specification of 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]]. The [[remainder]] becomes the result.

A CRC has properties that make it well suited for detecting [[burst error]]s. CRCs are particularly easy to implement in hardware and are therefore commonly used in [[computer network]]s and storage devices such as [[hard disk drives]].

The parity bit can be seen as a special-case 1-bit CRC.

=== Cryptographic hash function ===
{{Main|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 typically 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 not possible for the attacker to easily or conveniently calculate the correct keyed hash value for a modified message.

=== Digital signature ===
{{ main | Digital signature }}
Digital signatures can provide strong assurances about data integrity, whether the changes of the data are accidental or maliciously introduced.
Digital signatures are perhaps most notable for being part of the HTTPS protocol for securely browsing the web.

=== Error correction code ===
{{Main|Error correction code}}
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.