Power Error Locating Pairs

Alain Couvreur (1) , Isabella Panaccione (1)

1 GRACE - Geometry, arithmetic, algorithms, codes and encryption

We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding the half minimum distance. This algorithm applies to Reed--Solomon codes, algebraic geometry codes and any other code benefiting from an error correcting pair. When applied to Reed--Solomon or algebraic geometry codes, the algorithm's decoding radius turns out to be the same as Sudan's or power decoding algorithm. Similarly to power decoding it boils down to linear algebra, returns at most one solution and might fail in some rare cases. On the other hand it presents the advantage to have a smaller space and time complexity than power decoding.

Mots clés: Error correcting codes; Reed-Solomon codes; Algebraic geometry codes; Decoding algorithms; Power decoding; Error correcting pairs

Domaines: Mathématiques [math]; Théorie de l'information et codage [math.IT]; Géométrie algébrique [math.AG]; Théorie des nombres [math.NT]; Théorie de l'information [cs.IT]

Alain Couvreur, Isabella Panaccione. Power Error Locating Pairs. Designs, Codes and Cryptography, 2020, 88 (8), pp.1561-1593. ⟨10.1007/s10623-020-00774-3⟩. ⟨hal-02196650⟩