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 212=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 210.33.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.