RÉSUMÉ

Les codes de Reed-Muller sont des codes d'évaluation. Un mot du Reed-Muller sur F₂ est donc en fait l'image d'une fonction booléenne sur F_2^m. Notre mot bruité sera en fait représenté par une fonction booléenne. Il s'agit ensuite de trouver une ou plusieurs approximations de cette fonction par une ou des fonctions booléennes de degré total r donné. On verra qu'il est posssible de répondre à ce problème avec une complexité: O(polylog(2^m=n)). Ces algorithmes font du décodage par liste. Il s'agit d'algorithmes adaptatifs qui sont fortement inspirés de l'algorithme de Golreich et Levin. Nous nous intéresserons à deux contextes particuliers : le canal binaire symétrique et le canal adversaire. On étudiera en petites ou moyennes longueurs les performances de ces algorithmes. Des résultats expérimentaux accompagneront cet exposé.