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 .
Código Reed-Muller RM (r, m) | |
---|---|
Lleva el nombre de | Irving S. Reed y David E. Muller |
Clasificación | |
Tipo | Código de bloque lineal |
Longitud del bloque | |
Longitud del mensaje | |
Velocidad | |
Distancia | |
Tamaño del alfabeto | |
Notación | -código |
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 de código 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, dondese sostiene, el código RM ( r , m ) produce una palabra de código que consta de 2 m bits.
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]
Descripción usando polinomios de bajo grado
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]
Codificador
Un código de bloque puede tener una o más funciones de codificación. que mapean mensajes a palabras en clave . El código de Reed-Muller RM ( r , m ) tiene una longitud de mensaje y longitud del 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:
El hecho de que la palabra clave basta para reconstruir de forma única se deduce de la interpolación de Lagrange , que establece que los coeficientes de un polinomio se determinan de forma única cuando se dan suficientes puntos de evaluación. Desde y se mantiene para todos los mensajes , la función es un mapa lineal . Por tanto, el código Reed-Muller es un código lineal .
Ejemplo
Para el código RM ( 2 , 4 ) , los parámetros son los siguientes:
Dejar ser la función de codificación que se acaba de definir. Para codificar la cadena x = 1 1010 010101 de longitud 11, el codificador primero construye el polinomio en 4 variables:
Descifrador
Como ya se mencionó, la interpolación de Lagrange se puede utilizar para recuperar de manera eficiente el mensaje de una palabra de código. Sin embargo, un decodificador debe funcionar incluso si la palabra de código se ha dañado en algunas posiciones, es decir, cuando la palabra recibida es diferente de cualquier palabra de código. En este caso, un procedimiento de decodificación local puede ayudar.
Generalización a alfabetos más grandes mediante polinomios de bajo grado
Usar polinomios de bajo grado sobre un campo finito de tamaño , es posible ampliar la definición de códigos Reed-Muller a alfabetos de tamaño . Dejar y ser enteros positivos, donde debe considerarse más grande que . Para codificar un mensaje de ancho , el mensaje se vuelve a interpretar como un -variar polinomio de grado total como máximo y con coeficiente de . De hecho, tal polinomio tienecoeficientes. La codificación Reed-Muller de es la lista de todas las evaluaciones de general . Por tanto, la longitud del bloque es.
Descripción usando una matriz generadora
Se puede construir una matriz generadora para un código Reed-Muller RM ( r , m ) de longitud N = 2 m de la siguiente manera. Escribamos el conjunto de todos los vectores binarios m -dimensionales como:
Definimos en el espacio N -dimensionallos vectores indicadores
en subconjuntos por:
junto con, también en , la operación binaria
referido como el producto de la cuña (que no debe confundirse con el producto de la cuña definido en el álgebra exterior). Aquí, y son puntos en ( Vectores binarios N -dimensionales), y la operación es la multiplicación habitual en el campo .
es un espacio vectorial m -dimensional sobre el campo, entonces es posible escribir
Definimos en el espacio N -dimensional los siguientes vectores con longitud y
donde 1 ≤ i ≤ my los H i son hiperplanos en(con dimensión m - 1 ):
La matriz generadora
El código Reed-Muller RM ( r , m ) de orden r y longitud N = 2 m es el código generado por v 0 y los productos de cuña de hasta r de v i , 1 ≤ i ≤ m (donde por convención a El producto de cuña de menos de un vector es la identidad de la operación). En otras palabras, podemos construir una matriz generadora para el código RM ( r , m ) , usando vectores y sus permutaciones de productos de cuña hasta r a la vez., como las filas de la matriz del generador, donde 1 ≤ i k ≤ m .
Ejemplo 1
Sea m = 3. Entonces N = 8, y
y
El código RM (1,3) es generado por el conjunto
o más explícitamente por las filas de la matriz:
Ejemplo 2
El código RM (2,3) lo genera el conjunto:
o más explícitamente por las filas de la matriz:
Propiedades
Se mantienen las siguientes propiedades:
- El conjunto de todos los productos de cuña posibles de hasta m del v i forma una base para.
- El código RM ( r , m ) tiene rango
- RM ( r , m ) = RM ( r , m - 1) | RM ( r - 1, m - 1) donde '|' denota el producto de barras de dos códigos.
- RM ( r , m ) tiene un peso Hamming mínimo de 2 m - r .
Prueba
- Existen
tales vectores y tienen dimensión N, por lo que es suficiente comprobar que los N vectores abarcan; de manera equivalente, es suficiente comprobar que.
Deje x ser un vector binario de longitud m , un elemento de X . Sea ( x ) i el i- ésimo elemento de x . Definir
donde 1 ≤ i ≤ m .
Luego
La expansión a través de la distributividad del producto de la cuña da . Entonces, dado que los vectores lapso tenemos . - Por 1 , todos estos productos de cuña deben ser linealmente independientes, por lo que el rango de RM ( r, m ) debe ser simplemente el número de dichos vectores.
- Omitido.
- Por inducción.
- El código RM (0, m ) es el código de repetición de longitud N = 2 my peso N = 2 m −0 = 2 m - r . Por 1y tiene un peso 1 = 2 0 = 2 m - r .
- Si 0 < r < my si
- RM ( r , m - 1) tiene un peso de 2 m −1− r
- RM ( r - 1, m - 1) tiene un peso 2 m −1− ( r −1) = 2 m - r
- entonces el producto de barra tiene peso
Decodificación de códigos RM
Los códigos RM ( r , m ) se pueden decodificar utilizando decodificación lógica mayoritaria . La idea básica de la decodificación lógica mayoritaria es construir varias sumas de verificación para cada elemento de palabra de código recibido. Dado que cada una de las diferentes sumas de verificación deben tener el mismo valor (es decir, el valor del peso del elemento de la palabra del mensaje), podemos usar una decodificación lógica mayoritaria para descifrar el valor del elemento de la palabra del mensaje. Una vez que se decodifica cada orden del polinomio, la palabra recibida se modifica en consecuencia eliminando las palabras de código correspondientes ponderadas por las contribuciones del mensaje decodificado, hasta la etapa actual. Entonces, para un código RM de orden r , tenemos que decodificar iterativamente r + 1, veces antes de llegar a la palabra de código final recibida. Además, los valores de los bits del mensaje se calculan mediante este esquema; finalmente podemos calcular la palabra de código multiplicando la palabra del mensaje (recién decodificada) con la matriz generadora.
Una pista si la decodificación tuvo éxito, es tener una palabra recibida modificada todo cero, al final de la decodificación de la etapa ( r + 1) a través de la decodificación lógica mayoritaria. Esta técnica fue propuesta por Irving S. Reed, y es más general cuando se aplica a otros códigos de geometría finita.
Descripción usando una construcción recursiva
Existe un código Reed-Muller RM ( r, m ) para cualquier número entero y . RM ( m , m ) se define como el universo () código. RM (−1, m) se define como el código trivial (). Los códigos RM restantes se pueden construir a partir de estos códigos elementales utilizando la construcción de duplicación de longitud
A partir de esta construcción, RM ( r, m ) es un código de bloque lineal binario ( n , k , d ) con longitud n = 2 m , dimensión y distancia mínima por . El código dual de RM ( r, m ) es RM ( m - r -1, m ). Esto muestra que los códigos de repetición y SPC son duales, los códigos de Hamming biortogonales y extendidos son duales y que los códigos con k = n / 2 son auto-duales.
Casos especiales de códigos Reed-Muller
Tabla de todos los códigos RM (r, m) para m≤5
Todos los códigos RM ( r , m ) cony el tamaño del alfabeto 2 se muestran aquí, anotados con la notación de teoría de codificación estándar [n, k, d] para códigos de bloque . El código RM ( r , m ) es un-code, es decir, es un código lineal sobre un alfabeto binario , tiene una longitud de bloque , longitud (o dimensión) del mensaje k , y distancia mínima .
RM ( m, m ) ( 2 m , 2 m , 1) | códigos del universo | ||||||
RM (5,5) (32,32,1) | |||||||
RM (4,4) (16,16,1) | RM ( m - 1, m ) (2 m , 2 m −1, 2) | Códigos SPC | |||||
RM (3,3) (8,8,1) | RM (4,5) (32,31,2) | ||||||
RM (2,2) (4,4,1) | RM (3,4) (16,15,2) | RM ( m - 2, m ) (2 m , 2 m - m −1, 4) | ext. Códigos de Hamming | ||||
RM (1,1) (2,2,1) | RM (2,3) (8,7,2) | RM (3,5) (32,26,4) | |||||
RM (0,0) (1,1,1) | RM (1,2) (4,3,2) | RM (2,4) (16,11,4) | |||||
RM (0,1) (2,1,2) | RM (1,3) (8,4,4) | RM (2,5) (32,16,8) | códigos auto-duales | ||||
RM (−1,0) (1,0,) | RM (0,2) (4,1,4) | RM (1,4) (16,5,8) | |||||
RM (−1,1) (2,0,) | RM (0,3) (8,1,8) | RM (1,5) (32,6,16) | |||||
RM (−1,2) (4,0,) | RM (0,4) (16,1,16) | RM (1, m ) (2 m , m +1, 2 m −1 ) | Perforados códigos de Hadamard | ||||
RM (−1,3) (8,0,) | RM (0,5) (32,1,32) | ||||||
RM (−1,4) (16,0,) | RM (0, m ) (2 m , 1, 2 m ) | códigos de repetición | |||||
RM (−1,5) (32,0,) | |||||||
RM (−1, m ) (2 m , 0, ∞) | códigos triviales |
Propiedades de los códigos RM (r, m) para r≤1 o r≥m-1
- Los códigos RM (0, m ) son códigos de repetición de longitud N = 2 m , tasa y distancia mínima .
- Los códigos RM (1, m ) son códigos de verificación de paridad de longitud N = 2 m , tasa y distancia mínima .
- Los códigos RM ( m - 1, m ) son códigos de verificación de paridad simple de longitud N = 2 m , tasa y distancia mínima .
- Los códigos RM ( m - 2, m ) son la familia de códigos Hamming extendidos de longitud N = 2 m con distancia mínima. [7]
Referencias
- ^ Massey, James L. (1992), "Codificación y comunicaciones en el espacio profundo: un matrimonio hecho en el cielo", Métodos avanzados para comunicaciones por satélite y en el espacio profundo , Notas de la conferencia en Ciencias de la información y el control, 182 , Springer-Verlag, págs. 1–17, CiteSeerX 10.1.1.36.4265 , doi : 10.1007 / bfb0036046 , ISBN 978-3540558514pdf
- ^ "Informe final de la reunión # 87 del 3GPP RAN1" . 3GPP . Consultado el 31 de agosto de 2017 .
- ^ Arikan, Erdal (2009). "Polarización de canal: un método para construir códigos de logro de capacidad para canales sin memoria de entrada binaria simétricos - IEEE Journals & Magazine". Transacciones IEEE sobre teoría de la información . 55 (7): 3051-3073. arXiv : 0807.3917 . doi : 10.1109 / TIT.2009.2021379 . hdl : 11693/11695 .
- ^ Muller, David E. (1954). "Aplicación del álgebra de Boole al diseño de circuitos de conmutación y detección de errores". Transacciones del Grupo Profesional IRE sobre Computadoras Electrónicas . EC-3 (3): 6–12. doi : 10.1109 / irepgelc.1954.6499441 . ISSN 2168-1740 .
- ^ Reed, Irving S. (1954). "Una clase de códigos de corrección de errores múltiples y el esquema de decodificación". Transacciones del Grupo Profesional IRE sobre Teoría de la Información . 4 (4): 38–49. doi : 10.1109 / tit.1954.1057465 . hdl : 10338.dmlcz / 143797 . ISSN 2168-2690 .
- ^ Prahladh Harsha et al., Límites de los algoritmos de aproximación: PCP y juegos únicos (Notas de la clase tutorial DIMACS) , Sección 5.2.1.
- ^ Codificación Trellis y Turbo, C. Schlegel y L. Perez, Wiley Interscience, 2004, p149.
Otras lecturas
- Shu Lin; Daniel Costello (2005). Codificación de control de errores (2 ed.). Pearson. ISBN 978-0-13-017973-9. Capítulo 4.
- JH van Lint (1992). Introducción a la teoría de la codificación . GTM . 86 (2 ed.). Springer-Verlag . ISBN 978-3-540-54894-2. Capítulo 4.5.
enlaces externos
- MIT OpenCourseWare , 6.451 Principios de la comunicación digital II, Notas de la clase sección 6.4
- Implementación de GPL Matlab de códigos RM
- Fuente GPL Matlab-implementación de códigos RM
- Weiss, E. (septiembre de 1962). "Códigos Reed-Muller generalizados" . Información y control . 5 (3): 213-222. doi : 10.1016 / s0019-9958 (62) 90555-7 . ISSN 0019-9958 .