In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
and
electronics engineering
Electronic engineering is a sub-discipline of electrical engineering that emerged in the early 20th century and is distinguished by the additional use of active components such as semiconductor devices to amplify and control electric current flow ...
, a binary Golay code is a type of linear
error-correcting code
In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.
The centra ...
used in
digital communication
Data communication, including data transmission and data reception, is the transfer of data, transmitted and received over a point-to-point or point-to-multipoint communication channel. Examples of such channels are copper wires, optical ...
s. The binary Golay code, along with the
ternary Golay code
In coding theory, the ternary Golay codes are two closely related error-correcting codes.
The code generally known simply as the ternary Golay code is an 1, 6, 53-code, that is, it is a linear code over a ternary alphabet; the relative distan ...
, has a particularly deep and interesting connection to the theory of
finite sporadic groups in mathematics. These codes are named in honor of
Marcel J. E. Golay whose 1949 paper introducing them has been called, by
E. R. Berlekamp, the "best single published page" in
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...
.
There are two closely related binary Golay codes. The extended binary Golay code, ''G''
24 (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 4-bit errors can be detected.
The other, the perfect binary Golay code, ''G''
23, 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, or check bit, is a bit added to a string of binary code. Parity bits are a simple form of error detecting code. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit octets (bytes) ...
). In standard coding notation, the codes have parameters
4, 12, 8and
3, 12, 7 corresponding to the length of the codewords, the
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coo ...
of the code, and the minimum
Hamming distance
In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...
between two codewords, respectively.
Mathematical definition
In mathematical terms, the extended binary Golay code ''G''
24 consists of a 12-dimensional
linear subspace
In mathematics, the term ''linear'' is used in two distinct senses for two different properties:
* linearity of a ''function (mathematics), function'' (or ''mapping (mathematics), mapping'');
* linearity of a ''polynomial''.
An example of a li ...
''W'' of the space of 24-bit words such that any two distinct elements of ''W'' differ in at least 8 coordinates. ''W'' is called a linear code because it is a vector space. In all, ''W'' comprises elements.
* The elements of ''W'' are called ''
code words Code word may refer to:
* Code word (communication), an element of a standardized code or protocol
* Code word (figure of speech), designed to convey a predetermined meaning to a receptive audience, while remaining inconspicuous to others
** Proce ...
''. They can also be described as subsets of a set of 24 elements, where addition is defined as taking the symmetric difference of the subsets.
* In the extended binary Golay code, all code words have
Hamming weight
The Hamming weight of a string (computer science), string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the mo ...
s of 0, 8, 12, 16, or 24. Code words of weight 8 are called octads and code words of weight 12 are called dodecads.
* Octads of the code ''G''
24 are elements of the S(5,8,24)
Steiner system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner ...
. There are octads and 759 complements thereof. It follows that there are dodecads.
* Two octads intersect (have 1's in common) in 0, 2, or 4 coordinates in the binary vector representation (these are the possible intersection sizes in the subset representation). An octad and a dodecad intersect at 2, 4, or 6 coordinates.
* Up to relabeling coordinates, ''W'' is unique.
The binary Golay code, ''G''
23 is a
perfect code. That is, the spheres of radius three around code words form a partition of the vector space. ''G''
23 is a 12-dimensional
subspace of the space F.
The automorphism group of the perfect binary Golay code ''G''
23 (meaning the subgroup of the group ''S
23'' of permutations of the coordinates of F which leave ''G''
23 invariant), is the
Mathieu group
In group theory, a topic in abstract algebra, the Mathieu groups are the five sporadic simple groups ''M''11, ''M''12, ''M''22, ''M''23 and ''M''24 introduced by . They are multiply transitive permutation groups on 11, 12, 22, 23 or 24 objec ...
. The
automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
of the extended binary Golay code is the
Mathieu group
In group theory, a topic in abstract algebra, the Mathieu groups are the five sporadic simple groups ''M''11, ''M''12, ''M''22, ''M''23 and ''M''24 introduced by . They are multiply transitive permutation groups on 11, 12, 22, 23 or 24 objec ...
, of order .
is transitive on octads and on dodecads. The other Mathieu groups occur as
stabilizers of one or several elements of ''W''.
There is a single word of weight 24, which is a 1-dimensional invariant subspace.
therefore has an 11-dimensional irreducible representation on the field with 2 elements. In addition, since the binary golay code is a 12-dimensional subspace of a 24-dimensional space,
also acts on the 12-dimensional
quotient space, called the ''binary Golay cocode''. A word in the cocode is in the same
coset
In mathematics, specifically group theory, a subgroup of a group may be used to decompose the underlying set of into disjoint, equal-size subsets called cosets. There are ''left cosets'' and ''right cosets''. Cosets (both left and right) ...
as a word of length 0, 1, 2, 3, or 4. In the last case, 6 (disjoint) cocode words all lie in the same coset. There is an 11-dimensional invariant subspace, consisting of cocode words with odd weight, which gives
a second 11-dimensional representation on the field with 2 elements.
Constructions
*
Lexicographic code Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by
Vladimir Levenshtein and by John Horton Conway and Neil Sloane. The binary lexicographic codes are ...
: 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 = 0, define ''w''
1, ''w''
2, ..., ''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.
*
Mathieu group
In group theory, a topic in abstract algebra, the Mathieu groups are the five sporadic simple groups ''M''11, ''M''12, ''M''22, ''M''23 and ''M''24 introduced by . They are multiply transitive permutation groups on 11, 12, 22, 23 or 24 objec ...
: Witt in 1938 published a construction of the largest Mathieu group that can be used to construct the extended binary Golay code.
*
Quadratic residue code
A quadratic residue code is a type of cyclic code.
Examples
Examples of quadratic
residue codes include the (7,4) Hamming code
over GF(2), the (23,12) binary Golay code
over GF(2) and the (11,6) ternary Golay code
over GF(3).
Constructions
There ...
: Consider the set ''N'' of quadratic non-residues (mod 23). This is an 11-element subset of the
cyclic group
In abstract algebra, a cyclic group or monogenous group is a Group (mathematics), group, denoted C_n (also frequently \Z_n or Z_n, not to be confused with the commutative ring of P-adic number, -adic numbers), that is Generating set of a group, ge ...
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
In coding theory, a cyclic code is a block code, where the circular shifts of each codeword gives another word that belongs to the code. They are error-correcting codes that have algebraic properties that are convenient for efficient error detecti ...
: The perfect G
23 code can be constructed via the factorization of
over the binary field
GF(2)
(also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field with two elements.
is the Field (mathematics), field with the smallest possible number of elements, and is unique if the additive identity and the multiplicative identity ...
:
It is the code generated by
. Either of degree 11 irreducible factors can be used to generate the code.
* Turyn's construction of 1967, "A Simple Construction of the Binary Golay Code," that starts from the
Hamming code
In computer science and telecommunications, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the ...
of length 8 and does not use the quadratic residues mod 23.
* 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 difference
In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and ...
s 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 into two 4-sets and the 35 partitions of the finite vector space
into 4 planes. 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
A mathematical game is a game whose rules, strategies, and outcomes are defined by clear mathematics, mathematical parameters. Often, such games have simple rules and match procedures, such as tic-tac-toe and dots and boxes. Generally, mathemati ...
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
In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.
Terminolo ...
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
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph (discrete mathematics), graph. The elements of the matrix (mathematics), matrix indicate whether pairs of Vertex (graph theory), vertices ...
of the
icosahedron
In geometry, an icosahedron ( or ) is a polyhedron with 20 faces. The name comes . The plural can be either "icosahedra" () or "icosahedrons".
There are infinitely many non- similar shapes of icosahedra, some of them being more symmetrical tha ...
.
A convenient representation
It is convenient to use the "
Miracle Octad Generator" format, with coordinates in an array of 4 rows, 6 columns. Addition is taking the symmetric difference. All 6 columns have the same parity, which equals that of the top row.
A partition of the 6 columns into 3 pairs of adjacent ones constitutes a
trio. This is a partition into 3 octad sets. A subgroup, the
projective special linear group
In mathematics, especially in the group theoretic area of algebra, the projective linear group (also known as the projective general linear group or PGL) is the induced action of the general linear group of a vector space ''V'' on the associa ...
PSL(2,7) x S
3 of a trio subgroup of M
24 is useful for generating a basis. PSL(2,7) permutes the octads internally, in parallel. S
3 permutes the 3 octads bodily.
The basis begins with octad T:
0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
and 5 similar octads. The sum N of all 6 of these code words consists of all 1's. Adding N to a code word produces its complement.
Griess (p. 59) uses the labeling:
∞ 0 , ∞ 0 , ∞ 0
3 2 , 3 2 , 3 2
5 1 , 5 1 , 5 1
6 4 , 6 4 , 6 4
PSL(2,7) is naturally the linear fractional group generated by (0123456) and (0∞)(16)(23)(45). The 7-cycle acts on T to give a subspace including also the basis elements
0 1 1 0 1 0
0 0 0 0 0 0
0 1 0 1 0 1
1 1 0 0 0 0
and
0 1 1 0 1 0
0 1 0 1 0 1
1 1 0 0 0 0
0 0 0 0 0 0
The resulting 7-dimensional subspace has a 3-dimensional quotient space upon ignoring the latter 2 octads.
There are 4 other code words of similar structure that complete the basis of 12 code words for this representation of W.
W has a subspace of dimension 4, symmetric under PSL(2,7) x S
3, spanned by N and 3 dodecads formed of subsets , , and .
Practical applications of Golay codes
NASA deep space missions
Error correction was vital to data transmission in the
Voyager 1 and 2 spacecraft particularly because memory constraints dictated offloading data virtually instantly leaving no second chances. Hundreds of color pictures of
Jupiter
Jupiter is the fifth planet from the Sun and the List of Solar System objects by size, largest in the Solar System. It is a gas giant with a Jupiter mass, mass more than 2.5 times that of all the other planets in the Solar System combined a ...
and
Saturn
Saturn is the sixth planet from the Sun and the second largest in the Solar System, after Jupiter. It is a gas giant, with an average radius of about 9 times that of Earth. It has an eighth the average density of Earth, but is over 95 tim ...
in their 1979, 1980, and 1981 fly-bys would be transmitted within a constrained telecommunications bandwidth. Color image transmission required three times as much data as black and white images, so the 7-error correcting
Reed–Muller code
Reed–Muller codes are error-correcting codes that are used in wireless communications applications, particularly in deep-space communication. Moreover, the proposed 5G standard relies on the closely related polar codes for error correction i ...
that had been used to transmit the black and white Mariner images was replaced with the much higher data rate Golay (24,12,8) code.
Radio communications
The
MIL-STD-188
MIL-STD-188 is a series of U.S. military standards relating to telecommunications.
Purpose
Faced with "past technical deficiencies in telecommunications systems and equipment and software…that were traced to basic inadequacies in the appl ...
American military standards for
automatic link establishment in
high frequency
High frequency (HF) is the ITU designation for the band of radio waves with frequency between 3 and 30 megahertz (MHz). It is also known as the decameter band or decameter wave as its wavelengths range from one to ten decameters (ten to one ...
radio systems specify the use of an extended (24,12) Golay code for
forward error correction
In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.
The centra ...
.
In
two-way radio
A two-way radio is a radio transceiver (a radio that can both transmit and receive radio waves), which is used for bidirectional person-to-person voice communication with other users with similar radios, in contrast to a broadcast receiver, whi ...
communication
digital-coded squelch (DCS, CDCSS) system uses 23-bit Golay (23,12) code word which has the ability to detect and correct errors of 3 or fewer bits.
See also
*
Leech lattice
In mathematics, the Leech lattice is an even unimodular lattice Λ24 in 24-dimensional Euclidean space which is one of the best models for the kissing number problem. It was discovered by . It may also have been discovered (but not published) by Er ...
*
Linear code
In coding theory, a linear code is an error-correcting code for which any linear combination of Code word (communication), codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although t ...
References
Sources
*
*
*
*
*
*
*
*
{{CCSDS
Error detection and correction