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 , any nonzero pattern of at most flips changes a valid word into an invalid word and can therefore be detected. Every pattern of at most 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 of two distinct codewords would put those codewords within distance , 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.
The name Golay code refers to closely related exceptional linear codes. The binary Golay code has parameters : length twenty-three, dimension twelve over , and minimum distance seven. Adding an overall parity coordinate gives the extended binary Golay code . There is also a ternary code, whose extension has parameters ; specifying the alphabet and extension avoids ambiguity.[ref]
Golay codes in the Error Correction Zoo. Binary and ternary Golay code entries, parameters and perfect-code properties
The binary length-twenty-three code corrects three errors. A radius-three Hamming ball contains words. Its disjoint decoding balls therefore cover all received words exactly: this is a perfect code. The extended code has a larger minimum distance, but its radius-three balls do not fill the entire larger word space. These arithmetic properties explain why the codes are useful beyond their historical names.
A binary repetition code represents one bit by repeating it times, using codewords and . Their Hamming distance is , and the code rate is . For odd , the majority function recovers the input whenever fewer than half the positions have flipped. Even allows a tied vote, so a decoder must specify how it handles that case.
For , the received words decode to zero; decode to one. The decoder therefore corrects every single flip. This guarantee concerns the number of flipped positions, independent of any probabilistic model.
If each position passes independently through a binary symmetric channel with crossover probability , a decoded error requires at least two flips. The binomial distribution givesAt , the uncoded error probability is , while the three-bit code's decoded error probability is . This improvement costs three transmitted bits per message bit. For , ; for , one should first exploit the known tendency to invert symbols rather than applying the same majority rule blindly.
Independent flips are an essential assumption for the displayed formula. If a single common disturbance flips all three positions together with probability , repetition provides no improvement. More efficient error-correcting codes distribute redundancy across larger message blocks; repetition is useful as a transparent example of the geometry and the reliability–rate tradeoff.
Articles by others on the same topic
There are currently no matching articles.
