Error detection and correction
In mathematics, computer science, telecom-
munication, and information theory, error
detection and correction has great practic-
al importance in maintaining data (informa-
tion) integrity across noisy channels and less-
than-reliable storage media.
General definitions of
terms
Definitions of error detection and error
correction:
• Error detection is the ability to detect the
presence of errors caused by noise or
other impairments during transmission
from the transmitter to the receiver.
• Error correction is the additional ability to
reconstruct the original, error-free data.
There are two basic ways to design the chan-
nel code and protocol for an error correcting
system:
• Automatic repeat-request (ARQ): The
transmitter sends the data and also an
error detection code, which the receiver
uses to check for errors, and requests
retransmission of erroneous data. In many
cases, the request is implicit; the receiver
sends an acknowledgement (ACK) of
correctly received data, and the
transmitter re-sends anything not
acknowledged within a reasonable period
of time.
• Forward error correction (FEC): The
transmitter encodes the data with an
error-correcting code (ECC) and sends
the coded message. The receiver never
sends any messages back to the
transmitter. The receiver decodes what it
receives into the "most likely" data. The
codes are designed so that it would take
an "unreasonable" amount of noise to trick
the receiver into misinterpreting the data.
It is possible to combine the two, so that
minor errors are corrected without retrans-
mission, and major errors are detected and a
retransmission requested. The combination is
called hybrid automatic repeat-request.
Error detection schemes
In telecommunication, a redundancy check is
extra data added to a message for the pur-
poses of error detection.
Several schemes exist to achieve error de-
tection, and generally they are quite simple.
All error detection codes (which include all
error-detection-and-correction codes) trans-
mit more bits