# Binary Golay code

In

mathematics andcomputer science , a**binary Golay code**is a type oferror-correcting code used indigital communication s. The binary Golay code, along with theternary Golay code , has a particularly deep and interesting connection to the theory offinite sporadic group s in mathematics. The code is named in honour ofMarcel J. E. Golay .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 aparity bit ). In standard code notation the codes have parameters [24, 12, 8] and [23, 12, 7] .**Mathematical definition**In mathematical terms, the extended 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. Equivalently, 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 extended binary Golay code, all code words haveHamming weight 0, 8, 12, 16, or 24.

* Up to relabeling 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

automorphism group of the binary Golay code is theMathieu group $M\_\{23\}$. Theautomorphism group of the extended binary Golay code is theMathieu group $M\_\{24\}$. The other Mathieu groups occur as stabilizers of one or several elements of "W".The Golay

code word s of weight 8 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"

_{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 thecyclic 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 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 aCyclic code : The perfect G_{23}code can be constructed via factorization of $x^\{23\}-1$, it is the code generated by $x^\{11\}+x^\{10\}+x^6+x^5+x^4+x^2+1\; /\; x^\{23\}-1$

#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 viasymmetric difference s of subsets of the 24 cells-- i.e., by binary addition.

#Winning positions in themathematical 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.**Practical applications of Golay codes****NASA Deep Space Missions**The Voyager 1 & 2 spacecraft needed to transmit hundreds of color pictures of

Jupiter andSaturn in their 1979 and 1980 fly-bys within a constrained telecommunications bandwidth.

* Color image transmission required 3 times the amount of data, so the Golay (24,12,8) code was used. [*http://www-math.cudenver.edu/~wcherowi/courses/m6409/mariner9talk.pdf*]

* This Golay code is only 3-error correcting, but it could be transmitted at a much higher data rate than theHadamard code that was used during the Mariner mission.**ALE HF data communications**The new US government standards for

automatic link establishment (ALE) inHigh Frequency (HF) radio systems specifies the use of an extended (24,12) Golay block code forforward 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 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.

* 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 **References*** Curtis, R. T. A new combinatorial approach to M

_{24}. 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.

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Golay code**— may refer to:* Binary Golay code * Ternary Golay code … Wikipedia**Ternary Golay code**— There are two closely related error correcting codes known as ternary Golay codes. The code generally known simply as the ternary Golay code is a perfect (11, 6, 5) ternary linear code; the extended ternary Golay code is a (12, 6, 6) linear code… … Wikipedia**Code**— redirects here. CODE may also refer to Cultural Olympiad Digital Edition. Decoded redirects here. For the television show, see Brad Meltzer s Decoded. For code (computer programming), see source code. For other uses, see Code (disambiguation).… … Wikipedia**Cyclic code**— In coding theory, cyclic codes are linear block error correcting codes that have convenient algebraic structures for efficient error detection and correction. Contents 1 Definition 2 Algebraic structure 3 Examples … Wikipedia**Even code**— A binary code is called an even code if the Hamming weight of all its codewords is even. An even code should have a generator polynomial that include (1+x) minimal polynomial as a product. Furthermore, a binary code is called doubly even if the… … Wikipedia**Quadratic residue code**— A quadratic residue code is a type of cyclic code.There is a quadratic residue code of length pover the finite field GF(l) whenever pand l are primes, p is odd andl is a quadratic residue modulo p.Its generator polynomial as a cyclic code is… … Wikipedia**Concatenated error correction code**— In coding theory, concatenated codes form a class of error correcting codes that are derived by combining an inner code and an outer code. They were conceived in 1966 by Dave Forney as a solution to the problem of finding a code that has both… … Wikipedia**Linear code**— In mathematics and information theory, a linear code is an important type of block code used in error correction and detection schemes. Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome… … Wikipedia**Hamming code**— In telecommunication, a Hamming code is a linear error correcting code named after its inventor, Richard Hamming. Hamming codes can detect and correct single bit errors. In other words, the Hamming distance between the transmitted and received… … Wikipedia**Block code**— In computer science, a block code is a type of channel coding. It adds redundancy to a message so that, at the receiver, one can decode with minimal (theoretically zero) errors, provided that the information rate (amount of transported… … Wikipedia