Binary Golay code

Extended binary Golay code
Its generator matrix
Named after	Marcel J. E. Golay
Classification
Type	Linear block code
Parameters
Block length	24
Message length	12
Rate	12/24 = 0.5
Distance	8
Alphabet size	2
Notation	$[24,12,8]_2$ -code

Perfect binary Golay code
Named after	Marcel J. E. Golay
Classification
Type	Linear block code
Parameters
Block length	23
Message length	12
Rate	12/23 ~ 0.522
Distance	7
Alphabet size	2
Notation	$[23,12,7]_2$ -code

In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection to the theory of finite sporadic groups in mathematics.^[1] These codes are named in honor of Marcel J. E. Golay whose 1949 paper (Golay (1949)) introducing them has been called, by E. R. Berlekamp, the "best single published page" in coding theory.^[2]

There are two closely related binary Golay codes. The extended binary Golay code, G₂₄ (sometimes just called the "Golay code" in finite group theory) encodes 12 bits of data in a 24-bit word in such a way that any 3-bit errors can be corrected or any 7-bit errors can be detected. The other, the perfect binary Golay code, G₂₃, has codewords of length 23 and is obtained from the extended binary Golay code by deleting one coordinate position (conversely, the extended binary Golay code is obtained from the perfect binary Golay code by adding a parity bit). In standard code notation the codes have parameters [24, 12, 8] and [23, 12, 7], corresponding to the length of the codewords, the dimension of the code, and the minimum Hamming distance between two codewords, respectively.

Mathematical definition

In mathematical terms, the extended binary Golay code, G₂₄ consists of a 12-dimensional subspace W of the space V=F₂²⁴ of 24-bit words such that any two distinct elements of W differ in at least eight coordinates. By linearity, the distance statement is equivalent to any non-zero element of W having 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 the Hamming weights of 0, 8, 12, 16, or 24.
Up to relabeling coordinates, W is unique.

The perfect binary Golay code, G₂₃ is a perfect code. That is, the spheres of radius three around code words form a partition of the vector space.

The automorphism group of the perfect binary Golay code, G₂₃, is the Mathieu group $M_{23}$ . The automorphism group of the extended binary Golay code is the Mathieu group $M_{24}$ . The other Mathieu groups occur as stabilizers of one or several elements of W.

The supports of the Golay G₂₄ code words of weight eight are elements of the S(5,8,24) Steiner system.

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 w₁ = 0, define w₂, w₃, ..., w₁₂ 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₁, ..., w₁₂.
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 S_t by adding an element ∞. Then labeling 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. (The perfect code is obtained by leaving out ∞.)
As a Cyclic code: The perfect G₂₃ code can be constructed via the factorization of $x^{23}-1$ over the binary field GF(2):

x^{23} - 1 = (x+1)(x^{11} + x^9+x^7+x^6+x^5+x+1)(x^{11}+x^{10}+x^6+x^5+x^4+x^2+1).

It is the code generated by

\left(x^{11}+x^{10}+x^6+x^5+x^4+x^2+1\right)

.^[3] Either of degree 11 irreducible factors can be used to generate the code.^[4]

Turyn's construction of 1967, "A Simple Construction of the Binary Golay Code," that starts from the Hamming code of length 8 and does not use the quadratic residues mod 23.^[5]
From the Steiner System S(5,8,24), consisting of 759 subsets of a 24-set. If one interprets the support of each subset as a 0-1-codeword of length 24 (with Hamming-weight 8), these are the "octads" in the binary Golay code. The entire Golay code can be obtained by repeatedly taking the symmetric differences of subsets, i.e. binary addition. An easier way to write down the Steiner system resp. the octads is the Miracle Octad Generator of R. T. Curtis, that uses a particular 1:1-correspondence between the 35 partitions of an 8-set and the 35 partitions of the finite vector space $\mathbb{F}_2^4$ into 4 planes. ^[6] Nowadays often the compact approach of Conway's hexacode, that uses a 4×6 array of square cells, is used.
Winning positions in the mathematical game of Mogul: a position in Mogul is a row of 24 coins. Each turn consists of flipping from one to seven coins such that the leftmost of the flipped coins goes from head to tail. The losing positions are those with no legal move. If heads are interpreted as 1 and tails as 0 then moving to a codeword from the extended binary Golay code guarantees it will be possible to force a win.
A generator matrix for the binary Golay code is I A, where I is the 12×12 identity matrix, and A is the complement of the adjacency matrix of the icosahedron.

Practical applications of Golay codes

NASA deep space missions

The Voyager 1 and 2 spacecraft needed to transmit hundreds of color pictures of Jupiter and Saturn in their 1979, 1980, and 1981 fly-bys within a constrained telecommunications bandwidth.

Color image transmission required three times the amount of data as black and white images, so the Hadamard code that was used to transmit the black and white images was switched to the Golay (24,12,8) code. ^[7]
This Golay code is only triple-error correcting, but it could be transmitted at a much higher data rate than the Hadamard code that was used during the Mariner mission.

Radio communications

The new American government standards for automatic link establishment in high frequency radio systems specify the use of an extended (24,12) Golay block code for forward error correction (FEC).

The Extended (24,12) Golay Code specified is a (24,12) block code.
This code encodes 12 data bits to produce 24-bit code words.
It is furthermore a systematic code, meaning that the 12 data bits are present in unchanged form in the code word.

The minimum Hamming distance between any two code words (the number of bits by which any pair of code words differs) is eight.

Notes

↑ See Thompson 1983
↑ Berlekamp, E.R. (1974), Key Papers in the Development of Coding Theory, I.E.E.E. Press, p. 4
↑ Roman 1992, p. 324 Example 7.4.3
↑ Pless 1998, p. 114
↑ Turyn 1967, Section VI
↑ http://finitegeometry.org/sc/24/MOG.html
↑ http://www-math.ucdenver.edu/~wcherowi/courses/m7409/mariner9talk.pdf

References

Curtis, R. T. (1976). "A new combinatorial approach to M₂₄". Mathematical Proceedings of the Cambridge Philosophical Society 79: 25–42. doi:10.1017/S0305004100052075.
Golay, Marcel J. E. (1949). "Notes on Digital Coding". Proc. IRE 37: 657.
Greferath, Marcus (2003). "Golay Codes". In Proakis, John G. Encyclopedia of Telecommunications. Wiley. doi:10.1002/0471219282.
Griess, Robert L. (1998). Twelve Sporadic Groups. Springer. p. 167. ISBN 978-3-540-62778-4.
Pless, Vera (1998), Introduction to the Theory of Error-Correcting Codes (3rd ed.), John Wiley & Sons, ISBN 978-0-471-19047-9
Roman, Steven (1996), Coding and Information Theory, Graduate Texts in Mathematics #134, Springer-Verlag, ISBN 0-387-97812-7
Thompson, Thomas M. (1983). From Error Correcting Codes through Sphere Packings to Simple Groups. Carus Mathematical Monographs 21. Mathematical Association of America. ISBN 978-0-88385-023-7.
Turyn, Richard J. et al. (1967). Research to Develop the Algebraic Theory of Codes (Section VI) (PDF) (Report). Air Force Cambridge Research Laboratories.

Consultative Committee for Space Data Systems

Data compression	Images ICER JPEG JPEG 2000 122.0.B1 Data Adaptive Entropy Coder

Error Correction	Current Binary Golay code Concatenated codes Turbo codes Proposed LDPC codes

Telemetry command uplink	Command Loss Timer Reset Proximity-1 Space Link Protocol

Telemetry downlink	Spacecraft Monitoring & Control Beacon mode service

Telemetry general	Space Communications Protocol Specifications (SCPS): Performance Enhancing Proxy

Telemetry modulation systems	Current BPSK QPSK OQPSK Proposed GMSK

Frequencies	X band S band K_u band K_a band K band

Networking, interoperability and monitoring	Service-oriented architecture (Message Abstraction Layer)