Vendredi 27 mars 2015 à 10h30 en salle C47

Johan S. R. Nielsen (INRIA)

Titre : Power decoding of Hermitian codes in sub-quadratic time

Résumé :

Reed-Solomon codes have optimal minimum distance and we know efficient
encoding and decoding algorithms of quasi-linear complexity in the
length. Their main drawback is that their lengths are bounded by the
size of the alphabet, i.e. the field over which they are defined.
Algebraic geometry codes are a generalisation allowing longer codes on
the same alphabet, and one of the most interesting sub-families of these
are the Hermitian codes. The price for the greater length is more
complicated computations: so far, no decoding algorithm with
sub-quadratic complexity in the length of the code was known.
We show how to achieve this by building the decoder around the problem
of finding a short vector in an F[x]-module, and performing this step
using state-of-the-art algorithms from computer algebra. This approach
follows recent trends in decoding of Reed-Solomon codes. Furthermore,
our decoder is a "Power decoder", probabilistically capable of decoding
errors beyond half-the-minimum distance for low-rate codes.
The resulting decoder has complexity O(n^(5/3)*MM(ell)), where n is the
code length and ell is the "powering" degree parameter for the decoder.
MM(m) denotes the field-operation complexity of multiplying two m x m
matrices together over the field