Reed–Solomon Code

Reed–Solomon Code

For the Reed–Solomon code we need a larger field. So, let \(\mathbb{F}_{q}\) be a field of size \(q\). Now the symbols of our codewords will be elements of \(\mathbb{F}_{q}\) (while earlier they were bits, i.e., elements of \(\mathbb{F}_{2}\)). The definitions of various code properties generalize from the case \(q=2\) naturally. We call a code the set \(C \subseteq \mathbb{F}_{q}^{n}\), the distance of the code is defined as \(d=\min \{d_{H}(u,v) \colon u \neq v \in C\}\), and the dimension as \(\lfloor \log_{q} |C|\rfloor\). We call a code linear if it is a linear space: if \(u,v \in C\), then \(\alpha u + \beta v \in C\) for any \(\alpha, \beta \in \mathbb{F}_{q}\). It is easy to see that the distance is still equal to the minimum weight of a nonzero codeword.

Reed–Solomon codes are actively used in practice: for data storage (in particular, on CDs and DVDs), in barcodes, and in space communications. As we will see below, for given \(n\) and \(k\) they achieve the optimal distance. Their main drawback is that they use an alphabet of large size.

Theorem. Let \(k \le n \le q\) and let \(\alpha_{1}, \dotsc, \alpha_{n} \in \mathbb{F}_{q}\) be pairwise distinct elements. Then \[C = \{(P(\alpha_{1}), \dotsc, P(\alpha_{n})) \colon P \in \mathbb{F}_{q}[x], \ \deg(P) < k\}\] is a linear \((n,k,d=n-k+1)\)-code. Encoding can be performed in polynomial time.

Note that this code achieves the Singleton bound: for any \((n,k,d)\)-code over an alphabet of size \(q\) the inequality \(d \le n-k+1\) holds. This is easy to prove: since we have at least \(q^{k}\) (encoded) messages, some two of them must coincide in the first \(k-1\) symbols; thus the distance between these two codewords is at most \(n-(k-1)\). Hence, for given \(n\) and \(k\) this code achieves the optimal distance.

Proof.

• Linearity.  Clearly the code is linear: \[\begin{align*}\beta_{1}\cdot (P_{1}(\alpha_{1}), \dotsc, P_{1}(\alpha_{n}))+\beta_{2}\cdot (P_{2}(\alpha_{1}), \dotsc, P_{2}(\alpha_{n}))\\=((\beta_{1}P_{1}+\beta_{2}P_{2})(\alpha_{1}), \dotsc, (\beta_{1}P_{1}+\beta_{2}P_{2})(\alpha_{n})) \ .\end{align*}\]


• Dimension.  If \(P_{1} \not \equiv P_{2}\), then the vectors \((P_{1}(\alpha_{1}), \dotsc, P_{1}(\alpha_{n}))\) and \((P_{2}(\alpha_{1}), \dotsc, P_{2}(\alpha_{n}))\) are distinct: otherwise the polynomial \(P_{1}-P_{2}\) would have at least \(n\) roots, which is impossible since \(\deg(P_{1}-P_{2}) < k \le n\). Hence, the dimension of the code is \(k\).


• Encoding.  Encoding \(\phi \colon \mathbb{F}_{q}^{k} \to \mathbb{F}_{q}^{n}\) is simple: the given \(k\) elements of \(\mathbb{F}_{q}\) are considered as the coefficients of the polynomial \(P\). We then compute the values of this polynomial at the required points.


• Distance.  A nonzero polynomial of degree less than \(k\) can have at most \(k-1\) roots. Therefore, any nonzero vector \(u \in C\) has at least \(n-k+1\) nonzero components.

◼

Theorem. Decoding the Reed–Solomon code can be done in polynomial time.

Proof. We are given a function \(\tilde{P}\) which differs from \(P\) in at most \(e=\lfloor \frac{n-k}{2}\rfloor\) positions. Consider the error vector: \[D(x)=\prod_{i \colon P(\alpha_i) \neq \tilde{P}(\alpha_i)}(x-\alpha_{i}) \ .\] Let \(Q(x)=P(x)D(x)\) — a polynomial of degree less than \(k+e\). It is easy to see that \[Q(x)=\tilde{P}(x)D(x) \text{ for all \(x \in \{\alpha_{1}, \dotsc, \alpha_{n}\}\)}\ .\] In this equation we know \(\alpha_{1}, \dotsc, \alpha_{n}\) and the values of \(\tilde{P}\) at these points. But we do not know the coefficients of the polynomials \(Q\) and \(D\). Hence, the equality can be viewed as a system of linear equations for these coefficients. We know it has a solution, and we can find it. Nobody guarantees, however, that we find the original polynomials \(Q\) and \(D\). So let us assume we found polynomials \(\tilde{Q}\) and \(\tilde{D}\) such that \(\deg(\tilde{Q}) < k+e\), \(\deg(\tilde{D}) \le e\) and \(\tilde{Q}(x)=\tilde{P}(x)\tilde{D}(x)\) for all \(x \in \{\alpha_{1}, \dotsc, \alpha_{n}\}\). It turns out that even if we found different polynomials, it is enough to divide \(\tilde{Q}\) by \(\tilde{D}\) to obtain \(P\)! Indeed, consider the polynomials \(P\tilde{D}\) and \(\tilde{Q}\). We know that \(\tilde{Q}\) coincides with \(\tilde{P}\tilde{D}\) at all \(n\) points, and \(P\) coincides with \(\tilde{P}\) at least in \(n-e\) points. Therefore, \(P\tilde{D}\) and \(\tilde{Q}\) coincide in at least \(n-e \ge k+e\) points, and hence they are equal.◼