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 byIt has dimension , minimum Hamming distance , and its radius- Hamming balls partition . Its parity extension has length , dimension , and minimum Hamming distance .
// Target: algebra.bigb
Extended binary Golay code 2026-10-14
The extended binary Golay code is the parity extension of the length- 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.
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 30 4 Solution Created 2026-10-03 Updated 2026-10-14
Work over the finite field . The given factorization shows that divides , so it generates a length- cyclic code . Since , the vectors represented byform 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 thatare 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, useAll 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:
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 1 3K i Solution Created 2026-09-24 Updated 2026-09-25
For a binary block code, is the common length of its codewords, is the number of codewords, andis its minimum Hamming distance.
The parity extension isEvery extended word has even Hamming weight. The distance between two words increases by one exactly when their original distance is odd, so
Past exam of the mathematics course of the University of Cambridge 2024 ii Paper 2 3K c Solution Created 2026-09-24 Updated 2026-10-03
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.
Past exam of the mathematics course of the University of Cambridge 2026 ii Paper 1 11H b i Solution Created 2026-09-24 Updated 2026-09-25