Skip to Main content Skip to Navigation
Theses

On the Algorithms of Guruswami-Sudan List Decoding over Finite Rings

Guillaume Quintin 1, 2
1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Résumé : Cette thèse porte sur l'algorithmique des techniques de décodage en liste, initiée par Guruswami et Sudan en 1998, dans le contexte des codes de Reed-Solomon sur les anneaux finis. Deux approches sont considérées. Dans un premier temps, nous adaptons l'algorithme de décodage en liste de Guruswami-Sudan aux codes de Reed-Solomon généralisés sur les anneaux finis. Nous étudions en détails les complexités de l'algorithme pour les anneaux de Galois et les anneaux de séries tronquées. Dans un deuxième temps nous approfondissons l'étude d'une technique de remontée pour le décodage en liste. Nous montrons que cette derni're permet de corriger davantage de motifs d'erreurs que la technique de Guruswami-Sudan originale. Nous appliquons ensuite cette même technique aux codes de Reed-Solomon généralisés sur les anneaux de Galois et les anneaux de séries tronquées et obtenons de meilleures bornes de complexités. Enfin nous présentons l'implantation des algorithmes en C et C++ des algorithmes de décodage en liste étudiés au cours de cette thèse. Tous les sous-algorithmes nécessaires au décodage en liste, comme la recherche de racines pour les polynômes univariés, l'arithmétique des corps et anneaux finis sont aussi présentés. Indépendamment, ce manuscrit contient d'autres travaux sur les codes quasi-cycliques. Nous prouvons qu'ils sont en correspondance biunivoque avec les idéaux à gauche d'un certain anneaux de matrices. Enfin nous adaptons le cadre proposé par Guruswami et Sudan pour les codes à base d'ideaux aux codes construits à l'aide des corps de nombres. Nous fournissons un algorithme de décodage en liste dans ce contexte.
Complete list of metadatas

Cited literature [154 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00759820
Contributor : Guillaume Quintin <>
Submitted on : Monday, December 3, 2012 - 1:16:45 AM
Last modification on : Friday, November 22, 2019 - 1:18:32 AM
Document(s) archivé(s) le : Saturday, December 17, 2016 - 6:24:42 PM

Identifiers

  • HAL Id : pastel-00759820, version 1

Collections

Citation

Guillaume Quintin. On the Algorithms of Guruswami-Sudan List Decoding over Finite Rings. Information Theory [cs.IT]. Ecole Polytechnique X, 2012. English. ⟨pastel-00759820⟩

Share

Metrics

Record views

848

Files downloads

1383