Códigos de Reed–Muller

Abstract

Este trabajo se estructura en cinco capítulos en los que se desarrolla el es- tudio de los códigos Reed-Muller. Se comienza presentando los preliminares necesarios para el desarrollo del trabajo. Se introducen conceptos y resulta- dos sobre los cuerpos finitos y los códigos lineales, que constituyen la base sobre la cual se construyen y analizan los códigos Reed-Muller. En segundo lugar, se estudian los códigos de evaluación, se describe la construcción de los códigos a partir de las evaluaciones de los polinomios, y se presentan dos de sus parámetros fundamentales: la longitud y la dimensión. A continua- ción, calculamos la distancia mínima, y para ello recurriremos a los ideales monomiales y a la cota de footprint. Posteriormente, se analiza un algoritmo de descodificación, y se estudia su funcionamiento y su justificación teórica. Por último, se introduce el concepto de códigos descodificables localmente y se ve como los Reed-Muller cumplen esta propiedad.

This work is structured into five chapters, in which the study of Reed–Muller codes is developed. It begins by presenting the necessary preliminaries for the development of the work. Concepts and results related to finite fields and linear codes are introduced, as they form the foundation upon which Reed–Muller codes are constructed and analyzed. Secondly, evaluation codes are studied: the construction of the codes from polynomial evaluations is described, and two of their fundamental parameters length and dimension are presented. Next, the minimum distance is computed, for which monomial ideals and the footprint bound are employed. Subsequently, a decoding algorithm is analyzed, including its operation and theoretical justification. Finally, the concept of locally decodable codes is introduced, and it is shown how Reed–Muller codes satisfy this property.