Error detection and correction adds structured redundancy to messages so that corruption can be noticed or repaired. For a block block code with minimum Hamming distance , all patterns of at most symbol changes are detectable, and all patterns of at most changes are uniquely correctable.
The correction bound follows because radius- Hamming balls around distinct codewords are disjoint when . For example, encoding a bit as or gives distance three, so majority decoding corrects one flipped bit. A single parity bit detects one flipped bit but cannot identify its position; detection and correction require different amounts of information.
Unique decoding recovers a single codeword from a corrupted received word, with a guarantee that the transmitted codeword is the only candidate within the allowed error radius. If a block code has minimum distance , then every pattern of at most
symbol errors can be corrected in principle. Indeed, if two codewords were both within Hamming distance of , the triangle inequality would put them at distance at most , a contradiction.[ref]
The repetition code has , so one error is correctable: identifies . Two errors can produce , which lies closer to ; no decoder can guarantee success for all two-error patterns. The distance bound proves uniqueness, but does not itself give a fast decoding algorithm.
An erasure is a missing or explicitly flagged symbol of a transmitted codeword; its position is known to the decoder. An error instead replaces a symbol by an incorrect value without revealing its location. This distinction changes how much redundancy is needed.
A block code of minimum distance uniquely corrects every erasure pattern of size at most . Indeed, two different codewords agreeing at all unerased positions could differ in at most the erased positions, contradicting their distance of at least . Conversely, erasing all differing positions of a minimum-distance pair makes that pair indistinguishable.
For the binary even-parity code , one erased bit is recovered from the other two: the missing value is their sum modulo two. One arbitrary unflagged error is only detectable, because the minimum distance is two. More generally, errors and erasures are uniquely correctable whenever .
A checksum is a short value calculated from a data block and stored or transmitted with it to help detect corruption. The receiver recomputes the checksum from the received data and compares it with the supplied value. Different data blocks can have the same checksum, so a successful comparison does not prove equality.
For example, summing four bytes modulo gives a one-byte checksum. The bytes give ; changing the first byte to changes the checksum to , whereas exchanging two bytes leaves it unchanged. The particular checksum determines which error patterns are detected.
The Internet checksum groups bytes into 16-bit words, adds them with end-around carry, and complements the result. End-around carry adds an overflow bit back into the low end of the sum. Verification includes the checksum field and expects a sum with all bits set. The covered fields depend on the protocol; IPv6 has no header checksum.[ref][ref]
A cyclic redundancy check represents a bit string as a polynomial over the field with two elements and uses a polynomial remainder as checking information. Agree on a monic polynomial of polynomial degree with constant term . Under the basic systematic convention, a message polynomial produces
Here , and addition equals subtraction over the field with two elements, so divides the transmitted polynomial . The receiver tests the polynomial remainder on division by the same CRC generator polynomial.
For example, and give and . If an error polynomial changes to , the error is undetected exactly when divides . Thus the CRC generator polynomial controls which bit-error patterns the cyclic redundancy check detects. This basic convention fixes the mathematics; implementations can additionally specify initial register contents and bit-order conventions.
The CRC generator polynomial is the agreed divisor used in a cyclic redundancy check. In the basic binary convention it is a monic polynomial of polynomial degree with . A nonzero error polynomial goes undetected exactly when .
This algebra gives useful detection guarantees. A single changed bit has and cannot be divisible by when . More generally, suppose the first and last changed bits span at most consecutive positions. Write with and . Since and are coprime polynomials, would imply , contradicting the polynomial degree bound. Every such error pattern is therefore detected.
If divides , every error changing an odd number of bits is also detected: its error polynomial satisfies , whereas every multiple of has value zero at .
Error correction recovers a transmitted or stored message despite specified corruption. A decoder uses the redundancy of an error-correcting code to select the original codeword, or reports failure if the available information does not determine one reliably.
For the repetition code , , a received is corrected to by choosing the closest word in Hamming distance. This guarantees recovery after at most one bit flip, but two flips can produce a wrong choice. If corrupted positions are known, they are erasure, which are easier to repair: a code of minimum distance can recover from any erasures.

Articles by others on the same topic (1)

Error detection and correction refer to techniques used in digital communication and data storage to ensure the integrity and accuracy of data. As data is transmitted over networks or stored on devices, it can become corrupted due to noise, interference, or other issues. Error detection and correction techniques identify and rectify these errors to maintain data integrity. ### Error Detection Error detection involves identifying whether an error has occurred during data transmission or storage.