Cyclic code

A length-$n$ cyclic code over ${\mathbb{F}}_q$ is an ideal of ${\mathbb{F}}_q[X]/(X^n-1)$. It is generated by a monic divisor of $X^n-1$.

A linear code is negacyclic if $(c_0,\dots ,c_{n-1})$ being a codeword implies that $(-c_{n-1},c_0,\dots ,c_{n-2})$ is a codeword. Polynomial identification makes it an ideal modulo $X^n+1$. For odd $n$, the substitution $X\mapsto -X$ gives a monomial equivalence of linear codes between negacyclic and cyclic codes.

A zero of a cyclic code is a polynomial root of its generator polynomial, taken in a splitting field. Every codeword, represented as a polynomial, vanishes there. For a repeated-root cyclic code, the multiplicity of a root must also be retained: ordinary evaluations alone need not determine the code.

A repeated-root cyclic code has length divisible by the characteristic of its field, so the polynomial $X^N-1$ has repeated factors. Its generator can involve powers of those factors. In characteristic two, length $2^t$ gives $X^{2^t}+1=(X+1{)}^{2^t}$.

// Target: algebra.bigb

If the generator polynomial of a cyclic code has distinct roots ${\alpha }_i$ with multiplicities $m_i$, a word belongs to the code exactly when $c^{[\ell ]}({\alpha }_i)=0$ for $0\le \ell <m_i$, where $c^{[\ell ]}$ is its Hasse derivative. The corresponding rows have entries $\left(\genfrac{}{}{0ex}{}{j}{\ell }\right){\alpha }_i^{j-\ell }$ for $j\ge \ell$ and zero otherwise. Expansion in a basis of the splitting field gives equations over the original finite field; an independent selection has rank ${\sum }_i{m}_i$.

For $N=2^t$, the binary cyclic codes are exactly the nested ideals generated by $(X+1{)}^j$ for $0\le j\le N$. They have dimensions $N-j$ and canonical check polynomials $(X+1{)}^{N-j}$. The endpoint ideals are the entire word space and the zero code.

// Target: algebra.bigb

For a cyclic code with monic generator $g\mid X^N-1$, the canonical check polynomial is $h=(X^N-1)/g$. A word $a$ belongs to the code exactly when $ah$ is zero modulo $X^N-1$, since cancellation in the polynomial ring turns this condition into $g\mid a$. The kernel condition alone allows additional polynomials: it is equivalent to $\gcd (\tilde{h},X^N-1)=h$. Requiring the monic divisor of the modulus singles out the canonical choice.

// Target: algebra.bigb

Over ${\mathbb{F}}_2$, $X^5-1=(X+1)(X^4+X^3+X^2+X+1)$ and the degree-four factor is irreducible: it has no linear root and is not divisible by the sole irreducible quadratic $X^2+X+1$. The four monic divisors give precisely four cyclic codes: the full five-dimensional space, the four-dimensional even-weight code, the one-dimensional repetition code, and the zero code. Their generator polynomials of a cyclic code are respectively $1$, $X+1$, $X^4+X^3+X^2+X+1$, and $X^5-1$.

The unique monic divisor $g(X)$ of $X^n-1$ generating a cyclic code is its generator polynomial. The code has dimension $n-\mathrm{deg}g$.

Let $\alpha$ be a root of the generator polynomial of a cyclic code $g(X)$. Every codeword $c(X)$ satisfies $c(\alpha )=0$, so a received word $r=c+e$ satisfies $r(\alpha )=e(\alpha )$. For a single-symbol error $e(X)=a{X}^j$, the evaluation $r(\alpha )=a{\alpha }^j$ identifies its value and position when the relevant powers of $\alpha$ are distinct.

For a binary cyclic code with defining zeros of a cyclic code $\alpha$ and ${\alpha }^3$, a single error in coordinate $j$ has polynomial $X^j$ and syndromes $S_1={\alpha }^j$, $S_3={\alpha }^{3j}$. If $S_1\ne 0$ and $S_3=S_1^3$, recover $j$ from the exponent of $S_1$, flip that coordinate, and verify that the resulting polynomial vanishes at both roots. When the linear code has minimum Hamming distance at least five, this verified correction is the unique codeword within two errors. The syndrome relation alone should not replace checking the corrected word.

The dual of a cyclic code is cyclic. If $g(X)h(X)=X^n-1$, then the dual generator is the monic reciprocal polynomial $h^{\ast }(X)$.

Over ${\mathbb{F}}_2$,Its eight monic divisors generate the eight cyclic codes of length seven: the whole-space, even-weight, two Hamming, two simplex, repetition, and zero codes.

Given a primitive $n$th root $\alpha$, a BCH code of design distance $\delta$ has a generator polynomial vanishing at $\delta -1$ consecutive powers ${\alpha }^b,\dots ,{\alpha }^{b+\delta -2}$.

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

For odd $n$, multiplication by two permutes the residues modulo $n$. Its orbit through $i$ is the binary cyclotomic coset modulo an odd integer. If $\alpha$ has order $n$ in a finite field whose field characteristic is two, the Frobenius automorphism sends ${\alpha }^i$ to ${\alpha }^{2i}$. Hence the minimal polynomial of an algebraic element ${\alpha }^i$ over ${\mathbb{F}}_2$ is ${\prod }_{j\in C_i}(X-{\alpha }^j)$. Its coefficients are fixed by Frobenius and lie in ${\mathbb{F}}_2$, and its degree is the orbit size. Thus a binary cyclic code containing one defining zero of a cyclic code must contain the full orbit as zeros.

For error locations $i_1,\dots ,i_{\nu }$ in a cyclic code with primitive root $\alpha$, the error locator polynomial is $\sigma (Z)={\prod }_h(1-{\alpha }^{i_h}Z)$. Its roots encode the error positions.

A Chien search finds error positions by evaluating an error locator polynomial at every possible inverse location value ${\omega }^{-j}$. A zero identifies coordinate $j$. Using the recurrence between successive powers of $\omega$ avoids recomputing all monomials from scratch.

For errors $E_i$ at distinct nonzero locations $X_i$, the evaluator associated with syndromes $S_{\ell }={\sum }_i{E}_i{X}_i^{b+\ell }$ is $\Omega (z)={\sum }_i{E}_i{X}_i^b{\prod }_{h\ne i}(1-X_{h}z)$. Its degree is smaller than the number of errors. Together with the error locator polynomial it gives the Reed-Solomon key equation and the Forney algorithm for error magnitudes.

For distinct error locations and the syndrome convention $S_{\ell }={\sum }_i{E}_i{X}_i^{b+\ell }$, the displayed formula recovers the error magnitudes from the error evaluator polynomial and error locator polynomial. At $z=X_i^{-1}$, the evaluator is $E_i{X}_i^b{\prod }_{h\ne i}(1-X_h/X_i)$, whereas the locator's formal derivative is $-X_i{\prod }_{h\ne i}(1-X_h/X_i)$. Their quotient gives the formula; the denominator is nonzero because the locations are distinct.

// Target: polynomial.bigb

The minimum distance of a BCH code is at least its design distance. A hypothetical word of smaller weight yields a square Vandermonde system from the consecutive-root equations; its support elements are distinct, so the determinant is nonzero and every word coefficient must vanish.