Binary Golay code
The
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 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 binary Golay code, all code words have order 0, 8, 12, 16, or 24. Up to relabelling coordinates,
W is unique.
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.
Also see
