Decoding the Golay code by hand

Joe Fields

Southern Connecticut State University


We demonstrate a method for encoding and decoding the [24,12,8] extended binary Golay code using a simple apparatus. We also present several generalizations of this construction which admit similar decoding algorithms.


We will assume a certain familiarity with the notations and ideas of coding theory. A good introductory reference is [P1].

The [24,12,8] extended binary Golay code is a well-known and remarkable combinatorial object. It consists of 4096 binary words of length 24. Besides the zero word and the word consisting of 24 ones, there are 759 words of weight 8. (The weight, or more accurately, Hamming weight of a binary word is simply the number of ones in it.) There are also 759 words of weight 16, and the remainder of the words (2576) are of weight 12. The weight 8 words are called octads and the weight 12 words are called dodecads.

The words of any fixed weight "hold" a 5-design. That is, we take the set (1,2, ... 24) as a set of points, and consider a word in the code as the indicator function of a subset of the points, these subsets are the blocks of our design. Thus, the octads form a 5-(24,8,1) design or (equivalently) a Steiner system S(5,8,24).

The automorphism group of the Golay code (the group of permutations of the coordinates that send codewords to codewords) is the famous Mathieu group M24 -- well known as one of the first examples of a sporadic simple group.

The Golay code can also be used to construct the Leech lattice.

In [P2], V. Pless demonstrated a method for decoding the Golay code by hand. She used a characterization of the Golay code as the unique code which projects onto the [6,3,4]--GF(4) hexacode and satisfies certain parity conditions.

Specifically, one writes a Golay codeword into a \[ 4 \times 6 \] array and indexes the rows by the elements of GF(4) -- \[ \{0,1,\omega,\omega^2\} \] , thus each column of this array determines a certain linear combination of elements in GF(4), and hence an element thereof. A particular \[ 4 \times 6 \] array of zeros and ones is a golay codeword if the length 6 vector determined by the columns is in the hexacode and the first row and all columns have the same parity. Since the hexacode has a particularly nice group of symmetries, it is possible for a human being to recognize hexacode words. Indeed, with a little practice one can decode the hexacode in one's head.

This characterization is essentially equivalent to the MOG (Miracle Octad Generator), see [CS]. A generator matrix for the hexacode is

\[  G = \left( \begin{array}{cccccc} 
1 & 0 & 0 & 1 & \omega^2 & \omega \\ 
0 & 1 & 0 & 1 & \omega   & \omega^2 \\ 
0 & 0 & 1 & 1 & 1        & 1 
\end{array} \right) 

The process we will describe is quite different from this. In fact, the title of this paper, ``Decoding the Golay code by hand'', is meant (quite literally) to indicate a physical process.

This article includes "models" of certain polyhedral shapes that are encoded with the Virtual Reality Modeling Language (VRML). Here are instructions for configuring your browser to support VRML rendering.

The ambitious reader may wish to construct a non-virtual model dodecahedron with which to work. This template may be of use.