Golay Code Using Great Dodecahedron – Gerard Westendorp

The extended binary Golay code, or extended Golay code for short, is the essentially unique way to encode 12 bits of data in a 24-bit word in such a way that errors affecting up to 3 bits can be corrected, and errors affecting up to 7 bits can at least be detected.

The easiest way to describe this code uses the geometry of the dodecahedron. First, take the 12 bits to be coded and imagine them sitting on the faces of the great dodecahedron. This is a nonconvex polyhedron with the same vertices as the regular icosahedron, but with 12 large pentagons as faces. These pentagons intersect each other:

Great Dodecahedron – Robert Webb’s Stella Software

Then we need to describe 12 parity bits: additional bits, computed from the bits we want to code, whose function is to help us detect that errors have occurred, or perhaps even correct them.

We put the 12 parity bits at the 12 vertices of the icosahedron. The parity bit at any vertex is the sum, modulo 2, of the bits on faces that do not contain that vertex.

As we turn on bits at various faces of the great dodecahedron—that is, change them from 0 to 1, while keeping the other face bits 0—bits at various vertices will ‘light up’, as shown here:

Golay Code Using Great Dodecahedron – Greg Egan

The extended Golay code is a linear code, meaning that if two 24-bit words are allowed by this code, so is their sum. Thus, the extended Golay code is really a 12-dimensional subspace \(W\) of \(\mathbb{F}_2^{24}\), the 24-dimensional vector space over the field of two elements. The 12 ways of lighting up the great dodecahedron, shown in the image above, form a basis of this subspace.

We can also list these basis vectors, obtaining a matrix of 0’s and 1’s called a generator matrix. The generator matrix looks as follows, with blue for 0 and red for 1:

Generator Matrix for Binary Extended Golay Code – Life of Riley

The 12 bits being coded are at left; the 12 parity bits are at right. The great dodecahedron picture is much easier to remember!

The extended Golay code has the property that any two elements of this subspace \(W \subset \mathbb{F}_2^{24}\) differ in at least 8 coordinates. We say their Hamming distance is at least 8. Thus, if one is trying to transmit an element of \(W\) and some bit errors occur, any error affecting no more than 3 bits can be corrected, and any error affecting no more than 7 bits can be detected. Up to permuting coordinates, \(W\) is the unique 12-dimensional subspace of \(\mathbb{F}_2^{24}\) with this property.

If we delete any one component of the vectors in the extended Golay code, we obtain the perfect binary Golay code, a 12-dimensional subspace \(W’ \subset \mathbb{F}_2^{23}\). The Hamming distance between elements of this subspace is at least 7. This is a perfect code, meaning that the spheres of Hamming radius 3 around code words form a partition of \(\mathbb{F}_2^{23}\).

The group of permutations of the 23 coordinates that preserve \(W’ \subset \mathbb{F}_2^{23}\) is called the automorphism group of the perfect Golay code. This is a finite simple group, the Mathieu group \(M_{23}\), with

$$ 10,200,960 = 23 \cdot 22 \cdot 21 \cdot 20 \cdot 16 \cdot 3 $$

elements. Similarly, the automorphism group of the extended Golay code is a simple group called the Mathieu group \(M_{24}\), with

$$ 244,823,040 = 24 \cdot 23 \cdot 22 \cdot 21 \cdot 20 \cdot 16 \cdot 3 $$

elements.

The factorizations here reflect that \(M_{23}\) acts in a 4-transitive way on the 23-element set and \(M_{24}\) acts in a 5-transitive way on the 24-element set. Here a group \(G\) acting on a set \(X\) is said to be \(k\)-transitive if, given two sets of points \(p_1, \dots, p_k \in X\) and \(q_1, \dots, q_k \in X\) such that all the \(p_i\) are distinct and all the \(q_i\) are distinct, there is an element of \(G\) that maps each point \(p_i\) to the corresponding point \(q_i\). It’s easy to see that a group acting \(k\)-transitively on an \(n\)-element set must have an order divisible by

$$ n(n-1)\cdots(n-k+1) .$$

The extended Golay code has practical applications, some of which are mentioned here:

• Binary Golay code, Wikipedia.

Paraphrasing this article:

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 extended binary Golay code.

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 binary Golay code for forward error correction (FEC).

The image of the great dodecahedron was made using Robert Webb’s Stella software and put on Wikicommons here, with a copyright allowing its use under certain conditions. The picture of the generator matrix of the extended Golay code was put into the public domain here by ‘Life of Riley’.

Visual Insight is a place to share striking images that help explain advanced topics in mathematics. I’m always looking for truly beautiful images, so if you know about one, please drop a comment here and let me know!