In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels.
Error detection and correction
In
information theory and coding theory with applications in computer science and
telecommunication, error detection and correction or error control are
techniques that enable reliable delivery of digital data over unreliable
communication channels. Many communication channels are subject to channel
noise, and thus errors may be introduced during transmission from the source to
a receiver. Error detection techniques allow detecting such errors, while error
correction enables reconstruction of the original data in many cases.
1 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).
2 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).
Random-error-correcting
codes based on minimum distance coding can provide a suitable alternative to
hash functions when a strict guarantee on the minimum number of errors to be
detected is desired. Repetition codes, described below, are special cases of
error-correcting codes: although rather inefficient, they find applications for
both error correction and detection due to their simplicity.
3 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 is 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.
Repetition
codes are 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 Parity bits
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).
5 Checksums
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.
6 Cyclic redundancy checks (CRCs)
A cyclic
redundancy check (CRC) is a single-burst-error-detecting cyclic code and
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 so-called generator
polynomial, which is used as the divisor in a polynomial long division over a
finite field, taking the input data as the dividend, and where the remainder
becomes the result.
Cyclic codes
have favorable properties in that they are 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.
7 Cryptographic hash functions
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.
8 Error-correcting codes
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.
An
error-correcting code (ECC) or forward error correction (FEC) code is a system
of adding redundant data, or parity data, to a message, such that it can be
recovered by a receiver even when a number of errors (up to the capability of
the code being used) were introduced, either during the process of
transmission, or on storage. Since the receiver does not have to ask the sender
for retransmission of the data, a back-channel is not required in forward error
correction, and it is therefore suitable for simplex communication such as
broadcasting. Error-correcting codes are frequently used in lower-layer
communication, as well as for reliable storage in media such as CDs, DVDs, hard
disks, and RAM.
Error-correcting
codes are usually distinguished between convolution codes and block codes:
Convolution codes are processed on a
bit-by-bit basis. They are particularly suitable for implementation in
hardware, and the Viterbi decoder allows optimal decoding.
Block codes are processed on a
block-by-block basis. Early examples of block codes are repetition codes,
Hamming codes and multidimensional parity-check codes. They were followed by a
number of efficient codes, Reed–Solomon codes being the most notable due to
their current widespread use. Turbo codes and low-density parity-check codes
(LDPC) are relatively new constructions that can provide almost optimal
efficiency.
Shannon's
theorem is an important theorem in forward error correction, and describes the
maximum information rate at which reliable communication is possible over a
channel that has a certain error probability or signal-to-noise ratio (SNR).
This strict upper limit is expressed in terms of the channel capacity. More
specifically, the theorem says that there exist codes such that with increasing
encoding length the probability of error on a discrete memory less channel can
be made arbitrarily small, provided that the code rate is smaller than the
channel capacity. The code rate is defined as the fraction k/n of k source
symbols and n encoded symbols.
The
actual maximum code rate allowed depends on the error-correcting code used, and
may be lower. This is because Shannon's proof was only of existential nature,
and did not show how to construct codes which are both optimal and have
efficient encoding and decoding algorithms.
Automatic
Repeat request (ARQ) is an error control method for data transmission that makes
use of error-detection codes, acknowledgment and/or negative acknowledgment
messages, and timeouts to achieve reliable data transmission. An acknowledgment
is a message sent by the receiver to indicate that it has correctly received a
data frame.
Usually,
when the transmitter does not receive the acknowledgment before the timeout
occurs (i.e., within a reasonable amount of time after sending the data frame),
it retransmits the frame until it is either correctly received or the error
persists beyond a predetermined number of retransmissions.
Three
types of ARQ protocols are Stop-and-wait ARQ, Go-Back-N ARQ, and Selective
Repeat ARQ.
ARQ is
appropriate if the communication channel has varying or unknown capacity, such
as is the case on the Internet. However, ARQ requires the availability of a
back channel, results in possibly increased latency due to retransmissions, and
requires the maintenance of buffers and timers for retransmissions, which in
the case of network congestion can put a strain on the server and overall
network capacity.
ARQ is
used on shortwave radio data links in the form of ARQ-E or combined with
multiplexing as ARQ-M.
9 Automatic repeat request (ARQ)
Automatic
Repeat request (ARQ) is an error control method for data transmission that
makes use of error-detection codes, acknowledgment and/or negative
acknowledgment messages, and timeouts to achieve reliable data transmission. An
acknowledgment is a message sent by the receiver to indicate that it has
correctly received a data frame.
Usually,
when the transmitter does not receive the acknowledgment before the timeout
occurs (i.e., within a reasonable amount of time after sending the data frame),
it retransmits the frame until it is either correctly received or the error
persists beyond a predetermined number of retransmissions.
Three
types of ARQ protocols are Stop-and-wait ARQ, Go-Back-N ARQ, and Selective
Repeat ARQ.
ARQ is
appropriate if the communication channel has varying or unknown capacity, such
as is the case on the Internet. However, ARQ requires the availability of a
back channel, results in possibly increased latency due to retransmissions, and
requires the maintenance of buffers and timers for retransmissions, which in
the case of network congestion can put a strain on the server and overall
network capacity.
ARQ is
used on shortwave radio data links in the form of ARQ-E or combined with
multiplexing as ARQ-M.
10 Hybrid schemes
Hybrid
ARQ is a combination of ARQ and forward error correction. There are two basic
approaches:
Messages are always transmitted with
FEC parity data (and error-detection redundancy). A receiver decodes a message
using the parity information, and requests retransmission using ARQ only if the
parity data was not sufficient for successful decoding (identified through a
failed integrity check).
Messages are transmitted without
parity data (only with error-detection information). If a receiver detects an
error, it requests FEC information from the transmitter using ARQ, and uses it
to reconstruct the original message.
The
latter approach is particularly attractive on an erasure channel when using a
rate less erasure code.
11 Applications
Applications
that require low latency (such as telephone conversations) cannot use Automatic
Repeat request (ARQ); they must use forward error correction (FEC). By the time
an ARQ system discovers an error and re-transmits it, the re-sent data will
arrive too late to be any good.
Applications
where the transmitter immediately forgets the information as soon as it is sent
(such as most television cameras) cannot use ARQ; they must use FEC because
when an error occurs, the original data is no longer available. (This is also
why FEC is used in data storage systems such as RAID and distributed data
store).
Applications
that use ARQ must have a return channel; applications having no return channel
cannot use ARQ. Applications that require extremely low error rates (such as
digital money transfers) must use ARQ. Reliability and inspection engineering
also make use of the theory of error-correcting codes.