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