9873

Golay Code

When Voyager visited Saturn and Jupiter, data for the pictures used blocks of Golay code. Each 24-bit block of data could have up to three errors, and the computers here on Earth could fix these errors. The Golay code is thus an error-correcting code. It was originally published in 1949 with Marcel Golay's half-page paper, "Notes on Digital Coding". Today, this paper is considered one of the most remarkable papers ever published, with deep, deep connections to group theory, graph theory, number theory, combinatorics, game theory, multidimensional geometry, and even particle physics.
The 23-bit Golay code is called a perfect code. Any integer from 0 to is within distance three of one of the code words, so that up to three errors can be detected and corrected. The automorphism group is the Mathieu group The only other nontrivial perfect codes are the ternary Golay code and the Hamming code. The code words of weight 7 are elements of an (4, 7, 23) Steiner system.
The 24-bit Golay code is called a semiperfect code. Any integer from 0 to is within distance four of one of the code words. Up to four errors can be detected and up to three errors can be corrected. The automorphism group is the Mathieu group The code words of weight eight are elements of an (5, 8, 24) Steiner system.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

This Demonstration builds the Golay code in four different ways.
1. Greedy method. Start a list with the 24-bit 0 word (000…000). Add the first 24-bit word that has eight or more differences from all words in the list. Repeat, to get the 4096 code words. The code words are winning positions in the game of Mogul, played with 24 coins in a row. Each turn flips between one and seven coins such that the leftmost flipped coin goes from heads to tails. Last to move wins.
2. Icosahedron method. Start with the adjacency matrix of an icosahedron, and append the 12×12 matrix 1-I. These 12 vectors serve as a basis for the 4096 code words.
3. Nonresidue method. If an integer is squared modulus 23, the result will not be in , the quadratic nonresidues mod 23. In a 24-bit code word, change those places to 1. Obtain 11 more lists by adding 1 to 11 to , mod 23. Finally, change the bit of each to 1 and gain a basis for the 4096 code words.
4. Polynomial method. Modulus 2, one factor of is Consider the powers of , namely . There are 253 polynomials with seven terms. Choose 12 polynomial powers with differing initial terms, and append 1 to each polynomial's coefficient list to obtain a basis for the 4096 code words.
M. J. E. Golay, "Notes on Digital Coding," Proc. IRE, 37, 1949 p. 657.
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices, and Groups, 3rd ed., New York: Springer, 1999.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+