Error detection and correction Created 2026-10-24 Updated 2026-11-05
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.
A block code for line coding divides the data into five-bit groups and assigns each of the possible groups a distinct eight-bit codeword. The receiver reverses that assignment after finding the eight-bit boundaries. There are candidate codewords, so the designer has substantial freedom to select 32 suitable ones and reserve other patterns for control or synchronization.
The choice can limit long runs of equal bits to help clock recovery, balance high and low levels to reduce a persistent offset, and distinguish control patterns from data. These properties must hold across adjacent codeword boundaries too: two individually acceptable words can concatenate into an unacceptable run. The unused patterns can also help error detection and correction: an invalid received pattern exposes some errors, and the Hamming distance between valid codewords determines stronger guarantees. Redundancy alone does not imply that all errors are detected or correctable. Circuit complexity and propagation of a synchronization error also matter.
A physical link can deliver a continuous stream of bits; the data link layer needs to identify where each separately meaningful unit begins and ends. Framing supplies those boundaries, so the receiver can separate the data-link frame header, data and checking information, associate an error detection and correction result with a particular data-link frame, and regain alignment after damaged input.