Ternary Golay codes for error correction
In 1947, Juhani Virtakallio wrote to a football pool magazine that when betting on 11 matches (which each result in a win, loss, or draw), it is possible to make 729 different bets and be guaranteed that exactly one of those 729 bets will incorrectly predict the results of only two matches or fewer [1]. In 1949, mathematician Marcel Golay independently came up with a similar idea, called Golay codes, which Voyager 1 and 2 used in 1979 and 1980 to transmit color photos of Jupiter and Saturn back to Earth [2].
This article focuses on one type of Golay code, called the "(perfect) ternary Golay code", or the "\( (11, 6, 5) \) linear code". It expands the data you want to transmit by a factor of \( 11/6 \), meaning your message will take up \( 5/6=83\% \) more memory, and will take \( 83\% \) longer to be transmitted. But the advantage is that when parts of the message are transmitted incorrectly, you may be able to notice and correct those mistakes.
In this demo, there are 27 possible values for each character: either a space, or one of the 26 lowercase letters of the alphabet. When you don't use Golay coding, each character is converted to 3 trits. A "trit" (portmanteau for "trinary digit") is equivalent to \( log_2(3) \approx 1.585 \) bits of information. When using Golay coding, each pair of characters is converted to one of the \( 27^2 = 729 \) possible codewords, which are each 11 trits long, so we can treat them as elements of the vector space \( (\mathbb{F}_3)^{11} \).
The weight of a codeword is the number of nonzero coordinates, and the support of a codeword is the set of positions \( k \in \{ 1,\dots,11 \} \) such that the \(k\)th coordinate of the codeword is nonzero. Out of the 729 codewords, there are 132 which have weight 5. The only way two codewords can have the same support is if they are scalar multiples of each other, and since \( \mathbb{F}_3 \) has 2 invertible elements, that means there are \( 132/2=66 \) possibilities for the support of a weight-5 codeword in the ternary Golay code. Those supports form the 66 edges of the Steiner system \( S(4,5,11) \). To learn more about Steiner systems, visit my Spot-It card deck generator.
If you are interested in learning in-depth about various types of error correction, one of the best resources is the Error Control Coding Handbook written by my grandpa, Joe Odenwalder.
[1] Source: At the Dawn of the Theory of Codes by Alexander Barg
[2] Source: Combinatorics in Space: The Mariner 9 Telemetry System by Bill Cherowitzo
Original message:
Error rate: