Étude et amélioration du décodage des codes de Reed-Muller d'ordre deux.


Study and improvement of the decoding of Reed-Muller codes of second order.



Bassem Sakkour

Thèse de Doctorat, Ècole Polytechnique, 6 Avril 2007.
Ph.D. Thesis of Ecole Polytechnique, defended April 6, 2007.

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.

Abstract

This thesis is devoted to decoding of binary Reed-Muller codes of order two. The binary Reed-Muller codes are one of the most interesting and valuable classes of error correcting codes. Being invented half a century ago these codes remain a subject of many research. In particular, the key problem of the thesis - decoding of Reed-Muller codes, attracts a lot of attention in coding theory as well as in cryptography and computer science. This great interest can be explained by usage of Reed-Muller codes and their decoding algorithms for so-called holographic proofs, constructing of hard-core predicates (M.Levin and O.Goldreich,1989) and finding good linear, quadratic etc approximations to Boolean functions used in cryptography. We expose a unifying point of view to all known decoding algorithms of this codes, this point of view is that of the discrete derivative. We expose a powerful algorithm for the decoding of the codes of order two, which we analyze then. We discuss the results of simulations of the algorithms studied for the small and average lengths of code. Simulation results show that the proposed algorithm decodes in practice much further that the other algorithms.