Binary Golay Code - Constructions

Constructions

1. Lexicographic code: Order the vectors in V lexicographically (i.e., interpret them as unsigned 24-bit binary integers and take the usual ordering). Starting with w₁ = 0, define w₂, w₃, ..., w₁₂ by the rule that w_n is the smallest integer which differs from all linear combinations of previous elements in at least eight coordinates. Then W can be defined as the span of w₁, ..., w₁₂.
2. Quadratic residue code: Consider the set N of quadratic non-residues (mod 23). This is an 11-element subset of the cyclic group Z/23Z. Consider the translates t+N of this subset. Augment each translate to a 12-element set S_t by adding an element ∞. Then labeling the basis elements of V by 0, 1, 2, ..., 22, ∞, W can be defined as the span of the words S_t together with the word consisting of all basis vectors. (The perfect code is obtained by leaving out ∞.)
3. As a Cyclic code: The perfect G₂₃ code can be constructed via factorization of, it is the code generated by
4. From the Steiner System S(5,8,24), consisting of 759 subsets of a 24-set. If one interprets each subset as a 0-1-codeword of length 24 (and hence Hamming-weight 8), these are the "octads" in the binary Golay code. The entire Golay code can be obtained be taking repeatetly symmetric differences of subsets, i.e. binary addition. An easier way to write down the Steiner system resp. the octads is the Miracle Octad Generator of R. T. Curtis, that uses a particular 1:1-correspondence between the 35 partitions of an 8-set and the 35 partitions of the finite vector space into 4 planes. Nowadays often the compact approach of Conway's hexacode, that uses a 4×6 array of square cells, is used.
5. Winning positions in the mathematical game of Mogul: a position in Mogul is a row of 24 coins. Each turn consists of flipping from one to seven coins such that the leftmost of the flipped coins goes from head to tail. The losing positions are those with no legal move. If heads are interpreted as 1 and tails as 0 then moving to a codeword from the extended binary Golay code guarantees it will be possible to force a win.
6. A generator matrix for the binary Golay code is I A, where I is the 12×12 identity matrix, and A is the complement of the adjacency matrix of the icosahedron.