Decoding the Golay code by hand
Joe Fields
fieldsj1@SouthernCT.edu
Southern Connecticut State University
Abstract
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.
Introduction
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 \]](introduction_1.gif)
array
and indexes the rows by the elements of GF(4) --
![\[ \{0,1,\omega,\omega^2\} \]](introduction_2.gif)
, 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 \]](introduction_3.gif)
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)
\]](introduction_4.gif)
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.