Código de Reed-Muller

Los códigos Reed-Muller son códigos correctores 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 . Por ejemplo, se ha demostrado que alcanzan asintóticamente la capacidad de Shannon en canales simétricos sin memoria. ^{[ 4 ]}^{[ 5 ]}^{[ 6 ]}^{[ 7 ]}

Los códigos de Reed-Muller generalizan los códigos de Reed-Solomon y el código de Walsh-Hadamard . Son códigos de bloques lineales que se pueden comprobar localmente , decodificar localmente y decodificar mediante listas . Estas propiedades los hacen particularmente útiles en el diseño de pruebas verificables probabilísticamente .

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

Los códigos Reed-Muller reciben su nombre de David E. Muller , quien descubrió los códigos en 1954, ^{[ 8 ]} e Irving S. Reed , quien propuso el primer algoritmo de decodificación eficiente. ^{[ 9 ]}

Descripción mediante polinomios de bajo grado

Los códigos de Reed-Muller pueden describirse de varias maneras diferentes (pero en última instancia equivalentes). La descripción basada en polinomios de bajo grado es bastante elegante y particularmente adecuada para su aplicación como códigos localmente verificables y códigos localmente decodificables . ^{[ 10 ]}

Codificador

Un código de bloques puede tener una o más funciones de codificación. ${\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ esos mensajes del mapa ${\textstyle x\in \{0,1\}^{k}}$ a palabras clave ${\textstyle C(x)\in \{0,1\}^{n}}$ . El código Reed - Muller RM( r , m ) tiene longitud de mensaje $\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}$ y longitud del bloque $\textstyle n=2^{m}$ 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 como máximo r . Todo polinomio multilineal sobre el cuerpo finito con dos elementos se puede escribir de la siguiente manera: $p_{c}(Z_{1},\dots ,Z_{m})=\sum _{\underset {|S|\leq r}{S\subseteq \{1,\dots ,m\}}}c_{S}\cdot \prod _{i\in S}Z_{i}\,.$ El ${\textstyle Z_{1},\dots ,Z_{m}}$ son las variables del polinomio y los valores ${\textstyle c_{S}\in \{0,1\}}$ son los coeficientes del polinomio. Nótese que hay exactamente ${\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$ coeficientes. Teniendo esto en cuenta, un mensaje de entrada consta de: ${\textstyle k}$ valores ${\textstyle x\in \{0,1\}^{k}}$ que se utilizan como estos coeficientes. De esta manera, cada mensaje ${\textstyle x}$ da lugar a un polinomio único ${\textstyle p_{x}}$ en m variables. Para construir la palabra clave ${\textstyle C(x)}$ , el codificador evalúa el polinomio ${\textstyle p_{x}}$ en todos los puntos ${\textstyle Z=(Z_{1},\ldots ,Z_{m})\in \{0,1\}^{m}}$ donde el polinomio se toma con multiplicación y suma módulo 2 ${\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}$ . Es decir, la función de codificación se define mediante $C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.$

El hecho de que la palabra clave $C(x)$ basta para reconstruir de forma única $x$ Esto se deduce de la interpolación de Lagrange , que establece que los coeficientes de un polinomio están determinados de forma única cuando se proporcionan suficientes puntos de evaluación. Dado que $C(0)=0$ y $C(x+y)=C(x)+C(y){\bmod {2}}$ se mantiene para todos los mensajes $x,y\in \{0,1\}^{k}$ , la función $C$ es un mapa lineal . Por lo tanto, el código de Reed - Muller es un código lineal .

Ejemplo

Para el código RM( 2 , 4 ) , los parámetros son los siguientes:

${\textstyle {\begin{aligned}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4}{0}}=6+4+1=11\\n&=2^{m}=16\\\end{aligned}}}$

Dejar ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ sea la función de codificación que acabamos de definir. Para codificar la cadena x = 1 1010 010101 de longitud 11, el codificador primero construye el polinomio ${\textstyle p_{x}}$ en 4 variables: ${\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1+Z_{1}+Z_{3}+Z_{1}Z_{3}+Z_{2}Z_{3}+Z_{3}Z_{4}\end{aligned}}$ Luego evalúa este polinomio en los 16 puntos de evaluación (0101 significa $Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)$ : $p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=0,\;p_{x}(0011)=1,\;$

$p_{x}(0100)=1,\;p_{x}(0101)=1,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;$

$p_{x}(1000)=0,\;p_{x}(1001)=0,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;$

$p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=1,\;p_{x}(1111)=0\,.$ Como resultado, se cumple C(1 1010 010101) = 1101 1110 0001 0010.

Descifrador

Como ya se mencionó, la interpolación de Lagrange permite recuperar el mensaje de forma eficiente a partir de una palabra clave. Sin embargo, un decodificador debe funcionar incluso si la palabra clave se ha corrompido en algunas posiciones, es decir, cuando la palabra recibida difiere de cualquier palabra clave. En este caso, un procedimiento de decodificación local puede ser útil.

El algoritmo de Reed se basa en la siguiente propiedad: se parte de la palabra clave, que es una secuencia de puntos de evaluación de un polinomio desconocido. ${\textstyle p_{x}}$ de ${\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]}$ de grado como máximo ${\textstyle r}$ que deseas encontrar. La secuencia puede contener cualquier número de errores hasta ${\textstyle 2^{m-r-1}-1}$ incluido.

Si consideramos un monomio ${\textstyle \mu }$ del más alto grado ${\textstyle d}$ en ${\textstyle p_{x}}$ y sumar todos los puntos de evaluación del polinomio donde todas las variables en ${\textstyle \mu }$ tienen los valores 0 o 1, y todas las demás variables tienen el valor 0, se obtiene el valor del coeficiente (0 o 1) de ${\textstyle \mu }$ en ${\textstyle p_{x}}$ (Hay ${\textstyle 2^{d}}$ tales puntos). Esto se debe al hecho de que todos los divisores monomiales inferiores de ${\textstyle \mu }$ aparece un número par de veces en la suma, y solo ${\textstyle \mu }$ aparece una vez.

Para tener en cuenta la posibilidad de errores, también puede observar que puede fijar el valor de otras variables a cualquier valor. Entonces, en lugar de hacer la suma solo una vez para otras variables que no están en ${\textstyle \mu }$ con valor 0, lo haces ${\textstyle 2^{m-d}}$ veces para cada valor fijo de las demás variables. Si no hay error, todas esas sumas deberían ser iguales al valor del coeficiente buscado. El algoritmo consiste en tomar la mayoría de las respuestas como el valor buscado. Si la minoría es mayor que el número máximo de errores posibles, el paso de decodificación falla al saber que hay demasiados errores en el código de entrada.

Una vez calculado un coeficiente, si es 1, actualice el código para eliminar el monomio. ${\textstyle \mu }$ a partir del código de entrada y continuar con el siguiente monomio, en orden inverso de su grado.

Ejemplo

Consideremos el ejemplo anterior y comencemos desde el código. Con ${\textstyle r=2,m=4}$ Podemos corregir como máximo 1 error en el código. Consideremos el código de entrada como 1101 1110 0001 0110 (este es el código anterior con un error).

Conocemos el grado del polinomio ${\textstyle p_{x}}$ es como máximo ${\textstyle r=2}$ , comenzamos buscando un monomio de grado 2.

${\textstyle \mu =X_{3}X_{4}}$ ${\textstyle \mu =X_{3}X_{4}}$
- comenzamos buscando puntos de evaluación con ${\textstyle X_{1}=0,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}$ En el código esto es: 1101 1110 0001 0110. La primera suma es 1 (número impar de 1).
- buscamos puntos de evaluación con ${\textstyle X_{1}=0,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}$ . En el código esto es: 1101 1110 0001 0110. La segunda suma es 1.
- buscamos puntos de evaluación con ${\textstyle X_{1}=1,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}$ . En el código esto es: 1101 1110 0001 0110. La tercera suma es 1.
- buscamos puntos de evaluación con ${\textstyle X_{1}=1,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}$ . En el código esto es: 1101 1110 0001 0110 . La tercera suma es 0 (número par de 1).

Las cuatro sumas no coinciden (por lo que sabemos que hay un error), pero el informe de la minoría no es mayor que el número máximo de errores permitidos (1), por lo que tomamos la mayoría y el coeficiente de ${\textstyle \mu }$ es 1.

Nosotros eliminamos ${\textstyle \mu }$ del código antes de continuar : código : 1101 1110 0001 0110, valoración de ${\textstyle \mu }$ es 0001000100010001, el nuevo código es 1100 1111 0000 0111

${\textstyle \mu =X_{2}X_{4}}$ ${\textstyle \mu =X_{2}X_{4}}$
- 11 00 11 11 0000 0111. La suma es 0
- 11 00 11 11 0000 0111. La suma es 0
- 1100 1111 00 00 01 11. La suma es 1
- 1100 1111 00 00 01 11 . La suma es 0

Se ha detectado un error, el coeficiente es 0, no se realizan cambios en el código actual.

${\textstyle \mu =X_{1}X_{4}}$ ${\textstyle \mu =X_{1}X_{4}}$
- 11 00 1111 00 00 0111. La suma es 0
- 11 00 1111 00 00 0111. La suma es 0
- 1100 11 11 0000 01 11. La suma es 1
- 1100 11 11 0000 01 11 . La suma es 0

Se ha detectado un error, el coeficiente es 0, no se realizan cambios en el código actual.

${\textstyle \mu =X_{2}X_{3}}$ ${\textstyle \mu =X_{2}X_{3}}$
- 1 1 0 0 1 1 1 1 0000 0111. La suma es 1
- 1 1 0 0 1 1 1 1 0000 0111. La suma es 1
- 1100 1111 0 0 0 0 0 1 1 1. La suma es 1
- 1100 1111 0 0 0 0 0 1 1 1 . La suma es 0

Se detectó un error, el coeficiente es 1, valoración de ${\textstyle \mu }$ es 0000 0011 0000 0011, el código actual ahora es 1100 1100 0000 0100.

${\textstyle \mu =X_{1}X_{3}}$ ${\textstyle \mu =X_{1}X_{3}}$
- 1 1 0 0 1100 0 0 0 0 0100. La suma es 1
- 1 1 0 0 1100 0 0 0 0 0100. La suma es 1
- 1100 1 1 0 0 0000 0 1 0 0. La suma es 1
- 1100 1 1 0 0 0000 0 1 0 0 . La suma es 0

Se detectó un error, el coeficiente es 1, valoración de ${\textstyle \mu }$ es 0000 0000 0011 0011, el código actual ahora es 1100 1100 0011 0111.

${\textstyle \mu =X_{1}X_{2}}$ ${\textstyle \mu =X_{1}X_{2}}$
- 1 100 1 100 0 011 0 111. La suma es 0
- 1 1 00 1 1 00 0 0 11 0 1 11. La suma es 1
- 11 0 0 11 0 0 00 1 1 01 1 1. La suma es 0
- 110 0 110 0 001 1 011 1 . La suma es 0

Se ha detectado un error, el coeficiente es 0, no se modifica el código actual. Ahora que conocemos todos los coeficientes de grado 2 del polinomio, podemos empezar con los mononios de grado 1. Observa que para cada grado siguiente, hay el doble de sumas, y cada suma es la mitad.

${\textstyle \mu =X_{4}}$ ${\textstyle \mu =X_{4}}$
- 11 00 1100 0011 0111. La suma es 0
- 11 00 1100 0011 0111. La suma es 0
- 1100 11 00 0011 0111. La suma es 0
- 1100 11 00 0011 0111. La suma es 0
- 1100 1100 00 11 0111. La suma es 0
- 1100 1100 00 11 0111. La suma es 0
- 1100 1100 0011 01 11. La suma es 1
- 1100 1100 0011 01 11 . La suma es 0

Se ha detectado un error, el coeficiente es 0, no se realizan cambios en el código actual.

${\textstyle \mu =X_{3}}$ ${\textstyle \mu =X_{3}}$
- 1 1 0 0 1100 0011 0111. La suma es 1
- 1 1 0 0 1100 0011 0111. La suma es 1
- 1100 1 1 0 0 0011 0111. La suma es 1
- 1100 1 1 0 0 0011 0111. La suma es 1
- 1100 1100 0 0 1 1 0111. La suma es 1
- 1100 1100 0 0 1 1 0111. La suma es 1
- 1100 1100 0011 0 1 1 1. La suma es 1
- 1100 1100 0011 0 1 1 1 . La suma es 0

Se detectó un error, el coeficiente es 1, valoración de ${\textstyle \mu }$ es 0011 0011 0011 0011, el código actual ahora es 1111 1111 0000 0100.

Entonces encontraremos 0 para ${\textstyle \mu =X_{2}}$ , 1 para ${\textstyle \mu =X_{1}}$ y el código actual se convierte en 1111 1111 1111 1011.

Para el grado 0, tenemos 16 sumas de solo 1 bit. La minoría sigue siendo de tamaño 1, y encontramos ${\textstyle p_{x}=1+X_{1}+X_{3}+X_{1}X_{3}+X_{2}X_{3}+X_{3}X_{4}}$ y la palabra inicial correspondiente 1 1010 010101

Generalización a alfabetos más grandes mediante polinomios de bajo grado.

Utilizando polinomios de bajo grado sobre un campo finito. $\mathbb {F}$ de tamaño $q$ , es posible extender la definición de códigos Reed - Muller a alfabetos de tamaño $q$ . Dejar $m$ y $d$ sean enteros positivos, donde $m$ debe considerarse más grande que $d$ Para codificar un mensaje ${\textstyle x\in \mathbb {F} ^{k}}$ de ancho $k=\textstyle {\binom {m+d}{m}}$ , el mensaje se interpreta nuevamente como un $m$ polinomio multivariado $p_{x}$ de grado total como máximo $d$ y con coeficiente de $\mathbb {F}$ . De hecho, tal polinomio tiene $\textstyle {\binom {m+d}{m}}$ coeficientes. La codificación Reed-Muller de $x$ es la lista de todas las evaluaciones de $p_{x}(a)$ en general $a\in \mathbb {F} ^{m}$ Por lo tanto, la longitud del bloque es $n=q^{m}$ .

Descripción mediante una matriz generadora

Una matriz generadora para un código Reed - Muller RM( r , m ) de longitud N = 2m ^se puede construir de la siguiente manera. Escribamos el conjunto de todos los vectores binarios m- dimensionales como:

X=\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}.

Definimos en el espacio N -dimensional $\mathbb {F} _{2}^{N}$ los vectores indicadores

\mathbb {I} _{A}\in \mathbb {F} _{2}^{N}

en subconjuntos $A\subset X$ por:

\left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ if }}x_{i}\in A\\0&{\mbox{ otherwise}}\\\end{cases}}

junto con, también en $\mathbb {F} _{2}^{N}$ , la operación binaria

w\wedge z=(w_{1}\cdot z_{1},\ldots ,w_{N}\cdot z_{N}),

denominado producto exterior (que no debe confundirse con el producto exterior definido en álgebra exterior). Aquí, $w=(w_{1},w_{2},\ldots ,w_{N})$ y $z=(z_{1},z_{2},\ldots ,z_{N})$ son puntos en $\mathbb {F} _{2}^{N}$ ( vectores binarios N -dimensionales) y la operación $\cdot$ es la multiplicación habitual en el campo $\mathbb {F} _{2}$ .

$\mathbb {F} _{2}^{m}$ es un espacio vectorial m -dimensional sobre el campo $\mathbb {F} _{2}$ , por lo que es posible escribir

$(\mathbb {F} _{2})^{m}=\{(y_{m},\ldots ,y_{1})\mid y_{i}\in \mathbb {F} _{2}\}.$

Definimos en el espacio N -dimensional $\mathbb {F} _{2}^{N}$ los siguientes vectores con longitud $N:v_{0}=(1,1,\ldots ,1)$ y

v_{i}=\mathbb {I} _{H_{i}},

donde 1 ≤ i ≤ m y los H _i son hiperplanos en $(\mathbb {F} _{2})^{m}$ (con dimensión m − 1 ):

H_{i}=\{y\in (\mathbb {F} _{2})^{m}\mid y_{i}=0\}.

La matriz generadora

El código Reed - Muller RM( r , m ) de orden r y longitud N = 2m es el código generado por v0 y los productos de cuña de hasta r de los vi, 1 ≤ i ≤ m ₍ donde, por convención , ^un_producto de cuña de menos de un vector es la identidad para la operación). En otras palabras, podemos construir una matriz generadora para el código RM( r , m ) , utilizando vectores y sus permutaciones de productos de cuña hasta r a la vez. ${v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{2}}),\ldots (v_{i_{1}}\wedge v_{i_{2}}\ldots \wedge v_{i_{r}})}$ , como las filas de la matriz generadora, donde 1 ≤ i _k ≤ m .

Ejemplo 1

Sea m = 3. Entonces N = 8, y

X=\mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),(0,1,0)\ldots ,(1,1,1)\},

y

{\begin{aligned}v_{0}&=(1,1,1,1,1,1,1,1)\\[2pt]v_{1}&=(1,0,1,0,1,0,1,0)\\[2pt]v_{2}&=(1,1,0,0,1,1,0,0)\\[2pt]v_{3}&=(1,1,1,1,0,0,0,0).\end{aligned}}

El código RM(1,3) es generado por el conjunto

\{v_{0},v_{1},v_{2},v_{3}\},\,

o, más explícitamente, por las filas de la matriz:

{\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\end{pmatrix}}

Ejemplo 2

El código RM(2,3) se genera mediante el conjunto:

\{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}

o, más explícitamente, por las filas de la matriz:

{\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&0&1&0&0&0&0&0\\1&1&0&0&0&0&0&0\\\end{pmatrix}}

Propiedades

Se cumplen las siguientes propiedades:

El conjunto de todos los posibles productos de cuña de hasta m de los v _i forman una base para $\mathbb {F} _{2}^{N}$ .
El código RM ( r , m ) tiene rango
$\sum _{s=0}^{r}{m \choose s}.$
$RM (r, m) = RM (r, m - 1) | RM (r - 1, m - 1)$ donde '|' denota el producto barra de dos códigos.
$RM (r, m)$ tiene un peso de Hamming mínimo de 2 ^{m − r} .

La distribución completa de los pesos de las palabras clave es más compleja que la fórmula de distancia mínima. Tadao Kasami y Nobuki Tokura estudiaron la estructura de pesos de los códigos Reed-Muller, incluyendo palabras clave de bajo peso más allá del peso mínimo. ^{[ 11 ]}

Prueba

Hay
$\sum _{s=0}^{m}{m \choose s}=2^{m}=N$
tales vectores y $\mathbb {F} _{2}^{N}$ tienen dimensión N, por lo que es suficiente comprobar que los N vectores generan; equivalentemente, es suficiente comprobar que $\mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}$ .
Sea x un vector binario de longitud m , un elemento de X. Sea ( x ) _i el i- ^ésimo elemento de x . Definimos
$y_{i}={\begin{cases}v_{i}&{\text{ if }}(x)_{i}=0\\v_{0}+v_{i}&{\text{ if }}(x)_{i}=1\\\end{cases}}$
donde 1 ≤ i ≤ m .
Entonces $\mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}$
La expansión mediante la distributividad del producto cuña da como resultado $\mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)$ . Entonces, dado que los vectores $\{\mathbb {I} _{\{x\}}\mid x\in X\}$ durar $\mathbb {F} _{2}^{N}$ tenemos $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}$ .
Por 1 , todos esos productos de cuña deben ser linealmente independientes, por lo que el rango de RM( r, m ) debe ser simplemente el número de tales vectores.
Omitido.
Por inducción.
El código $RM(0, m)$ es el código de repetición de longitud $N =2 m$ y peso N = 2 ^{m − 0} = 2 ^{m − r} . Por 1 $\mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}$ y tiene un peso 1 = 2 ⁰ = 2 ^{m − r} .
El artículo producto barra (teoría de codificación) proporciona una prueba de que el peso del producto barra de dos códigos C ₁ , C ₂ viene dado por
$\min\{2w(C_{1}),w(C_{2})\}$
Si 0 < r < m y si
1. $RM(r, m - 1)$ tiene un peso $de 2 m - 1 - r$
2. $RM(r - 1, m - 1)$ tiene un peso $de 2 m - 1 - (r - 1) = 2 m - r$
entonces el producto en barra tiene peso
$\min\{2\times 2^{m-1-r},2^{m-r}\}=2^{m-r}.$

Decodificación de códigos RM

Los códigos RM( r , m ) se pueden decodificar mediante decodificación por lógica de mayoría . La idea básica de la decodificación por lógica de mayoría es construir varias sumas de verificación para cada elemento de la palabra código recibida. Dado que todas las sumas de verificación deben tener el mismo valor (es decir, el valor del peso del elemento de la palabra mensaje), podemos usar la decodificación por lógica de mayoría para descifrar el valor de dicho elemento. Una vez decodificado cada orden del polinomio, la palabra recibida se modifica eliminando las palabras código correspondientes ponderadas por las contribuciones del mensaje decodificado, hasta la etapa actual. Así, para un código RM de orden r , debemos decodificarlo iterativamente r+1 veces antes de llegar a la palabra código final recibida. Además, los valores de los bits del mensaje se calculan mediante este esquema; finalmente, podemos calcular la palabra código multiplicando la palabra mensaje (recién decodificada) por la matriz generadora.

Una señal de que la decodificación se realizó correctamente es obtener una palabra modificada compuesta únicamente por ceros al final de la decodificación de ( r + 1) etapas mediante la lógica de mayoría. Esta técnica fue propuesta por Irving S. Reed y resulta más general al aplicarse a otros códigos de geometría finita .

Descripción mediante una construcción recursiva

Existe un código Reed-Muller RM( r,m ) para cualquier número entero. $m\geq 0$ y $0\leq r\leq m$ . RM( m , m ) se define como el universo ( $2^{m},2^{m},1$ ) código. RM( − 1,m) se define como el código trivial ( $2^{m},0,\infty$ ). Los códigos RM restantes se pueden construir a partir de estos códigos elementales utilizando la construcción de duplicación de longitud.

\mathrm {RM} (r,m)=\{(\mathbf {u} ,\mathbf {u} +\mathbf {v} )\mid \mathbf {u} \in \mathrm {RM} (r,m-1),\mathbf {v} \in \mathrm {RM} (r-1,m-1)\}.

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 $k(r,m)=k(r,m-1)+k(r-1,m-1)$ y distancia mínima $d=2^{m-r}$ para $r\geq 0$ El código dual de RM( r,m ) es RM( m - r -1, m ). Esto demuestra que los códigos de repetición y SPC son duales, los códigos biorthogonales y de Hamming extendidos son duales y que los códigos con $k = n /2$ son autoduales.

Casos especiales de códigos Reed - Müller

Tabla de todos los códigos RM(r,m) para m≤5

Todos los códigos $RM(r, m)$ con $0\leq m\leq 5$ y el tamaño del alfabeto 2 se muestran aquí, anotados con la notación estándar de la teoría de codificación [n,k,d] para códigos de bloque . El código $RM(r, m)$ es un $\textstyle [2^{m},k,2^{m-r}]_{2}$ -código, es decir, es un código lineal sobre un alfabeto binario , tiene longitud de bloque $\textstyle 2^{m}$ , longitud (o dimensión) del mensaje $k$ y distancia mínima $\textstyle 2^{m-r}$ .

Propiedades de los códigos RM(r,m) para r≤1 o r≥m-2

$Los códigos RM(0, m)$ son códigos de repetición de longitud $N = 2 m$ , tasa ${R={\tfrac {1}{N}}}$ y distancia mínima $d_{\min }=N$ .
$Los códigos RM(1, m)$ son códigos de verificación de paridad de longitud $N = 2 m$ , tasa $R={\tfrac {m+1}{N}}$ y distancia mínima $d_{\min }={\tfrac {N}{2}}$ .
$Los códigos RM(m - 1, m)$ son códigos de verificación de paridad simple de longitud $N = 2 m$ , tasa $R={\tfrac {N-1}{N}}$ y distancia mínima $d_{\min }=2$ .
$Los códigos RM(m - 2, m)$ son la familia de códigos de Hamming extendidos de longitud $N = 2 m$ con distancia mínima $d_{\min }=4$ . ^{[ 12 ]}

Referencias

↑ Massey, James L. (1992), "Comunicaciones y codificación en el espacio profundo: una combinación perfecta", Métodos avanzados para comunicaciones satelitales y en el espacio profundo , Notas de clase en ciencias del control e información, vol. 182, Springer-Verlag, pp. 1–17 , CiteSeerX 10.1.1.36.4265 , doi : 10.1007/bfb0036046 , ISBN 978-3540558514PDF
↑ "Informe final de la reunión n.º 87 de 3GPP RAN1" . 3GPP . Consultado el 31 de agosto de 2017 .
↑ Arikan, Erdal (2009). "Polarización de canal: un método para construir códigos que alcanzan capacidad para canales sin memoria de entrada binaria simétrica - IEEE Journals & Magazine". IEEE Transactions on Information Theory . 55 (7): 3051– 3073. arXiv : 0807.3917 . doi : 10.1109/TIT.2009.2021379 . hdl : 11693/11695 . S2CID 889822 .
↑ Abbe, Emmanuel; Shpilka, Amir; Wigderson, Avi (14 de junio de 2015). Códigos Reed-Muller para borrados y errores aleatorios . ACM. págs. 297–306 . doi : 10.1145/2746539.2746575 . ISBN 978-1-4503-3536-2. Consultado el 12 de noviembre de 2025 .
↑ Kudekar, Shrinivas; Kumar, Santhosh; Mondelli, Marco; Pfister, Henry D.; Sasoglu, Eren; Urbanke, Ridiger L. (2017). "Los códigos Reed-Muller alcanzan capacidad en canales de borrado" . IEEE Transactions on Information Theory . 63 (7): 4298– 4316. doi : 10.1109/TIT.2017.2673829 . ISSN 0018-9448 . Recuperado el 12 de noviembre de 2025 .
↑ Reeves, Galen; Pfister, Henry D. (2024). "Los códigos Reed-Muller en canales BMS logran una probabilidad de error de bit nula para todas las tasas por debajo de la capacidad" . IEEE Transactions on Information Theory . 70 (2): 920– 949. doi : 10.1109/TIT.2023.3286452 . ISSN 0018-9448 . Recuperado el 12 de noviembre de 2025 .
↑ Abbe, Emmanuel; Sandon, Colin (6 de noviembre de 2023). Una prueba de que los códigos Reed-Muller alcanzan la capacidad de Shannon en canales simétricos . IEEE. págs. 177–193 . doi : 10.1109/FOCS57990.2023.00020 . ISBN 979-8-3503-1894-4. Consultado el 12 de noviembre de 2025 .
↑ Muller, David E. (1954). "Aplicación del álgebra booleana al diseño de circuitos de conmutación y a la detección de errores". Transactions of the IRE Professional Group on Electronic Computers . 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". Transactions of the IRE Professional Group on Information Theory . 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 clase del tutorial de DIMACS) , Sección 5.2.1.
↑ Kasami, Tadao; Tokura, Nobuki (noviembre de 1970). "Sobre la estructura de pesos de los códigos Reed-Muller". IEEE Transactions on Information Theory . 16 (6): 752– 759. doi : 10.1109/TIT.1970.1054545 .
↑ Trellis y Turbo Coding, C. Schlegel y L. Perez, Wiley Interscience, 2004, pág. 149.

Lecturas adicionales

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 . Vol. 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, sección 6.4 de las notas de clase
Implementación en Matlab de códigos RM bajo licencia GPL
Código fuente GPL Implementación en Matlab de códigos RM
Weiss, E. (septiembre de 1962). "Códigos Reed-Muller generalizados". Information and Control . 5 (3): 213– 222. doi : 10.1016/s0019-9958(62)90555-7 . ISSN 0019-9958 .

[1] Massey, James L. (1992), "Comunicaciones y codificación en el espacio profundo: una combinación perfecta", Métodos avanzados para comunicaciones satelitales y en el espacio profundo , Notas de clase en ciencias del control e información, vol. 182, Springer-Verlag, pp. 1–17 , CiteSeerX 10.1.1.36.4265 , doi : 10.1007/bfb0036046 , ISBN 978-3540558514PDF

[2] "Informe final de la reunión n.º 87 de 3GPP RAN1" . 3GPP . Consultado el 31 de agosto de 2017 .

[3] Arikan, Erdal (2009). "Polarización de canal: un método para construir códigos que alcanzan capacidad para canales sin memoria de entrada binaria simétrica - IEEE Journals & Magazine". IEEE Transactions on Information Theory . 55 (7): 3051– 3073. arXiv : 0807.3917 . doi : 10.1109/TIT.2009.2021379 . hdl : 11693/11695 . S2CID 889822 .

[z571-4] Abbe, Emmanuel; Shpilka, Amir; Wigderson, Avi (14 de junio de 2015). Códigos Reed-Muller para borrados y errores aleatorios . ACM. págs. 297–306 . doi : 10.1145/2746539.2746575 . ISBN 978-1-4503-3536-2. Consultado el 12 de noviembre de 2025 .

[k411-5] Kudekar, Shrinivas; Kumar, Santhosh; Mondelli, Marco; Pfister, Henry D.; Sasoglu, Eren; Urbanke, Ridiger L. (2017). "Los códigos Reed-Muller alcanzan capacidad en canales de borrado" . IEEE Transactions on Information Theory . 63 (7): 4298– 4316. doi : 10.1109/TIT.2017.2673829 . ISSN 0018-9448 . Recuperado el 12 de noviembre de 2025 .

[c245-6] Reeves, Galen; Pfister, Henry D. (2024). "Los códigos Reed-Muller en canales BMS logran una probabilidad de error de bit nula para todas las tasas por debajo de la capacidad" . IEEE Transactions on Information Theory . 70 (2): 920– 949. doi : 10.1109/TIT.2023.3286452 . ISSN 0018-9448 . Recuperado el 12 de noviembre de 2025 .

[j572-7] Abbe, Emmanuel; Sandon, Colin (6 de noviembre de 2023). Una prueba de que los códigos Reed-Muller alcanzan la capacidad de Shannon en canales simétricos . IEEE. págs. 177–193 . doi : 10.1109/FOCS57990.2023.00020 . ISBN 979-8-3503-1894-4. Consultado el 12 de noviembre de 2025 .

[8] Muller, David E. (1954). "Aplicación del álgebra booleana al diseño de circuitos de conmutación y a la detección de errores". Transactions of the IRE Professional Group on Electronic Computers . EC-3 (3): 6– 12. doi : 10.1109/irepgelc.1954.6499441 . ISSN 2168-1740 .

[9] Reed, Irving S. (1954). "Una clase de códigos de corrección de errores múltiples y el esquema de decodificación". Transactions of the IRE Professional Group on Information Theory . 4 (4): 38– 49. doi : 10.1109/tit.1954.1057465 . hdl : 10338.dmlcz/143797 . ISSN 2168-2690 .

[10] Prahladh Harsha et al., Límites de los algoritmos de aproximación: PCP y juegos únicos (Notas de clase del tutorial de DIMACS) , Sección 5.2.1.

[11] Kasami, Tadao; Tokura, Nobuki (noviembre de 1970). "Sobre la estructura de pesos de los códigos Reed-Muller". IEEE Transactions on Information Theory . 16 (6): 752– 759. doi : 10.1109/TIT.1970.1054545 .

[12] Trellis y Turbo Coding, C. Schlegel y L. Perez, Wiley Interscience, 2004, pág. 149.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]