A root of the binary Golay generator polynomial has order , and the Frobenius endomorphism shows that are roots: . 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
Binary Golay code 2026-10-14
The length- binary Golay code is the cyclic code over generated by
It has dimension , minimum Hamming distance , and its radius- Hamming balls partition . Its parity extension has length , dimension , and minimum Hamming distance .
// Target: algebra.bigb
Work over the finite field . The given factorization shows that divides , so it generates a length- cyclic code . Since , the vectors represented by
form a basis: their distinct leading degrees prove their linear independence, and every multiple of representing a polynomial of degree below has a multiplier of degree at most . Hence is a binary linear code of dimension , containing codewords. The generator has Hamming weight seven, so the minimum Hamming distance of a linear code satisfies .
The BCH bound used here is the following consecutive-root theorem. If a length- cyclic code over , with relatively prime to , has a generator polynomial of a cyclic code vanishing at for a primitive th root , then its minimum Hamming distance is at least .
Choose a root of in an algebraic closure of . The factorization implies , while in , so . As is prime, has order . The Frobenius endomorphism preserves the roots of a polynomial with coefficients in : . Thus every is a root. In particular, shows that
are roots of . These four consecutive roots give by the BCH bound. A further argument is needed to exclude weights five and six.
Put . Cancelling in the supplied factorization gives . In the quotient ring , is invertible and every cyclic shift of equals . Since ,
The coefficient of in this circular product is , the binary inner product of the coefficient vector of with a cyclic shift of itself. Every coefficient of is one. The circular autocorrelation of the binary Golay generator therefore implies that all pairs of basis rows , including equal rows, satisfy
Each has Hamming weight seven. Append its parity bit, which is one, and write . The extended rows have Hamming weight eight and satisfy . Their linear span is precisely the parity extension of , because the appended coordinate is the linear functional equal to the sum of all coordinates.
These extended generators produce a doubly even code. To prove this rather than assume it, use
All the extended generators have weights divisible by four. A sum of previous generators is orthogonal to the next generator, so the intersection size in this identity is even. Induction proves that every word in has Hamming weight divisible by four; this is the orthogonal generators of doubly even codes argument.
An original word of weight five acquires a parity bit and has extended weight six, while a word of weight six acquires a zero parity bit and still has extended weight six. Both contradict divisibility by four. Together with the BCH bound and the weight-seven generator, this completes the BCH and parity-extension proof of the binary Golay distance:
Its radius-three Hamming balls are disjoint, and their volume is
There are such balls, so they contain words, exactly the size of the ambient binary cube. They therefore cover the cube, with every word in exactly one ball. Hence
For a binary block code, is the common length of its codewords, is the number of codewords, and
is its minimum Hamming distance.
The parity extension is
Every extended word has even Hamming weight. The distance between two words increases by one exactly when their original distance is odd, so
Yes, for a binary code. Correcting errors requires minimum distance at least . Apply the parity extension: append to each word the bit that makes its total weight even. Every odd distance increases by one and every even distance is unchanged, so the extended minimum distance is at least . It therefore detects every pattern of at most errors.
By parity extension, each code keeps size , gains length , and has distance . Extension is injective. A common extended word punctures to a word in , so only the zero and all-one words occur; both extend to and .