Binary Golay code ($G_{23}=[23,12,7]$)

The length-$23$ binary Golay code is the cyclic code over ${\mathbb{F}}_2$ generated byIt has dimension $12$, minimum Hamming distance $7$, and its radius-$3$ Hamming balls partition ${\mathbb{F}}_2^{23}$. Its parity extension has length $24$, dimension $12$, and minimum Hamming distance $8$.

// Target: algebra.bigb

The extended binary Golay code is the parity extension of the length-$23$ binary Golay code. It is a self-dual code and a doubly even code, with minimum Hamming distance eight. Its radius-three Hamming balls are disjoint but do not cover its Hamming space; it is not a perfect code.

For a binary symmetric matrix $A$ with $A^2=I$, the syndrome of an error $(p,q)$ relative to the column parity-check matrix $(I;A)$ is $s=p+qA$. An error of total Hamming weight at most three has at most one nonzero bit in one half. Test $s$, each $s+A_i$, $sA$, and each $sA+A_i$ for weights at most three, two, three and two respectively. These identify $(s,0)$, $(s+A_i,e_i)$, $(0,sA)$ and $(e_i,sA+A_i)$. For the extended binary Golay code, minimum Hamming distance eight guarantees that at most one such error exists.

Suppose a binary symmetric matrix $A$ satisfies $A^2=I$, has one row of Hamming weight eleven and eleven rows of Hamming weight seven, and every sum of two distinct rows has Hamming weight six. Then $(I\mid A)$ generates a self-dual code. Its rows have weights twelve or eight; their mutual orthogonality makes every generated word doubly even. A weight-four word $(u,uA)$ would have left-half weight one, two, three or four. The first two cases are excluded by the stated row weights; weight three would force $uA$ to be a unit vector and hence $u$ to be a row of $A$; weight four would force $uA=0$. Thus weight four is impossible and the minimum Hamming distance is eight.

The generator polynomial of a cyclic code defining the binary Golay code is $1+X+X^5+X^6+X^7+X^9+X^{11}$.

A root $\beta$ of the binary Golay generator polynomial has order $23$, and the Frobenius endomorphism shows that $\beta ,{\beta }^2,{\beta }^3,{\beta }^4$ are roots: $2^8\equiv 3(\mathrm{mod}23)$. The BCH bound gives minimum Hamming distance at least five. The circular autocorrelation of the binary Golay generator makes its parity extension doubly even, excluding original weights five and six. The generator itself has Hamming weight seven, proving that the distance is exactly seven.

// Target: algebra.bigb

The polynomial identity $(X+1)g(X)g^{\mathrm{rev}}(X)=X^{23}+1$, where $g^{\mathrm{rev}}(X)=X^{11}g(X^{-1})$, impliesEvery coefficient is the binary inner product of the coefficient vector of $g$ with one cyclic shift. Thus every such inner product is one. Appending a parity bit to the cyclic shifts gives mutually orthogonal weight-eight vectors, so orthogonal generators of doubly even codes applies.

// Target: algebra.bigb