= Solution
For distinct evaluation points $a_0,\ldots,a_{n-1}\in\mathbb F_q$ and $1\leq k\leq n$, the <Reed-Solomon code> is
$$
\operatorname{RS}_k(a)=\{(f(a_0),\ldots,f(a_{n-1})):\ f\in\mathbb F_q[x],\ \deg f<k\}.
$$
This is a <linear code> of <dimension> $k$: evaluation is <linear>, and a nonzero <polynomial> of degree less than $k\leq 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 series>
$$
\sum_{j=0}^{n-1}\omega^{jt}=\begin{cases}n,&n\mid t,\\0,&n\nmid t.\end{cases}
$$
Here the scalar $n=q-1$ is nonzero in $\mathbb F_q$. Write $f(x)=\sum_{a=0}^{k-1}m_ax^a$ and $c(x)=\sum_{j=0}^{n-1}f(\omega^j)x^j$. For $1\leq\ell\leq n-k$,
$$
c(\omega^\ell)=\sum_{a=0}^{k-1}m_a\sum_{j=0}^{n-1}\omega^{j(a+\ell)}=0,
$$
since $1\leq a+\ell\leq 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
$$
\boxed{\operatorname{RS}_k(1,\omega,\ldots,\omega^{n-1})=\langle g\rangle,\qquad g(x)=\prod_{\ell=1}^{n-k}(x-\omega^\ell),\quad n=q-1.}
$$
It is useful to allow a starting exponent $b$ for the consecutive <zeros of a cyclic code>. Define the <primitive cyclic Reed-Solomon code>
$$
C_{k,b}=\left\langle\prod_{\ell=b}^{b+n-k-1}(x-\omega^\ell)\right\rangle.
$$
All exponents are understood modulo $n$. The same geometric-sum calculation shows that
$$
C_{k,b}=\{(a_j^{1-b}f(a_j))_{j=0}^{n-1}:\deg f<k\}.
$$
Indeed evaluating its word polynomial at $\omega^{b+\ell}$, $0\leq\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\leq q^{n-d+1}$ and $d\leq 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\geq 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
$$
\boxed{\operatorname{RS}_k\text{ and }C_{k,b}\text{ have parameters }[n,k,n-k+1]\text{ and are MDS codes}.}
$$
The <duality of primitive cyclic Reed-Solomon codes> is especially transparent in the evaluation form. Assume first $1\leq k<n$. A vector of $C_{k,b}$ has coordinates $a_j^{1-b}f(a_j)$, $\deg f<k$; a vector of $C_{n-k,1-b}$ has coordinates $a_j^b h(a_j)$, $\deg h<n-k$. Their standard <dot product> is
$$
\sum_{j=0}^{n-1}a_j f(a_j)h(a_j)=0.
$$
Every monomial in $x f(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$, giving
$$
\boxed{C_{k,b}^\perp=C_{n-k,1-b},\qquad g^\perp(x)=\prod_{\ell=1-b}^{k-b}(x-\omega^\ell).}
$$
In 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_jh(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:
$$
\widehat c_\ell=\sum_{j=0}^{n-1}c_j\omega^{j\ell},\qquad c_j=n^{-1}\sum_{\ell=0}^{n-1}\widehat c_\ell\omega^{-j\ell}.
$$
For a message $(m_0,\ldots,m_{k-1})$, put $\widehat c_{b-1-a}=n m_a$ for $0\leq a<k$, and set all other transform coordinates to zero. The <inverse discrete Fourier transform> returns
$$
\boxed{c_j=a_j^{1-b}\sum_{a=0}^{k-1}m_a a_j^a,\qquad a_j=\omega^j.}
$$
The $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^rM(x)$ upon division by $g(x)$. Then $c(x)=x^rM(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.
* Compute the <syndromes> $S_\ell=y(\omega^{b+\ell})=\widehat y_{b+\ell}$ for $0\leq\ell<r$. The corresponding codeword transform values vanish. An error of value $E_i$ at coordinate $j_i$ contributes $E_iX_i^{b+\ell}$, where $X_i=\omega^{j_i}$, so $S_\ell=\sum_iE_iX_i^{b+\ell}$.
* Form $S(z)=\sum_{\ell=0}^{r-1}S_\ell z^\ell$. Use the <Berlekamp-Massey algorithm>, or the polynomial <extended Euclidean algorithm> applied to $z^r$ and $S(z)$, to solve $\Lambda S\equiv\Omega\pmod{z^r}$ with $\Lambda(0)=1$, $\deg\Lambda=\nu\leq T$, and $\deg\Omega<\nu$. Choose the minimal-degree locator; zero syndrome gives $\Lambda=1$, $\Omega=0$. The <error locator polynomial> is $\Lambda(z)=\prod_{i=1}^\nu(1-X_i z)$, and $\Omega$ is the <error evaluator polynomial>.
* Perform a <Chien search>: test $\Lambda(\omega^{-j})$ for $0\leq j<n$. Its $\nu$ distinct zeros identify the erroneous coordinates. A mismatch between the degree and the number of distinct permitted roots is a decoding failure.
* Recover each error value by the <Forney algorithm>, with the present syndrome offset:
$$
\boxed{E_i=-X_i^{1-b}\frac{\Omega(X_i^{-1})}{\Lambda'(X_i^{-1})}.}
$$
* Set $e_{j_i}=E_i$, all other error coordinates to zero, and output $c=y-e$. Verify that all $r$ root checks vanish and that the correction has weight at most $T$. Recover the message from the unconstrained transform coordinates by $m_a=n^{-1}\widehat c_{b-1-a}$, or from the last $k$ coefficients if <systematic encoding> was used.
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. \b[The guaranteed correction radius is $\lfloor(n-k)/2\rfloor$ symbol errors.]
Back to article page
