= Error-correcting code
{wiki}
An error-correcting code is a set of <codewords> chosen with enough separation to recover a transmitted message after specified errors. For equal-length words and bit-flip errors, separation is measured by <Hamming distance>. If the <minimum distance> is $d$, any nonzero pattern of at most $d-1$ flips changes a valid word into an invalid word and can therefore be detected. Every pattern of at most $t=\lfloor(d-1)/2\rfloor$ flips can be corrected by choosing the unique nearby <codeword>.
The distinction matters. A distance-two code detects a single flip but need not locate it; a distance-three code corrects a single flip. The <triangle inequality> explains the correction threshold: a received word within distance $t$ of two distinct <codewords> would put those <codewords> within distance $2t<d$, a contradiction. Actual decoders also need an efficient way to find the nearby word; a <parity-check matrix> and <syndrome decoding> exploit the structure of a <linear code> to do this.
Back to article page
