Power Decoding of Reed–Solomon Codes Revisited

Abstract

Power decoding, or “decoding by virtual interleaving”, of Reed–Solomon codes is a method for unique decoding beyond half the minimum distance. We give a new variant of the Power decoding scheme, building upon the key equation of Gao. We show various interesting properties such as behavioural equivalence to the classical scheme using syndromes, as well as a new bound on the failure probability when the powering degree is 3.

1 Introduction

Power decoding was originally developed by Schmidt, Sidorenko and Bossert for low-rate Reed–Solomon codes (RS) [5], and is usually capable of decoding almost as many errors as the Sudan decoder [8] though it is a unique decoder. If an answer is found, this is always the closest codeword, but in some cases the method will fail; in particular, this happens if two codewords are equally close to the received. With random errors this seems to happen exceedingly rarely, though a bound for the probability has only been shown for the simplest case of powering degree 2 [5, 10].

The algorithm rests on the surprising fact that a received word coming from a low-rate RS code can be “powered” to give received words of higher-rate RS codes having the same error positions. For each of these received words, one constructs a classical key equation by calculating the corresponding syndromes and solves them simultaneously for the same error locator polynomial.

Gao gave a variant of unique decoding up to half the minimum distance [1]: in essence, his algorithm uses a different key equation and with this finds the information polynomial directly. We here show how to easily derive a variant of Power decoding for Generalised RS (GRS) codes, Power Gao, where we obtain multiple of Gao’s type of key equation, and we solve these simultaneously.

We then show that Power Gao is equivalent to Power syndromes in the sense that they will either both fail or both succeed for a given received word. Power Gao has some “practical” advantages, though: it extends Power decoding to the case of using 0 as an evaluation point (which Power syndromes does not support); and the information is obtained directly when solving the key equations, so finding roots of the error locator and Forney’s formula is not necessary.

The main theoretical advantage is that Power Gao seems easier to analyse: in particular, we show two new properties of Power decoding: (1) that whether Power decoding fails or not depends only on the error and not on the sent codeword; and (2) a new bound on the failure probability when the powering degree is 3.

We briefly sketched Power Gao already in [2], but its behaviour was not well analysed and its relation to Power syndromes not examined. In Sect. 2 we derive the powered Gao key equations, and in Sect. 3 we describe the complete algorithm and discuss computational complexity issues. In Sect. 4 we show the behavioural equivalence to Power syndromes as well as the new properties on Power decoding. Section 5 describes an explicit family of errors for which Power decoding will fail.

2 The Key Equations

Consider some finite field $\mathbb{F}$. The [n, k, d] Generalised Reed-Solomon (GRS) code is the set

$$\displaystyle{\mathcal{C} =\big\{\big (\beta _{1}f(\alpha _{1}),\ldots,\beta _{n}f(\alpha _{n})\big)\mid f \in \mathbb{F}[x] \wedge \deg f < k\big\}}$$

where $\alpha _{1},\ldots,\alpha _{n} \in \mathbb{F}$ are distinct, and the $\beta _{1},\ldots,\beta _{n} \in \mathbb{F}$ are non-zero (not necessarily distinct). The α _i are called evaluation points and the β _i column multipliers. $\mathcal{C}$ has minimum distance d = n − k + 1 and the code is therefore MDS.

Consider now that some $\boldsymbol{c} = (c_{1},\ldots,c_{n})$ was sent, resulting from evaluating some $f \in \mathbb{F}[x]$, and that $\boldsymbol{r} = (\beta _{1}r_{1},\ldots,\beta _{n}r_{n}) =\boldsymbol{ c} + (\beta _{1}e_{1},\ldots,\beta _{n}e_{n})$ was the received word with (normalised) error $\boldsymbol{e} = (e_{1},\ldots,e_{n})$. Let $\mathcal{E} =\{ i\mid e_{i}\neq 0\}$ and $\epsilon = \vert \mathcal{E}\vert$. In failure probability considerations, we consider the $\vert \mathbb{F}\vert$-ary symmetric channel.

Introduce $G \triangleq \prod _{i=1}^{n}(x -\alpha _{i})$, and for any integer t ≥ 1, let R ^(t) be the Lagrangian polynomial through the “powered” $\boldsymbol{r}$, i.e. the minimal degree polynomial satisfying $R^{(t)}(\alpha _{i}) = r_{i}^{t}$ for i = 1, …, n. Naturally, we have degR ^(t) ≤ n − 1 and R ^(t) can be directly calculated by the receiver. As usual for key equation decoders, the algorithm will revolve around the notion of error locator: $\varLambda =\prod _{j\in \mathcal{E}}(x -\alpha _{j})$. Choose now some $\ell\in \mathbb{N}$ subject to ℓ(k − 1) < n. Then we easily derive the powered Gao key equations:

Proposition 1

$\varLambda R^{(t)} \equiv \varLambda f^{t}\mod G$

Proof

Polynomials are equivalent modulo G if and only if they have the same evaluation at α ₁, …, α _n . For α _i where e _i ≠ 0, both sides of the above evaluate to zero, while for the remaining α _i they give $\varLambda (\alpha _{i})r_{i}^{t} =\varLambda (\alpha _{i})f(\alpha _{i})^{t}$. □ 

3 The Decoding Algorithm

The key equations of Proposition 1 are non-linear in Λ and f, so the approach for solving them is to relax the equations into a linear system, similarly to classical key equation decoding. We will ignore the structure of the right hand-sides and therefore seek polynomials λ and $\psi ^{(1)},\ldots,\psi ^{(\ell)}$ such that $\lambda R^{(t)} \equiv \psi ^{(t)}\mod G$ as well as $\deg \lambda +t(k - 1) \geq \deg \psi ^{(t)}$ for t = 1, …, ℓ. We will call such $(\lambda,\psi ^{(1)},\ldots,\psi ^{(\ell)})$ a solution to the key equations.

Clearly $(\varLambda,\varLambda f,\ldots,\varLambda f^{\ell})$ is a solution. There are, however, infinitely many more, so the strategy is to find a solution such that degλ is minimal; we will call this the minimal solution. Thus decoding can only succeed when Λ has minimal degree of all solutions. The probability of this occurring will be discussed in Sect. 4.

Conceptually, Power Gao decoding is then straightforward: pre-calculate G and from the received word, calculate $R^{(1)},\ldots,R^{(\ell)}$. Find then a minimal solution $(\lambda,\psi _{1},\ldots,\psi _{\ell})$ with λ monic. If this has the valid structure of $(\varLambda,\varLambda f,\ldots,\varLambda f^{\ell})$, then return f. Otherwise, declare decoding failure.

For Power syndromes, the key equations are similar to ours except that the modulo polynomials are just powers of x. In this case, finding a minimal solution is known as multi-sequence shift-register synthesis, and the fastest known algorithm is an extension of the Berlekamp–Massey algorithm [5] or the Divide-&-Conquer variant of this [6]. These can not handle the modulus G that we need, however.

Table 1 Complexities of solving the key equations for the three approaches discussed in [2]

A generalised form of multi-sequence shift-register synthesis was considered in [2], and several algorithms for finding a minimal solution were presented. The key equations for our case fit into this framework. We refer the reader to [2] for the details on these algorithms, but the asymptotic complexities when applied to Power Gao decoding are given in Table 1. The same complexities would apply to Power syndromes and also match the algorithms [5, 6] mentioned before. The other steps of the decoding are easily seen to be cheaper than this; e.g. the calculation of $R^{(1)},\ldots,R^{(\ell)}$ by Lagrangian interpolation can be done trivially in $O(\ell n^{2})$ or using fast Fourier techniques in $O(\ell n\log ^{2}n)$ [9, p. 231]. Thus Power Gao decoding is asymptotically as fast as Power syndromes.

4 Properties of the Algorithm

Power Gao will fail if $(\varLambda,\varLambda f,\ldots,\varLambda f^{\ell})$ is not the found minimal solution, so the question is when one can expect this to occur. Since the algorithm returns at most one codeword, it must fail for some received words whenever ε ≥ d∕2. Whenever an answer is found, however, this must correspond to a closest codeword: any closer codeword would have its own corresponding error locator and information polynomial, and these would yield a smaller solution to the key equations.

We first show that Power syndromes is behaviourally equivalent to Power Gao. We will need to assume that the evaluation points α _i ≠ 0 for all i, which is a condition for Power syndromes decoding. This implies x ∤ G. We will use a “coefficient reversal” operator defined for any $p \in \mathbb{F}[x]$ as $\overline{p} = x^{\deg p}p(x^{-1})$.

In Power syndromes decoding, one considers $\boldsymbol{r}^{(t)} = (\beta _{1}r_{1}^{t},\ldots,\beta _{n}r_{n}^{t})$ for t = 1, …, ℓ as received words of GRS codes with parameters [n, t(k − 1) + 1, n − t(k − 1)], resulting from evaluating f ^t; these “virtual” codes have the same evaluation points and column multipliers as $\mathcal{C}$. The $\boldsymbol{r}^{(t)}$ will therefore have the same error positions as $\boldsymbol{r}$, so the same error locator applies. For each t, we can calculate the syndrome S ^(t) corresponding to $\boldsymbol{r}^{(t)}$, which can be written as

$$\displaystyle{S^{(t)} =\Big (\sum _{ i=1}^{n} \frac{r_{i}^{t}\zeta _{ i}} {1 - x\alpha _{i}}\bmod x^{n-t(k-1)+1}\Big)}$$

where $\zeta _{i} =\prod _{j\neq i}(\alpha _{i} -\alpha _{j})^{-1}$; see e.g. [4, p. 185]. By insertion one sees that

$$\displaystyle{\overline{\varLambda }S^{(t)} \equiv \varOmega ^{(t)}\mod x^{n-t(k-1)+1},\quad t = 1,\ldots,\ell}$$

where Ω ^(t) is a certain polynomial satisfying $\deg \varOmega ^{(t)} <\deg \varLambda$. Note that we are using Λ reversed; indeed, one often defines error-locator as $\prod _{i\in \mathcal{E}}(1 - x\alpha _{i}) = \overline{\varLambda }$ when considering the syndrome key equation. The decoding algorithm follows simply from finding a minimal degree polynomial $\overline{\lambda }$ such that $\omega ^{(t)} = (\overline{\lambda }S^{(t)}\bmod x^{n-t(k-1)+1})$ satisfies $\deg \lambda >\deg \omega ^{(t)}$ for all t. The decoding method fails if $\overline{\lambda }\neq \gamma \overline{\varLambda },\forall \gamma \in \mathbb{F}$. We now have:

Proposition 2

Decoding using Power Gao fails if and only if decoding using Power syndromes fails.

Proof

Note first that $R^{(t)} =\sum _{ i=1}^{n}r_{i}^{t}\zeta _{i}\prod _{j\neq i}(x -\alpha _{j})$. By insertion we get $S^{(t)} \equiv \overline{R}^{(t)}\overline{G}^{-1}\mod x^{n-t(k-1)+1}$ (since $x \nmid G$). Power Gao fails if there is some $\lambda \in \mathbb{F}[x]$ which is not a constant times Λ and such that degλ ≤ degΛ and $\psi ^{(t)} = (\lambda R^{(t)}\bmod G)$ has $\deg \psi ^{(t)} <\deg \lambda +t(k - 1) + 1$ for each t = 1, …, ℓ. This means there must be some ω ^(t) with degω ^(t) ≤ degλ − 1 such that

$$\displaystyle\begin{array}{rcl} \begin{array}{rclc} \lambda R^{(t)} -\omega ^{(t)}G& =&\psi &\;\Longleftrightarrow\; \\ \overline{\lambda }\,\overline{R}^{(t)} -\overline{\omega }^{(t)}\overline{G}& =&\overline{\psi }^{(t)}x^{\deg G+\deg \lambda -1-(\deg \lambda +t(k-1))} & \Rightarrow \\ \overline{\lambda }\,\overline{R}^{(t)} & \equiv &\overline{\omega }^{(t)}\overline{G}\mod x^{n-t(k-1)-1}\end{array} & & {}\\ \end{array}$$

Dividing by $\overline{G}$, we see that $\overline{\lambda }$ and the $\overline{\omega }^{(t)}$ satisfy the congruences necessary to form a solution to the Power syndromes key equation, and they also satisfy the degree bounds. Showing the proposition in the other direction runs analogously. □ 

Corollary 3 (Combining [5] and Proposition 2)

Power Gao decoding succeeds if ε < d∕2. Let

$$\displaystyle{\tau (\ell) = \tfrac{\ell} {\ell+1}n -\tfrac{1} {2}\ell(k - 1) - \tfrac{\ell} {\ell+1}}$$

Then decoding will fail with high probability if $\epsilon >\tau (\hat{\ell})$ , where $1 \leq \hat{\ell}\leq \ell$ is chosen to maximise τ(ℓ). ¹

Between the above two bounds, Power decoding will sometimes succeed and sometimes fail. Simulations indicate that failure occurs with quite small probability. The only proven bound so far is for ℓ = 2 where for exactly ε errors occurring, we have $P_{f}(\epsilon ) < (q/q - 1)^{\epsilon }q^{3(\epsilon -\tau (2))}/(q - 1)$, [5, 10].

We will give a new bound for P _f (ε) when ℓ = 3, but we will first show a property which allows a major simplification in all subsequent analyses.

Proposition 4

Power Gao decoding fails for some received word $\boldsymbol{r}$ if and only if it fails for $\boldsymbol{r} +\hat{\boldsymbol{ c}}$ where $\hat{\boldsymbol{c}}$ is any codeword.

Proof

We will show that Power Gao decoding fails for $\boldsymbol{r} =\boldsymbol{ c} +\boldsymbol{ e}$ if and only if it fails for $\boldsymbol{e}$ as received word; since $\boldsymbol{c}$ was arbitrary, that implies the proposition.

Let $R_{e}^{(t)}$ be the power Lagrangians for $\boldsymbol{e}$ as received word, i.e. $R_{e}^{(t)}(\alpha _{i}) = e_{i}^{t}$ for each i and t, and let $R_{e} = R_{e}^{(1)}$. Consider a solution to the corresponding Power Gao key equations $(\lambda,\psi _{1},\ldots,\psi _{\ell})$; i.e. $\lambda R_{e}^{(t)} \equiv \psi _{t}\mod G$ and $\deg \lambda +t(k - 1) + 1 >\deg \psi _{t}$. Let as usual $R^{(t)}$ be the power Lagrangians for $\boldsymbol{r}$ as received word and R = R ⁽¹⁾. Note now that $R^{(t)} \equiv R^{t}\mod G$ since both sides of the congruence evaluate to the same at all α _i ; similarly $R_{e}^{(t)} \equiv R_{e}^{t}\mod G$. Since r _i  = f(α _i ) + e _i linearity implies that R = f + R _e . Define ψ ₀ = λ and note that then also for t = 0 we have $\deg \lambda +t(k - 1) + 1 >\deg \psi _{t}$. We then have the chain of congruences modulo G:

$$\displaystyle\begin{array}{rcl} \begin{array}{l} \lambda R^{(t)} \equiv \lambda R^{t} \equiv \lambda (f + R_{e})^{t} \equiv \lambda \sum _{s=0}^{t}\tbinom{t}{s}f^{s}R_{e}^{t-s} \equiv \sum _{s=0}^{t}\tbinom{t}{s}f^{s}\psi _{t-s}\mod G\end{array} & & {}\\ \end{array}$$

Each term in the last sum has degree $s\deg f +\deg \psi _{t-s} < s(k - 1) +\deg \lambda +(t - s)(k - 1) + 1 =\deg \lambda +t(k - 1) + 1$, which means that

$$\displaystyle{\Big(\lambda,\ \sum _{s=0}^{1}\tbinom{1}{s}f^{s}\psi _{1-s},\ \ldots \,\ \sum _{s=0}^{\ell}\tbinom{\ell}{s}f^{s}\psi _{\ell-s}\Big)}$$

is a solution to the Power Gao key equations with $\boldsymbol{r}$ as a received word. The same argument holds in the other direction, so any solution to one of the key equations induces a solution to the other with the same first component; obviously then, their minimal solutions must be in bijection, which directly implies that they either both fail or neither of them fail. □ 

For the new bound on the failure probability, we first need a technical lemma:

Lemma 5

Let $U \in \mathbb{F}[x]$ of degree N, and let K ₁ < K ₂ < K ₃ < N be integers. Let $S =\{ (f_{1},f_{2},f_{3})\mid f_{1}f_{3} \equiv f_{2}^{2}\mod U,\ f_{2}\mathrm{monic},\ \forall t.\deg f_{t} < K_{t}\}$ . Then

$$\displaystyle\begin{array}{rcl} \begin{array}{rcll} \vert S\vert & \leq &3^{K_{2}-1}q^{K_{2}} & \mathrm{if}K_{1} + K_{3} - 2 < N \\ \vert S\vert & \leq &2^{K_{1}+K_{3}-2}q^{K_{1}+K_{2}+K_{3}-N-2} & \mathrm{if}K_{1} + K_{3} - 2 \geq N\end{array} & &{}\end{array}$$

(1)

Proof

If K ₁ + K ₃ − 2 < N, then $f_{1}f_{3} \equiv f_{2}^{2}\mod U$ implies $f_{1}f_{3} = f_{2}^{2}$. We can choose a monic f ₂ in $(q^{K_{2}} - 1)/(q - 1)$ ways. For each choice, then f ₂ has at most K ₂ − 1 prime factors, so the factors of f ₂ ² can be distributed among f ₁ and f ₃ in at most $3^{K_{2}-1}$ ways. Lastly, the leading coefficient of f ₁ can be chosen in q − 1 ways.

If K ₁ + K ₃ − 2 ≥ N, then for each choice of f ₂, the product f ₁ f ₃ can be among $\{f_{2}^{2} + gU\mid \deg g \leq K_{1} + K_{3} - 2 - N\}$. This yields at most $q^{K_{1}+K_{2}+K_{3}-N-2}/(q - 1)$ candidates for f ₁ f ₃; each of these has at most K ₁ + K ₃ − 2 unique prime factors, which can then be distributed among f ₁ and f ₃ in at most $2^{K_{1}+K_{3}-2}$ ways. Again, the leading coefficient of f ₁ leads to a factor q − 1 more. □ 

Proposition 6

For $\ell= 3$ , the probability that Power decoding (Gao or Syndrome) fails when ε > d∕2 is at most

$$\displaystyle\begin{array}{rcl} \begin{array}{rl} (q/(q - 1))^{\epsilon }(3/q)^{2\epsilon -(n-2k+1)}q^{3(\epsilon -\tau (2))+k-1} & \mathrm{if}\epsilon <\tau (2) -\tfrac{1} {3}k + 1 \\ (q/(q - 1))^{\epsilon }2^{2(2\epsilon -d)+2(k-1)}q^{4(\epsilon -\tau (3))-2} & \mathrm{if}\epsilon \geq \tau (2) -\tfrac{1} {3}k + 1\end{array} & & {}\\ \end{array}$$

Proof

By Proposition 4, we can assume that $\boldsymbol{c} = 0$, i.e. that $\boldsymbol{r} =\boldsymbol{ e}$. That means $R^{(t)}(\alpha _{i}) = 0$ for $i\notin \mathcal{E}$, so we can write $R^{(t)} = E^{(t)}\varUpsilon$ for some E ^(t) with $\deg E^{(t)} <\epsilon$, where $\varUpsilon = G/\varLambda$ is the “truth-locator”. Power Gao decoding fails if and only if there exists $(\lambda,\psi _{1},\psi _{2},\psi _{3})$ such that $\lambda \neq \varLambda$, $\deg \lambda \leq \deg \varLambda$, $\deg \lambda +t(k - 1) + 1 >\deg \psi _{t}$ for t = 1, 2, 3 as well as

$$\displaystyle\begin{array}{rcl} \begin{array}{rclcrcl} \lambda R^{(t)} & \equiv &\psi _{t}\mod G&\;\Longleftrightarrow\;&\lambda E^{(t)} & \equiv &\hat{\psi }_{t}\mod \varLambda \end{array} & &{}\end{array}$$

(2)

where $\hat{\psi }_{t} =\psi _{t}/\varUpsilon$. Note that ψ _t must be divisible by Υ since both the modulus and the left-hand side of the first congruence is.

Denote by E the unique polynomial with degree less than ε having E(α _i ) = e _i for $i \in \mathcal{E}$. For any $i \in \mathcal{E}$ then $(\lambda E^{(t)})(\alpha _{i}) =\lambda (\alpha _{i})\varUpsilon (\alpha _{i})^{-1}e_{i}^{t}$, which means $\lambda E^{(t)} \equiv \hat{\lambda } E^{t}\mod \varLambda$ for some polynomial $\hat{\lambda }$.

After having chosen error positions, drawing error values uniformly at random is the same as drawing uniformly at random from possible E. So given the error positions, the probability that Power decoding will fail is $T_{\varLambda }/(q - 1)^{\epsilon }$, where T _Λ is the number of choices of E such that there exist $\hat{\lambda },\hat{\psi }_{1},\hat{\psi }_{2},\hat{\psi }_{3}$ having

$$\displaystyle{\hat{\lambda }E^{t} \equiv \hat{\psi }_{ t}\mod \varLambda,\quad t = 1,2,3}$$

as well as $\deg \hat{\psi }_{t} <\deg \varLambda +t(k - 1) + 1 - (n-\deg \varLambda ) = 2\epsilon - (n - t(k - 1) - 1)$.

Note that these congruences imply $\hat{\psi }_{1}\hat{\psi }_{3} \equiv \hat{\psi }_{2}^{2}\mod \varLambda$. Denote by $\hat{T}_{\varLambda }$ the number of triples $(\hat{\psi }_{1},\hat{\psi }_{2},\hat{\psi }_{3}) \in \mathbb{F}[x]^{3}$ satisfying just this congruence as well as the above degree bounds. Then $\hat{T}_{\varLambda } \geq T_{\varLambda }$: for if $\gcd (\hat{\lambda },\varLambda ) = 1$ then two different values of E could not yield the same triple since $E \equiv \hat{\psi }_{2}/\hat{\psi }_{1}\mod \varLambda$ uniquely determines E. Alternatively, if $\gcd (\hat{\lambda },\varLambda ) = g\neq 1$ then the congruences imply $g\mid \hat{\psi }_{t}$ for all t, so that $E \equiv (\hat{\psi }_{2}/g)/(\hat{\psi }_{1}/g)\mod \varLambda /g$. This leaves a potential q ^degg possible other choices of E yielding the same triple; but all these possibilities are counted in the triples since $(t\psi _{1}/g,t\psi _{2}/g,t\psi _{3}/g)$ will be counted for any $t \in \mathbb{F}[x]$ with degt < degg.

In fact, we have $\hat{T}_{\varLambda } \geq (q - 1)T_{\varLambda }$, since whenever $(\hat{\psi }_{1},\hat{\psi }_{2},\hat{\psi }_{3})$ is counted, so is $(\beta \hat{\psi }_{1},\beta \hat{\psi }_{2},\hat{\psi }_{3})$, and this doesn’t change the fraction $\hat{\psi }_{1}/\hat{\psi }_{2}$. Thus, we over-estimate instead $\hat{T}_{\varLambda }/(q - 1)$ by counting the number of triples where $\hat{\psi }_{2}$ is monic. Lemma 5 gives an upper bound for exactly this number, setting N = ε and K _t  = 2ε − (n − t(k − 1) − 1). Divided by (q − 1)^ε, this is then an upper bound on the failure probability given the error positions. But since this probability is independent of the choice of Λ, it is also the failure probability over all errors vectors of weight ε. □ 

By experimentation, one can demonstrate that the bound is not tight: for instance, for a [250, 30, 221] GRS code, the bound is greater than 1 for ε > 143, while simulation indicate almost flawless decoding up to 147 errors. However, in a relative and asymptotic sense the above bound is strong enough to show that up to τ(3) errors can be corrected with arbitrary low failure probability:

Corollary 7

Having ℓ = 3, then for any δ > 0, with n →∞ while keeping q∕n, k∕n and ε∕n constant, the probability that Power decoding fails goes to 0 when ε∕n < τ(3)∕n −δ.

Proof (Proof sketch)

We consider only the high-error failure probability of Proposition 6. For n → ∞, the failure probability bound will approach

$$\displaystyle\begin{array}{rcl} \begin{array}{rcl} 2^{2(2\epsilon -d)+2(k-1)}q^{4(\epsilon -\tau (3))} & \leq &(q^{n})^{4(\epsilon /n-\tau (3)/n)+(2(2\epsilon /n-d/n)+2k/n)/\log q}\end{array} & & {}\\ \end{array}$$

The contribution $(2(2\epsilon /n - d/n) + 2k/n)/\log q$ goes to 0 as n → ∞, leaving (q ⁿ)^a for a = 4(ε∕n −τ(3)∕n) < −4δ. □ 

5 A Family of Bad Errors

Power decoding will usually fail when the powered key equations are linearly dependent; in particular, it will fail if one of the key equations is trivially satisfied.

An anonymous reviewer of this paper suggested the following construction of errors where, for a given sent codeword, the second key equation will be trivial: let $\mathbb{F}$ be a non-binary field, and let $\hat{\boldsymbol{c}} \in \mathcal{C}$ be some non-zero codeword, obtained as the evaluation of $\hat{f}$ with $\deg \hat{f} < k$. Choose d∕2 ≤ ε ≤ τ(2) positions for which $\hat{\boldsymbol{c}}$ is non-zero. Let then $\boldsymbol{e} = (e_{1},\ldots,e_{n})$ be given by $e_{i} = -2\hat{c}_{i}$ when i is one of the chosen position, and e _i  = 0 otherwise. If $\hat{\boldsymbol{r}} =\hat{\boldsymbol{ c}} +\boldsymbol{ e}$ is received, then the second Lagrangian $\hat{R}^{(2)}$ equals $\hat{f}^{2}$, i.e. $\deg \hat{R}^{(2)} < 2k - 1$ (in other words, we have $\hat{\boldsymbol{r}}^{(2)} =\hat{\boldsymbol{ c}}^{(2)}$ so the squared received word is a codeword in the “squared” GRS code). That means that for any $\lambda \in \mathbb{F}[x]$, then $\deg (\lambda \hat{R}^{(2)}\bmod G) \leq \deg \lambda +2k - 1$, and so the second key equation is useless.

Clearly then, if $\hat{\boldsymbol{r}}$ is received, then almost surely²Power decoding will fail when ℓ = 2, and it is easy to show that it will also fail when ℓ > 2.

From Proposition 4 it follows that decoding will also fail when receiving $\boldsymbol{c} +\boldsymbol{ e}$ for any sent codeword $\boldsymbol{c} \in \mathcal{C}$; in particular when sending $\boldsymbol{0}$ and receiving $\boldsymbol{e}$. This might at first seem counter-intuitive since the second Lagrangian E ⁽²⁾ when $\boldsymbol{e}$ is the received word does not have low degree (i.e. $\boldsymbol{e}^{(2)}$ is not in the squared GRS code). However, in this case the key equation involving E ⁽²⁾ will be linearly dependent on that involving E = E ⁽¹⁾, and so will not add further requirements. This can be seen directly as follows: since $\boldsymbol{e} =\hat{\boldsymbol{ r}} -\hat{\boldsymbol{ c}}$ then $\boldsymbol{e}^{(2)} =\hat{\boldsymbol{ r}}^{(2)} +\hat{\boldsymbol{ c}}^{(2)} - 2\hat{\boldsymbol{c}} \star \hat{\boldsymbol{ r}} = 2\hat{\boldsymbol{c}}^{(2)} - 2\hat{\boldsymbol{c}} \star \hat{\boldsymbol{ r}}$, where ⋆ is the component-wise product. Thus $E^{(2)} \equiv 2\hat{f}^{2} - 2\hat{f}R\mod G$. So if $\lambda \in \mathbb{F}[x]$ satisfies the first key equation, i.e. $\deg (\lambda E\bmod G) \leq \deg \lambda +k - 1$, then we get

$$\displaystyle{\deg (\lambda E^{(2)}\bmod G) =\deg (\lambda \hat{f}^{2} +\lambda E\hat{f}\bmod G) \leq \deg \lambda +2(k - 1)}$$

So λ satisfies the second key equation.

The “bad error” construction can easily be generalised for higher ℓ whenever $\mathbb{F}$ has ℓ’th roots of unity different from 1: then e _i can be chosen as $(\xi _{i} - 1)\hat{c}_{i}$ where ξ _i ≠ 1 is any of those roots of unity. Then for $\hat{\boldsymbol{r}} =\hat{\boldsymbol{ c}} +\boldsymbol{ e}$ we get $\hat{\boldsymbol{r}}^{(\ell)} =\hat{\boldsymbol{ c}}^{(\ell)}$ and so $\deg R^{(\ell)} \leq \ell (k - 1)$.

A full Power Gao decoder has been implemented in Sage v5.13 [7] and is available for download at http://jsrn.dk/code-for-articles. Also implemented is randomly constructing “bad errors” $\boldsymbol{e}$ as above (for any $\ell$), and a demonstration that Power decoding fails for $\hat{\boldsymbol{r}}$, $\boldsymbol{e}$ and $\boldsymbol{c} +\boldsymbol{ e}$ for any random codeword $\boldsymbol{c}$.