# 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*=

**F**_{2}^{24} 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.

- 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 *w*_{1} = 0, define *w*_{2}, *w*_{3}, ..., *w*_{12} by the rule that *w*_{n} 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 *w*_{1}, ..., *w*_{12}.
- Quadratic residue code: Consider the set
*N* of quadratic non-residues (mod 23). This is an 11-element subset of the cyclic group **Z**/23**Z**. Consider the translates *t*+*N* of this subset. Augment each translate to a 12-element set *S*_{t} 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 *S*_{t} together with the word consisting of all basis vectors.

## Also see