Folded Reed–Solomon code

In coding theory, folded Reed–Solomon codes are like Reed–Solomon codes, which are obtained by mapping Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m } Reed–Solomon codewords over a larger alphabet by careful bundling of codeword symbols.

Folded Reed–Solomon codes are also a special case of Parvaresh–Vardy codes.

Using optimal parameters one can decode with a rate of R, and achieve a decoding radius of 1 − R.

The term "folded Reed–Solomon codes" was coined in a paper by V.Y. Krachkovsky with an algorithm that presented Reed–Solomon codes with many random "phased burst" errors [1]. The list-decoding algorithm for folded RS codes corrects beyond the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-\sqrt{R} } bound for Reed–Solomon codes achieved by the Guruswami–Sudan algorithm for such phased burst errors.

History

One of the ongoing challenges in Coding Theory is to have error correcting codes achieve an optimal trade-off between (Coding) Rate and Error-Correction Radius. Though this may not be possible to achieve practically (due to Noisy Channel Coding Theory issues), quasi optimal tradeoffs can be achieved theoretically.

Prior to Folded Reed–Solomon codes being devised, the best Error-Correction Radius achieved was Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1- \sqrt{R} } , by Reed–Solomon codes for all rates $R$.

An improvement upon this Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1- \sqrt{R} } bound was achieved by Parvaresh and Vardy for rates Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R <\tfrac{1}{16}.}

For Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R\to 0 } the Parvaresh–Vardy algorithm can decode a fraction Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1- O(R \log(1/R))} of errors.

Folded Reed–Solomon Codes improve on these previous constructions, and can be list decoded in polynomial time for a fraction Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-R-\varepsilon)} of errors for any constant $\varepsilon >0$.

Definition

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(X)\mapsto\begin{bmatrix}f(1)\\f(\gamma)\\\vdots\\f(\gamma^{m-1})\end{bmatrix},\begin{bmatrix}f(\gamma^m)\\f(\gamma^{m+1})\\\vdots\\f(\gamma^{2m-1})\end{bmatrix},\ldots,\begin{bmatrix}f(\gamma^{n-m})\\f(\gamma^{n-m+1})\\\vdots\\f(\gamma^{n-1})\end{bmatrix}}

Consider a Reed–Solomon Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [n=q-1,k]_q} code of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } and dimension $k$ and a folding parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \ge 1 } . Assume that $m$ divides Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Mapping for Reed–Solomon codes like this:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \mapsto \left \langle f(1), f \left (\gamma^1 \right ), f \left (\gamma^2 \right ), \ldots , f \left (\gamma^{n-1} \right ) \right \rangle }

where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma \in \mathbb{F}_q } is a primitive element in

$\mathbb {F} _{q}=\left\{0,1,\gamma ,\gamma ^{2},\ldots ,\gamma ^{n-1}\right\}$.

The Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} folded version of Reed Solomon code Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} , denoted $FRS_{\mathbb {F} ,\gamma ,m,k}$ is a code of block length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = n/m} over $\mathbb {F} ^{m}$. $FRS_{\mathbb {F} ,\gamma ,m,k}$ are just Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [q-1,k] } Reed Solomon codes with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m } consecutive symbols from RS codewords grouped together.

Graphic description

The above definition is made more clear by means of the diagram with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m=3} , where $m$ is the folding parameter.

The message is denoted by $f(X)$, which when encoded using Reed–Solomon encoding, consists of values of $f$ at $x_{0},x_{1},x_{2},\ldots ,x_{n-1}$, where $x_{i}=\gamma ^{i}$.

Then bundling is performed in groups of 3 elements, to give a codeword of length $n/3$ over the alphabet $\mathbb {F} _{q}^{3}$.

Something to be observed here is that the folding operation demonstrated does not change the rate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R } of the original Reed–Solomon code.

To prove this, consider a linear $[n,k,d]_{q}$ code, of length Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } , dimension $k$ and distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d } . The $m$ folding operation will make it a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left[\tfrac{n}{m}, \tfrac{k}{m},\tfrac{d}{m}\right]_{q^m}} code. By this, the rate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R = \tfrac{n}{k} } will be the same.

Folded Reed–Solomon codes and the singleton bound

According to the asymptotic version of the singleton bound, it is known that the relative distance $\delta$, of a code must satisfy Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R \leqslant 1-\delta + o(1) } where $R$is the rate of the code. As proved earlier, since the rate $R$ is maintained, the relative distance Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \delta \geqslant 1-R } also meets the Singleton bound.

Why folding might help?

Folded Reed–Solomon codes are basically the same as Reed Solomon codes, just viewed over a larger alphabet. To show how this might help, consider a folded Reed–Solomon code with $m=3$. Decoding a Reed–Solomon code and folded Reed–Solomon code from the same fraction of errors Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} are tasks of almost of the same computational intensity: one can unfold the received word of the folded Reed–Solomon code, treat it as an received word of the original Reed–Solomon code, and run the Reed–Solomon list decoding algorithm on it. Obviously, this list will contain all the folded Reed–Solomon codewords within distance $\rho$ of the received word, along with some extras, which we can expurgate.

Also, decoding a folded Reed–Solomon code is an easier task. Suppose we want to correct a third of errors. The decoding algorithm chosen must correct an error pattern that corrects every third symbol in the Reed–Solomon encoding. But after folding, this error pattern will corrupt all symbols over $\mathbb {F} _{q}^{3}$ and will eliminate the need for error correction. This propagation of errors is indicated by the blue color in the graphical description. This proves that the for a fixed fraction of errors $\rho ,$ the folding operation reduces the channel's flexibility to distribute errors, which in turn leads to a reduction in the number of error patterns that need to be corrected.

How folded Reed–Solomon (FRS) codes and Parvaresh Vardy (PV) codes are related

We can relate Folded Reed Solomon codes with Parvaresh Vardy codes which encodes a polynomial $f$ of degree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} with polynomials $f_{0}=f,f_{1},\ldots ,f_{s-1}(s\geqslant 2)$ where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_i(X)=f_{i-1}(X)^d \mod E(X)} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E(X)} is an irreducible polynomial. While choosing irreducible polynomial $E(X)=X^{q}-\gamma$ and parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} we should check if every polynomial $f$ of degree at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} satisfies $f(\gamma X)=f(X)^{d}\mod E(X)$ since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(\gamma X)} is just the shifted counterpart of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(X)} where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} is the primitive element in $\mathbb {F} _{q}.$ Thus folded RS code with bundling together code symbols is PV code of order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s=m} for the set of evaluation points

$\left\{1,\gamma ,\gamma ^{2m},\ldots ,\gamma ^{\left({\frac {n}{m}}-1\right)m}\right\}$.

If we compare the folded RS code to a PV code of order 2 for the set of evaluation points

$\left\{1,\gamma ,\ldots ,\gamma ^{m-2},\gamma ^{m},\gamma ^{m+1},\ldots ,\gamma ^{2m-2},\ldots ,\gamma ^{n-m},\gamma ^{n-m+1},\ldots ,\gamma ^{n-2}\right\}$

we can see that in PV encoding of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} , for every $0\leq i\leq n/m-1$ and every Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0<j<m-1, f(\gamma^{mi+j})} appears at $f(\gamma ^{mi+j})$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_1(\gamma^{-1}\gamma^{mi+j})} ,

unlike in the folded FRS encoding in which it appears only once. Thus, the PV and folded RS codes have same information but only the rate of FRS is bigger by a factor of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2(m-1)/m} and hence the list decoding radius trade-off is better for folded RS code by just using the list decodability of the PV codes. The plus point is in choosing FRS code in a way that they are compressed forms of suitable PV code with similar error correction performance with better rate than corresponding PV code. One can use this idea to construct a folded RS codes of rate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} that are list decodable up to radius approximately Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-R^{s/[s+1]}} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s\geq 1} . [2]

Brief overview of list-decoding folded Reed–Solomon codes

A list decoding algorithm which runs in quadratic time to decode FRS code up to radius Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1-R-\varepsilon} is presented by Guruswami. The algorithm essentially has three steps namely the interpolation step in which welch berlekamp style interpolation is used to interpolate the non-zero polynomial

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(X,Y_1,Y_2,\ldots,Y_s)=A_0(X) + A_1(X)Y_1 + A_2(X)Y_2 + \cdots + A_s(X)Y_s,}

after which all the polynomials $f\in \mathbb {F} _{q}[X]$ with degree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k-1} satisfying the equation derived in interpolation are found. In the third step the actual list of close-by codewords are known by pruning the solution subspace which takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^s} time.

Linear-algebraic list decoding algorithm

Guruswami presents a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\Omega (1/\varepsilon^2)}} time list decoding algorithm based on linear-algebra, which can decode folded Reed–Solomon code up to radius $1-R-\varepsilon$ with a list-size of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {n^{O(1/\varepsilon^2)}}} . There are three steps in this algorithm: Interpolation Step, Root Finding Step and Prune Step. In the Interpolation step it will try to find the candidate message polynomial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} by solving a linear system. In the Root Finding step, it will try to find the solution subspace by solving another linear system. The last step will try to prune the solution subspace gained in the second step. We will introduce each step in details in the following.

Step 1: The interpolation step

It is a Welch–Berlekamp-style interpolation (because it can be viewed as the higher-dimensional generalization of the Welch–Berlekamp algorithm). Suppose we received a codeword Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} -folded Reed–Solomon code as shown below

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(\begin{bmatrix}y_0\\y_1\\y_2\\\cdots\\y_{m-1}\end{bmatrix},\begin{bmatrix}y_m\\y_{m+1}\\y_{m+2}\\\cdots\\y_{2m-1}\end{bmatrix},\cdots,\begin{bmatrix}y_{n-m}\\y_{n-m+1}\\y_{n-m+2}\\\cdots\\y_{n-1}\end{bmatrix}\right)}

We interpolate the nonzero polynomial

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(X,Y_1,\ldots,Y_s)=A_0(X) + A_1(X)Y_1 + \cdots + A_s(X)Y_s, \qquad \begin{cases} \deg(A_i) \leqslant D & 1 \leqslant i \leqslant s \\ \deg(A_0) \leqslant D + k -1 & \end{cases}}

by using a carefully chosen degree parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} .

$D=\left\lfloor {\frac {N(m-s+1)-k+1}{s+1}}\right\rfloor$

So the interpolation requirements will be

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q \left (\gamma^{im+j},y_{im+j},y_{im+j+1},\ldots,y_{im+j+s-1} \right )=0, \quad \text{for} \quad i=0,1,\ldots, \tfrac{n}{m} - 1, j=0,1,\ldots,m-s.}

Then the number of monomials in $Q(X,Y_{1},\ldots ,Y_{s})$ is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (D + 1)s + D + k = (D+1)(s+1) + k -1 > N(m - s + 1)}

Because the number of monomials in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(X,Y_1,\ldots,Y_s)} is greater than the number of interpolation conditions. We have below lemma

Lemma 1. $0\neq Q\in \mathbb {F} _{q}[X,Y_{1},\ldots ,Y_{s}]$ satisfying the above interpolation condition can be found by solving a homogeneous linear system over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} with at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Nm} constraints and variables. Moreover this interpolation can be performed in $O(Nm\log ^{2}(Nm)\log \log(Nm))$ operations over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} .

This lemma shows us that the interpolation step can be done in near-linear time.

For now, we have talked about everything we need for the multivariate polynomial Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Q(X,Y_1,\ldots,Y_s)} . The remaining task is to focus on the message polynomials Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(X)} .

Lemma 2. If a candidate message polynomial $f(X)\in \mathbb {F} [X]$ is a polynomial of degree at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k-1} whose Folded Reed-Solomon encoding agrees with the received word $y$ in at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} columns with

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t>,}

then $Q(X,f(X),f(\gamma X),\ldots ,f(\gamma _{s-1}X))=0.$

Here "agree" means that all the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} values in a column should match the corresponding values in codeword $y$.

This lemma shows us that any such polynomial $Q(X,Y_{1},\ldots ,Y_{s})$ presents an algebraic condition that must be satisfied for those message polynomials Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} that we are interested in list decoding.

Combining Lemma 2 and parameter Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} , we have

$t(m-s+1)>{\frac {N(m-s+1)+s(k-1)}{s+1}}$

Further we can get the decoding bound

$t\geqslant {\frac {N}{s+1}}+{\frac {s}{s+1}}\cdot {\frac {k}{m-s+1}}=N\left({\frac {1}{s+1}}+{\frac {s}{s+1}}\cdot {\frac {mR}{m-s+1}}\right)$

We notice that the fractional agreement is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dfrac{1}{s+1} + \dfrac{s}{s+1} \cdot \dfrac{mR}{m-s+1}}

Step 2: The root-finding step

During this step, our task focus on how to find all polynomials Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\in{\mathbb{F}_q[X]}} with degree no more than $k-1$ and satisfy the equation we get from Step 1, namely

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_0(X) + A_1(X)f(X) + A_2(X)f(\gamma X) + \cdots + A_s(X)f(\gamma^{s-1}X)=0}

Since the above equation forms a linear system equations over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}_q} in the coefficients $f_{0},f_{1},\ldots ,f_{k-1}$ of the polynomial

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(X) = f_0 + f_1X + \cdots + f_{k-1}X^{k-1},}

the solutions to the above equation is an affine subspace of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{F}^k_q} . This fact is the key point that gives rise to an efficient algorithm - we can solve the linear system.

It is natural to ask how large is the dimension of the solution? Is there any upper bound on the dimension? Having an upper bound is very important in constructing an efficient list decoding algorithm because one can simply output all the codewords for any given decoding problem.

Actually it indeed has an upper bound as below lemma argues.

Lemma 3. If the order of $\gamma$ is at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} (in particular when $\gamma$ is primitive), then the dimension of the solution is at most $s-1$.

This lemma shows us the upper bound of the dimension for the solution space.

Finally, based on the above analysis, we have below theorem

Theorem 1. For the folded Reed–Solomon code Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle FRS^{(m)}_q[n,k]} of block length $N={\tfrac {n}{m}}$ and rate Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R=\tfrac{k}{n},} the following holds for all integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s, 1 \leqslant s \leqslant m} . Given a received word $y\in (\mathbb {F} _{q}^{m})^{N}$, in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O((Nm\log q)^2)} time, one can find a basis for a subspace of dimension at most Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s-1} that contains all message polynomials Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \in \mathbb{F}_q[X]} of degree less than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} whose FRS encoding differs from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} in at most a fraction

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{s}{s+1}\left(1-\frac{mR}{m-s+1}\right)}

of the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} codeword positions.

When $s=m=1$, we notice that this reduces to a unique decoding algorithm with up to a fraction Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-R)/2} of errors. In other words, we can treat unique decoding algorithm as a specialty of list decoding algorithm. The quantity is about Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{O(1/\varepsilon)}} for the parameter choices that achieve a list decoding radius of $1-R-\varepsilon$.

Theorem 1 tells us exactly how large the error radius would be.

Now we finally get the solution subspace. However, there is still one problem standing. The list size in the worst case is $n^{\Omega (1/\varepsilon )}$. But the actual list of close-by codewords is only a small set within that subspace. So we need some process to prune the subspace to narrow it down. This prune process takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^s} time in the worst case. Unfortunately it is not known how to improve the running time because we do not know how to improve the bound of the list size for folded Reed-Solomon code.

Things get better if we change the code by carefully choosing a subset of all possible degree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k -1} polynomials as messages, the list size shows to be much smaller while only losing a little bit in the rate. We will talk about this briefly in next step.

Step 3: The prune step

By converting the problem of decoding a folded Reed–Solomon code into two linear systems, one linear system that is used for the interpolation step and another linear system to find the candidate solution subspace, the complexity of the decoding problem is successfully reduced to quadratic. However, in the worst case, the bound of list size of the output is pretty bad.

It was mentioned in Step 2 that if one carefully chooses only a subset of all possible degree Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k -1} polynomials as messages, the list size can be much reduced. Here we will expand our discussion.

To achieve this goal, the idea is to limit the coefficient vector Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (f_0,f_1,\ldots,f_{k-1})} to a special subset Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu \subseteq \mathbb{F}_q^k} , which satisfies below two conditions:

Condition 1. The set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu} must be large enough ($|\nu |\geq q^{(1-\varepsilon )k}$).

This is to make sure that the rate will be at most reduced by factor of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1-\varepsilon)} .

Condition 2. The set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nu} should have low intersection with any subspace Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} of dimension Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} satisfying Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S \subset \mathbb{F}_q^k} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |S \cap \nu| \leqslant L.} Such a subset is called subspace-evasive subset.

The bound for the list size at worst case is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\Omega(1/\varepsilon)}} , and it can be reduced to a relative small bound $O(1/\varepsilon ^{2})$ by using subspace-evasive subsets.

During this step, as it has to check each element of the solution subspace that we get from Step 2, it takes Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^s} time in the worst case (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} is the dimension of the solution subspace).

Dvir and Lovett improved the result based on the work of Guruswami, which can reduce the list size to a constant.

Here is only presented the idea that is used to prune the solution subspace. For the details of the prune process, please refer to papers by Guruswami, Dvir and Lovett, which are listed in the reference.

Summary

If we don't consider the Step 3, this algorithm can run in quadratic time. A summary for this algorithm is listed below.

Overview of Linear-algebraic list decoding algorithm for FRS code

Steps
Runtime	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{\Omega(1/\varepsilon^2)}}
Error Radius	1–R–ε
List Size	Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{O(1/\varepsilon^2)}}

See also

• Reed–Solomon error correction
• Singleton bound
• Coding theory
• List decoding

Source

http://wikipedia.org/