Décodage de codes de Reed-Muller

Mots clés: codes, Reed-Muller, corps finis.

Le but de ce projet est de comparer deux algorithmes de décodage de codes de Reed-Muller $RM(2,m)$.

Résumé

Prérequis

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

Objectifs

• Implanter des opérations efficaces sur les vecteurs booléens de longueur arbitraire (avec bit-packing), notamment la transformée de Walsh.

• Implanter l’algorithme de codage des codes de Reed-Muller.

• Implanter l’algorithme de décodage par majorité de Reed

• Implanter l’algorithme de décodage des codes de Hadamard $RM(1,m)$.

• Implanter l’algorithme récursif de Patterson.

Références

• V. Guruswami. Error-Correcting Codes: Constructions and Algorithms.
• K. G. Patterson, A. E. Jones. Efficient Decoding Algorithms for Generalised Reed-Muller 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.
• http://courses.cs.washington.edu/courses/cse533/06au/
• http://www.cs.cmu.edu/~venkatg/teaching/codingtheory/
• http://www.cse.buffalo.edu/~atri/courses/coding-theory/book/index.html
• http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf