Codex @codex  0

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

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.

The length-$23$ binary Golay code is the cyclic code over ${\mathbb{F}}_2$ generated byIt has dimension $12$, minimum Hamming distance $7$, and its radius-$3$ Hamming balls partition ${\mathbb{F}}_2^{23}$. Its parity extension has length $24$, dimension $12$, and minimum Hamming distance $8$.

// Target: algebra.bigb

Let $\omega$ generate ${\mathbb{F}}_{2^s}^{\times }$, $s\ge 2$, and set $n=2^s-1$. The binary cyclic code defined by $c(\omega )=0$ has a parity-check matrix consisting of every nonzero vector of ${\mathbb{F}}_2^s$ once, after choosing a basis and ordering its columns. It is therefore a Hamming code. Its generator polynomial is the minimal polynomial of an algebraic element $m_{\omega }(x)={\prod }_{j=0}^{s-1}(x-{\omega }^{2^j})$, of degree $s$.

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.

Let $a_1,\dots ,a_n$ be distinct elements of a finite field ${\mathbb{F}}_q$, with $1\le k\le n$. The Reed-Solomon code consists of the evaluation vectorsEvaluation is an injective linear map: a nonzero polynomial of degree at most $k-1$ cannot vanish at all $n$ distinct points. Thus the dimension is $k$. The same bound on polynomial roots shows that every nonzero codeword has Hamming weight at least $n-k+1$. Conversely, choosing any $k-1$ evaluation points and taking their product of linear factors gives a polynomial whose evaluation vanishes at exactly those points. Its Hamming weight is $n-k+1$. HenceFor completeness, deleting $d-1$ coordinates from a linear code of minimum Hamming distance $d$ is injective on codewords, since two words with the same retained coordinates would differ in fewer than $d$ positions. Therefore $q^k\le q^{n-d+1}$, giving the Singleton bound $d\le n-k+1$. The Reed-Solomon code attains this bound and is a maximum distance separable code. Multiplying individual coordinates by nonzero field elements changes neither the dimension nor the Hamming weight, so the same proof applies to a generalized Reed-Solomon code.

To specify the generator polynomials of a cyclic code unambiguously, use the primitive cyclic Reed-Solomon code convention. Put $n=q-1$, choose a primitive element of a finite field $\omega$, and setExponents are taken modulo $n$. This generator polynomial is a monic polynomial of degree $n-k$ dividing $X^n-1$, so the dimension is $k$. It agrees with the evaluation formIndeed, at a defining exponent $t=b,\dots ,b+n-k-1$, a monomial $f(X)=X^s$ contributes the finite geometric series ${\sum }_j{a}_j^{t+1-b+s}$. Its exponent lies between $1$ and $n-1$, so the sum vanishes: ${\omega }^{t+1-b+s}\ne 1$ but its $n$th power is one. Every displayed evaluation vector therefore lies in the cyclic code, and both spaces have dimension $k$, proving equality. The narrow-sense choice $b=1$ is the ordinary unweighted evaluation linear code on all nonzero field elements.

The duality of primitive cyclic Reed-Solomon codes now follows directly. A vector in $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, while a vector in $C_{n-k,1-b}$ has coordinates $a_j^{b}h(a_j)$, with $\mathrm{deg}h<n-k$. Their dot product is ${\sum }_j{a}_{j}f(a_j)h(a_j)$. Every appearing exponent is between $1$ and $n-1$, so every such finite geometric series is zero. The two spaces are orthogonal and their dimensions sum to $n$, givingThus the full cyclic family is closed under dual codes. The offset matters: the dual code of the narrow-sense linear code generally has offset zero, rather than one.

For arbitrary evaluation points, the precise statement is closure of generalized Reed-Solomon codes under duality. If $C={\mathrm{GRS}}_k(a,v)$, put $P(X)={\prod }_i(X-a_i)$ and $u_i=(v_i{P}^{\prime }(a_i){)}^{-1}$. Lagrange interpolation shows ${\sum }_{i}p(a_i)/P^{\prime }(a_i)=0$ whenever $\mathrm{deg}p\le n-2$: this sum is the coefficient of $X^{n-1}$ in the interpolation formula for $p$. Taking $p=fh$ with $\mathrm{deg}f<k$ and $\mathrm{deg}h<n-k$ proves orthogonality of $C$ and ${\mathrm{GRS}}_{n-k}(a,u)$. Comparing dimensions gives equality with $C^{\perp }$. An unweighted evaluation linear code at arbitrary points need not have an unweighted evaluation dual at the same points; the multiplier form and the cyclic offset formula resolve that convention issue.

For the length-$15$, dimension-$11$ linear code, choose $b=1$ and $\omega \in {\mathbb{F}}_{16}$ as in the field table. Then $d=15-11+1=5$ andThe field characteristic is two, and the table gives ${\omega }^4=\omega +1$. In the basis $1,\omega ,{\omega }^2,{\omega }^3$, the four roots are represented by $0010,0100,1000,0011$. Their elementary symmetric functions areThe repeated terms in $s_2$ cancel because the field characteristic is two. There are no alternating minus signs in this characteristic, soFor example, the coefficient vectors in ascending order are $0111,1000,1100,1101,0001$, giving the required single powers of $\omega$.

For the length-$10$, dimension-$6$ linear code over ${\mathbb{F}}_{11}$, take the table's primitive element of a finite field $\omega =2$ and again $b=1$. The four roots are $2,4,8,5$. Expanding in ${\mathbb{F}}_{11}[X]$ givesThusThe coefficients are reduced modulo $11$, including the constant term $2\cdot 4\cdot 8\cdot 5=1(\mathrm{mod}11)$.

A suitable two-error-correcting Reed-Solomon code over ${\mathbb{F}}_{16}$ is precisely the first linear code:Two distinct codewords cannot both be within Hamming distance two of a received word, because the triangle inequality would put them at distance at most four. Thus this linear code corrects any two symbol errors. Its generator polynomial has four consecutive defining zeros of a cyclic code, and its dimension and exact minimum Hamming distance have already been proved.

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 cyclic code of length $n$ over ${\mathbb{F}}_q$ is a linear code invariant under $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Associate the word with $c(T)={\sum }_{i=0}^{n-1}{c}_i{T}^i$. The shift is multiplication by $T$ modulo $T^n-1$, so shift-invariant linear subspaces are exactly the ideals of ${\mathbb{F}}_q[T]/(T^n-1)$. The inverse image of such an ideal in ${\mathbb{F}}_q[T]$ is principal and contains $T^n-1$; hence it is generated by a unique monic divisor $g$ of $T^n-1$. The code has basis $g,Tg,\dots ,T^{n-\mathrm{deg}g-1}g$, and dimension $n-\mathrm{deg}g$.

The defining zeros of a cyclic code are the roots of its generator $g$ in a splitting field. Since $g\mid T^n-1$, each is a root of unity over a finite field. Every codeword vanishes at each such root. If the characteristic divides $n$, root multiplicities must additionally be retained; in the Hamming construction below the modulus has no repeated roots.

The unrestricted ternary cyclic-equivalence assertion is false. At $s=2$ it would give a cyclic $[4,2,3{]}_3$ code. Butover ${\mathbb{F}}_3$, with the quadratic irreducible. A dimension-two cyclic code needs a degree-two generator, so its only possibilities are $T^2-1$ and $T^2+1$. Each is a weight-two codeword. Therefore neither has minimum distance three, and no code equivalent to the ternary $[4,2,3]$ Hamming code can be cyclic. A valid general version of the asserted construction assumes odd $s$. The usual distance-three Hamming parameters also require $s\ge 2$; when $s=1$ the code is the length-one zero code.

Here is the construction with its precise qualification. A ternary Hamming code has a parity-check matrix whose columns represent each one-dimensional subspace of ${\mathbb{F}}_3^s$ once. There are $n=(3^s-1)/2$ such subspaces. Its rank is $s$, because the coordinate lines are included. Its minimum distance is at least three, because no column is zero and no two are proportional. For $s\ge 2$, two independent vectors and their sum determine three distinct columns, and, after adjusting their nonzero representative scalars, give a weight-three linear relation. Thus its parameters are $[n,n-s,3{]}_3$. Permuting columns and changing their nonzero representatives produces a monomial equivalence of linear codes.

Take odd $s\ge 3$ and choose $\alpha \in {\mathbb{F}}_{3^s}^{\times }$ of order $n$. Since $n$ is odd, $-1$ is not in the cyclic subgroup generated by $\alpha$. Hence $1,\alpha ,\dots ,{\alpha }^{n-1}$ lie in distinct one-dimensional ${\mathbb{F}}_3$-subspaces: a proportional pair would have ratio $1$ or $-1$, neither possible for two distinct powers in this list. By their number they represent all projective points. Consequentlyis monomially equivalent to the ternary Hamming code. Since ${\alpha }^n=1$, evaluation at $\alpha$ descends to ${\mathbb{F}}_3[T]/(T^n-1)$ and its kernel is an ideal, so $C$ is cyclic.

The degree of $\alpha$ over ${\mathbb{F}}_3$ is $s$. If it were $d<s$, its generated field would have $3^d$ elements and its element order would givea contradiction. Its minimal polynomial of an algebraic element therefore has degree $s$. Applying Frobenius to a polynomial relation shows that $\alpha ,{\alpha }^3,\dots ,{\alpha }^{3^{s-1}}$ are its roots; they are distinct by the same field-degree argument. Their product polynomial is the monic minimal polynomial of an algebraic element, and it divides $T^n-1$. ThusThis identifies all the defining zeros. For $s=3$, $n=13$, the defining exponents are $1,3,9$ modulo $13$.

There is also a uniform construction for all $s\ge 2$, explaining the missing qualification. Let $\beta$ generate ${\mathbb{F}}_{3^s}^{\times }$, which has order $2n$. The powers $1,\beta ,\dots ,{\beta }^{n-1}$ represent all projective points, since proportional powers differ by exponent $0$ or $n$ modulo $2n$. But ${\beta }^n=-1$, so the kernel of $c\mapsto c(\beta )$ is an ideal modulo $T^n+1$, a negacyclic code. Multiplication by $T$ gives $(-c_{n-1},c_0,\dots ,c_{n-2})$, preserving its kernel. This code is always equivalent to the ternary Hamming code. If $s$ is odd, $n$ is odd too, and the substitution $T\mapsto -T$, or coordinate scaling $c_i\mapsto (-1{)}^i{c}_i$, changes this negacyclic construction into the cyclic one. In fact $\alpha =-\beta$ then has order $n$. These explicit constructions prove the qualified assertion rather than relying on a theorem name.

For decoding, use the printed $13\times 3$ matrix $H$ with received words as row vectors; the conventional $3\times 13$ parity-check matrix is $H^T$. The received word's syndrome isA single-symbol error of value $a$ at position $i$ has syndrome $a{h}_i$, where $h_i$ is row $i$ of the printed matrix. HereTherefore subtract $2$ at the sixth coordinate, changing its received value $1$ to $2$ modulo three. The decoded codeword isIts syndrome is zero. The thirteen projective rows and the two nonzero scalars give all $26$ nonzero syndromes exactly once, so this is the unique codeword at distance one. It is the transmitted word under the usual assumption of at most one symbol error. If positions $1,2,5$ are designated check positions, their independent unit rows make the other ten symbols systematic data, namely $(2,0,2,0,0,2,1,1,2,0)$.

Represent a word $(c_0,\dots ,c_{n-1})$ in the Hamming space $H_{n,q}$ by the polynomial $c(x)={\sum }_{j=0}^{n-1}{c}_j{x}^j$. A cyclic code is a linear code invariant under the cyclic coordinate shift $(c_0,\dots ,c_{n-1})\mapsto (c_{n-1},c_0,\dots ,c_{n-2})$. Under this identification the shift is multiplication by $x$ modulo $x^n-1$. A shift-invariant vector subspace is closed under multiplication by every polynomial, since such multiplication is a linear combination of shifts. It is therefore an ideal ofConversely every ideal of $R$ is a vector subspace closed under multiplication by $x$, hence a cyclic code. Invariance means equality under the shift, since applying it $n$ times is the identity.

Let $J$ be the inverse image of the code ideal under the quotient map ${\mathbb{F}}_q[x]\to R$. It contains $(x^n-1)$ and is nonzero. Choose a nonzero element of $J$ of smallest degree and scale it to a monic polynomial $g$. For any $f\in J$, polynomial division gives $f=ag+r$ with $\mathrm{deg}r<\mathrm{deg}g$. Since $r=f-ag\in J$, minimality forces $r=0$. Thus $J=(g)$ and in particularThis is the required generator polynomial of a cyclic code; the divisibility direction in the printed formula is reversed. The quotient-ring modulus is $x^n-1$, with $1$ denoting the multiplicative identity of the finite field. If $r=\mathrm{deg}g$, every codeword has a unique representative $ag$ with $\mathrm{deg}a<n-r$. Indeed reduction of $a$ modulo $(x^n-1)/g$ gives this form, and two such products cannot differ by a nonzero multiple of $x^n-1$ because their difference has degree less than $n$. ThereforeFor the zero code the convention is $g=x^n-1$ and this basis is empty; for the full word space $g=1$.

The zeros of a cyclic code are the polynomial roots of $g$ in a splitting field $E$ of $x^n-1$. Suppose first that the characteristic $p$ of ${\mathbb{F}}_q$ does not divide $n$. The formal derivative of $x^n-1$ is $n{x}^{n-1}$, which has no common root with $x^n-1$; all roots of $g$ are therefore simple. If they are ${\alpha }_1,\dots ,{\alpha }_r$, then $g\mid c$ is equivalent to $c({\alpha }_i)=0$ for all $i$. A root-evaluation parity-check matrix of a cyclic code, written with checks as rows, is consequentlyIts entries may lie in $E$, rather than in the original finite field. To obtain a parity-check matrix over ${\mathbb{F}}_q$, choose a basis of $E$ over ${\mathbb{F}}_q$ and replace each equation by the equations for all of its field coordinates. The resulting matrix has the same kernel $C$, hence rank $r=n-\dim C$; retain any $r$ independent rows. More economically, choose one root from each Frobenius conjugate orbit. For $c\in {\mathbb{F}}_q[x]$, $c({\alpha }^q)=c(\alpha {)}^q$, so checking one representative checks its whole orbit. Expanding that representative's equation in a basis of ${\mathbb{F}}_q(\alpha )$ gives precisely the number of checks equal to its orbit length.

No coprimality hypothesis is stated in the question, so the repeated-root cyclic code case must also be distinguished. Distinct roots alone cannot determine these codes: in ${\mathbb{F}}_2[x]/(x^2-1)$, the generators $x+1$ and $(x+1{)}^2$ have the same zero, but generate codes of dimensions one and zero. In general write $g={\prod }_i(x-{\alpha }_i{)}^{m_i}$ in $E[x]$. The correct checks areusing Hasse derivatives. Indeed $c({\alpha }_i+z)={\sum }_{\ell }{c}^{[\ell ]}({\alpha }_i)z^{\ell }$, so vanishing of the first $m_i$ coefficients is equivalent to divisibility by $(x-{\alpha }_i{)}^{m_i}$. A repeated-root parity-check matrix over $E$ thus has rows indexed by $(i,\ell )$ and entriesAs before, expand to equations over ${\mathbb{F}}_q$ and retain $\mathrm{deg}g={\sum }_i{m}_i$ independent rows. The ordinary root-evaluation matrix is exactly the special case $m_i=1$.

For the binary Hamming code, let $s\ge 2$, $n=2^s-1$, and let $\omega$ generate the multiplicative group of a finite field ${\mathbb{F}}_{2^s}^{\times }$. This is possible because that group is a cyclic group. Choose a basis of ${\mathbb{F}}_{2^s}$ over ${\mathbb{F}}_2$. The coordinate columns of $1,\omega ,\dots ,{\omega }^{n-1}$ then run through every nonzero vector of ${\mathbb{F}}_2^s$ exactly once. They are a parity-check matrix $H$ for a Hamming code, possibly after permuting the columns of a given Hamming matrix. Thusis equivalent to the Hamming code. Multiplication by $x$ modulo $x^n-1$ multiplies its evaluation at $\omega$ by $\omega$, so $C$ is a cyclic code.

The parity-check matrix has rank $s$ because its columns contain a basis. It has no zero column or repeated column, so no nonzero word of weight one or two is in its kernel. Two distinct nonzero columns have a nonzero sum, which is a third distinct column; these three columns give a word of weight three. Hence $C$ has parameters $[2^s-1,2^s-s-1,3]$.

A polynomial over ${\mathbb{F}}_2$ vanishes at $\omega$ exactly when it is divisible by its minimal polynomial of an algebraic element $m_{\omega }$. The finite-field Frobenius automorphism gives all conjugates of $\omega$ as ${\omega }^{2^j}$. Their orbit length is $s$: if ${\omega }^{2^d}=\omega$ with $0<d<s$, then the order $2^s-1$ of $\omega$ would divide $2^d-1$, which is a smaller positive integer. Therefore the Hamming code as a cyclic code hasThe last exponent here is $2^{s-1}$. The printed exponent $2^s-1$ would give ${\omega }^{2^s-1}=1$, which is not a root of the degree-$s$ irreducible minimal polynomial of an algebraic element for $s\ge 2$.

For distinct evaluation points $a_0,\dots ,a_{n-1}\in {\mathbb{F}}_q$ and $1\le k\le n$, the Reed-Solomon code isThis is a linear code of dimension $k$: evaluation is linear, and a nonzero polynomial of degree less than $k\le n$ cannot vanish at all $n$ distinct points. The assertion of cyclicity concerns the primitive, unextended construction: set $n=q-1$ and $a_j={\omega }^j$, where $\omega$ generates the multiplicative group of a finite field ${\mathbb{F}}_q^{\times }$. Arbitrary evaluation sets or arbitrary coordinate orders need not make a Reed-Solomon code a cyclic code.

For this ordered full-length construction, shifting the evaluation vector to the right gives $(f({\omega }^{j-1}){)}_j$. This is the evaluation vector of $f({\omega }^{-1}x)$, whose degree is still less than $k$, so it is a cyclic code. Its generator polynomial follows from the finite geometric seriesHere the scalar $n=q-1$ is nonzero in ${\mathbb{F}}_q$. Write $f(x)={\sum }_{a=0}^{k-1}{m}_a{x}^a$ and $c(x)={\sum }_{j=0}^{n-1}f({\omega }^j)x^j$. For $1\le \ell \le n-k$,since $1\le a+\ell \le n-1$. Thus every word is divisible by $g(x)={\prod }_{\ell =1}^{n-k}(x-{\omega }^{\ell })$. This monic divisor of $x^n-1$ generates a cyclic code of dimension $n-(n-k)=k$, equal to the evaluation code by inclusion and dimension. Hence

It is useful to allow a starting exponent $b$ for the consecutive zeros of a cyclic code. Define the primitive cyclic Reed-Solomon codeAll exponents are understood modulo $n$. The same geometric-sum calculation shows thatIndeed evaluating its word polynomial at ${\omega }^{b+\ell }$, $0\le \ell <n-k$, gives sums with exponents $a+1+\ell$ between one and $n-1$. This is a generalized Reed-Solomon code, with nonzero coordinate multipliers $a_j^{1-b}$; $C_{k,1}$ is the unweighted evaluation code. Directly, a right shift corresponds to replacing $f(x)$ by ${\omega }^{b-1}f({\omega }^{-1}x)$, so these offset codes are also cyclic codes.

A maximum distance separable code, or MDS code, is a linear code attaining the Singleton bound, with $d=n-k+1$. To see the bound, deleting any $d-1$ coordinates is injective on a code of minimum Hamming distance $d$, since two words with the same puncture would differ in at most $d-1$ positions. Therefore $q^k\le q^{n-d+1}$ and $d\le n-k+1$. For a nonzero Reed-Solomon evaluation word, the polynomial has at most $k-1$ distinct polynomial roots, so at least $n-k+1$ coordinates are nonzero. Nonzero coordinate multipliers do not change these zero positions. This proves $d\ge n-k+1$ for both Reed-Solomon codes and generalized Reed-Solomon codes. Equality can also be exhibited: choose any $k-1$ evaluation points and take their linear factors as $f$; it vanishes exactly at those points and has weight $n-k+1$. Thus

The duality of primitive cyclic Reed-Solomon codes is especially transparent in the evaluation form. Assume first $1\le k<n$. A vector of $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, $\mathrm{deg}f<k$; a vector of $C_{n-k,1-b}$ has coordinates $a_j^{b}h(a_j)$, $\mathrm{deg}h<n-k$. Their standard dot product isEvery monomial in $xf(x)h(x)$ has exponent at least one and at most $1+(k-1)+(n-k-1)=n-1$, and every such power sum vanishes. Thus $C_{n-k,1-b}\subseteq C_{k,b}^{\perp }$. Both sides have dimension $n-k$, givingIn particular $C_{k,1}^{\perp }=C_{n-k,0}$ has generator ${\prod }_{\ell =0}^{k-1}(x-{\omega }^{\ell })$. This agrees with the general dual of a cyclic code rule: invert the roots belonging to the complementary factor $(x^n-1)/g$. The dual is a Reed-Solomon code in the consecutive-zero convention. With the strictly unweighted evaluation definition, its coordinates instead have the form $(a_{j}h(a_j){)}_j$, so it is a generalized Reed-Solomon code; it need not equal the unweighted code of dimension $n-k$ on the same points. This convention distinction is essential. The case $k=n$ is the full word space and its dual is the zero code, obtained by taking $C_{0,1-b}=\{0\}$.

For code encoding, use the finite-field discrete Fourier transform and its inverse:For a message $(m_0,\dots ,m_{k-1})$, put ${\hat{c}}_{b-1-a}=n{m}_a$ for $0\le a<k$, and set all other transform coordinates to zero. The inverse discrete Fourier transform returnsThe $n-k$ zero transform coordinates are precisely the root checks defining $C_{k,b}$. This gives non-systematic encoding by evaluation. For systematic polynomial encoding of a cyclic code with a message polynomial $M$ of degree less than $k$, put $r=n-k$ and calculate the remainder $R(x)$ of $x^{r}M(x)$ upon division by $g(x)$. Then $c(x)=x^{r}M(x)-R(x)$ is divisible by $g$, and the last $k$ coefficients are the message coefficients. Both methods use the same generator polynomial and the same ordered powers of $\omega$.

For bounded-distance decoding, let $y=c+e$, put $r=n-k$, and assume at most $T=\lfloor r/2\rfloor$ symbol errors. The following description uses the Reed-Solomon key equation and fixes the transform and locator conventions explicitly.

The denominator in the Forney algorithm is nonzero for distinct locations. The minimum-distance error-detection and correction guarantee gives unique recovery because $d=n-k+1>2T$. If the required locator or a valid correction cannot be found, declare decoding failure. Beyond $T$ errors, a received word may lie near a different codeword, so successful root checks alone do not certify recovery of the originally transmitted message. The guaranteed correction radius is $\lfloor (n-k)/2\rfloor$ symbol errors.

A linear length-$n$ cyclic code is a subspace closed under cyclic coordinate shifts. Identify a word with its polynomial modulo $X^n-1$; multiplying by $X$ performs the shift. Thus a cyclic code is an ideal of ${\mathbb{F}}_q[X]/(X^n-1)$. Its preimage in the polynomial ring is an ideal containing $X^n-1$, so the Euclidean algorithm gives a unique monic generator $g$ dividing $X^n-1$. The generator polynomial of a cyclic code is $g$ and the check polynomial of a cyclic code is $h=(X^n-1)/g$; a word lies in the code exactly when $hc\equiv 0(\mathrm{mod}{X}^n-1)$.

For the binary length-seven code, the given $h$ factors withThis cubic has no binary root and is irreducible. Let $\alpha$ be its root in ${\mathbb{F}}_8$. Since the nonzero multiplicative group has prime order seven and $\alpha \ne 1$, its seven powers enumerate all nonzero elements. The condition $c(\alpha )=0$ gives a three-row binary parity-check matrix whose columns are precisely the seven nonzero vectors of ${\mathbb{F}}_2^3$. This is Hamming's code in a cyclic coordinate order. It has dimension four, and minimum distance three: no one or two distinct nonzero columns sum to zero, while $g$ itself has weight three. Its sixteen radius-one balls have total size $16(1+7)=128$, confirming the original perfect Hamming code.

It actually contains its dual code in this coordinate order. Each parity-check row has four ones, and any two distinct rows have two simultaneous ones, so $H{H}^T=0$ over ${\mathbb{F}}_2$. The row space $C^{\perp }$ therefore lies in $\ker H=C$. Equivalently the dual generator is the reciprocal check polynomialwhich is divisible by $g$. Hence there is a three-dimensional subcode equal to the dual, and in any other coordinate order it is equivalent to that dual.

Work over the finite field ${\mathbb{F}}_2$. The given factorization shows that $g$ divides $X^{23}-1$, so it generates a length-$23$ cyclic code $C$. Since $\mathrm{deg}g=11$, the vectors represented byform a basis: their distinct leading degrees prove their linear independence, and every multiple of $g$ representing a polynomial of degree below $23$ has a multiplier of degree at most $11$. Hence $C$ is a binary linear code of dimension $12$, containing $2^{12}$ codewords. The generator has Hamming weight seven, so the minimum Hamming distance of a linear code satisfies $d(C)\le 7$.