Loading AI tools
Type of linear error-correcting code From Wikipedia, the free encyclopedia
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[2] introducing them has been called, by E. R. Berlekamp, the "best single published page" in coding theory.[3]
Extended binary Golay code | |
---|---|
![]() | |
Named after | Marcel J. E. Golay |
Classification | |
Type | Linear block code |
Block length | 24 |
Message length | 12 |
Rate | 12/24 = 0.5 |
Distance | 8 |
Alphabet size | 2 |
Notation | -code |
Perfect binary Golay code | |
---|---|
Named after | Marcel J. E. Golay |
Classification | |
Type | Linear block code |
Block length | 23 |
Message length | 12 |
Rate | 12/23 ~ 0.522 |
Distance | 7 |
Alphabet size | 2 |
Notation | -code |
There are two closely related binary Golay codes. The extended binary Golay code, G24 (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, G23, 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 coding 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.
In mathematical terms, the extended binary Golay code G24 consists of a 12-dimensional linear subspace W of the space V = F24
2 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 4096 = 212 elements.
The binary Golay code, G23 is a perfect code. That is, the spheres of radius three around code words form a partition of the vector space. G23 is a 12-dimensional subspace of the space F23
2.
The automorphism group of the perfect binary Golay code G23 (meaning the subgroup of the group S23 of permutations of the coordinates of F23
2 which leave G23 invariant), is the Mathieu group . The automorphism group of the extended binary Golay code is the Mathieu group , of order 210 × 33 × 5 × 7 × 11 × 23. 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 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.
It is convenient to use the "Miracle Octad Generator" format, with co-ordinates 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 PSL(2,7) x S3 of a trio subgroup of M24 is useful for generating a basis. PSL(2,7) permutes the octads internally, in parallel. S3 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 S3, spanned by N and 3 dodecads formed of subsets {0,3,5,6}, {0,1,4,6}, and {0,1,2,5}.
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 and Saturn 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 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.[9]
The MIL-STD-188 American military standards for automatic link establishment in high frequency radio systems specify the use of an extended (24,12) Golay code for forward error correction.[10][11]
In two-way radio 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.