Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 11K (Coding and Cryptography)

A binary cyclic code of odd length $n$ is an ideal of ${\mathbb{F}}_2[X]/(X^n-1)$. For a primitive $n$th root $\alpha$, its defining set is the set of powers ${\alpha }^i$ at which every code polynomial vanishes. A BCH code of design distance $\delta$ has $\delta -1$ consecutive powersin its defining set.

If a nonzero codeword had weight $w<\delta$, write it as $c(X)={\sum }_{j=1}^w{c}_j{X}^{i_j}$. Evaluation at $w$ consecutive defining roots gives a homogeneous Vandermonde system in the nonzero values $c_j{\alpha }^{b{i}_j}$. Its determinant is nonzero because the support elements ${\alpha }^{i_j}$ are distinct. Thus every $c_j$ would vanish, a contradiction. This proves the BCH bound

The defining roots are $\alpha ,{\alpha }^2,{\alpha }^3,{\alpha }^4$. Frobenius conjugacy gives the two binary cyclotomic classesHencewhile ${\alpha }^3$ has order five andThe generator is their least common multiple:

For received polynomial $r$, define the syndromes $S_j=r({\alpha }^j)$. If the error positions are $i_1,\dots ,i_{\nu }$, the error locator polynomial isIts roots are ${\alpha }^{-i_h}$, and its coefficients satisfy the Newton syndrome recurrences. For this design-distance-five code, bounded-distance decoding seeks degree at most two.

For $r(X)=1+X+X^7$, reduction using ${\alpha }^4=\alpha +1$ givesThe degree-two syndrome recurrence yieldsChecking the fifteen nonzero field elements shows that this polynomial has no root in ${\mathbb{F}}_{16}$. It therefore cannot be expressed as $(1-{\alpha }^{i}Z)(1-{\alpha }^{j}Z)$ for error positions $i,j$. The received word lies outside the code's two-error decoding radius, so the error positions cannot be determined uniquely by this decoder.