Binary Golay code
|
|
The extended binary Golay code is an error-correcting code which encodes 12 bits of data in a 24-bit word in such a way that any triple-bit error can be corrected and any quadruple-bit error can be detected. In mathematical terms, the extended binary Golay code consists of a 12-dimensional subspace W of the space V=F224 of 24-bit words such that any two distinct elements of W differ in at least eight coordinates or, equivalently, such that any non-zero element of W has at least eight non-zero coordinates. The possible sets of non-zero coordinates as w ranges over W are called code words. In the extended binary Golay code, all code words have order 0, 8, 12, 16, or 24. Up to relabelling coordinates, W is unique.
The perfect binary Golay code is obtained from the extended binary Golay code by deleting one coordinate position (and conversely, the extended binary Golay code is obtained from the perfect binary Golay code by adding a parity check bit). It is perfect, that is, the balls of radius 3 around code words form a partition of the vector space.
Constructions
- Lexicographic code: Order the vectors in V lexicographically (i.e., interpret them as unsigned 24-bit binary integers and take the usual ordering). Starting with w1 = 0, define w2, w3, ..., w12 by the rule that wn is the smallest integer which differs from all linear combinations of previous elements in at least eight coordinates. Then W can be defined as the span of w1, ..., w12.
- Quadratic residue code: Consider the set N of quadratic non-residues (mod 23). This is an 11-element subset of the cyclic group Z/23Z. Consider the translates t+N of this subset. Augment each translate to a 12-element set St by adding an element ∞. Then labelling the basis elements of V by 0, 1, 2, ..., 22, ∞, W can be defined as the span of the words St together with the word consisting of all basis vectors.