5 The Greatest Code of Them All: Reed-Solomon Codes
A polynomial over a variable \(X\) and a finite field \(\mathbb {F}_q\) is given by a finite sequence \((f_0, f_1, \ldots , f_d)\) with \(f_i \in \mathbb {F}_q\), denoted \(F(X) = \sum _{i=0}^{d} f_i X^i\). The degree of \(F(X)\), denoted \(\deg (F)\), is the largest index \(i\) such that \(f_i \neq 0\). The set \(\mathbb {F}_q[X]\) of all such polynomials, with the usual coefficientwise addition and convolution multiplication, forms a commutative ring.
Given a polynomial \(F(X) \in \mathbb {F}_q[X]\) and \(\alpha \in \mathbb {F}_q\), the evaluation of \(F(X)\) at \(\alpha \), denoted \(F(\alpha )\), is \(\sum _{i=0}^{\deg F} f_i \alpha ^i \in \mathbb {F}_q\). (More generally, if \(\alpha \) lies in an extension field \(\mathbb {F}_Q \supseteq \mathbb {F}_q\), the evaluation \(F(\alpha ) \in \mathbb {F}_Q\) is defined the same way.)
Given polynomials \(f(X), g(X) \in \mathbb {F}_q[X]\) with \(g \neq 0\), there exist unique polynomials \(q(X)\), the quotient, and \(r(X)\), the remainder, with \(\deg (r) {\lt} \deg (g)\), such that \(f(X) = q(X)g(X) + r(X)\). If \(g(X) = X - \alpha \) for \(\alpha \in \mathbb {F}_q\), then \(r(X)\) is the degree-\(0\) polynomial \(f(\alpha )\), i.e., the evaluation of \(f\) at \(\alpha \).
\(\alpha \in \mathbb {F}_q\) is a root of a polynomial \(F(X)\) if \(F(\alpha ) = 0\).
A nonzero polynomial \(f(X)\) of degree \(t\) over a field \(\mathbb {F}_q\) has at most \(t\) distinct roots in \(\mathbb {F}_q\).
A polynomial \(F(X)\) is irreducible if for every \(G_1(X), G_2(X)\) such that \(F(X) = G_1(X) G_2(X)\), we have \(\min (\deg (G_1), \deg (G_2)) = 0\).
Let \(E(X)\) be an irreducible polynomial of degree \(s \geq 2\) over \(\mathbb {F}_p\), \(p\) prime. Then the set of polynomials in \(\mathbb {F}_p[X]\) modulo \(E(X)\), denoted \(\mathbb {F}_p[X]/E(X)\), with addition, multiplication, additive/multiplicative identities and inverses induced by the ring \(\mathbb {F}_p[X]\), is a field.
Let \(E(x) \in \mathbb {F}_q[x]\) be an irreducible polynomial of degree \(s\). Then \(\mathbb {F}_q[x]/E(x)\) is a field of size \(q^s\).
For all \(s \geq 2\) and prime \(p\), there exists an irreducible polynomial of degree \(s\) over \(\mathbb {F}_p\). In fact, the number of such monic irreducible polynomials is \(\Theta \! \left(\dfrac {p^s}{s}\right)\). (The existence statement holds more generally over any finite field \(\mathbb {F}_q\), not just prime fields \(\mathbb {F}_p\).)
The field \(\mathbb {F}_{p^s}\) is \(\mathbb {F}_p[X]/E(X)\), where \(E(X)\) is an irreducible polynomial of degree \(s\).
Input: A prime power \(q\) and an integer \(s {\gt} 1\).
Output: A monic irreducible polynomial of degree \(s\) over \(\mathbb {F}_q\).
Repeat:
Choose \(F(X) = X^s + \sum _{i=0}^{s-1} f_i X^i\) with each \(f_i\) chosen uniformly at random from \(\mathbb {F}_q\).
Test whether \(F(X)\) is irreducible by checking: \(\gcd (F(X), X^{q^s} - X) = F(X)\), and for every \(t \notin \{ 1, s\} \) dividing \(s\), \(\gcd (F(X), X^{q^t} - X) = 1\).
Until \(F(X)\) passes the irreducibility test; return \(F(X)\).
Correctness of the test in step (1b) rests on the fact (Appendix D) that an irreducible polynomial of degree exactly \(t\) divides \(X^{q^t} - X\); checking the two gcd conditions therefore certifies that \(F(X)\) has no factor of degree dividing \(s\) other than \(1\) and \(s\) itself, i.e., that \(F(X)\) is irreducible. Since Euclid’s algorithm for \(\gcd (A(X), B(X))\) runs in time polynomial in \(\min (\deg A, \deg B)\) and \(\log q\), each iteration of the loop runs in time \(\mathrm{poly}(s, \log q)\). By Theorem 124, the number of monic irreducible polynomials of degree \(s\) over \(\mathbb {F}_q\) is \(\Theta (q^s/s)\) out of \(q^s\) monic polynomials of degree \(s\), so a uniformly random monic polynomial of degree \(s\) is irreducible with probability \(\Theta (1/s)\); hence the expected number of iterations is \(O(s)\).
There is a Las Vegas algorithm (Algorithm 126) to generate an irreducible polynomial of degree \(s\) over any \(\mathbb {F}_q\) in expected time \(\mathrm{poly}(s, \log q)\).
This is immediate from the analysis in the proof of Algorithm 126: each iteration takes time \(\mathrm{poly}(s, \log q)\) and the expected number of iterations is \(O(s)\), giving a total expected running time of \(\mathrm{poly}(s, \log q)\).
Let \(\mathbb {F}_q\) be a finite field, and choose \(n\) and \(k\) satisfying \(k \leq n \leq q\). Fix a sequence \(\alpha = (\alpha _1, \alpha _2, \ldots , \alpha _n)\) of \(n\) distinct elements (evaluation points) from \(\mathbb {F}_q\). The encoding function of the Reed-Solomon code \(\mathrm{RS}_q[\alpha , k] : \mathbb {F}_q^k \to \mathbb {F}_q^n\) maps a message \(m = (m_0, m_1, \ldots , m_{k-1})\) with \(m_i \in \mathbb {F}_q\) to the degree-\((k-1)\) polynomial
and then outputs
We write simply \(\mathrm{RS}\) when \(q\), \(\alpha \), \(k\) are clear from context, and call the image \(\{ \mathrm{RS}[m] \mid m \in \mathbb {F}_q^k\} \) the Reed-Solomon code, or RS code. A common special case is \(n = q - 1\) with evaluation points \(\mathbb {F}_q^* = \mathbb {F}_q \setminus \{ 0\} \).
The Reed-Solomon code \(\mathrm{RS}\) of Definition 128 is a linear code.
If \(a \in \mathbb {F}_q\) and \(f(X), g(X) \in \mathbb {F}_q[X]\) are polynomials of degree at most \(k - 1\), then \(af(X)\) and \(f(X) + g(X)\) are also polynomials of degree at most \(k-1\). In particular, let messages \(m_1, m_2 \in \mathbb {F}_q^k\) be mapped to \(f_{m_1}(X), f_{m_2}(X)\); by the definition of \(f_m\),
Since evaluation at each \(\alpha _i\) is applied coordinatewise, this gives
Hence \(\mathrm{RS}\) is an \([n,k]_q\) linear code.
The minimum distance of the Reed-Solomon code \(\mathrm{RS}\) of Definition 128 is \(n - k + 1\).
Fix arbitrary \(m_1 \neq m_2 \in \mathbb {F}_q^k\). The polynomials \(f_{m_1}(X), f_{m_2}(X) \in \mathbb {F}_q[X]\) are distinct polynomials of degree at most \(k-1\), so \(f_{m_1}(X) - f_{m_2}(X) \neq 0\) also has degree at most \(k-1\). Since \(\mathrm{wt}(\mathrm{RS}(m_2) - \mathrm{RS}(m_1)) = \Delta (\mathrm{RS}(m_1), \mathrm{RS}(m_2))\), and the weight of \(\mathrm{RS}(m_2) - \mathrm{RS}(m_1)\) is \(n\) minus the number of zero coordinates, which equals \(n\) minus the number of roots of \(f_{m_1}(X) - f_{m_2}(X)\) among \(\{ \alpha _1, \ldots , \alpha _n\} \), we get
By the Degree Mantra (Proposition 120), \(f_{m_1}(X) - f_{m_2}(X)\) has at most \(k-1\) roots. Thus the weight of \(\mathrm{RS}(m_2) - \mathrm{RS}(m_1)\) is at least \(n - (k-1) = n-k+1\), so the minimum distance \(d\) of \(\mathrm{RS}\) satisfies \(d \geq n-k+1\). Since the Singleton bound (110) gives \(d \leq n-k+1\), we conclude \(d = n-k+1\).
The same argument shows distinct polynomials \(f_{m_1}(X) \neq f_{m_2}(X)\) of degree at most \(k-1\) are mapped to distinct codewords, since their Hamming distance is at least \(n-k+1 \geq 1\) (as \(k \leq n\)). Hence \(\mathrm{RS}\) has exactly \(q^k\) codewords and, by Lemma 129, dimension \(k\).
\(\mathrm{RS}\) is an \([n, k, n-k+1]_q\) code. That is, Reed-Solomon codes match the Singleton bound.
Any basis \(f_{m^1}, \ldots , f_{m^k}\) of the space of polynomials of degree at most \(k-1\) gives rise, via Definition 128, to a basis \(\mathrm{RS}(m^1), \ldots , \mathrm{RS}(m^k)\) of the Reed-Solomon code. Taking the monomial basis \(1, X, \ldots , X^{k-1}\) yields the \(k \times n\) Vandermonde generator matrix whose \(i\)-th row (for \(0 \leq i \leq k-1\)) is \((\alpha _1^i, \alpha _2^i, \ldots , \alpha _n^i)\).
By Lemma 129, \(\mathrm{RS}\) is linear, hence the image of a basis of the message/polynomial space under the (linear, by Definition 128) encoding map is a basis of the code, i.e., forms a valid generator matrix. Choosing the monomial basis \(X^0, \ldots , X^{k-1}\), the \(i\)-th basis polynomial \(X^i\) encodes to \((\alpha _1^i, \ldots , \alpha _n^i)\), giving exactly the stated matrix.
An \((n,k,d)_q\) code is called Maximum Distance Separable (MDS) if \(d = n-k+1\).
For every subset of indices \(S \subseteq [n]\) of size exactly \(k\) and a code \(C \subseteq \Sigma ^n\), \(C_S\) is the set of all codewords in \(C\) projected onto the indices in \(S\).
Let \(C \subseteq \Sigma ^n\) of integral dimension \(k\) be an MDS code. Then for every \(S \subseteq [n]\) with \(|S| = k\), we have \(C_S = \Sigma ^k\).
Consider the \(|C| \times n\) matrix whose rows are the codewords of \(C\); there are \(|C| = |\Sigma |^k\) rows (since \(C\) has dimension \(k\)) and \(n\) columns. Since \(C\) is MDS, its minimum distance is \(d = n-k+1\).
Fix \(S \subseteq [n]\) with \(|S| = k\). For any distinct \(c^i \neq c^j \in C\), the projections \(c^i_S \neq c^j_S \in C_S\) are distinct: if they agreed, then \(c^i\) and \(c^j\) would agree on all \(k\) coordinates in \(S\), so \(\Delta (c^i, c^j) \leq n - k = d - 1\), contradicting that the minimum distance of \(C\) is \(d\). Hence every codeword of \(C\) maps to a distinct element of \(C_S\), giving \(|C_S| = |C| = |\Sigma |^k\). Since \(C_S \subseteq \Sigma ^k\) and \(|C_S| = |\Sigma ^k|\), we conclude \(C_S = \Sigma ^k\).