École Nationale Supérieure de
Techniques Avancées

Résumé

Dans cette thèse, nous étudions les codes de Reed-Muller qui constituent une des familles de codes correcteurs les plus étudiées, et les plus utilisées dans la transmission des communications numériques. Grâce à leur rapidité d'encodage et de décodage, ils furent notamment utilisés pour les transmissions satellitaires. Ils ont également un lien très fort avec les notions de fonctions booléennes. L'étude de ces dernières constitue le coeur de la réalisation et de la sécurité des systèmes de chiffrement à clé secrète, tant par blocs que par flot. Depuis l'introduction de ces codes, de très nombreux algorithmes de décodage virent le jour, et aujourd'hui encore étudier leur structure afin de construire des algorithmes de décodage constitue un fructueux domaine de recherche. Ces algorithmes de décodage peuvent être utilisés dans l'étude de la structure de systèmes de chiffrement à clé secrète. Nous exposons un point de vue unificateur à l'ensemble des algorithmes de décodage des codes de Reed-Muller, ce point de vue étant celui de la dérivée discrète. Nous exposons un algorithme performant pour le décodage des codes d'ordre deux, que nous analysons ensuite. Nous discutons les résultats de simulations des algorithmes étudiés pour les petites et moyennes longueurs de code. Ces résultats montrent que l'algorithme proposé décode beaucoup plus loin en pratique que les autres algorithmes.