Binary Golay code[1]

Description

A \([23, 12, 7]\) perfect binary linear code with connections to the theory of sporadic simple groups. Adding a parity bit to the code results in the \([24, 12, 8]\) extended Golay code. The codespace is a 12-dimensional linear subspace of \(GF(2)^{23}\), or \(GF(2)^{24}\) in the extended case.

The \([23, 12, 7]\) code can be constructed with the polynomial \(x^{11} + x^{10} + x^6 + x^5 + x^4 + x^2 + 1\) over \(GF(2)\). This representation of the Golay code is cyclic. Alternatively, one can use the Great Dodecahedron to generate codewords by placing message bits on the faces and calculating the parity bits that live on the 12 vertices of the inner icosahedron.

Protection

The binary Golay code has distance 7 and can correct up to \(\frac{7-1}{2}=3\) errors.

Rate

The perfect binary Golay code has a rate of \(12/23 = 0.522\). The extended binary Golay code has a rate of \(12/24 = 0.5\).

Decoding

Table lookup or algebraic algorithms such as Berlekamp-Welch [2].Both Golay codes have a trellis representation and can thus be decoded using trellis decoding [3][4].

Realizations

Used in the Voyager 1 and 2 spacecraft [5].

Notes

The automorphism group of the binary Golay code is the Mathieu group \(\mathcal{M}_{23}\), and the automorphism group of the extended binary Golay code is the Mathieu group \(\mathcal{M}_{24}\), two of the sporadic simple groups.

Parents

Zoo code information

Internal code ID: golay

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: golay

Cite as:
“Binary Golay code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/golay
BibTeX:
@incollection{eczoo_golay, title={Binary Golay code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/golay} }
Permanent link:
https://errorcorrectionzoo.org/c/golay

References

[1]
Golay, M. J. E. "Notes on Digital Coding." Proc. IRE 37, 657, 1949.
[2]
E. R. Berlekamp and L. Welch, Error Correction of Algebraic Block Codes. U.S. Patent, Number 4,633,470 1986.
[3]
A. J. VITERBI, “Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm”, The Foundations of the Digital Wireless World 41 (2009). DOI
[4]
B. Honary and G. Markarian, “New simple encoder and trellis decoder for Golay codes”, Electronics Letters 29, 2170 (1993). DOI
[5]
E. C. Stone, “The Voyager 2 encounter with Uranus”, Journal of Geophysical Research: Space Physics 92, 14873 (1987). DOI

Cite as:

“Binary Golay code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/golay

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/golay.yml.