Sub-quadratic Decoding of One-point Hermitian Codes

Johan Sebastian Rosenkilde Nielsen 1 Peter Beelen 2
1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
Inria Saclay - Ile de France
2 DTU - Technical University of Denmark [Lyngby]
Abstract : We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realisation of the Guruswami–Sudan algorithm by using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimisation. The second is a Power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the matrix minimisation algorithms from computer algebra, yielding similar asymptotic complexities.
Keywords : Power decoding Guruswami-Sudan Hermitian codes AG codes list decoding
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2015, 61 (6), pp.3225-3240 〈10.1109/TIT.2015.2424415〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01245062
Contributeur : Johan S. R. Nielsen <>
Soumis le : jeudi 17 décembre 2015 - 15:39:26
Dernière modification le : samedi 18 février 2017 - 01:14:36
Document(s) archivé(s) le : samedi 29 avril 2017 - 16:58:56

Fichier

2015_ieee_hermitian.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

INRIA | UNIV-PARIS-SACLAY

Citation

Johan Sebastian Rosenkilde Nielsen, Peter Beelen. Sub-quadratic Decoding of One-point Hermitian Codes. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2015, 61 (6), pp.3225-3240 〈10.1109/TIT.2015.2424415〉. 〈hal-01245062〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

87

Téléchargements de fichiers

59

Contact


archive-ouverte@inria.fr