Décodage de codes de Reed-Solomon par l'algorithme de Gao

Mots clés: codes, Reed-Solomon, corps finis, polynômes, FFT.

Le but de ce projet est d’implanter l’algorithme de Gao pour le décodage des codes de Reed-Solomon.

Résumé

Prérequis

• Connaissances de base sur les corps finis et les codes.

Objectifs

• Implanter l’arithmétique des polynômes à coefficients dans $\mathbb{F}_p$ (addition, multiplication, division euclidéenne, xgcd, interpolation)

• Implanter l’algorithme de Gao pour des Reed-Solomon sur un corps premier

• Revenir sur l’arithmétique de $\mathbb{F}_p[X]$ en implantant la FFT pour certains premiers p spéciaux, comme décrit dans le papier.

• Faire des tests de performances.

Références

• S. Gao. A new algorithm for decoding Reed-Solomon codes
• A. Rudra. Error Correcting Codes: Combinatorics, Algorithms and Applications.
• J.-G. Dumas. Théorie des codes : compression, cryptage, correction. Côte BU: 005.82 THE.
• B. Martin. Codage, cryptologie et applications. Côte BU: 005.82 MAR.
• R. Lidl. Finite fields. (chapitres 9 et 10 sur les codes).
• R. Lidl, H. Niederreiter. Introduction to Finite fields and their applications (chapitre 8).
• J. von zur Gathen, J. Gerhard. Modern computer Algebra.
• A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, É. Schost. Algorithmes Efficaces en Calcul Formel.
• S. Fedorenko. A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm.