Código Reed-Muller

Los códigos Reed-Muller son códigos de corrección de errores que se utilizan en aplicaciones de comunicaciones inalámbricas, particularmente en comunicaciones en el espacio profundo. ^[1] Además, el estándar 5G propuesto ^{[2] se} basa en los códigos polares estrechamente relacionados ^[3] para la corrección de errores en el canal de control. Debido a sus favorables propiedades teóricas y matemáticas, los códigos Reed-Muller también se han estudiado ampliamente en la informática teórica .

Los códigos Reed-Muller generalizan los códigos Reed-Solomon y el código Walsh-Hadamard . Códigos de Reed-Muller son códigos de bloque lineales que son localmente comprobable , localmente descifrable , y la lista descifrable . Estas propiedades los hacen particularmente útiles en el diseño de pruebas comprobables probabilísticamente .

Los códigos tradicionales de Reed-Muller son códigos binarios, lo que significa que los mensajes y las palabras en clave son cadenas binarias. Cuando r y m son números enteros con 0 ≤ r ≤ m , el código Reed-Muller con los parámetros r y m se denota como RM ( r , m ). Cuando se le pide que codifique un mensaje que consta de k bits, donde se mantiene, el código RM ( r , m ) produce una palabra de código que consta de 2 ^m bits. ${\ Displaystyle \ textstyle k = \ sum _ {i = 0} ^ {r} {\ binom {m} {i}}}$

Los códigos Reed-Muller llevan el nombre de David E. Muller , quien descubrió los códigos en 1954, ^[4] e Irving S. Reed , quien propuso el primer algoritmo de decodificación eficiente. ^[5]

Los códigos Reed-Muller se pueden describir de varias formas diferentes (pero en última instancia equivalentes). La descripción que se basa en polinomios de bajo grado es bastante elegante y particularmente adecuada para su aplicación como códigos comprobables localmente y códigos decodificables localmente . ^[6]

Un código de bloque puede tener una o más funciones de codificación que mapean mensajes a palabras de código . El código de Reed-Muller RM ( r , m ) tiene una longitud de mensaje y una longitud de bloque . Una forma de definir una codificación para este código se basa en la evaluación de polinomios multilineales con m variables y grado total r . Cada polinomio multilineal sobre el campo finito con dos elementos se puede escribir de la siguiente manera: ${\ estilo de texto C: \ {0,1 \} ^ {k} \ a \ {0,1 \} ^ {n}}$ ${\ textstyle x \ in \ {0,1 \} ^ {k}}$ ${\ estilo de texto C (x) \ en \ {0,1 \} ^ {n}}$ ${\ Displaystyle \ textstyle k = \ sum _ {i = 0} ^ {r} {\ binom {m} {i}}}$ ${\ Displaystyle \ textstyle n = 2 ^ {m}}$