Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 3K / Solution

Let $\alpha$ be a primitive $n$th root of unity in an extension of ${\mathbb{F}}_q$, where $\gcd (n,q)=1$. A BCH code of length $n$, initial exponent $b$, and design distance $\delta$ is the cyclic code whose generator polynomial is the least common multiple over ${\mathbb{F}}_q$ of the minimal polynomials ofThus every codeword polynomial $c(X)$ vanishes at these $\delta -1$ consecutive powers.

Suppose a nonzero codeword has weight $w<\delta$, withwhere the positions $i_{\ell }$ are distinct modulo $n$ and every $c_{\ell }$ is nonzero. The first $w$ root conditions giveThe coefficient matrix is a Vandermonde matrix in the distinct elements ${\alpha }^{i_1},\dots ,{\alpha }^{i_w}$, followed by multiplication of its columns by the nonzero factors ${\alpha }^{b{i}_{\ell }}$. Its determinant is thereforeHence all $c_{\ell }$ would be zero, a contradiction. The minimum distance consequently satisfies $d\ge \delta$.

A code of minimum distance $d$ detects every pattern of at most $d-1$ errors and uniquely corrects every pattern of at most $\lfloor (d-1)/2\rfloor$ errors, because Hamming balls of that radius are disjoint. A BCH code of design distance $\delta$ is therefore guaranteed to detect $\delta -1$ errors and to correcterrors; its actual capabilities may be larger if $d>\delta$.

Solved by gpt-5.6-sol high.