12 Efficient Decoding of Reed-Solomon Codes
This chapter studies efficient decoding of Reed-Solomon codes. We first give an efficient unique-decoding algorithm (the Welch-Berlekamp algorithm) that corrects up to half the minimum distance. We then generalize this to a sequence of list-decoding algorithms, culminating in an algorithm (Guruswami-Sudan) that efficiently achieves the Johnson bound (cross-referenced as thm:c07-johnson-bound) for Reed-Solomon codes, i.e. corrects up to \(1-\sqrt{R}\) fraction of errors for a rate-\(R\) Reed-Solomon code.
We will repeatedly use the basic fact that a non-zero univariate polynomial of degree \(d\) over a field has at most \(d\) roots (called the "degree mantra" in the source text, Proposition 5.1.5). We record it here once as a settled leaf, local to this chapter, since it is standard commutative algebra.
A non-zero polynomial \(f \in \mathbb {F}[X]\) of degree \(d\) over a field \(\mathbb {F}\) has at most \(d\) roots in \(\mathbb {F}\).
12.1 Unique decoding of Reed-Solomon codes
Throughout this section, fix the \([n,k,d=n-k+1]_q\) Reed-Solomon code (cross-ref def:c05-reed-solomon) with distinct evaluation points \((\alpha _1,\dots ,\alpha _n) \in \mathbb {F}_q^n\). A message is a polynomial \(P(X) = \sum _{i=0}^{k-1} c_i X^i \in \mathbb {F}_q[X]\) of degree at most \(k-1\), encoded as \((P(\alpha _1),\dots ,P(\alpha _n)) \in \mathbb {F}_q^n\).
Input: Code parameters \(\mathbb {F}_q\), \((\alpha _1,\dots ,\alpha _n) \in \mathbb {F}_q^n\) and \(k\). Received word \(y \in \mathbb {F}_q^n\).
Output: A polynomial \(P(X) \in \mathbb {F}_q[X]\) of degree less than \(k\) such that \(e := |\{ i \in [n] \mid y_i \neq P(\alpha _i)\} | {\lt} \frac{n-k+1}{2}\), if such a polynomial exists, and fail otherwise.
Given a received word \(y=(y_1,\dots ,y_n)\) and a polynomial \(P(X)\), a non-zero polynomial \(E(X)\) is called an error-locator polynomial for \((P,y)\) if for all \(i \in [n]\),
In particular, the polynomial \(E(X) = \prod _{i : y_i \neq P(\alpha _i)} (X-\alpha _i)\) is an error-locator polynomial of degree exactly \(e := |\{ i \mid y_i \neq P(\alpha _i)\} |\), and for every \(1 \le i \le n\) it satisfies \(y_i E(\alpha _i) = P(\alpha _i)E(\alpha _i)\).
Input: \(n \ge k \ge 1\), \(0 {\lt} e {\lt} \frac{n-k+1}{2}\), and \(n\) pairs \(\{ (\alpha _i,y_i)\} _{i=1}^n\) with \(\alpha _i\) distinct.
Output: A polynomial \(P(X)\) of degree at most \(k-1\), or fail.
Compute a non-zero polynomial \(E(X)\) of degree exactly \(e\), and a polynomial \(N(X)\) of degree at most \(e+k-1\), such that
\[ y_i E(\alpha _i) = N(\alpha _i), \qquad 1 \le i \le n. \]If no such \(E(X), N(X)\) exist, or \(E(X)\) does not divide \(N(X)\), return fail.
Set \(P(X) \gets N(X)/E(X)\).
If \(\Delta \! \left(y,(P(\alpha _i))_{i=1}^n\right) {\gt} e\), return fail; otherwise return \(P(X)\).
Suppose \((P(\alpha _i))_{i=1}^n\) is transmitted, where \(P(X)\) has degree at most \(k-1\), and the received word \(y\) satisfies \(\Delta (y,(P(\alpha _i))_{i=1}^n) \le e\). Then there exist polynomials \(E^*(X)\) of degree exactly \(e\) and \(N^*(X)\) of degree at most \(e+k-1\) satisfying Step 1 of Algorithm 259 such that \(N^*(X)/E^*(X) = P(X)\).
Define
a non-zero polynomial of degree exactly \(e\) (the extra power of \(X\) pads the degree up to \(e\)), with the property that \(E^*(\alpha _i) \neq 0 \implies y_i = P(\alpha _i)\). Set \(N^*(X) = P(X) E^*(X)\), which has degree at most \(\deg (P) + \deg (E^*) \le (k-1) + e\).
We check \(y_i E^*(\alpha _i) = N^*(\alpha _i)\) for every \(i\). If \(E^*(\alpha _i) = 0\) then both sides are \(0\). If \(E^*(\alpha _i) \neq 0\) then \(y_i = P(\alpha _i)\), so \(y_i E^*(\alpha _i) = P(\alpha _i)E^*(\alpha _i) = N^*(\alpha _i)\). In either case the equality holds, and by construction \(N^*(X)/E^*(X) = P(X)\).
If \((E_1(X),N_1(X)) \neq (E_2(X),N_2(X))\) are two distinct pairs each satisfying Step 1 of Algorithm 259 (for the same input), then
Define \(R(X) = N_1(X)E_2(X) - N_2(X)E_1(X)\), a polynomial of degree at most \(2e+k-1\) (since each of \(N_1E_2\) and \(N_2E_1\) has degree at most \((e+k-1)+e = 2e+k-1\)). For every \(1 \le i \le n\), Step 1 gives \(N_1(\alpha _i) = y_i E_1(\alpha _i)\) and \(N_2(\alpha _i) = y_i E_2(\alpha _i)\), hence
Thus \(R(X)\) has \(n\) roots. Since \(e {\lt} \frac{n-k+1}{2}\), we have \(2e+k-1 {\lt} n\), so by the degree mantra (Lemma 256), \(R(X)\) is identically zero. Hence \(N_1(X)E_2(X) \equiv N_2(X)E_1(X)\), and since \(E_1,E_2\) are non-zero, this gives \(N_1(X)/E_1(X) = N_2(X)/E_2(X)\).
If \((P(\alpha _i))_{i=1}^n\) is transmitted, where \(P(X)\) has degree at most \(k-1\), and at most \(e {\lt} \frac{n-k+1}{2}\) errors occur (i.e. \(\Delta (y,(P(\alpha _i))_{i=1}^n) \le e\)), then Algorithm 259 outputs \(P(X)\). Consequently, the Welch-Berlekamp algorithm corrects Reed-Solomon codes of rate \(R\) from up to \(\frac{1-R}{2}\) fraction of errors.
By Lemma 260, there is a pair \((N_1,E_1)\) satisfying Step 1 with \(N_1(X)/E_1(X) = P(X)\); in particular Step 1 does not fail. Let \((N_2,E_2)\) be the pair the algorithm actually computes in Step 1; it also satisfies Step 1’s constraints. By Lemma 261, \(N_2(X)/E_2(X) = N_1(X)/E_1(X) = P(X)\), so \(E_2\) divides \(N_2\) and Step 4 correctly sets \(P(X) \gets N_2(X)/E_2(X) = P(X)\). Finally \(\Delta (y,(P(\alpha _i))_{i=1}^n) \le e\) by hypothesis, so Step 5 does not trigger fail, and the algorithm outputs \(P(X)\).
Problem 257 (Reed-Solomon Unique Decoding) can be solved in \(O(n^3)\) field operations over \(\mathbb {F}_q\).
By Theorem 262, it suffices to implement Algorithm 259 in \(O(n^3)\) time. All steps other than Step 1 and the division in Steps 2,4 are simple bookkeeping computable in \(O(n)\) time; the division of \(N(X)\) by \(E(X)\) (via long division) takes \(O(n^2)\) time. For Step 1, write \(E(X) = \sum _{j=0}^e E_j X^j\) and \(N(X) = \sum _{j=0}^{e+k-1} N_j X^j\), treating the \(2e+k+1 \le n+1\) coefficients \(E_0,\dots ,E_e,N_0,\dots ,N_{e+k-1}\) as unknowns. Each constraint \(y_i E(\alpha _i) = N(\alpha _i)\) is linear in these unknowns, giving \(n\) linear equations. Adding the normalization \(E_e = 1\) (which forces \(\deg (E)=e\) exactly, and loses no solutions since any solution with \(E_e \neq 0\) can be rescaled to have leading coefficient \(1\)) gives a system of \(n+1\) linear equations in at most \(n+1\) unknowns, solvable in \(O(n^3)\) time by Gaussian elimination. Hence the whole algorithm runs in \(O(n^3)\) time.
12.2 List Decoding Reed-Solomon Codes
We now turn to the list-decoding problem for Reed-Solomon codes (cross-ref def:c07-list-decoding), aiming to answer affirmatively the question (cross-ref: Question 7.4.3) of whether a rate-\(R\) code meeting the Singleton bound (cross-ref thm:c04-singleton-bound) with \(\delta = 1-R\) can be efficiently list-decoded up to the Johnson bound (cross-ref thm:c07-johnson-bound), i.e. up to \(1-\sqrt{R}\) fraction of errors.
Input: Code parameters \(\mathbb {F}_q\), \((\alpha _1,\dots ,\alpha _n) \in \mathbb {F}_q^n\), \(k\) and \(e\). Received word \(y=(y_1,\dots ,y_n) \in \mathbb {F}_q^n\).
Output: The set of all polynomials \(P(X) \in \mathbb {F}_q[X]\) of degree less than \(k\) such that \(t := |\{ i \in [n] \mid y_i = P(\alpha _i)\} | \ge n-e\).
All the list-decoding algorithms below share a common two-step structure, obtained by rewriting the Welch-Berlekamp algorithm: an interpolation step, which finds a non-zero bivariate polynomial \(Q(X,Y)\) with \(Q(\alpha _i,y_i)=0\) for all \(i\) (in the Welch-Berlekamp case, \(Q(X,Y) = YE(X)-N(X)\)), and a root-finding step, which extracts the linear factors \(Y-P(X)\) of \(Q(X,Y)\) (equivalently, the roots of \(Q(X,Y)\) viewed as a polynomial in \(Y\) over \(\mathbb {F}_q[X]\)). Root-finding is carried out by bivariate polynomial factorization, which can be done in polynomial time (cross-ref Theorem D.7.9, Appendix D.7 –
12.2.1 The Basic List-Decoder
For a bivariate polynomial \(Q(X,Y) = \sum _{i,j} c_{ij} X^i Y^j\), \(\deg _X(Q)\) is the maximum degree of \(X\) appearing in any monomial of \(Q(X,Y)\) with nonzero coefficient, and similarly \(\deg _Y(Q)\) is the maximum degree of \(Y\). If \(\deg _X(Q) \le a\) and \(\deg _Y(Q) \le b\) then \(Q(X,Y) = \sum _{0 \le i \le a, 0 \le j \le b} c_{ij}X^iY^j\) has \((a+1)(b+1)\) coefficients.
Input: \(n \ge k \ge 1\), \(\ell \ge 1\), \(e=n-t\), and \(n\) pairs \(\{ (\alpha _i,y_i)\} _{i=1}^n\).
Output: A (possibly empty) list of polynomials \(P(X)\) of degree at most \(k-1\).
Find a non-zero \(Q(X,Y)\) with \(\deg _X(Q) \le \ell \), \(\deg _Y(Q) \le n/\ell \) such that \(Q(\alpha _i,y_i) = 0\) for \(1 \le i \le n\).
Factor \(Q(X,Y)\) into irreducible factors \(Q_1(X,Y),\dots ,Q_m(X,Y)\).
Set \(L \gets \emptyset \).
For every factor \(Q_j(X,Y) = Y-P_j(X)\) of \(Q(X,Y)\): if \(\Delta (y,(P_j(\alpha _i))_{i=1}^n) \le e\) and \(\deg (P_j) \le k-1\), add \(P_j(X)\) to \(L\).
Return \(L\).
For every input sequence \(\{ (\alpha _i,y_i)\} _{i=1}^n\) with \(\alpha _i\) distinct and every \(\ell \ge 1\), Step 1 of Algorithm 266 has a non-zero solution \(Q(X,Y)\) with \(\deg _X(Q) \le \ell \) and \(\deg _Y(Q) \le n/\ell \) satisfying \(Q(\alpha _i,y_i)=0\) for all \(1 \le i \le n\).
Finding the coefficients of such a \(Q(X,Y)\) amounts to finding a non-trivial solution to a homogeneous linear system with \(n\) equations (one per constraint \(Q(\alpha _i,y_i)=0\), each linear in the coefficients \(c_{ij}\) of \(Q\)) in \((\ell +1)(\lfloor n/\ell \rfloor +1)\) unknowns. Since
the number of unknowns strictly exceeds the number of equations, so the homogeneous system has a non-trivial solution.
Algorithm 266 (with \(\ell = \lceil \sqrt{n(k-1)}\rceil \)) list-decodes Reed-Solomon codes of rate \(R\) from up to \(1-2\sqrt{R}\) fraction of errors, and can be implemented in polynomial time.
Runtime: By Lemma 267, Step 1 always succeeds, and can be solved by Gaussian elimination on the homogeneous linear system in polynomial time; Step 2 can be done in polynomial time by bivariate polynomial factorization (
Correctness: We must show that if \(P(X)\) has degree at most \(k-1\) and agrees with \(y\) in at least \(t\) positions, then \(Y-P(X)\) divides \(Q(X,Y)\), i.e. \(R(X) := Q(X,P(X)) \equiv 0\). Suppose for contradiction \(R(X) \not\equiv 0\). Since \(Q\) has \(\deg _X(Q) \le \ell \) and \(\deg _Y(Q) \le n/\ell \), substituting \(Y=P(X)\) (of degree \(\le k-1\)) gives
On the other hand, whenever \(P(\alpha _i)=y_i\) we have \(Q(\alpha _i,y_i) = Q(\alpha _i,P(\alpha _i))=0\) by Step 1, so \(\alpha _i\) is a root of \(R(X)\); this happens for at least \(t\) values of \(i\). By the degree mantra (Lemma 256), if \(t {\gt} \deg (R)\) this forces \(R \equiv 0\), contradiction. So it suffices to pick \(\ell \) so that \(t {\gt} \ell + \frac{n(k-1)}{\ell }\). Taking \(\ell = \sqrt{n(k-1)}\) gives \(t {\gt} 2\sqrt{n(k-1)}\). Writing \(R=k/n\), this gives \(e/n = 1-t/n {\lt} 1-2\sqrt{R(1-1/n)} \approx 1-2\sqrt{R}\), i.e. the algorithm corrects up to \(1-2\sqrt{R}\) fraction of errors.
12.2.2 Algorithm 2: Weighted-Degree List-Decoder
The \((1,w)\)-weighted degree of the monomial \(X^iY^j\) is \(i+wj\). The \((1,w)\)-weighted degree of \(Q(X,Y)\) (or just its \((1,w)\)-degree) is the maximum \((1,w)\)-weighted degree over its monomials with non-zero coefficient. (The \((1,1)\)-degree is the usual total degree.) A bivariate polynomial of \((1,w)\)-degree at most \(D\) can be written \(Q(X,Y) = \sum _{i+wj \le D,\, i,j \ge 0} c_{i,j}X^iY^j\).
Let \(Q(X,Y)\) be a bivariate polynomial of \((1,w)\)-degree at most \(D\), and let \(P(X)\) be a polynomial with \(\deg (P) \le w\). Then \(\deg (Q(X,P(X))) \le D\).
Write \(Q(X,Y) = \sum _{i+wj \le D} c_{i,j}X^iY^j\). Each monomial contributes \(c_{i,j}X^i P(X)^j\) to \(Q(X,P(X))\), of degree at most \(i + j\deg (P) \le i+wj \le D\). Hence the degree of the sum \(Q(X,P(X))\) is at most \(D\).
Input: \(n \ge k \ge 1\), \(D \ge 1\), \(e=n-t\), and \(n\) pairs \(\{ (\alpha _i,y_i)\} _{i=1}^n\).
Output: A (possibly empty) list of polynomials \(P(X)\) of degree at most \(k-1\).
Find a non-zero \(Q(X,Y)\) with \((1,k-1)\)-degree at most \(D\) such that \(Q(\alpha _i,y_i)=0\) for \(1 \le i \le n\).
Set \(L \gets \emptyset \).
For every factor \(Y-P(X)\) of \(Q(X,Y)\): if \(\Delta (y,(P(\alpha _i))_{i=1}^n) \le e\) and \(\deg (P) \le k-1\), add \(P(X)\) to \(L\).
Return \(L\).
Algorithm 271 (with \(D = \lceil \sqrt{2(k-1)n}\rceil \)) list-decodes Reed-Solomon codes of rate \(R\) from up to \(1-\sqrt{2R}\) fraction of errors, runs in polynomial time, and outputs a list of size at most \(O(1/\sqrt{R})\).
Interpolation step: Let \(N\) be the number of coefficients of a \((1,k-1)\)-degree-\(D\) polynomial \(Q(X,Y) = \sum _{i+(k-1)j \le D} c_{i,j}X^iY^j\), and let \(L = \lfloor D/(k-1)\rfloor \) (this will be the eventual output list-size bound). Then
Using \(L \le D/(k-1)\) we get \(2D+2-(k-1)L \ge D+2\), so \(N \ge \frac{L+1}{2}(D+2)\); using further \(D/(k-1) - 1 \le L\) we get \(N \ge \frac{D(D+2)}{2(k-1)}\). Hence the homogeneous linear system from the \(n\) constraints \(Q(\alpha _i,y_i)=0\) has a non-trivial solution (i.e. Step 1 succeeds) as soon as \(\frac{D(D+2)}{2(k-1)} {\gt} n\). Since \(\frac{D(D+2)}{2(k-1)} {\gt} \frac{D^2}{2(k-1)} \ge \frac{2(k-1)n}{2(k-1)} = n\) for \(D=\lceil \sqrt{2(k-1)n}\rceil \), this choice of \(D\) works, and \(N = O(n)\) so Gaussian elimination runs in polynomial time.
Root-finding step: If \(P(X)\) has degree \(\le k-1\) and \(\Delta (y,(P(\alpha _i))) \le e\), let \(R(X) = Q(X,P(X))\); by Lemma 270, \(\deg (R) \le D\). As before every \(\alpha _i\) with \(P(\alpha _i)=y_i\) is a root of \(R(X)\), and there are at least \(t\) such \(i\). By the degree mantra (Lemma 256), \(t {\gt} D\) forces \(R \equiv 0\), i.e. \(Y-P(X)\) divides \(Q(X,Y)\). Taking \(t {\gt} \lceil \sqrt{2(k-1)n}\rceil \) and \(R=k/n\) gives \(e/n {\lt} 1-\sqrt{2R}\) asymptotically. Root-finding itself is done by bivariate polynomial factorization in polynomial time (O(1/R)\( bounds the output list size. \)
12.2.3 Algorithm 3: Multiplicity List-Decoder
A bivariate polynomial \(\)Q(X,Y)\( has \)\(\)r\( roots at \)(0,0)\(\) if \(\)Q(X,Y)\( has no non-zero monomial of degree at most \)r-1\( (i.e.\ every monomial \)X^iY^j\( with \)c_i,j ≠0\( satisfies \)i+j ≥r\(). \)
\(\)Q(X,Y)\( has \)\(\)r\( roots at \)(α,β)\(\) if the shifted polynomial \(\)Q_α,β(X,Y) := Q(X+α,Y+β)\( has \)r\( roots at \)(0,0)\( (Definition~ \ref{def:c12-multiplicity-origin}). \)
Input:
\(\)n ≥k ≥1\(, \)D ≥1\(, \)r ≥1\(, \)e=n-t\(, and \)n\( pairs \){(α_i,y_i)}_i=1^n\(. \textbf{Output}: A (possibly empty) list of polynomials \)P(X)\( of degree at most \)k-1\(. \begin{enumerate} \item Find a non-zero \end{enumerate}\)Q(X,Y)\( with \)(1,k-1)\(-degree at most \)D\( such that \)Q(X,Y)\( has \)r\( roots at \)(α_i,y_i)\( for every \)1 ≤i ≤n\(. \item Set \)L ∅\(. \item For every factor \)Y-P(X)\( of \)Q(X,Y)\(: if \)Δ(y,(P(α_i))_i=1^n) ≤e\( and \)(P) ≤k-1\(, add \)P(X)\( to \)L\(. \item Return \)L\(. \)
For each \(\)i\(, the constraint that \)Q(X,Y)\( has \)r\( roots at \)(α_i,y_i)\( imposes \)r+12\( homogeneous linear constraints on the coefficients of \)Q(X,Y)\(. \)
Write
\(\)Q(X,Y) = ∑_i+(k-1)j ≤D c_i,jX^iY^j\( and \)Q_α,β(X,Y) = Q(X+α,Y+β) = ∑_i,j c^α,β_i,jX^iY^j\(. Comparing coefficients of \)X^iY^j\( on both sides of \)∑_i,j c^α,β_i,jX^iY^j = ∑_i’≥i, j’ ≥j c_i’,j’i’ij’jα^i’-iβ^j’-j\(, we see each \)c^α,β_i,j\( is a homogeneous linear combination of the \)c_i’,j’\('s with \)i’ ≥i, j’ ≥j\(: this proves part (i). By Definition~ \ref{def:c12-multiplicity-point}, \)Q(X,Y)\( has \)r\( roots at \)(α,β)\( iff \)c^α,β_i,j=0\( whenever \)i+j ≤r-1\(. The number of such pairs \)(i,j)\( with \)i,j ≥0\( is \[ \sum _{j=0}^{r-1}(r-j) = \sum _{\ell =1}^r \ell = \binom {r+1}{2}. \] This proves part (ii); combining (i) and (ii), the \)r\(-root constraint at \)(α_i,y_i)\( imposes \)r+12\( homogeneous linear constraints on the \)c_i,j\('s. \)
Let
\(\)Q(X,Y)\( have \)r\( roots at \)(α_i,y_i)\(, let \)P(X)\( be a polynomial with \)P(α_i)=y_i\(, and let \)R(X) := Q(X,P(X))\(. Then \)(X-α_i)^r\( divides \)R(X)\(. \)
Define
\(\)P_α_i,y_i(X) := P(X+α_i)-y_i\( and \)R_α_i,y_i(X) := R(X+α_i)\(. Unwinding definitions, \[ R_{\alpha _i,y_i}(X) = Q(X+\alpha _i, P(X+\alpha _i)) = Q(X+\alpha _i, P_{\alpha _i,y_i}(X)+y_i) = Q_{\alpha _i,y_i}(X, P_{\alpha _i,y_i}(X)). \] If \)X\( divides \)R_α_i,y_i(X)\( then \)R_α_i,y_i(0)=R(α_i)=0\(, i.e.\ \)X-α_i\( divides \)R(X)\(; more generally, if \)X^r\( divides \)R_α_i,y_i(X)\( then \)(X-α_i)^r\( divides \)R(X)\( (the argument is the substitution \)X ↦X-α_i\(, analogous to the proof of the degree mantra, Lemma~ \ref{lem:c12-degree-mantra}). So it suffices to show \)X^r ∣R_α_i,y_i(X)\(. Since \)P(α_i)=y_i\(, we have \)P_α_i,y_i(0)=0\(, so \)P_α_i,y_i(X) = X·g(X)\( for some polynomial \)g(X)\( of degree at most \)k-1\(. Writing \)Q_α_i,y_i(X,Y) = ∑_i’,j’ c^α_i,y_i_i’,j’X^i’Y^j’\(, \[ R_{\alpha _i,y_i}(X) = \sum _{i',j'} c^{\alpha _i,y_i}_{i',j'} X^{i'}(P_{\alpha _i,y_i}(X))^{j'} = \sum _{i',j'} c^{\alpha _i,y_i}_{i',j'} X^{i'}(Xg(X))^{j'}. \] Every term with \)c^α_i,y_i_i’,j’ ≠0\( has \)i’+j’ ≥r\( since \)Q(X,Y)\( has \)r\( roots at \)(α_i,y_i)\(, so each such term is divisible by \)X^i’+j’\(, hence by \)X^r\(. Thus \)X^r\( divides \)R_α_i,y_i(X)\(, as required. \)
Let
\(\)Q(X,Y)\( be a polynomial computed by Step~ 1 of Algorithm~ \ref{alg:c12-multiplicity-list-decoder} (with \)(1,k-1)\(-degree at most \)D\( and \)r\( roots at each \)(α_i,y_i)\(). Let \)P(X)\( have degree at most \)k-1\( with \)P(α_i)=y_i\( for at least \)t > D/r\( values of \)i\(. Then \)Y-P(X)\( divides \)Q(X,Y)\(. \)
Let
\(\)R(X) = Q(X,P(X))\(. By Lemma~ \ref{lem:c12-weighted-degree-bound} (using \)(P)≤k-1\(), \)(R) ≤D\(. By Lemma~ \ref{lem:c12-multiplicity-claim}, for each of the at least \)t\( indices \)i\( with \)P(α_i)=y_i\(, \)(X-α_i)^r\( divides \)R(X)\(; since the \)α_i\('s are distinct, \)R(X)\( has at least \)tr\( roots counted with multiplicity. Since \)tr > D ≥(R)\(, the degree mantra (Lemma~ \ref{lem:c12-degree-mantra}) forces \)R ≡0\(, i.e.\ \)Y-P(X)\( divides \)Q(X,Y)\(. \)
Algorithm 275 list-decodes Reed-Solomon codes of rate
\(\)R\( from up to \)1-R\( fraction of errors, in polynomial time. \)
Interpolation step: By Lemma 276, the
\(\)n\( multiplicity-\)r\( constraints impose a total of \)nr+12\( homogeneous linear constraints on the coefficients of \)Q(X,Y)\(. As in the proof of Theorem~ \ref{thm:c12-weighted-correctness}, the number of coefficients of a \)(1,k-1)\(-degree-\)D\( polynomial is at least \)\(, so Step~ 1 succeeds whenever \[ \frac{D(D+2)}{2(k-1)} {\gt} n\binom {r+1}{2}, \quad \text{equivalently}\quad D^2+2D {\gt} n(k-1)r(r+1). \] The choice \)D = (k-1)nr(r+1)\( suffices. \emph{Root-finding step}: By Lemma~ \ref{lem:c12-multiplicity-roots}, it suffices to have \)t > D/r\(. Substituting \)D=(k-1)nr(r+1)\( and choosing \)r = 2(k-1)n\( gives, for \)t ≥(k-1)n+12\(, that \)tr>D\(; and since \)-n+1/2<0\( for \)n≥1\(, this is satisfied by \)t ≥kn\(. Writing \)R=k/n\(, \)t/n ≥R\(, so the algorithm corrects up to \)e/n = 1-t/n ≤1-R\( fraction of errors, matching the Johnson bound (cross-ref thm:c07-johnson-bound). \emph{Runtime}: Step~ 1 is Gaussian elimination on \)O(n)\( coefficients (as \)D=O(n)\( for fixed \)k,r\( chosen polynomial in \)n\(), and root-finding is done by polynomial-time bivariate factorization (Theorem~ \ref{thm:c12-weighted-correctness}. \)
12.3 Extensions
The multiplicity list-decoding algorithm generalizes to non-uniform multiplicities, to repeated evaluation points, and to a "soft" version of the decoding problem where the constraint at each position is a set of weights rather than a single symbol. The book leaves the proofs of the results in this section as exercises; we record the statements as (unready) nodes below, since honestly reconstructing the proofs would require redoing significant parts of Lemma 276’s argument that are not spelled out in the source.
Given non-negative integer multiplicities
\(\)w_i ≥0\( for \)1 ≤i ≤n\(, Algorithm~ \ref{alg:c12-multiplicity-list-decoder} can be generalized (by requiring \)Q(X,Y)\( to have \)w_i\( roots at \)(α_i,y_i)\() to output all polynomials \)P(X)\( of degree at most \)k-1\( such that \[ \sum _{i : P(\alpha _i)=y_i} w_i {\gt} \sqrt{2(k-1)\sum _{i=0}^n \binom {w_i+1}{2}}. \] \)
There is an algorithm that, given positive integer weights
\(\)w_i,α\( for every \)1 ≤i ≤n\( and \)αF\(, runs in time polynomial in \)n\( and \)∑_i,αw_i,α\(, and outputs all polynomials \)P(X)\( of degree at most \)k-1\( such that \[ \sum _i w_{i,P(\alpha _i)} {\gt} \sqrt{(k-1)\sum _{i=0}^n \sum _{\alpha \in \mathbb {F}} w_{i,\alpha }^2}. \] \)
In the soft decoding problem, the decoder is given non-negative weights
\(\)w_i,α\( (\)1 ≤i ≤n\(, \)αF_q\() and a threshold \)W ≥0\(, and must output all codewords \)(c_1,…,c_n)\( of a \)q\(-ary code of block length \)n\( satisfying \)∑_i=1^n w_i,c_i ≥W\(. \)
For every
\(\)ε>0\(, the algorithm of Theorem~ \ref{thm:c12-general-multiplicity} solves the soft decoding problem (Definition~ \ref{def:c12-soft-decoding}) with \[ W = \sqrt{(1+\varepsilon )(k-1)\sum _{i=0}^n\sum _{\alpha \in \mathbb {F}} w_{i,\alpha }^2}. \] \)
Immediate from Theorem 281, taking the weight sum threshold with a
\(\)(1+ε)\( slack to absorb rounding of the integer weights. \)
Setting
\(\)w_i,y_i=1\( and \)w_i,α=0\( for \)αF∖{y_i}\( (\)1≤i ≤n\() in the soft decoding problem (Definition~ \ref{def:c12-soft-decoding}) recovers exactly the list decoding problem (Problem~ \ref{def:c12-rs-list-decoding}) for received word \)(y_1,…,y_n)\(. \)
Let
\(\)C ⊆F_q^n\( be a code. For \)ε[0,1]\( and integers \)0 ≤ℓ≤q\( and \)L\(, \)C\( is \)\(\)(ε,ℓ,L)\(-list recoverable\) if for every sequence of sets \(\)S_1,…,S_n\( with \)|S_i| ≤ℓ\( for all \)i\(, there are at most \)L\( codewords \)c=(c_1,…,c_n) C\( satisfying \)|{i [n] ∣c_i S_i}| ≥t := (1-ε)n\(. \)C\( is \)\(\)(ε,ℓ,L)\(-efficiently-list-recoverable\) if there is a polynomial-time algorithm finding all such codewords.
\(\)w_i,α=1\( for \)αS_i\( and \)w_i,α=0\( otherwise. \)
For every
\(\)k ≤n ≤q\(, the \)[n,k]_q\( Reed-Solomon code (cross-ref def:c05-reed-solomon) is \)(1-(k-1)ℓ/n), ℓ, poly(n)\(-efficiently list recoverable. \)