Improved Power Decoding of
Algebraic Geometry Codes

In this section we briefly introduce AG codes as evaluation codes and formulate the decoding problem that we wish to solve. We assume that the reader is familiar with the language of function fields, which is presented in great detail in [24].

Let $F$ be a function field having genus $g$ over a base field $\mathbb{F}$. Let $P_{1},\dots,P_{n},P_{\infty}$ be rational places of $F$, and fix two divisors $D=P_{1}+\cdots+P_{n}$ and $G$ with $\deg G=\gamma$, such that $\operatorname{supp}G\cap\operatorname{supp}D=\emptyset$. The code that we will be considering is

where $\mathcal{L}(G)=\{f\in F\;|\;(f)\geq-G\}\cup\{0\}$ is the Riemann-Roch space of $G$. The dimension of this code is $k=\mathfrak{l}(G)$, where $\mathfrak{l}(A)$ denotes the dimension of $\mathcal{L}(A)$ for any divisor $A$; and the code’s minimum distance is bounded from below by the designed minimum distance $d^{*}=n-\gamma$.

The problem that we wish to address is as follows:

In the next section, in the traditional spirit of power decoding, we show how II.1 can be reformulated as a highly non-linear system of equations.

In this section we formulate the so called key equations that lie at the heart of power decoding using the language of function fields.

We begin by defining the error locator and the received word interpolator, following up with some results about their sizes.

and $R(P_{i})=r_{i}$ for $i=1,\dots,n$.

It will be convenient to define the following divisors:

for $j=0,\dots,s-1$ and $t=1,\dots,\ell$.

The next lemma relates these divisors to $f$, $\Lambda_{s}$ and $R$.

We are now ready to present the key equations, which express an algebraic relationship between the sent message $f$, an ${\boldsymbol{r}}$-interpolator $R$ and a corresponding error locator $\Lambda_{s}$.

Since (1) is satisfied by the sent message, it makes sense to look for a solution of (1) in order to address II.1. We explain how this can be done in the next section.

In this section we show how to solve the following problem, which is motivated by Theorem III.6 and II.1:

According to Theorem III.6, if $f$ is the sent message and there exists an error locator $\Lambda_{s}$ with degree at most $\lambda_{s}$, then among the possible solutions of IV.1 we would find

Since $\deg\Lambda_{s}$ is roughly proportional to the number of errors (see Lemma III.4), this means that a solution of IV.1 of the type (2) for the smallest-possible $\lambda_{s}$ corresponds to a codeword that is among the closest codewords to our received word.²²2Note that it might happen that for two errors of similar weight, the error locator degree of the one of smaller weight is larger or equal to the one of larger weight. For large enough parameter $s$, this case becomes less likely for random errors. It might be that IV.1 for small $\lambda_{s}$ has solutions that do not correspond to an error locator/message pair. This might happen since IV.1 poses weaker constraints on its solutions compared to (1). Previous works on (improved) power decoding indicate that such “spurious” solutions only occur with very small probability. Also our simulation results in Section VI indicate this. We will get back to types of failure in the next section.

These arguments motivate our decoding strategy: Find a solution of IV.1 for the smallest $\lambda_{s}$ for which the problem has a solution. If we are successful, we get a solution of IV.1 of the form in (2) (or a scalar multiple thereof), where $\Lambda_{s}$ and $f$ correspond to a close codeword to ${\boldsymbol{r}}$. We can extract $f$, and thus ${\boldsymbol{c}}$ from this solution by division $\tfrac{\phi_{1}}{\psi_{0}}=\tfrac{\Lambda_{s}f^{1}}{\Lambda_{s}}=f$.

Since computational complexity is not a primary concern here, we describe in this section how to solve the problem for a fixed $\lambda_{s}$. The “smallest solution” can then be found by iterating $\lambda_{s}$ from $0$ to the maximal possible value for which we expect to be able to decode.

The entire decoding strategy is outlined in Algorithm 1.

In the remainder of this section we give an explicit construction of a matrix $\boldsymbol{U}$ over $\mathbb{F}$ whose right kernel contains vectors from which solutions to IV.1 can be obtained, i.e., how to implement Lines 1 and 1 of Algorithm 1.

For any divisor $A$ let $\boldsymbol{\beta}_{A}\in\mathcal{L}(A)^{\mathfrak{l}(A)}$ denote a vector whose entries form any $\mathbb{F}$-basis of $\mathcal{L}(A)$ such that for any two divisors $A$ and $B$ it holds that

For any $h\in\mathcal{L}(A)$ let $h_{A}\in\mathbb{F}^{\mathfrak{l}(A)}$ be the unique vector such that $\boldsymbol{\beta}_{A}\cdot h_{A}=h$, and for any $p\in\mathcal{L}(B-A)$ let $p_{B,A}\in\mathbb{F}^{\mathfrak{l}(B)\times\mathfrak{l}(A)}$ be the matrix whose $i$-th column is $(pa_{i})_{B}$, where $(a_{1},\dots,a_{\mathfrak{l}(A)})=\boldsymbol{\beta}_{A}$. It is easy to see that

In order to construct $\boldsymbol{U}$ we will need a satisfactory received word interpolator $R$ which can be for example be obtained as follows: If $\boldsymbol{M}\in\mathbb{F}^{n\times\mathfrak{l}(H)}$, where $H=\rho P_{\infty}+G$, is the matrix whose $i$-th column is

where $(b_{1},\dots,b_{\mathfrak{l}(H)})=\boldsymbol{\beta}_{H}$, then $R=\boldsymbol{\beta}_{H}\cdot\boldsymbol{z}$, where $\boldsymbol{z}$ is any solution to the linear system $\boldsymbol{M}\boldsymbol{z}=\boldsymbol{r}$.

The next lemma together with the the subsequent Corollary IV.3 give an explicit construction of $\boldsymbol{U}$ and show its relation to IV.1.

In the next section we describe the conditions under which decoding is expected to fail.

We turn to investigating the decoding performance of the proposed decoder. Since the decoder returns at most one codeword while attempting to decode beyond half the minimum distance, it must obviously fail for certain received words. Theoretically bounding this probability seems a difficult problem even for the simplest case of Reed–Solomon codes, and only partial results are known [1, 5]. We follow the approach of several previous papers on power decoding: we derive theoretically a number of errors at which our decoder is always guaranteed to fail, and we define this to be the “decoding radius”; this name will be supported by simulations in Section VI which indicates that the decoding algorithm succeeds with high probability whenever fewer, random errors occur.

It can be seen from Algorithm 1 that our decoder declares a decoding failure if and only if there is no value of $\lambda_{s}$ for which the matrix $\boldsymbol{U}$ in Corollary IV.3 has a right kernel of $\mathbb{F}_{q}$-dimension exactly 1.

On the other hand, when we do not declare decoding failure, the returned message candidate $\hat{f}\in\mathcal{L}(G)$ must correspond to the closest codeword to the received word, as in the discussion in the preceding section.

This notion of decoding failure motivates a natural bound for when we – simply by linear algebraic arguments – would know a priori that the decoder will fail in the generic case when the smallest error locator corresponding to a codeword has degree $\lambda_{s}=s|\mathcal{E}|+g$ (and not smaller), where $|\mathcal{E}|$ is the distance of the codeword to the received word:

Since the proposed decoder will typically return no solutions (and therefore fail) when $|\mathcal{E}|>\tau$, the decoding radius tells us how many errors we should at most expect to correct.³³3It might succeed in rare cases in which the error locator has surprisingly low degree. Our simulation results suggest that this happens with very small probability. We reiterate that, at this point we have given no indications that the decoder should usually succeed up to $\tau_{\mathsf{max}}$ errors, but we address this by simulations in Section VI.

For a given code $\mathcal{C}$, one may compute $\tau_{\mathsf{max}}$ exactly, but since the equations involve dimensions of sequences of Riemann–Roch spaces, it seems impossible to give a general precise closed form. However, we may lower-bound these numbers using common function field tools:

The next lemma gives bounds on the dimensions of $\boldsymbol{U}$.

With the aid of Lemma V.3 we can deduce a lower bound on values of $\lambda_{s}$ for which decoding must fail.

In this section we present Monte-Carlo simulation results of the proposed decoder for a few different AG codes in order to experimentally verify our hypothesis that Algorithm 1 corrects up to $\tau_{\mathsf{max}}(\ell,s)$ errors with high probability and fails with high probability above.

To be precise, for a given code and radius $\tau$, we test the following:

• •

  Draw a random message $f$ and encode it into ${\boldsymbol{c}}$

• •

  Draw an error ${\boldsymbol{e}}$ uniformly at random from the set of vectors in $\mathbb{F}^{n}$ of Hamming weight $\tau$

• •

  Decode ${\boldsymbol{r}}={\boldsymbol{c}}+{\boldsymbol{e}}$ using Algorithm 1

• •

  If the algorithm does not return a decoding failure and the returned message polynomial is exactly $f$, then count it as success.

Note that the simulation might be unsuccessful also in cases in which Algorithm 1 returns a valid close codeword, but not the transmitted one. This is called a miscorrection, and typically occurs only rarely (see, e.g., [25] for RS codes).

The above described simulation was tested on a few one- and two-point codes over two well known function fields:

• •

  The Hermitian function field is defined by the equation

  $$H_{q}:y^{q}+y=x^{q+1}$$

  over $\mathbb{F}_{q^{2}}$, i.e. the finite field of cardinality $q^{2}$. It has genus $\frac{1}{2}q(q-1)$ and $q^{3}+1$ rational places.

• •

  The Suzuki function field is defined by the equation

  $$S_{q}:y^{q}+y=x^{q_{0}}(x^{q}+x)$$

  over $\mathbb{F}_{q^{4}}$, where $q=2q_{0}^{2}>2$. It has genus $q_{0}(q-1)$ and $q^{2}+1$ rational places.

• •

  The function from [26, Lemma 3.2] field is defined by

  $$T_{q}:y^{q}+y=\frac{x^{q}}{x^{q-1}+1}$$

  over $\mathbb{F}_{q^{2}}$. It has genus $(q-1)^{2}$ and $q^{3}-q^{2}+2q$ rational places.

Table I contains simulation results for various function field family, code, and decoder parameters. All results confirm our hypothesis.