Isabella Panaccione – The Power Error Locating Pairs algorithm

In this talk we present an overview of some decoding algorithms for Reed-Solomon codes, together with a « power » extension of the Error Correcting Pairs algorithm.

It is known that several algorithms have been designed in order to decode Reed-Solomon codes. In particular Welch-Berlekamp algorithm and the Error Correcting Pairs algorithm are two classical algorithms which correct up to half the minimum distance of the code.

Some extensions of Welch-Berlekamp algorithm can even correct beyond this bound: on the one hand two such extensions are Sudan algorithm and Guruswami-Sudan algorithm, which are deterministic and return the list L of all possible solutions (note that in the typical situation |L|=1). On the other hand, the Power Decoding algorithm has the same decoding radius as Sudan algorithm, is quicker but may fail (it gives one solution or zero).

The Error Correcting Pairs algorithm behaves slightly differently with respect to Welch-Berlekamp algorithm, since it mainly consists in localizing errors. After that, decoding boils down to elementary linear algebra. The advantage of this algorithm is that it can be applied to a larger class of codes (Reed-Solomon, algebraic-geometry codes, some cyclic codes). The idea that motivated our work was then to design an extension of the Error Correcting Pairs algorithm with the same versatility and with decoding radius beyond half the minimum distance.

This extension takes the name of Power Error Locating Pairs algorithm. It consists, as for the Power Decoding algorithm, in considering more subproblems (each of them given by a power of the main one) at the same time. Though, while for the Power Decoding algorithm the condition to have a solution depends on the dimension of a linear system solution space, for the Power Error Correcting Pairs algorithm, it depends on the nullity of a certain space.

https://webconference.unicaen.fr/b/mor-7jm-rcy