In mathematics and computer science, a binary Golay code is a type of 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. The code is named in honour of Marcel J. E. Golay. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In information theory and coding, an error-correcting code or ECC is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected and corrected. ... Digital communication, as opposed to analogue communication refers to all emerging communications and technologies via a digital platform usually combining text, graphics, sound, and video, utilising computer or mobile technology. ... There are two closely related error-correcting codes known as ternary Golay codes. ... The classification of the finite simple groups, also called the enormous theorem, is a vast body of work in mathematics, mostly published between around 1955 and 1983, which is thought to classify all of the finite simple groups. ... Marcel J.E. Golay (May 3, 1902 – 1989) was a Swiss-born mathematician, physicist, and information theorist, who applied mathematics to real-world military and industrial problems. ...

There are two closely related binary Golay codes. The extended binary Golay code 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. The other, the perfect binary Golay code, 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). A parity bit is a binary digit that indicates whether the number of bits with value of one in a given set of bits is even or odd. ...

How Golay codes are transmitted

It is possible to send standard 8-bit bytes using this standard Golay code via using 8-to-12 modulation. Other bit allocation schemes may be used to allow 8-bit data to share bandwidth with 4-bit telemetry.

Mathematical definition

In mathematical terms, the extended binary Golay code 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. Equivalently, any non-zero element of W has at least eight non-zero coordinates. The concept of a linear subspace (or vector subspace) is important in linear algebra and related fields of mathematics. ...

• 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 Hamming weight 0, 8, 12, 16, or 24.
• Up to relabelling coordinates, W is unique.

The perfect binary Golay code is a perfect code; that is, the spheres of radius 3 around code words form a partition of the vector space. The Hamming weight of a string of bits is the number of 1s in it. ... The Hamming bound is a bound on the parameters of a (not necessarily linear) code . ...

The automorphism group of the binary Golay code is the Mathieu group M₂₃. The automorphism group of the extended binary Golay code is the Mathieu group M₂₄. The other Mathieu groups occur as stabilizers of one or several elements of W. In mathematics, an automorphism is an isomorphism from a mathematical object to itself. ... In mathematics, the Mathieu groups are five finite simple groups discovered by the French mathematician Emile Léonard Mathieu. ... In mathematics, an automorphism is an isomorphism from a mathematical object to itself. ... In mathematics, the Mathieu groups are five finite simple groups discovered by the French mathematician Emile Léonard Mathieu. ... In mathematics, a symmetry group describes all symmetries of objects. ...

The Golay code words are elements of the S(5,8,24) Steiner system. A Code word may refer any of several concepts: For telecommunications senses, see Code word (telecommunication). ... In mathematics, a Steiner system is a type of block design. ...

Constructions

1. 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₁₂.
2. 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 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. (The perfect code is obtained by leaving out ∞.)
3. As a Cyclic code: The perfect G₂₃ code, can be constructed via factorisation of x²³ − 1, it is the code generated by x¹¹ + x¹⁰ + x⁶ + x⁵ + x⁴ + x² + 1 / x²³ − 1
4. The "Miracle Octad Generator" of R. T. Curtis: This uses a 4×6 array of square cells to picture the 759 Hamming-weight-8 code words, or "octads," of the extended binary Golay code. The remaining code words are obtained via symmetric differences of subsets of the 24 cells-- i.e., by binary addition. For details, see geometry of the 4×4 square.
5. 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.

In mathematics, a number q is called a quadratic residue modulo p if there exists an integer x such that: Otherwise, q is called a quadratic non-residue. ... In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na... Let C be a linear code over a finite field A of block length n. ... In mathematics, the symmetric difference of two sets is the set of elements which are in one of either set, but not in both. ... Mathematical games include many topics which are a part of recreational mathematics, but can also cover topics such as the mathematics of games, and playing games with mathematics. ...

Practical applications of Golay Codes

NASA Deep Space Missions

The Voyager 1 & 2 spacecraft needed to transmit hundreds of color pictures of Jupiter and Saturn in their 1979 and 1980 fly-bys within a constrained telecommunications bandwidth. Voyager Project redirects here. ... Adjectives: Jovian Atmosphere Surface pressure: 20–200 kPa[4] (cloud layer) Composition: ~86% H2 ~13% Helium 0. ... Note: This article contains special characters. ...

• Color image transmission required 3 times the amount of data, so the Golay (24,12,8) code was used.
• This Golay code is only 3-error correcting, but it could be transmitted at a much higher data rate.

ALE HF Data Communications

The new US government standards for automatic link establishment (ALE) in High Frequency (HF) radio systems specifies the use of an extended (24,12) Golay block code for forward error correction (FEC). In telecommunication, the term automatic link establishment (ALE) has the following meanings: 1. ... High frequency (HF) radio frequencies are between 3 and 30 MHz. ... In telecommunication, forward error correction (FEC) is a system of error control for data transmission, whereby the sender adds redundant data to its messages, which allows the receiver to detect and correct errors (within some bound) without the need to ask the sender for additional data. ...

• 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 8, giving this code the power to detect up to 7 errors in each code word (and correct none), correct up to 3 while detecting 4, or any intermediate combination. In information theory, the Hamming distance, named after Richard Hamming, is the number of positions in two strings of equal length for which the corresponding elements are different. ...

• These modes may be listed as (0,7), (1,6), (2,5), and (3,4), where the first number indicates the number of errors which may be corrected, and the second the number of errors which will be detected by each mode.

See also

• Mathieu group
• Steiner system
• Leech lattice

In mathematics, the Mathieu groups are five finite simple groups discovered by the French mathematician Emile Léonard Mathieu. ... In mathematics, a Steiner system is a type of block design. ... In mathematics, the Leech lattice is a lattice Λ in R24 discovered John Leech ( 16 (1964), 657--682). ...

References

• Curtis, R. T. A new combinatorial approach to M₂₄. Math. Proc. Camb. Phil. Soc. 79 (1976) 25-42.
• Griess, Robert L.: "Twelve Sporadic Groups", Springer-Verlag, 1998.
• Thompson, Thomas M.: "From Error Correcting Codes through Sphere Packings to Simple Groups", Carus Mathematical Monographs, Mathematical Association of America, 1983.