We motivate our idea for a decoding algorithm with the following physical idea: Notice that the nine error patterns that we have considered (with one exception) have inherent asymmetries. If we imagined them suspended from their centers in a gravitational field, they have a "heavy side" that would cause them to attain a particular orientation.

In practice, what we need to do is build a function that simulates such a potential and apply group generators (for the symmetry group of the underlying polytope) in such a way as to maximize this potential function. Once we have the error patterns in a well-defined orientation, it is easy to cycle through the list of possible error patterns until we detect one (or in failing to do so, recognize that more errors have occurred than we can correct).

A particularly nice potential function can be gotten from any
super-increasing set, e.g. powers of 2, {1,2,4,8,...}.
Given a fixed numbering of the faces of the dodecahdron, each
pattern of failed decoding checks corresponds to a length
12 vector -- as our potential function we can use the (rational)
inner product of this vector with [1,2,4,...,4096].
Because any integer can be expressed in a unique way in terms of subset
sums from this set each possible value for the inner product will
be achieved *k* times, where *k* is the number of
symmetries of the pattern.

In an automated algorithm implementing the decoding scheme we have discussed, we would need to fully enumerate the possible patterns of decoding check failures. There are 39 in total -- since four of the nine patterns we have looked at can be modified in several ways.

Our 'patterns of failed decoding checks' are really just the syndromes of the
received vector, and our method of decoding really amounts to knowing that there
is a particular group (A5) that acts on these syndromes. In ordinary syndrome
decoding of the Golay code, one would need to compare the syndrome of a received
vector with 2^{12}=4096 possible syndromes. In our method we only need
compare with 39 possible syndromes -- provided that we can do this comparison
'up to' the action of the group involved. We merely keep track of which permutation
we applied to the syndrome in maximizing the potential function, do a table lookup
in order to determine the error vector and then apply the inverse of the permutation
(in parallel -- to the information *and* the parity check positions) to this error
vector then add the permuted error vector to the received word.

This approach has clear advantages if we consider building codes (for example) from some four dimensional polytopes. A human being would have distinct difficulties "spinning" a given pattern of failed decoding checks under such an object's group in order to recognize it. To a machine the process would involve only slightly greater complexity than for three-dimensional objects.

In general, there is no way to (deterministically) find the minimum weight of a code without enumerating all codewords. For codes of dimension greater than about 40, this becomes impractical.

When one has knowledge of the group of a code, the calculation of minimal distance
can take advantage of this knowledge. Thus an algorithm (essentially Polya counting)
computing the minimum distance of the codes we have considered is possible for codes
having dimensions much higher than would be practical for generic codes.
What we need to enumerate is the set of information vectors that
are inequivalent under the action of the symmetry group of our
CW complex. For example, returning to the Golay code, there
are 12 choose 2 = 66 information vectors having weight 2,
but these vectors fall into just three orbits under the action
of A5. Similarly, there are 12 choose 3 = 220 information
vectors of weight 3, which fall into only 5 orbits under A5.
Furthermore, since we can easily tell whether a code of the
type under consideration contains the all ones vector -- and
the Golay code does -- we need only consider information vectors
up to *k/2* in weight (the others are complements of these).
In the final analysis, we can find the weight distribution of
this code by considering only 1+3+5+12+14+24 = 59 vectors,
a considerable savings over 4096.

From a group theoretic perspective, this construction is
interesting because we have built an object whose
automorphism group is M24 (the simple group of
order 2^{10}.3^{3}.5.7.11.23 = 244823040)
out of an object whose automorphism group is A5. Can this be
generalized? I.e. do any of the other sporadic simple groups
bear a similar relation to known smaller simple groups?

In [Cu] Curtis describes natural "geometric" generators for the Mathieu groups M12 and M24. M12 (the automorphism group of the extended ternary Golay code of length 12) is constucted from the group of a dodecahedron with certain additional "twists".

The Mathieu group M24 is also constucted geometrically, but in terms of a rather complicated figure (an icosatetrahedron) having 24 heptagonal faces, 56 vertices and 84 edges. If we consider just the vertices and edges, we have a non-planar graph that can be drawn (without crossing lines) on a surface of genus 3. Since this group and the extended binary Golay code are intimately related, it seems natural (in view of our construction) to consider whether there are natural geometric generators for M24 that can be viewed via the dodecahedron.

- Introduction
- Encoding
- Decoding
- An Example
- Generalizations
- Conclusions
- References