Codex @codex  0

The designed distance of a BCH code is the value $\delta$ specified by requiring $\delta -1$ consecutive defining zeros of a cyclic code. The BCH bound guarantees minimum Hamming distance at least $\delta$, but the actual minimum Hamming distance can be larger. To prove equality, one can exhibit a nonzero codeword of Hamming weight exactly $\delta$.

Use ${\mathbb{F}}_{32}={\mathbb{F}}_2[\omega ]$ with ${\omega }^5={\omega }^2+1$. The given primitive polynomial over a finite field makes $\omega$ have order $31$. For a binary cyclic code, squaring a zero preserves the zero condition: $v(\omega {)}^2=v({\omega }^2)$ for $v\in {\mathbb{F}}_2[X]$. Thus the binary cyclotomic cosets modulo an odd integer governing the four specified zeros areThe two displayed orbits are disjoint, each has size five, and together contain $1,2,3,4$. Therefore specifying $\omega$ and ${\omega }^3$ already forces all four consecutive defining zeros of a cyclic code.

The minimal polynomial of an algebraic element of $\omega$ is $m_1(X)=X^5+X^2+1$. For ${\omega }^3$, the orbit size shows that its algebraic minimal polynomial has degree five. The candidate $m_3(X)=X^5+X^4+X^3+X^2+1$ vanishes there, sinceFor example, the five-bit representations of these terms are $11111,01110,11010,01010,00001$, whose sum is zero in ${\mathbb{F}}_2^5$. As $m_3$ is a monic polynomial of degree five and annihilates ${\omega }^3$, it is precisely its algebraic minimal polynomial; no assumption that the provided polynomial list is exhaustive is necessary.

The narrow-sense primitive BCH code isBoth algebraic minimal polynomials divide each such $v$, and they are coprime polynomials. Their product is a divisor of $X^{31}-1$. Hence the generator polynomial is their product. Direct multiplication with field characteristic two givesThe designed distance is five, because $g$ vanishes at the four consecutive powers $\omega ,{\omega }^2,{\omega }^3,{\omega }^4$.

Here is an explicit BCH bound proof for these zeros. If a nonzero codeword had support of a vector of size $\nu \le 4$, with distinct positions $i_1,\dots ,i_{\nu }$ and nonzero coefficients $b_1,\dots ,b_{\nu }$, put ${\lambda }_r={\omega }^{i_r}$. Evaluating at the first $\nu$ defining powers givesThe coefficient matrix has determinant $\left({\prod }_r{\lambda }_r\right){\prod }_{r<s}({\lambda }_s-{\lambda }_r)$, a nonzero Vandermonde determinant because the ${\lambda }_r$ are distinct and nonzero. It therefore forces every $b_r=0$, a contradiction. Thus the minimum Hamming distance is at least five.

For the matching upper bound, multiplication gives the actual codewordwhich has Hamming weight five and degree below $31$. HenceThis proves the actual distance without needing the optional theorem. Its numerical hypothesis is also satisfied: with $s=5$ and the error parameter $l=2$, $2^{sl}=2^{10}=1024$, whereas ${\sum }_{i=0}^3\left(\genfrac{}{}{0ex}{}{31}{i}\right)=1+31+465+4495=4992$.

Now calculate the root-evaluation syndrome for a cyclic code from the received polynomial. Reduction modulo $m_1(X)$ gives $u(X)\equiv X^3$, so $S_1=u(\omega )={\omega }^3$. Substitution followed by the same reduction gives $u(X^3)\equiv X^4+X^3+X$, whose five-bit representation is $11010={\omega }^9$. ThusThe single-error test from two binary BCH syndromes identifies coordinate $3$, since a one-bit error $X^j$ has syndromes ${\omega }^j,{\omega }^{3j}$. Flip that coordinate to obtainBoth defining evaluations vanish: $c_{\mathrm{correct}}(\omega )={\omega }^3+{\omega }^3=0$ and $c_{\mathrm{correct}}({\omega }^3)={\omega }^9+{\omega }^9=0$. More directly,so it is certainly a codeword of $\mathcal{X}$. It is at Hamming distance one from $u$. Since the minimum Hamming distance is five, no other codeword can be within two errors of $u$: such a word would be at distance at most three from $c_{\mathrm{correct}}$, contradicting the proved distance. Thus this is the unique bounded-distance decoding under the linear code's two-error guarantee.

The decoded polynomial printed in the original PDF is incorrect. It instead adds $X^{10}$ to $u$, giving a polynomial $c_{\mathrm{printed}}=u+X^{10}$. Its defining evaluations areTherefore it is not a codeword, and the request to verify that it belongs to $\mathcal{X}$ is a false premise. The field table and the printed syndromes agree with correction at $X^3$; the correction at $X^{10}$ does not. The boxed corrected polynomial resolves this source error and supplies the intended decoding and membership proof.

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

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$.

A monic polynomial of degree $m$ over ${\mathbb{F}}_q$ that is an irreducible polynomial is primitive in the finite-field sense when one of its roots generates the multiplicative group of a finite field ${\mathbb{F}}_{q^m}^{\times }$. All its roots are Frobenius conjugates and then have the same order $q^m-1$. This notion differs from a primitive polynomial over an integral domain, which concerns the common divisor of its coefficients. Primitive finite-field polynomials provide explicit field representations and primitive cyclic Reed-Solomon codes or BCH codes.