<figure><img src="image_1.png" /></figure>

HAL
open science

# Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach

Magali Bardet, Rocco Mora, Jean-Pierre Tillich

► To cite this version:

Magali Bardet, Rocco Mora, Jean-Pierre Tillich. Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach. ISIT 2021 - IEEE International Symposium on Information Theory, Jul 2021, Melbourne, Australia. pp.872-877, 10.1109/ISIT45174.2021.9517838. hal-03533311

HAL Id: hal-03533311

https://inria.hal.science/hal-03533311

Submitted on 18 Jan 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach

Magali Bardet

LITIS, University of Rouen Normandie
Inria, Team COSMIQ,
2 rue Simone Iff, CS 42112,
75589 Paris Cedex 12, France

Email: magali.bardet@univ-rouen.fr

Rocco Mora

Sorbonne Universités, UPMC Univ Paris 06
Inria, Team COSMIQ,
2 rue Simone Iff, CS 42112,
75589 Paris Cedex 12, France

Email: rocco.mora@inria.fr

Jean-Pierre Tillich

Inria, Team COSMIQ,

2 rue Simone Iff, CS 42112,
75589 Paris Cedex 12, France

Email: jean-pierre.tillich@inria.fr

**Abstract**—Decoding a Reed-Solomon code can be modeled by a bilinear system which can be solved by Gröbner basis techniques. We will show that in this particular case, these techniques are much more efficient than for generic bilinear systems with the same number of unknowns and equations (where these techniques have exponential complexity). Here we show that they are able to solve the problem in polynomial time up to the Sudan radius. Moreover, beyond this radius these techniques recover automatically polynomial identities that are at the heart of improvements of the power decoding approach for reaching the Johnson decoding radius. They also allow to derive new polynomial identities that can be used to derive new algebraic decoding algorithms for Reed-Solomon codes. We provide numerical evidence that this sometimes allows to correct efficiently slightly more errors than the Johnson radius.

Note A full version containing the proofs is accessible on arxiv at: https://arxiv.org/abs/2102.02544

## I. INTRODUCTION

**Decoding a large number of errors in Reed-Solomon codes.** A long-standing open problem in algebraic coding theory was that of decoding Reed-Solomon codes beyond the error-correction radius, $\frac{1-R}{2}$ (where R stands for the code rate). This problem was solved in a breakthrough paper by Sudan in [1] where it was shown that there exists an algebraic decoder that works up to a fraction of errors $1 - \sqrt{2R}$ (the so called Sudan radius here). This was even improved later on by Guruswami and Sudan in [2] with a decoder that works up to the Johnson radius $1 - \sqrt{R}$. This represents in a sense the limit for such decoders since these decoders are list decoders that output all codewords up to this radius and beyond this radius the list size is not guaranteed to be polynomial anymore. However, if we do not insist on having a decoder that outputs all codewords within a certain radius, or if we just want a decoder that is successful most of the time on the q-ary symmetric channel of crossover probability p, then we can still hope to have an efficient decoder beyond this bound. Moreover, it is even interesting to investigate if there are decoding algorithms of say subexponential complexity above the radius $1 - \sqrt{R}$.

**A Gröbner basis approach.** Our approach for decoding is to model decoding by an algebraic system and then to solve it with Gröbner bases techniques. At first sight, it might seem

that this approach is not new in this setting: such techniques have already been used here, mainly to solve algebraic systems involved in the Guruswami-Sudan approach [3]–[8]. They were used up to now on systems where such techniques are expected to run efficiently just because the number of variables was very small for instance: for instance [3]–[6] consider only two variables X and Y corresponding to the variables of the interpolation polynomial which is sought.

Our approach in this paper is different. We consider the classical bilinear system (2) modeling the decoding problem. This is at first sight a no go, because solving generic bilinear systems with the same number of variables and equations is here of exponential complexity. However it will turn that for the system at hand this approach is astonishingly efficient: we will for instance show that it runs in polynomial time when the fraction of errors is below the Sudan radius. Indeed, consider a k-dimensional Reed-Solomon code of length n over $\mathbb{F}_q$ with support $\mathbf{a} = (a_i)_{1 \le i \le n} \in \mathbb{F}_q^n$:

$$ \mathbf{RS}_k(\mathbf{a}) = \{(P(a_i))_{1 \le i \le n} : P \in \mathbb{F}_q[X], \deg P < k\}. $$

Let $\mathbf{b} = (b_i)_{1 \le i \le n}$ be the received word, $\mathcal{E}$ be the set of positions in error and define the error locator as usual

$$ \Lambda(X) \stackrel{\text{def}}{=} \Pi_{i \in \mathcal{E}} (X - a_i). \quad (1) $$

From this, we can write the bilinear system with unknowns the coefficients $p_i$ of the polynomial $P(X) = \sum_{i=0}^{k-1} p_i X^i$ corresponding to the codeword that was sent and the coefficients $\lambda_j$ of the error locator polynomial $\Lambda(X) = X^t + \sum_{j=0}^{t-1} \lambda_j X^j$ if we assume that there were t errors. We have n bilinear equations in the $k+t$ variables $p_i$'s and $\lambda_j$'s coming from the n relations $P(a_\ell)\Lambda(a_\ell) = b_\ell\Lambda(a_\ell)$, $\ell \in [1, n]$, namely

$$ \sum_{i=0}^{k-1} \sum_{j=0}^{t} a_{\ell}^{i+j} p_i \lambda_j = \sum_{j=0}^{t} b_{\ell} a_{\ell}^{j} \lambda_j, \quad \ell \in [1, n] \quad \text{and} \quad \lambda_t = 1. \quad (2) $$

**Gröbner basis techniques: a simple and automatic way for obtaining a polynomial time algorithm in our case.** Standard Gröbner bases techniques can be used to solve this system, however solving (2) is much easier than solving a generic bilinear system with the same parameters. In particular
these techniques solve typically in polynomial time the decoding problem when the fraction of errors is below the Sudan radius. This is explained in Section III-A. The reason why the Gröbner basis approach works in polynomial time is related to power-decoding [9], [10] and can be explained by similar arguments. However, the nice thing about this Gröbner basis approach is that the algorithm itself is very simple and can be given without any reference to power decoding (or the Sudan algorithm). The computation of the Gröbner basis reveals degree falls which are instrumental for its very low complexity. Understanding these degree falls can be explained by the polynomial equations used by power decoding. However, this simple algorithm also appears to be very powerful beyond the Sudan bound: experimentally it seems that it is efficient up to the Johnson radius and that it is even able to correct more errors in some cases than the refinement of the original power decoding algorithm [11] (which reaches asymptotically the Johnson radius). This is demonstrated in Section IV.

**Understanding the nice behavior of the Gröbner basis approach.** Moreover, trying to understand theoretically why this algorithm behaves so well, is not only explained by the polynomial relations which are at the heart of the power decoding approach, it also reveals new polynomial relations that are not exploited by the power decoding approach as shown in Section III. In other words, this approach not only gives an efficient algorithm, it also exploits other polynomial relations. It seems fruitful to understand and describe them, this namely paves the road towards new algebraic decoders of Reed-Solomon codes.

**Notation.** Throughout the paper we will use the following notation. The integer interval $\{a, a+1, \dots, b\}$ will be denoted by $\llbracket a, b\rrbracket$. For a polynomial $Q(X) = \sum_{i=0}^m q_i X^i$, $\text{coeff}(Q(X), X^s)$ stands for the coefficient $q_s$ of $X^s$ in $Q(X)$. For two polynomials $Q(X)$ and $G(X)$, $[Q(X)]_{G(X)}$ stands for the remainder of $Q(X)$ divided by $G(X)$.

## II. THE ALGORITHM

Consider an algebraic system of equations

$$ \left\{ \begin{array}{l} f_1(x_1, \dots, x_\ell) = 0 \\ \vdots \\ f_m(x_1, \dots, x_\ell) = 0 \end{array} \right. \qquad (3) $$

where the $f_i$'s are polynomials in $x_1, \dots, x_\ell$. Such systems can be solved by Gröbner basis techniques (see [12] for instance). To simplify the discussion assume that we have a unique solution to the algebraic system (3) and that the polynomial ideal $\mathcal{I}$ generated by the $f_i$'s is radical, meaning that whenever there is a polynomial $f$ and a positive integer $s$ such that $f^s$ is in $\mathcal{I}$, then $f$ is in $\mathcal{I}$. This seems to be the typical case for (2) when the number of errors is below the Gilbert-Varshamov bound. In such a case, the reduced Gröbner basis of the ideal $\mathcal{I}$ is given by the set $\{x_1 - r_1, \dots, x_n - r_\ell\}$ for any admissible monomial ordering, where $(r_1, \dots, r_\ell)$ stands for the unique solution of (3) (this is standard, see for instance [13, Lemma 2.4.3, p.40]). Recall here that a Gröbner

basis of a polynomial ideal is defined for a given admissible monomial ordering<fnref n="1" /> as a generating set $\{g_1, \dots, g_s\}$ of the ideal such that the ideal generated by the leading monomials $LM(g_i)$ (where $LM(g)$ is the largest monomial in $g$) of the $g_i$'s coincides with the ideal generated by all the leading monomials of the elements of $\mathcal{I}$:

$$ \langle \mathrm{LM}(g_1), \dots, \mathrm{LM}(g_s) \rangle = \langle \mathrm{LM}(f) : f \in \mathcal{I} \rangle. $$

We will adopt Lazard's point of view [14] to compute a Gröbner basis and use Gaussian elimination on the Macaulay matrices associated to the system. The main known and efficient algorithm for this is Faugère's F4 algorithm [15], see [12] for background on the subject.

We recall that the Macaulay matrix $M_D^{\text{acaulay}}(S)$ in degree $D$ of a set $S = \{f_1, \dots, f_m\}$ of polynomials is the matrix whose columns correspond to the monomials of degree $\le D$ sorted in descending order w.r.t. a chosen monomial ordering, whose rows correspond to the polynomials $tf_i$ for all $i$ where $t$ is a monomial of degree $\le D - \deg f_i$, and whose entry in row $tf_i$ and column $u$ is the coefficient of the monomial $u$ in the polynomial $tf_i$. A Gröbner basis for the system can be computed by computing a row echelon form of $M_D^{\text{acaulay}}$ for large enough $D$ [14] and [12, chap. 10]. However, this way of solving (2) is very inefficient (unless $t \le \frac{n-k}{2}$ where direct row echelonizing (2) is enough) because during the Gaussian elimination process we have a sequence of degree falls which are instrumental for computing a Gröbner basis by staying at a very small degree (this appears clearly if we use for instance Faugère's F4 algorithm [15] on (2)).

A degree fall is a polynomial combination $\sum_{i=1}^m g_i f_i$ of the $f_i$'s which satisfies

$$ 0 < s \stackrel{\text{def}}{=} \deg \sum_{i=1}^{m} g_i f_i < \max_{i=1}^{m} \deg g_i f_i. $$

We say that $\deg \sum_{i=1}^m g_i f_i$ is a degree fall of degree $s$.

The simplest example of such a degree fall occurs in (2) when $t < n-k$. Here there are linear combinations of the bilinear equations of (2) giving linear equations. This can be verified by performing the change of variables $z_s \stackrel{\text{def}}{=} \sum_{i,j:i+j=s} p_i \lambda_j$ in (2) and get the system

$$ \sum_{s=0}^{t+k-1} a_{\ell}^{s} z_{s} = \sum_{j=0}^{t} b_{\ell} a_{\ell}^{j} \lambda_{j}, \quad \ell \in \llbracket 1, n \rrbracket. \qquad (4) $$

In other words, by eliminating the $z_s$'s in these equations we obtain linear equations involving only the $\lambda_i$'s. When $t \le \frac{n-k}{2}$ there are enough such equations to recover from them the $\lambda_i$'s and by substituting for them in (2) the $p_i$'s by solving again a linear system. Of course, this is well known, and there are much more efficient algorithms for solving this system but still it is interesting to notice that the Gröbner basis approach already yields a polynomial time algorithm for the particular

<footnote n="1">¹This is a total ordering < of the monomials such that (i) $m < m' \Rightarrow mt < m't$ for any monomial $t$ (ii) every subset of monomials has a smallest element.</footnote>
bilinear system (2) despite being exponential (for a large range of parameters) for generic bilinear systems with the same number of unknowns and equations as (2) [16], [17].

A slightly less trivial degree fall behavior is obtained in the case the fraction of errors is Sudan's radius. Here, after substituting for the $\lambda_i$'s which can be expressed as linear functions of the other $\lambda_i$'s by using the aforementioned linear equations involving the $\lambda_i$'s we obtain new bilinear equations $f_1^t, \dots, f_m^t$. It turns out that we can perform linear combinations on these $f_i^t$'s to eliminate the monomials of degree 2 in them and derive new linear equations involving only the $\lambda_i$'s. This is proved in §III-A. This process can be iterated and there are typically enough such linear equations to recover the $\lambda_i$'s in this way as long as $t$ is below or equal to the Sudan decoding radius. As explained above, this allows to recover the right codeword by plugging the values for $\lambda_i$ in (2) and solving the corresponding linear system in the $p_i$'s.

Note that here, and in all the paper, we are considering graded monomial orderings (a monomial of degree $d$ is always smaller than a monomial of degree $d' > d$). Through this paper, we use the notion of affine $D$-Gröbner basis, which is the truncated Gröbner basis obtained by ignoring computations in degree greater than $D$. It is well known that there exists a $D$ such that a $D$-Gröbner basis is indeed a Gröbner basis. We describe here Algorithm 1 which computes a $D$-Gröner basis of a given system through linear algebra. It is less efficient than standard algorithms but has the merit of being simple and showing what is computed during such algorithms. It is also of polynomial time complexity when $D$ is fixed. It uses the function $\text{Pol}(M)$ that returns the polynomials represented by the rows of a Macaulay matrix $M$.

<table><caption>**Algorithm 1** $D$-Gröbner Basis</caption><thead><tr><th>Input</th><th></th></tr></thead><tbody><tr><td>$D$</td><td>Maximal degree,</td></tr><tr><td>$S$</td><td>= {$f_1, \dots, f_m$} set of polynomials.</td></tr><tr><td>repeat</td><td></td></tr><tr><td>$S \leftarrow \text{Pol}(\text{EchelonForm}(M_D^{\text{macaulay}}(S)))$</td><td></td></tr><tr><td>until $\dim_{\mathbb{F}_q} S$ has not increased.</td><td></td></tr><tr><td>Output $S$.</td><td></td></tr></tbody></table>

It is clear that Algorithm 1 terminates and has a polynomial complexity if $D$ is fixed. The previous remarks show that we can decode up to the Sudan decoding radius with $D = 2$. However, when the number of errors becomes bigger, $D = 2$ is not enough to exhibit more degree falls. We have to go a higher degree. However, already taking $D = 3$ yields interesting degree falls that are instrumental to the generalization of the power decoding approach of [11] decoding up to the Johnson radius.

### III. A PARTIAL EXPLANATION OF THE ALGEBRAIC BEHAVIOR

#### A. Correcting up to the Sudan bound in polynomial time

The efficiency of Algorithm 1 is already demonstrated by the fact that choosing $D = 2$ in it corrects in polynomial

time as many errors as Sudan's algorithm. Choosing $D = 2$ in Algorithm 1 means that we just keep the equations of degree 2 and try to produce new linear equations by linear combinations of the equations of degree 2 aiming at eliminating the degree 2 monomials. The efficiency of this algorithm is related to power decoding [9]: the algorithm finds automatically the linear equations exploited by the power decoding approach. It is here convenient in order to explain the effectiveness of the Gröbner basis approach to bring in an equivalent algebraic system which is basically the key equation implicit in Gao's decoder [18] (and the one used in the power decoding approach) which is the following polynomial equation:

$$P(X)\Lambda(X) \equiv R(X)\Lambda(X) \quad \mod G(X) \quad (5)$$

where $R(X)$ is the polynomial of degree $\le n-1$ interpolating the received values, i.e

$$R(a_{\ell}) = b_{\ell}, \quad \ell \in [1, n] \quad \text{and} \quad G(X) \stackrel{\text{def}}{=} \prod_{\ell=1}^{n} (X - a_{\ell}).$$

Note that these two polynomials are immediately computable by the receiver (and $G$ can be precomputed). By using the same unknowns as in (2), namely the coefficients of $P(X)$ and $\Lambda(X)$ we obtain a bilinear system with $n$ equations. It is readily seen that

**Proposition 1:** The bilinear systems (2) and (5) are equivalent: (5) can be obtained from linear combinations of (2) and vice versa.

The point of (5) is that

* These equations are more convenient to work with to understand what is going on algebraically during the Gröbner basis calculations of Algorithm 1.

* They give directly $n-k-t+1$ linear equations, since (i) the coefficient of $S(X)$ of degree $d \in [t+k, n-1]$ coincides with the coefficient of the same degree in $-R(X)\Lambda(X) \mod G(X)$ since $\Lambda(X)P(X)$ is of degree $\le t+k-1$; (ii) the coefficient of $S(X)$ of degree $t+k-1$ is equal to $p_{k-1} - \text{coeff}([\Lambda(X)R(X)]_{G(X)}, X^{t+k-1})$ because $\Lambda(X)$ is monic and of degree $t$.

With this at hand we can now prove that

**Proposition 2:** Let $q_1 \stackrel{\text{def}}{=} \max\{u : t + (k-1)u \le n-1\} = \left\lfloor \frac{n-t-1}{k-1} \right\rfloor$. All affine functions in the $\lambda_i$'s of the form $\text{coeff}([\Lambda(X)R^j(X)]_{G(X)}, X^u)$ for $j \in [1, q_1]$ and $u \in [t+(k-1)j+1, n-1]$ are in the linear span of the set $S$ output by Algorithm 1 when $D = 2$.

These linear equations that we produce coincide exactly with the linear equations produced by the power decoding approach [9] and this allows to correct as many errors as the power decoding approach based on the same assumption, namely that they are all independent, which is actually the typical scenario. However, contrarily to power decoding that is bound to make such an assumption to work, the Gröbner basis is more versatile, as it allows to decode even without this assumption as explained in Section IV.
## B. Decoding up to the Johnson radius

Power decoding [9] was generalized in [11] to decode up to the Johnson radius by bringing in the “error evaluator” polynomial $\Omega(X)$ of degree $\le t-1$ defined by

$$ \Omega(a_i) = -e_i, \text{ for all } i \in [1, n] \text{ for which } e_i \neq 0. \quad (6) $$

where $e_i$ is the error value at position $i$. In other words, it is the interpolation polynomial defined by (6) for all $i$ in error. This crucially relies on [11, Lemma 2.1]:

$$ \Lambda(P-R) = \Omega G. \quad (7) $$

The generalization of power decoding then uses this identity to derive further identities that are summarized by the following formulas (this is Theorem 3.1 in [11]), for any positive integer $s$ and $v$ such that $s \le v$ we have

$$ \Lambda^s P^u = \sum_{i=0}^{u} \binom{\Lambda^{s-i} \Omega^i}{i} \binom{u}{i} R^{u-i} G^i \quad u \in [1, s-1], \quad (8) $$

$$ \Lambda^s P^u \equiv \sum_{i=0}^{s-1} \binom{\Lambda^{s-i} \Omega^i}{i} \binom{u}{i} R^{u-i} G^i \quad \mod G^s \quad u \in [s, v]. \quad (9) $$

[11] relies on the fact that when the number of errors is below the Johnson radius, there is a choice of $s$ and $v$ such that the total number of coefficients of the polynomials $\Lambda^s, \Lambda^{s-1}\Omega, \dots, \Omega^s$ as well as $\Lambda^s P, \dots, \Lambda^s P^v$ is less than or equal to the number of equations linking these coefficients coming from (8) and (9). In this case (and if these equations are independent) we recover them by solving the corresponding linear system. Notice that with this strategy, there is for a given value $s$ a maximal value for $u$ given by

$$ q_s \stackrel{\text{def}}{=} \max\{u : st + u(k-1) \le sn-1\}. $$

It is readily seen that taking larger of $u$ only increases the number of variables in the linear system without being able to make it determinate if it was not determinate before. Interestingly enough our Gröbner basis approach also exhibits degree falls of degree $s$ that are related to (8) and (9). This can be understood by using an equivalent definition of $\Omega$ as

$$ \Omega \stackrel{\text{def}}{=} -\Lambda R \div G. \quad (10) $$

Notice that from this definition we directly derive two results

1) The coefficients of $\Omega$ are affine functions of the $\lambda_i$'s.

2) As long as $t \le n-k$, (7) follows from (10) and (5). Indeed $[\Lambda R]_G = \Lambda P$. This follows from (5) and $t+k-1 \le n-1$ implying that $\Lambda P = \Lambda R \mod G$. This and (10) then imply that $\Lambda R = -\Omega G + \Lambda P$ which is obviously equivalent to (7).

Note that from these considerations, that if we equate the coefficients of the polynomials in (8) for all the degrees in $[st+u(k-1)+1, st+u(n-1)]$ and in (9) for all the degrees in $[st+u(k-1)+1, s(n-1)]$, the coefficient of the left-hand term vanishes and the coefficient in the righthand term is a polynomial of degree $s$ in the $\lambda_i$'s (this follows from the fact that the coefficients of $\Omega$ are affine functions in those $\lambda_i$'s). This gives polynomial equations in the $\lambda_i$'s of degree $s$. In a sense, they can be viewed as generalizations at degree $s$ of

the linear equations that were mentioned when Algorithm 1 is applied when $D=2$. These equations are actually produced as degree falls that are in the linear span of intermediate sets $S$ produced in Algorithm 1 when $D=s+1$. There are also other equations of degree $s$ produced by Algorithm 1 in such a case. To explain this point it makes sense to bring in notation for the right-hand term in (8) and (9). Let us define

$$ \chi(s, u) \stackrel{\text{def}}{=} \sum_{i=0}^{u} \binom{u}{i} \Lambda^{s-i} R^{u-i} \Omega^i G^i = \Lambda^{s-u} (\Lambda R + \Omega G)^u \quad \text{if } u < s, $$

$$ \chi(s, u) \stackrel{\text{def}}{=} \left[ \sum_{i=0}^{s-1} \binom{u}{i} \Lambda^{s-i} R^{u-i} \Omega^i G^i \right]_{G^s} \quad \text{if } u \ge s $$

We also let $\chi(s, u)_H$ be the polynomial where we dropped all the terms of degree $\le ts+u(k-1)$ in $\chi(s, u)$, i.e. $\chi(s, u) = \sum_i a_i X^i$, then $\chi(s, u)_H = \sum_{i>ts+u(k-1)} a_i X^i$.

**Theorem 1:** Let $\mathcal{I}_D = \langle S \rangle_{\mathbb{F}_q}$ where $S$ is the set output by Algorithm 1. We have for all nonnegative integers $s, s', u \le q_s, u' \le q_{s'}$

$$ \chi(s, u)_H \in_{\text{coef}} \mathcal{I}_{s+1} \quad (11) $$

$$ \chi(s, u)\chi(s', u') - \chi(s + s', u + u') \in_{\text{coef}} \mathcal{I}_{s+s'+1}. \quad (12) $$

where $P \in_{\text{coef}} \mathcal{I}_v$ (where $P$ is a polynomial with coefficients that are polynomials in the $\lambda_i$'s and the $p_i$'s) means that all the coefficients of $P$ belong to $\mathcal{I}_v$.

From (8) and (9) it is of course clear that $\chi(s, u)\chi(s', u') - \chi(s + s', u + u')$ belongs to the ideal generated by the polynomial equations since they basically come from the identity $\Lambda^s P^u \Lambda^{s'} P^{u'} = \Lambda^{s+s'} P^{u+u'}$. What is somehow surprising is that these equations are actually discovered at a rather small degree Gröbner basis computation (namely by staying at degree $s+s'+1$). Moreover these equations only involve the $\lambda_i$'s. By inspection of the behavior of the Gröbner basis computation, it seems that the linear equations that we produce later on are first produced by degree falls only involving these equations of degree $s$. It is therefore tempting to change the Gröbner basis decoding procedure strategy: instead of feeding Algorithm 1 with the initial system (2) or (5) we run it with the equations of degree $s$ given by Theorem 1. Once we have recovered the $\lambda_i$'s in this way we recover the $p_i$'s by solving a linear system as explained earlier. How this strategy behaves on non-trivial examples is now explained in the next section.

## IV. EXPERIMENTAL RESULTS

In this section, we compare the behavior of a $D$-Gröbner basis computation on the bilinear system (5), with a system involving equations in the $\lambda_j$'s only. We give examples where Johnson's bound is attained and passed.

The systems in $\lambda_j$'s we use contains equations $\chi(s, u)_H$ and some relations $\chi(s, u)\chi(s', u') - \chi(s + s', u + u')$. Experimentally, they are linearly dependent from $\chi(s + s' - 1, u + u')\chi(1, 0) - \chi(s + s', u + u')$ and $\chi(s, q_s)_H$. Moreover, $\chi(s-1, u)\chi(1, 0) \mod G^{s-1} = \chi(s, u) \mod G^{s-1}$, so we will consider equations $M_{s,u}$ defined by

$$ (\chi(s-1, u)\chi(1, 0) - \chi(s, u)) \div G^{s-1}. \quad (M_{s,u}) $$
We do not add equations that are polynomially dependent from $\chi(s, q_s)_H$ or $M_{s+1, q_s}$ at degree at most $D$, and thus unnecessary for the computation.

Tables I, II and III show results for $[n, k]_q$ taking values $[64, 27]_{64}$, $[256, 63]_{256}$ and $[37, 5]_{61}$. The column $\#\lambda_j$ indicates the number of remaining $\lambda_j$'s after elimination of the linear ones from the $\chi(1, \ast)_H$ relations. The column "Eq" indicates the equations used. The column "\#Eq" contains the degrees of the equations$^2$.

We do our experiments using the GroebnerBasis (S, D) function in the computer algebra system magma v2.25-6. The practical complexity $\mathbb{C}$ is given by the magma function ClockCycles. For instance, on our machine with an Intel® Xeon® 2.00GHz processor, $2^{30.9}$ clock cycles are done in 1 second, $2^{36.8}$ in 1 minute and $2^{42.7}$ in 1 hour. "Max Matrix" indicates the size of the largest matrix during the process. The complexities include the computation of the equations $\chi(i, j)_H$ and $M_{i,j}$ that could be improved.

For systems where the number of remaining $\lambda_j$'s is small compared to the number of $p_i$'s, e.g. Table I or Table II, it is clearly interesting to compute a Gröbner basis for a system containing only polynomials in $\lambda_j$'s: even if the maximal degree $D$ is larger than for the bilinear system, the number of variables is much smaller and the computation is faster. For instance for $[n, k]_q = [64, 27]_{64}$ in Table I, on Johnson bound $t = 23$ the Gröbner basis for the bilinear system requires more than 6 hours of computation and 47 GB of memory, whereas the computation in $\lambda_j$'s only takes less than a second. For $t = 24$ we couldn't solve the bilinear system directly, whereas the system in $\lambda_j$'s only solves in less than a minute.

<caption>TABLE I</caption>

EXPERIMENTAL RESULTS FOR A $[n, k]_q = [64, 27]_{64}$ RS-CODE. SYSTEM (5) CONTAINS 26 VARIABLES $p_i$. JOHNSON'S BOUND IS $t = 23$.

<table><thead><tr><th>t</th><th>#λ<sub>j</sub></th><th>Eq.</th><th>#Eq.</th><th>D</th><th>Max Matrix</th><th>C</th></tr></thead><tbody><tr><td rowspan="2">19</td><td rowspan="2">1</td><td>(5)</td><td>2:45</td><td>2</td><td>65 × 57</td><td>2<sup>22.2</sup></td></tr><tr><td>χ(2, 3)<sub>H</sub></td><td>2:11</td><td>2</td><td>45 × 28</td><td>2<sup>23.7</sup></td></tr><tr><td rowspan="2">20</td><td rowspan="2">3</td><td>(5)</td><td>2:46</td><td>3</td><td>1522 × 1800</td><td>2<sup>26.5</sup></td></tr><tr><td>χ(2, 3)<sub>H</sub></td><td>2:9</td><td>2</td><td>47 × 28</td><td>2<sup>24.4</sup></td></tr><tr><td rowspan="2">21</td><td rowspan="2">5</td><td>(5)</td><td>2:47</td><td>3</td><td>1711 × 2889</td><td>2<sup>27.1</sup></td></tr><tr><td>χ(2, 3)<sub>H</sub> + χ(3, 4)<sub>H</sub></td><td>2:7, 3:24</td><td>3</td><td>66 × 56</td><td>2<sup>26.8</sup></td></tr><tr><td rowspan="2">22</td><td rowspan="2">7</td><td>(5)</td><td>2:48</td><td>4</td><td>31348 × 35972</td><td>2<sup>36.1</sup></td></tr><tr><td>χ(2, 3)<sub>H</sub> + χ(3, 4)<sub>H</sub></td><td>2:5, 3:21</td><td>4</td><td>271 × 283</td><td>2<sup>27.6</sup></td></tr><tr><td rowspan="2">23</td><td rowspan="2">9</td><td>(5)</td><td>2:49</td><td>5</td><td>428533 × 406773</td><td>2<sup>45.4</sup></td></tr><tr><td>χ(2, 3)<sub>H</sub> + M<sub>3,3</sub></td><td>2:4, 3:22</td><td>5</td><td>1466 × 1641</td><td>2<sup>30.1</sup></td></tr><tr><td rowspan="2">24</td><td rowspan="2">11</td><td>(5)</td><td>2:50</td><td>≥ 6</td><td>-</td><td>-</td></tr><tr><td>M<sub>3,3</sub></td><td>2:1, 3:23</td><td>7</td><td>28199 × 23536</td><td>2<sup>35.8</sup></td></tr></tbody></table>

Table II gives an example where the number of $\lambda_j$'s variables is quite large, but still smaller than the number of $p_i$'s. The benefit of using equations in $\lambda_j$'s only is clear. On the contrary, Table III shows that for a small value of $k$ compared to the number of $\lambda_j$'s, the maximal degree for the bilinear system is smaller than the one for a system involving only $\lambda_j$'s, but the total number of variables is almost the same, hence it is more interesting to solve directly the bilinear system. Moreover, here computing the $M_{i,j}$ equations

<caption>TABLE II</caption>

EXPERIMENTAL RESULTS FOR A $[n, k]_q = [256, 63]_{256}$ RS-CODE. SYSTEM (5) CONTAINS 62 VARIABLES $p_i$. JOHNSON'S BOUND IS $t = 130$.

<table><thead><tr><th>t</th><th>#λ<sub>j</sub></th><th>Eq.</th><th>#Eq.</th><th>D</th><th>Max Matrix</th><th>C</th></tr></thead><tbody><tr><td rowspan="2">120</td><td rowspan="2">36</td><td>(5)</td><td>2:182</td><td>3</td><td>20023 × 128018</td><td>2<sup>38.0</sup></td></tr><tr><td>χ(2, 3)<sub>H</sub></td><td>2:85</td><td>2</td><td>119 × 703</td><td>2<sup>34.5</sup></td></tr><tr><td rowspan="2">121</td><td rowspan="2">39</td><td>(5)</td><td>2:183</td><td>3</td><td>21009 × 143741</td><td>2<sup>38.9</sup></td></tr><tr><td>M<sub>2,2</sub></td><td>2:111</td><td>3</td><td>9780 × 8517</td><td>2<sup>35.0</sup></td></tr><tr><td rowspan="2">122</td><td rowspan="2">42</td><td>(5)</td><td>2:184</td><td>3</td><td>22050 × 160434</td><td>2<sup>39.7</sup></td></tr><tr><td>M<sub>2,2</sub></td><td>2:113</td><td>3</td><td>4858 × 14189</td><td>2<sup>35.3</sup></td></tr><tr><td rowspan="2">123</td><td rowspan="2">45</td><td>(5)</td><td>2:185</td><td>3</td><td>23112 × 178090</td><td>2<sup>40.1</sup></td></tr><tr><td>M<sub>2,2</sub></td><td>2:115</td><td>3</td><td>5289 × 17295</td><td>2<sup>35.8</sup></td></tr><tr><td rowspan="2">124</td><td rowspan="2">48</td><td>(5)</td><td>2:186</td><td>≥ 4</td><td>-</td><td>-</td></tr><tr><td>M<sub>2,2</sub> + M<sub>4,6</sub></td><td>2:117, 3:1, 4:189</td><td>4</td><td>164600 × 270725</td><td>2<sup>45.2</sup></td></tr></tbody></table>

(that are equations in $\lambda_j$'s of degree $i$) takes time. Note that, for $t \ge 26$ we may have several solutions: the Gröbner basis computation performs a list decoding and returns all the solutions.

<caption>TABLE III</caption>

EXPERIMENTAL RESULTS FOR A $[n, k]_q = [37, 5]_{61}$ RS-CODE. SYSTEM (5) CONTAINS 4 VARIABLES $p_i$. JOHNSON'S BOUND IS $t = 24$, GILBERT-VARSHAMOV'S BOUND IS $t = 28$.

<table><thead><tr><th>t</th><th>#λ<sub>j</sub></th><th>Eq.</th><th>#Eq.</th><th>D</th><th>Max Matrix</th><th>C</th></tr></thead><tbody><tr><td rowspan="2">24</td><td rowspan="2">12</td><td>(5)</td><td>2:28</td><td>3</td><td>1065 × 1034</td><td>2<sup>26.0</sup></td></tr><tr><td>M<sub>2,3</sub></td><td>2:37</td><td>3</td><td>454 × 454</td><td>2<sup>28.0</sup></td></tr><tr><td rowspan="2">25</td><td rowspan="2">15</td><td>(5)</td><td>2:29</td><td>3</td><td>2520 × 1573</td><td>2<sup>28.0</sup></td></tr><tr><td>χ(2, 5)<sub>H</sub> + χ(3, 8)<sub>H</sub> + M<sub>2,2</sub> + M<sub>3,5</sub></td><td>2:25, 3:40</td><td>4</td><td>3193 × 3311</td><td>2<sup>34.3</sup></td></tr><tr><td rowspan="2">26</td><td rowspan="2">18</td><td>(5)</td><td>2:30</td><td>4</td><td>20446 × 15171</td><td>2<sup>33.1</sup></td></tr><tr><td>χ(2, 5)<sub>H</sub> + M<sub>2,2</sub> + M<sub>3,5</sub> + M<sub>4,8</sub></td><td>2:25, 3:37, 4:37</td><td>5</td><td>38796 × 22263</td><td>2<sup>38.1</sup></td></tr><tr><td rowspan="2">27</td><td rowspan="2">21</td><td>(5)</td><td>2:31</td><td>4</td><td>27366 × 24894</td><td>2<sup>36.0</sup></td></tr></tbody></table>

V. CONCLUDING REMARKS

This paper demonstrates that using a standard Gröbner basis computation on the bilinear system (5) for decoding a Reed-Solomon code is of polynomial complexity below Sudan's radius. The Gröbner basis computation reveals polynomial equations of small degree involving the coefficients $\lambda_i$ of the error locator polynomial. They are related to the power decoding approach [11]. We give a theorem explaining why these polynomial relations are obtained at a surprisingly small degree. This is a first step for understanding why the Gröbner works surprisingly well beyond the Sudan radius and is successful by staying at a small degree. We have also explored another way of using this approach, namely by feeding some of the aforementioned polynomial relations directly in a Gröbner basis computation. This results in some cases in a considerable complexity gain. We have considered some of the examples given in [11] and show that this Gröbner basis approach can still be effective slightly beyond Johnson's bound. We also remark that contrarily to the power decoding approach which is restricted to the case where there is a unique solution to the decoding problem, the Gröbner basis computation is also able to compute all solutions. This approach opens new roads for decoding algebraically a Reed-Solomon code.

<footnote>$^2$2:45 means that the system contains 45 equations of degree 2.</footnote>
REFERENCES

[1] M. Sudan, “Decoding of Reed–Solomon codes beyond the error-correction bound,” *J. Complexity*, vol. 13, no. 1, pp. 180–193, 1997. [Online]. Available: http://dx.doi.org/10.1006/jcom.1997.0439

[2] V. Guruswami and M. Sudan, “Improved decoding of Reed–Solomon and algebraic-geometric codes,” in *Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280)*. IEEE, 1998, pp. 28–37.

[3] K. Lee and M. E. O'Sullivan, “An interpolation algorithm using gröbner bases for soft-decision decoding of reed-solomon codes,” in *2006 IEEE International Symposium on Information Theory*, 2006, pp. 2032–2036.

[4] K. Lee and M. E. O'Sullivan, “List decoding of reed–solomon codes from a gröbner basis perspective,” *Journal of Symbolic Computation*, vol. 43, no. 9, pp. 645–658, 2008. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0747717108000059

[5] M. Ali and M. Kuijper, “A parametric approach to list decoding of reed-solomon codes using interpolation,” *IEEE Transactions on Information Theory*, vol. 57, no. 10, pp. 6718–6728, 2011.

[6] P. V. Trifonov, “Efficient interpolation in the guruswami–sudan algorithm,” *IEEE Transactions on Information Theory*, vol. 56, no. 9, pp. 4341–4349, 2010.

[7] A. Zeh and C. Senger, “A link between guruswami-sudan’s list-decoding and decoding of interleaved reed-solomon codes,” in *2010 IEEE International Symposium on Information Theory*, 2010, pp. 1198–1202.

[8] A. W.-Z. Hannes Bartz, “Efficient decoding of interleaved subspace and gabidulin codes beyond their unique decoding radius using gröbner bases,” *Advances in Mathematics of Communications*, vol. 12, no. 4, pp. 773–804, 2018.

[9] G. Schmidt, V. Sidorenko, and M. Bossert, “Syndrome decoding of Reed-Solomon codes beyond half the minimum distance based on shift-register synthesis,” *IEEE Trans. Inf. Theory*, vol. 56, no. 10, pp. 5245–5252, 2010. [Online]. Available: https://doi.org/10.1109/TIT.2010.2060130

[10] J. S. R. Nielsen, “Power decoding of reed-solomon codes revisited,” in *Coding Theory and Applications, 4th International Castle Meeting, ICMCTA 2014, Palmela Castle, Portugal, September 15-18, 2014*, ser. CIM Series in Mathematical Sciences, R. Pinto, P. R. Malonek, and P. Vettori, Eds., vol. 3. Springer, 2014, pp. 297–305. [Online]. Available: https://doi.org/10.1007/978-3-319-17296-5_32

[11] ——, “Power decoding Reed-Solomon codes up to the Johnson radius,” *Advances in Mathematics of Communications*, vol. 12, no. 1, p. 81, 2018.

[12] D. Cox, J. Little, and D. O’Shea, *Ideals, Varieties, and algorithms: an Introduction to Computational Algebraic Geometry and Commutative Algebra*. Undergraduate Texts in Mathematics, Springer-Verlag, New York, 2015.

[13] M. Bardet, “Étude des systèmes algébriques surdéterminés. applications aux codes correcteurs et à la cryptographie,” Ph.D. dissertation, Université Paris VI, Dec. 2004, http://tel.archives-ouvertes.fr/tel-00449609/en/.

[14] D. Lazard, “Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations,” in *Computer algebra*, ser. LNCS, vol. 162. Berlin: Springer, 1983, pp. 146–156, proceedings Eurocal’83, London, 1983.

[15] J.-C. Faugère, “A new efficient algorithm for computing Gröbner bases (F4),” *J. Pure Appl. Algebra*, vol. 139, no. 1-3, pp. 61–88, 1999.

[16] J.-C. Faugère, M. Safey El Din, and P.-J. Spacodecrenlehauer, “Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): Algorithms and complexity,” *J. Symbolic Comput.*, vol. 46, no. 4, pp. 406–437, 2011.

[17] P. Spaenlenhauer, “Résolution de systèmes multi-homogènes et determinantiels,” Ph.D. dissertation, Univ. Pierre et Marie Curie- Paris 6, Oct. 2012.

[18] S. Gao, “A new algorithm for decoding Reed-Solomon codes,” in *Communications, Information and Network Security*, V. K. Bhargava, H. V. Poor, V. Tarokh, and S. Yoon, Eds. Boston, MA: Springer US, 2003, pp. 55–68. [Online]. Available: https://doi.org/10.1007/978-1-4757-3789-9_5