13 Decoding Reed-Muller Codes

In this chapter we describe decoding algorithms for the Reed-Muller codes introduced in Chapter 9 (see , not rendered as a dependency of this paragraph but recalled here for context). Recall that \(\)RM(q,m,r) = {f : F_q^m F_q ∣(f) ≤r}\(, and that its minimum distance is \)Δ_q,m,r = (q-t)·q^m-s-1\( where \)s,t\( satisfy \)r = s(q-1)+t\( and \)0 ≤t ≤q-2\(. We first describe an algorithm to correct \)ε·Δ_q,m,r\( errors for some constant \)ε>0\( depending only on \)q\(; later we give algorithms correcting up to \)(Δ_q,m,r-1)/2 \( errors. \)

13.1 A natural decoding algorithm

\(\)m\(-variate polynomial \)P F_q[X_1,…,X_m]\( and an \)m\(-dimensional \)s\(-variate affine form \)A = a_1,…,a_m(F_q[Z])^m\( where \)Z=(Z_1,…,Z_s)\(, the \emph{affine substitution} of \)A\( into \)P\( is the polynomial \)P○A F_q[Z]\( given by \)(P○A)(Z) = P(a_1(Z),…,a_m(Z))\(. The notion of affine substitution extends naturally to functions, viewing both \)f\( and \)A\( as functions given by the evaluations of the corresponding polynomials. \)

\(\)A\( is an affine form, then for every polynomial \)P\(, we have \)(P○A) ≤(P)\(. \begin{proof} For any single monomial \end{proof}\)M = ∏_i=1^m X_i^r_i\(, the affine substitution \)M ○A = ∏_i=1^m a_i(Z)^r_i\( has degree at most \)(M)\(, since each \)a_i(Z)\( has degree at most \)1\(. Writing a general polynomial as a sum of monomials \)P = ∑_M c_M ·M\(, affine substitution is additive, so \)P ○A = ∑_M c_M (M○A)\(. Hence \[ \deg (P\circ A) = \deg \Big(\sum _M c_M (M \circ A)\Big) \le \max _M \{ \deg (M\circ A)\} \le \max _M \deg (M) = \deg (P). \qedhere \] \)

\(\)A(z) = Mz + b\(, i.e.\ where \)M F_q^m×s\( and \)b F_q^m\( are chosen uniformly and independently from their respective domains. \begin{enumerate} \item Fix \end{enumerate}\)z F_q^s\(. Then, for a uniformly random \)A\(, the point \)A(z)\( is distributed uniformly in \)F_q^m\(. \item Fix \)z F_q^s ∖{0}\( and \)x F_q^m\(, and let \)A\( be chosen uniformly subject to the condition \)A(0) = x\(. Then the point \)A(z)\( is distributed uniformly in \)F_q^m\(. Consequently, for every pair of functions \)f,g : F_q^m F_q\(, \[ \Pr _A\big[ f\circ A(\mathbf z) \ne g \circ A(\mathbf z)\big] = \delta (f,g). \] \)

\(\)A(z) = Mz + b\( where \)M F_q^m×s\( and \)b F_q^m\( are chosen uniformly and independently. \emph{Part (1).} For every fixed \)M\( and \)z\(, \)Mz + b\( is uniform over \)F_q^m\( when \)b\( is uniform: for every \)y F_q^m\(, \)_b[Mz + b = y] = _b[b = y - Mz] = q^-m\(. Since this holds for every \)M\(, we get \)_M,b[Mz+b = y] = q^-m\(, i.e.\ \)A(z) = Mz + y\( is uniformly distributed over \)F_q^m\(. \emph{Part (2).} The condition \)A(0)=x\( forces \)b = x\(. So, for fixed \)y F_q^m\(, \[ \Pr _{M,\mathbf b}[A(\mathbf z) = \mathbf y \mid A(\mathbf0)=\mathbf x] = \Pr _M[M\mathbf z + \mathbf x = \mathbf y]. \] Write \)z = (z_1,…,z_s)\( and let \)M_1,…,M_s\( be the columns of \)M\(, so \)Mz = z_1M_1 + + z_sM_s\(. Since \)z ≠0\(, let \)i\( be the largest index with \)z_i ≠0\(. For every choice of the other columns, the probability over the choice of \)M_i\( that \)Mz + x = y\( is \)q^-m\(, since this occurs iff \)M_i = z_i^-1(y - (z_1M_1++z_i-1M_i-1+x))\(, an event of probability \)q^-m\(. Averaging over the remaining columns, \)_M,b[A(z)=y ∣A(0)=x] = q^-m\( for every \)y\(, establishing uniformity of \)A(z)\( conditioned on \)A(0)=x\(. For the final claim, fix \)f,g\( and let \)E = {y F_q^m ∣f(y)≠g(y)}\(, so \)δ(f,g) = _y[y E]\(. Then \[ \Pr _A[f\circ A(\mathbf z) \ne g\circ A(\mathbf z)] = \Pr _A[A(\mathbf z)\in E] = \Pr _{\mathbf y}[\mathbf y \in E] = \delta (f,g), \] using that \)A(z)\( is uniform in \)F_q^m\( even conditioned on \)A(0) = x\(. \qedhere \)

\(\)r < m\(, \)0 < e ≤13 ·q^m - (r+1)/(q-1)\(, and a function \)f : F_q^m F_q\(. \textbf{Output:} A polynomial \)P F_q[X_1,…,X_m]\( with \)(P) ≤r\( such that \)|{x F_q^m ∣f(x) ≠P(x)}| ≤e\(, if such a polynomial exists, and \)NULL\( otherwise. For every \)x F_q^m\(, compute \)g(x) = Local-Decode-RM-Simple(x,f)\( and return \)Interpolate(q,m,g,r,F_q^m)\(, where: \begin{itemize} \item \end{itemize}\)Local-Decode-RM-Simple(x,f)\( repeats \)Local-Decode-RM-Simple-Iter(x,f)\( \)O(mq)\( times and returns the most frequent answer. \item \)Local-Decode-RM-Simple-Iter(x,f)\( sets \)s ←(r+1)/(q-1)\(, selects an \)m\(-dimensional \)s\(-variate affine form \)A\( uniformly conditioned on \)A(0)=x\(, computes \)g ←Interpolate(q,s,f○A, r, F_q^s ∖{0})\( (setting \)g ←0\( if this returns \)NULL\(), and returns \)g(0)\(. \item \)Interpolate(q,m,f,r,S)\( returns a polynomial \)P F_q[Z_1,…,Z_s]\( with \)(P)≤r\( and \)P(x) = f(x)\( for every \)x S\(, or \)NULL\( if no such \)P\( exists; this can be implemented by Gaussian elimination. \)

\(\)P F_q[X_1,…,X_m]\( be a polynomial of degree at most \)r\( and let \)f : F_q^m F_q\( be such that \[ e = |\{ \mathbf x \in \mathbb {F}_q^m \mid f(\mathbf x)\ne P(\mathbf x)\} | \le \frac13 \cdot q^{m-\lceil (r+1)/(q-1)\rceil }. \] Then, for every \)x F_q^m\(, the probability that \)Local-Decode-RM-Simple-Iter(x,f)\( returns \)P(x)\( is at least \)2/3\(. \begin{proof} Let \end{proof}\)s = (r+1)/(q-1)\(, so \)e ≤q^m-s/3\(. Fix \)z F_q^s ∖{0}\(. Since \)A\( is picked conditioned on \)A(0) = x\(, part (2) of \ref{prop:c13-affine-uniform} gives that \)A(z)\( is uniformly random in \)F_q^m\( (independent of \)x\(), so \)_A[f(A(z)) ≠P(A(z))] = e/q^m\(. Taking a union bound over all \)z F_q^s∖{0}\(, \[ \Pr _A\big[\exists \mathbf z \in \mathbb {F}_q^s\setminus \{ 0\} \text{ s.t. } f(A(\mathbf z)) \ne P(A(\mathbf z))\big] \le (q^s-1)\cdot \frac{e}{q^m} \le \frac{e}{q^{m-s}} \le \frac13. \] So with probability at least \)2/3\(, \)f○A(z) = P○A(z)\( for every \)z F_q^s∖{0}\(. We argue this suffices. Since \)P○A\( is a polynomial in \)F_q[Z_1,…,Z_s]\( of degree at most \)r\( agreeing with \)f○A\( on every \)z F_q^s ∖{0}\(, there is at least one polynomial satisfying the condition of the interpolation step. It remains to show it is unique. Any two distinct polynomials of degree less than \)s(q-1)\( in \)s\( variables over \)F_q\( disagree in at least two points of \)F_q^s\( ; since our choice \)s = (r+1)/(q-1)\( ensures \)r < (q-1)s\(, this applies to \)P○A\( and any competing interpolant \)h\(, so they disagree in at least one point of \)F_q^s∖{0}\(. Hence \)P○A\( is the unique polynomial fitting the interpolation condition, and \)Local-Decode-RM-Simple-Iter(x,f)\( returns \)(P○A)(0) = P(A(0)) = P(x)\(, proving the lemma. \qedhere \)

\(\)X_1,…,X_n\( are independent Boolean random variables with \)[X_i=1] ≥p\( for each \)i\(, then for every \)γ>0\(, \[ \Pr \Big[\sum _{i=1}^n X_i {\lt} (p-\gamma )n\Big] \le \exp (-2\gamma ^2 n). \] \)

\(\)n\( time algorithm decoding the Reed-Muller code \)RM(q,m,r)\( from \)e ≤13 ·q^m-(r+1)/(q-1)\( errors. \begin{proof} Fix \end{proof}\)P F_q[X_1,…,X_m]\( of degree at most \)r\( and \)f : F_q^m F_q\( with \)e = |{x ∣f(x) ≠P(x)}| ≤13 q^m-(r+1)/(q-1)\(. Fix \)x F_q^m\(. By \ref{lem:c13-simple-rm-analysis}, a single call to \)Local-Decode-RM-Simple-Iter(x,f)\( returns \)P(x)\( with probability at least \)2/3\(. By \ref{lem:c13-chernoff-bound}, applied to the \)O(mq)\( independent repetitions, the majority answer equals \)P(x)\( except with probability \)(-Ω(mq))\(; choosing the constant in the \)O(·)\( appropriately makes this probability at most \)q^-m/3\(. By the union bound over all \)x F_q^m\(, with probability at least \)2/3\( the outer loop computes \)g(x) = P(x)\( for every \)x\(, and the final interpolation then returns \)P\( with probability at least \)2/3\(. For the running time, let \)T_int(n)\( be the (near-linear) time to interpolate a degree-\)≤r\( polynomial from \)n\( evaluations. Each call to \)Local-Decode-RM-Simple-Iter\( takes time \)T_int(q^s)\(, so \)Local-Decode-RM-Simple\( takes \)O(m·T_int(q^s) q)\( steps, and since it is invoked \)q^m\( times, the overall running time is bounded by \)T_int(q^m) + O(m·q^m ·T_int(q^s)q)\(. With \)n=q^m\( and \)e_ = q^m-s/3\(, and crudely bounding interpolation cost by a cubic function, this is \)O(n^3) + On\(. \qedhere \)

13.2 Majority logic decoding

The algorithm of Section 13.1 corrects errors up to a constant fraction of the distance (with the constant depending on \(\)q\(, but not on \)m\( or \)r\(). In this section we develop an algorithm, over \)F_2\(, correcting the optimal number of errors, i.e.\ up to half the minimum distance. \begin{thmenv}[Sum of a low-degree polynomial over the full cube vanishes] \label{lem:c13-monomial-sum-zero} Let \end{thmenv} \)g F_2[X_1,…,X_r]\( have degree strictly less than \)r\(. Then \)∑_a F_2^r g(a) = 0\(. \begin{proof} By linearity it suffices to prove this for a monomial \end{proof}\)X_S = ∏_iS X_i\( with \)S [r]\(. Since \)S ≠[r]\(, fix \)j S\(. The value of \)X_S\( does not depend on the coordinate \)a_j\(, so \[ \sum _{\mathbf a \in \mathbb {F}_2^r} X_S(\mathbf a) = \sum _{a_j \in \mathbb {F}_2} \; \sum _{\mathbf a : \text{coordinate } j = a_j} X_S(\mathbf a) = 2 \cdot \sum _{\mathbf a: a_j = 0} X_S(\mathbf a) = 0 \] in \)F_2\(, since \)2=0\(. Summing over all monomials of degree \)<r\( appearing in \)g\( gives the claim. \qedhere \)

\(\)P F_2[X_1,…,X_m]\( be of degree \)r\( and let \)C F_2\( be the coefficient of the monomial \)∏_i=1^r X_i\( in \)P\(. Then, for every \)b F_2^m-r\(, it is the case that \)∑_a F_2^r P(a,b) = C\(. \begin{proof} Let \end{proof}\)P_b(X_1,…,X_r) = P(X_1,…,X_r,b)\(, i.e.\ \)P_b\( is \)P\( restricted to the subspace \)X_i = b_i\( for \)r < i ≤m\(. The coefficient of the monomial \)X_1X_r\( in \)P_b\( remains \)C\(, since every other monomial of \)P\( has degree strictly less than \)r\( after the substitutions \)X_i=b_i\( (using \)(P)≤r\(). So we can write \)P_b = C·X_1X_r + g\( where \)(g) < r\(. We compute \[ \sum _{\mathbf a \in \mathbb {F}_2^r} P_{\mathbf b}(\mathbf a) = \sum _{\mathbf a \in \mathbb {F}_2^r} C\cdot \Big(\prod _{j=1}^r a_j\Big) + \sum _{\mathbf a\in \mathbb {F}_2^r} g(\mathbf a) = C, \] where the first summation equals \)C\( since every term with some \)a_j = 0\( vanishes and only the term \)a = 1\( contributes, and the second summation is \)0\( by \ref{lem:c13-monomial-sum-zero}. \qedhere \)

\(\)S ⊆[m]\(, let \)X_S\( denote the monomial \)∏_iS X_i\(. \)

\(\)S ⊆[m]\( with \)|S|=t\( and vectors \)a F_2^t\(, \)b F_2^m-t\(, let \)(S ←a, S ←b)\( denote the vector in \)F_2^m\( whose coordinates in \)S\( are given by \)a\( and coordinates in \)S = [m]∖S\( are given by \)b\(. \)

\(\)S ⊆[m]\( with \)|S|=t\( and vectors \)a F_2^t\(, \)b F_2^m-t\(, let \)f(S←a, S ←b)\( denote the evaluation of \)f\( on \)(S←a, S ←b)\(. \)

\(\)r < m\(, \)0 ≤e < 12 2^m-r\(, and function \)f : F_2^m F_2\(. \textbf{Output:} A polynomial \)P\( with \)(P) ≤r\( and \)|{xF_2^m ∣P(x)≠f(x)}| ≤e\(. Set \)P_r+1 ←0\(. For \)t = r\( downto \)0\(: \begin{itemize} \item \end{itemize}\)f_t ←f - P_t+1\(. \item For every \)S ⊆[m]\( with \)|S|=t\( and every \)b F_2^m-t\(, compute \)C_S,b ←∑_a F_2^t f_t(S←a, S ←b)\(, and set \)C_S ←majority_b{C_S,b}\(. \item \)P_t ←P_t+1 + ∑_S⊆[m], |S|=t C_S X_S\(. \)

Return \(\)P_0\(. \)

\(\)f : F_2^m F_2\( that disagrees with a polynomial \)Q F_2[X_1,…,X_m]\( of degree at most \)r\( on at most \)e < 12 ·2^m-r\( points, the algorithm \)Majority Logic Decoder(f)\( correctly outputs \)Q\(. \begin{proof} Let \end{proof}\)Q(X) = ∑_S⊆[m] C’_S X_S\( and \)Q_t(X) = ∑_S⊆[m]: |S|≥t C’_S X_S\(. We argue by downward induction on \)t\( (from \)r+1\( down to \)0\() that \)Q_t = P_t\(, where \)P_t\( are the polynomials computed by the algorithm. The base case \)t=r+1\( is immediate since \)P_r+1=Q_r+1=0\(. Assume \)P_t+1 = Q_t+1\(. Then \)f_t = f - P_t+1\( and \)Q - Q_t+1\( satisfy: for every \)x\(, \)f_t(x) ≠(Q-Q_t+1)(x)\( iff \)f(x) ≠Q(x)\( (both sides are obtained from \)f,Q\( by subtracting the same function \)P_t+1=Q_t+1\(), so \)f_t\( disagrees with \)Q-Q_t+1\( on at most \)e\( points, exactly the same set as \)f,Q\(. We show that for every \)S⊆[m]\( with \)|S|=t\(, \)C_S = C’_S\(. Fix such \)S\(. For \)b F_2^m-t\(, call the partial assignment \)S ←b\( a \emph{subcube}, corresponding to the points \){(S←a,S←b) ∣a F_2^t}\(; say this subcube is \emph{in error} if there exists \)a\( with \)f_t(S←a,S←b) ≠(Q-Q_t+1)(S←a,S←b)\(. By \ref{prop:c13-majority-coefficient}, if a subcube is not in error then \)C_S,b = C’_S\(, since \)C’_S\( is the coefficient of \)X_S\( in \)Q-Q_t+1\( (a polynomial of degree at most \)t\(). At most \)e\( subcubes can be in error: each disagreement point \)x\( between \)f_t\( and \)Q-Q_t+1\( lies in exactly one subcube (namely \)S ←x|_S\(), so the number of subcubes containing at least one disagreement point is at most the total number \)e\( of disagreements. Since the total number of subcubes is \)2^m-t ≥2^m-r > 2e\(, a strict majority of subcubes are not in error, so \)C_S = majority_b{C_S,b} = C’_S\(. Hence for every \)S\( with \)|S|=t\(, \)C_S=C’_S\(, so \)Q_t=P_t\(, completing the inductive step. So for every \)t\(, \)P_t=Q_t\(, and in particular \)P_0=Q_0=Q\(. \qedhere \)

\(\)0 ≤r < m\(, the Majority Logic Decoder (\ref{alg:c13-majority-logic-decoder}) corrects up to \)d2-1\( errors in the Reed-Muller code \)RM(2,m,r)\( in \)O(n^2)\( time, where \)n=2^m\( is the block length of the code and \)d=2^m-r\( is its minimum distance. \begin{proof} By \ref{lem:c13-majority-logic-analysis}, on input \end{proof}\)f\( disagreeing with some degree-\)≤r\( polynomial \)Q\( on \)e < 12 2^m-r = d/2\( points, the algorithm correctly outputs \)Q\(; since \)d\( is even, this is exactly \)e ≤d/2-1\( errors corrected. For the running time, the algorithm runs for at most \)n=2^m\( iterations of the outer structure times the number of coefficients of a degree-\)r\( polynomial, which is \)∑_i=0^r mi ≤n\( in the binary case; computing each \)C_S,b\( and the majority takes time linear in the corresponding subcube sizes, and summing over all \)S,b\( gives a crude bound of \)O(n^2)\( overall. \qedhere \)

13.3 Decoding by reduction to Reed-Solomon decoding

The algorithms so far are based on basic ideas, but the Simple Reed-Muller Decoder (292) fails to correct up to half the minimum distance, and the Majority Logic Decoder (301) seems to work only over \(\)F_2\(. We now give an algorithm using a slightly more sophisticated algebraic idea, which yields an almost ‘trivial’ reduction to Reed-Solomon decoding, and thus can use any algorithm for Reed-Solomon decoding . \)

13.3.1 A bijection from F_q^m\( vs. \)F_q^m

\(\)q\( and \)m ≥1\(, the trace map \)Tr : F_q^m F_q\( given by \)Tr(x) = ∑_j=0^m-1 x^q^j\( is \)F_q\(-linear, and for every nonzero \)c F_q^m\( the map \)z ↦Tr(cz)\( is a nonzero \)F_q\(-linear functional \)F_q^m F_q\(. \)

\(\)F_q\(-linear bijection from \)F_q^m\( to \)F_q^m\(. If \)Φ= (Φ_1,…,Φ_m) : F_q^m F_q^m\( is an \)F_q\(-linear bijection then each \)Φ_i(Z)\( is a trace function: there exist \)λ_1,…,λ_m F_q^m\(, linearly independent over \)F_q\(, such that \)Φ_i(Z) = Tr(λ_i Z) = ∑_j=0^m-1 λ_i^q^j Z^q^j\(. In particular \)(Φ_i) = q^m-1\( and \)Φ\( is a linearized polynomial map (only nonzero coefficients are for monomials \)Z^q^j\(). \begin{proof} That every \end{proof}\)F_q\(-linear bijection \)Φ\( has each coordinate given by a trace function \)Φ_i(Z) = Tr(λ_iZ)\( for some \)λ_i F_q^m\( is a standard fact about \)F_q\(-linear functionals on \)F_q^m\( ; it remains to show that \)λ_1,…,λ_m\( (linearly independent, since \)Φ\( is injective) give a bijection, i.e.\ that the resulting \)Φ\( is surjective. Linearity of \)Φ\( follows from linearity of \)Tr\( (\ref{lem:c13-trace-basic}). Since \)dom(Φ)\( and \)range(Φ)\( have the same cardinality \)q^m\(, it suffices to show \)Φ\( is surjective. Let \)S = {Φ(u) ∣u F_q^m} ⊆F_q^m\(; by linearity of \)Φ\(, \)S\( is an \)F_q\(-subspace of \)F_q^m\(. Suppose towards a contradiction that \)S ≠F_q^m\(. Since \)S\( is a proper subspace, it is contained in the kernel of some nonzero linear functional, i.e.\ there exists \)(α_1,…,α_m) F_q^m ∖{0}\( such that \)∑_i=1^m α_iβ_i = 0\( for every \)(β_1,…,β_m) S\( (standard linear algebra over \)F_q\(). Applying this to \)β_i = Φ_i(u)\( for every \)uF_q^m\( gives, using linearity of \)Tr\(, \[ 0 = \sum _i \alpha _i \Phi _i(u) = \sum _i \alpha _i \mathrm{Tr}(\lambda _i u) = \mathrm{Tr}\Big(\Big(\sum _i \alpha _i\lambda _i\Big)\cdot u\Big) \quad \text{for every } u\in \mathbb {F}_{q^m}. \] Let \)c = ∑_i α_iλ_i\(. Since \)λ_1,…,λ_m\( are linearly independent over \)F_q\( and \)(α_i)\( is not all zero, \)c≠0\(. By \ref{lem:c13-trace-basic}, \)z↦Tr(cz)\( is then a nonzero polynomial of degree at most \)q^m-1\( in \)Z\(; but we have just shown it vanishes on every \)u F_q^m\(, a set of size \)q^m > q^m-1\(, contradicting the fact that a nonzero polynomial of degree \)D\( has at most \)D\( roots. Hence \)S = F_q^m\(, i.e.\ \)Φ\( is surjective, and hence bijective. \qedhere \)

\(\)q\( and non-negative integers \)m,r\(, the \)extension degree of \(\)r\( over \)F_q^m\(\), denoted \(\)R_q,m(r)\(, is the maximum degree of \)p○Φ\( over all choices of \)p F_q[X_1,…,X_m]\( (or the associated function \)p:F_q^mF_q\() of degree at most \)r\( and over all \)F_q\(-linear bijections \)Φ: F_q^mF_q^m\(. (Here \)f○Φ\(, for \)F:F_q^m F_q^m\(, has as its degree the degree of the unique polynomial \)PF_q^m[Z]\( with \)(P)<q^m\( representing \)F\(.) \)

\(\)q\(, \)r < m(q-1)\(, \)0 ≤e < (q^m - R_q,m(r))/2\(, and a function \)f : F_q^m F_q\(. \textbf{Output:} A polynomial \)p\( with \)(p) ≤r\( and \)|{x F_q^m ∣p(x)≠f(x)}| ≤e\(. Let \)Φ: F_q^m F_q^m\( be an \)F_q\(-linear bijection. For \)u F_q^m\(, set \)F(u) ←f(Φ(u))\(. Let \)P\( be the output of decoding \)F\( using a Reed-Solomon decoder (with \)k = R_q,m(r)+1\(, \)n=q^m\(, and pairs \)(u,F(u))\( for \)uF_q^m\(). For \)uF_q^m\(, set \)p(u) ←P(Φ^-1(u))\(. Return \)p\(. \)

\(\)f : F_q^m F_q\( be any function and let \)g : F_q^m F_q\( be a degree-\)r\( polynomial such that \)|{uF_q^m ∣f(u)≠g(u)}| ≤e < (q^m-R_q,m(r))/2\(. Then \)Reed-Solomon-based Decoder(f)\( returns \)g\(. \begin{proof} Let \end{proof}\)G = g○Φ\(. Then \)(G) ≤R_q,m(r)\( and \){vF_q^m ∣F(v)≠G(v)}| ≤e < (q^m-R_q,m(r))/2\(. Since the distance of the Reed-Solomon code with \)N=q^m\( and \)K = R_q,m(r)+1\( is \)N-K+1 = q^m - R_q,m(r)\(, and \)e\( is less than half this distance, \)G\( is the unique degree \)<K\( polynomial with this property, so the Reed-Solomon decoder must return \)P=G\(. Hence \)p = P○Φ^-1 = G○Φ^-1 = g\(, as claimed. \qedhere \)

13.3.2 Analysis of extension degree

\(\)R_q,m(r) = r·q^m-1\(. \begin{proof} We prove \end{proof}\)R_q,m(r) ≤r·q^m-1\(; the matching lower bound is obtained via an explicit extremal polynomial construction which we do not reconstruct here (see the TODO above). Let \)p F_q[X_1,…,X_m]\( have degree at most \)r\( and let \)Φ=(Φ_1,…,Φ_m)\( be an \)F_q\(-linear bijection. By \ref{prop:c13-linear-bijection-exists} each \)Φ_i\( is a polynomial of degree \)q^m-1\(, so \)p(Φ_1(Z),…, Φ_m(Z))\( is a polynomial of degree at most \)r·q^m-1\(. Since reduction modulo \)(Z^q^m-Z)\( does not increase degree, \)p○Φ\( is a polynomial of degree at most \)r·q^m-1\(, as desired. \)

\(\)r < q\( then the Reed-Solomon-based Decoder decodes \)RM(q,m,r)\( up to half its minimum distance. \begin{proof} The distance of \end{proof}\)RM(q,m,r)\( (for \)r<q\() is \)(q-r)·q^m-1\(. By \ref{prop:c13-extension-degree-linear}, the Reed-Solomon-based Decoder decodes provided \)e < (q^m - R_q,m(r))/2 = (q^m - r·q^m-1)/2 = (q-r)·q^m-1/2\(, i.e.\ up to half the minimum distance. \qedhere \)

\(\)α,βF_q^m\( and \)P,P_1,P_2 F_q^m[Z]\(: \begin{enumerate} \item \end{enumerate}\)_q(αP_1+βP_2) ≤{_q(P_1),_q(P_2)}\(. \item \)_q(P_1·P_2) ≤_q(P_1)+_q(P_2)\(. \item \)_q(P (Z^q^m-Z)) ≤_q(P)\(. (Note that here the total degree \)(P)\( can be strictly greater than \)q^m\(.) \item If \)(P) < q^m\( and \)_q(P) = s(q-1)+t\( for \)0≤t<q-1\(, then \)(P) ≤q^m - (q-t)q^m-s-1\(. \)

\(\)αP_1+βP_2\( lie in the union of the monomials of \)P_1\( and \)P_2\(. By part (1), it suffices to prove parts (2)–(4) for monomials. \emph{Part (2).} We wish to show \)_q(Z^d·Z^e) ≤_q(Z^d) + _q(Z^e)\(. Let \)d=∑_i d_iq^i\(, \)e=∑_i e_iq^i\( and \)f=d+e=∑_i f_iq^i\( be their base-\)q\( expansions. By carrying in base-\)q\( addition, one checks by induction that for every \)i\(, \)∑_j=0^i f_j ≤∑_j=0^i(d_j+e_j)\( (each carry only decreases the partial digit sum on the left relative to the uncarried sum on the right). Hence \[ \deg _q(Z^{d+e}) = \sum _j f_j \le \sum _j (d_j+e_j) = \deg _q(Z^d)+\deg _q(Z^e). \] \emph{Part (3).} Since \)Z^q^i = (Z^q^i/m)^m^i m\( modulo \)(Z^q^m-Z)\( we have \)Z^q^i ≡Z^q^i m Z^q^m-Z\(, so for \)d=∑_i d_iq^i\( with \)0≤d_i<q\(, \)Z^d_iq^i (Z^q^m-Z) = Z^d_iq^im\(. Then \[ \deg _q\big(Z^d \bmod (Z^{q^m}-Z)\big) = \deg _q\big(Z^{\sum _i d_iq^{i\bmod m}} \bmod (Z^{q^m}-Z)\big) \le \deg _q\big(Z^{\sum _i d_iq^{i \bmod m}}\big) \le \sum _i \deg _q\big(Z^{d_iq^{i\bmod m}}\big) = \sum _i d_i = \deg _q(Z^d), \] where the first inequality reduces exponents modulo \)m\( into range and the second uses part (2). \emph{Part (4).} Let \)d < q^m\( be given by \)d = ∑_i=0^m-1d_iq^i\(. Subject to \)∑_i d_i ≤s(q-1)+t\(, \)d\( is maximized when \)d_m-1==d_m-s=(q-1)\( and \)d_m-s-1=t\( (the base-\)q\( digits are pushed as high as possible while respecting the digit-sum bound and the constraint \)d_i<q\(), giving \)d ≤(q-1)(q^m-1++q^m-s) + tq^m-s-1 = q^m - (q-t)q^m-s-1\(. \qedhere \)

\(\)p F_q[X_1,…,X_m]\( and every \)F_q\(-linear bijection \)Φ\(, we have \)_q(p○Φ) ≤(p)\(. \begin{proof} By part (1) of \ref{prop:c13-q-degree-properties}, it suffices to prove this for a monomial \end{proof}\)M(X_1,…,X_m) = X_1^r_1X_m^r_m\( with \)∑_j r_j = r\(. Fix \)Φ= (Φ_1,…,Φ_m)\(. Let \)M\( denote the univariate polynomial \)M○ΦZ^q^m-Z\(. Note that \)M○Φ(Z) = ∏_i=1^m Φ_i(Z)^r_i\(, and \)_q(Φ_i(Z))=1\( for every \)i\( (by \ref{prop:c13-linear-bijection-exists}, \)Φ_i\( is a trace polynomial supported on monomials \)Z^q^j\(, each of \)q\(-degree exactly \)1\(; combined with part (1), \)_q(Φ_i) ≤1\(, and since \)Φ_i ≠0\(, \)_q(Φ_i)=1\(). By part (2) of \ref{prop:c13-q-degree-properties}, \[ \deg _q\Big(\prod _{i=1}^m \Phi _i(Z)^{r_i}\Big) \le \sum _{i=1}^m r_i = r. \] Finally by part (3) of \ref{prop:c13-q-degree-properties}, \[ \deg _q(\tilde M) = \deg _q\big(M\circ \Phi \bmod (Z^{q^m}-Z)\big) \le \deg _q(M\circ \Phi ) \le r, \] as desired. \qedhere \)

\(\)r = s(q-1)+t\( where \)0≤t<q-1\(. Then \)R_q,m(r) = q^m-(q-t)q^m-s-1\(. \begin{proof} We prove \end{proof}\)R_q,m(s(q-1)+t) ≤q^m-(q-t)q^m-s-1\(; the matching lower bound is obtained via an explicit extremal polynomial construction which we do not reconstruct here (see the TODO above). Fix \)pF_q[X_1, …,X_m]\( of degree at most \)r=s(q-1)+t\( and consider the function \)p○Φ: F_q^mF_q^m\(; this corresponds to the polynomial \)p(Z) = p(Φ_1(Z),…,Φ_m(Z)) (Z^q^m-Z)\(. By \ref{lem:c13-degq-bound}, \)_q(p) ≤r\(, and by construction \)(p) < q^m\(. So by part (4) of \ref{prop:c13-q-degree-properties}, \)(p) ≤q^m-(q-t)q^m-s-1\(, yielding the claimed bound on \)R_q,m(r) = (p)\(, maximized over \)p\( and \)Φ\(. \qedhere \)

\(\)q\(, integer \)m≥1\( and \)0≤r<m(q-1)\(, the Reed-Solomon-based Decoder decodes \)RM(q,m,r)\( up to half its minimum distance. \begin{proof} Let \end{proof}\)r=s(q-1)+t\( with \)0≤t<q-1\(. The distance of \)RM(q,m,r)\( is \)(q-t)·q^m-s-1\(. Combining \ref{prop:c13-rs-decoder-correct} with \ref{lem:c13-extension-degree-general}, the Reed-Solomon-based Decoder decodes provided \)e < (q^m - R_q,m(r))/2 = (q-t)q^m-s-1/2\(, i.e.\ up to half the minimum distance of \)RM(q,m,r)\(. \qedhere \)