Código Reed-Muller

Códigos de corrección de errores utilizados en la comunicación inalámbrica

Los códigos Reed-Muller son códigos de corrección de errores que se utilizan en aplicaciones de comunicaciones inalámbricas, en particular en comunicaciones en el espacio profundo. ^[1] Además, el estándar 5G propuesto ^{[2] se basa en los} códigos polares ^[3], estrechamente relacionados , 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 . Los códigos Reed-Muller son códigos de bloques lineales que se pueden probar localmente , decodificar localmente y decodificar en listas . Estas propiedades los hacen particularmente útiles en el diseño de pruebas probabilísticamente comprobables .

Los códigos tradicionales de Reed-Muller son códigos binarios, lo que significa que los mensajes y las palabras clave son cadenas binarias. Cuando r y m son números enteros con 0 ≤ r ≤ m , el código de Reed-Muller con 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 cumple, el código RM( r ,  m ) produce una palabra clave que consta de 2 ^m bits. ${\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$

Los códigos Reed-Muller reciben su 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 utilizando polinomios de bajo grado

Los códigos Reed-Muller se pueden describir de varias maneras 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 asignan mensajes a palabras de código . El código Reed-Muller RM( r , m ) tiene longitud de mensaje y 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 como máximo r . Cada polinomio multilineal sobre el cuerpo finito con dos elementos se puede escribir de la siguiente manera: Las son las variables del polinomio y los valores son los coeficientes del polinomio. Nótese que hay exactamente coeficientes. Con esto en mente, un mensaje de entrada consta de valores que se utilizan como estos coeficientes. De esta manera, cada mensaje da lugar a un polinomio único en m variables. Para construir la palabra de código , el codificador evalúa el polinomio en todos los puntos , donde el polinomio se toma con multiplicación y adición módulo 2. Es decir, la función de codificación se define mediante ${\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$ ${\textstyle x\in \{0,1\}^{k}}$ ${\textstyle C(x)\in \{0,1\}^{n}}$ ${\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$ ${\displaystyle \textstyle n=2^{m}}$ $${\displaystyle 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}\,.}$$ ${\textstyle Z_{1},\dots ,Z_{m}}$ ${\textstyle c_{S}\in \{0,1\}}$ ${\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}$ ${\textstyle k}$ ${\textstyle x\in \{0,1\}^{k}}$ ${\textstyle x}$ ${\textstyle p_{x}}$ ${\textstyle C(x)}$ ${\textstyle p_{x}}$ ${\textstyle Z=(Z_{1},\ldots ,Z_{n})\in \{0,1\}^{m}}$ ${\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}$ $${\displaystyle C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.}$$

El hecho de que la palabra clave sea suficiente para reconstruir de forma única se desprende 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. Dado que y se cumple para todos los mensajes , la función es una función lineal . Por lo tanto, el código de Reed-Muller es un código lineal . ${\displaystyle C(x)}$ ${\displaystyle x}$ ${\displaystyle C(0)=0}$ ${\displaystyle C(x+y)=C(x)+C(y){\bmod {2}}}$ ${\displaystyle x,y\in \{0,1\}^{k}}$ ${\displaystyle C}$

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}}}$

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 en 4 variables: Luego evalúa este polinomio en los 16 puntos de evaluación (0101 significa : ${\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}$ ${\textstyle p_{x}}$ $${\displaystyle {\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}}}$$ ${\displaystyle Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)}$ $${\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=0,\;p_{x}(0011)=1,\;}$$

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

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

$${\displaystyle 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 ha mencionado, la interpolación de Lagrange se puede utilizar para recuperar de forma eficiente el mensaje de una palabra clave. Sin embargo, un decodificador debe funcionar incluso si la palabra clave se ha dañado en algunas posiciones, es decir, cuando la palabra recibida es diferente de cualquier palabra clave. En este caso, un procedimiento de decodificación local puede resultar de ayuda.

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

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

Para tener en cuenta la posibilidad de errores, también se puede observar que se puede fijar el valor de otras variables a cualquier valor. Así, en lugar de hacer la suma una sola vez para otras variables que no tengan el valor 0, se hace varias veces para cada valor fijo de las otras variables. Si no hay ningún error, todas esas sumas deben ser iguales al valor del coeficiente buscado. El algoritmo consiste aquí 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 sabiendo que hay demasiados errores en el código de entrada. ${\textstyle \mu }$ ${\textstyle 2^{m-d}}$

Una vez que se calcula un coeficiente, si es 1, actualice el código para eliminar el monomio del código de entrada y continúe con el siguiente monomio, en orden inverso a su grado. ${\textstyle \mu }$

Ejemplo

Consideremos el ejemplo anterior y comencemos por el código. Con esto 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). ${\textstyle r=2,m=4}$

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

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

Las cuatro sumas no concuerdan (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 permitido (1), por lo que tomamos la mayoría y el coeficiente de es 1. ${\textstyle \mu }$

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

• ${\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 detectó un error, el coeficiente es 0, no hay cambios en el código actual.

• ${\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 detectó un error, el coeficiente es 0, no hay cambios en el código actual.

• ${\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, la valoración es 0000 0011 0000 0011, el código actual ahora es 1100 1100 0000 0100. ${\textstyle \mu }$

• ${\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, la valoración es 0000 0000 0011 0011, el código actual ahora es 1100 1100 0011 0111. ${\textstyle \mu }$

• ${\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 detectó un error, el coeficiente es 0, no hay cambios en el código actual. Ahora conocemos todos los coeficientes de grado 2 para el polinomio, podemos comenzar con mononios de grado 1. Observe que para cada grado siguiente, hay el doble de sumas y cada suma es la mitad más pequeña.

• ${\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 detectó un error, el coeficiente es 0, no hay cambios en el código actual.

• ${\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, la valoración de es 0011 0011 0011 0011, el código actual ahora es 1111 1111 0000 0100. ${\textstyle \mu }$

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

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

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

Utilizando polinomios de bajo grado sobre un campo finito de tamaño , es posible extender la definición de códigos Reed-Muller a alfabetos de tamaño . Sean y enteros positivos, donde se deben considerar mayores que . Para codificar un mensaje de ancho , el mensaje se interpreta nuevamente como un polinomio de -variante de grado total como máximo y con coeficiente de . Un polinomio de este tipo tiene coeficientes. La codificación Reed-Muller de es la lista de todas las evaluaciones de sobre todo . Por lo tanto, la longitud del bloque es . ${\displaystyle \mathbb {F} }$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle m}$ ${\displaystyle d}$ ${\displaystyle m}$ ${\displaystyle d}$ ${\textstyle x\in \mathbb {F} ^{k}}$ ${\displaystyle k=\textstyle {\binom {m+d}{m}}}$ ${\displaystyle m}$ ${\displaystyle p_{x}}$ ${\displaystyle d}$ ${\displaystyle \mathbb {F} }$ ${\displaystyle \textstyle {\binom {m+d}{m}}}$ ${\displaystyle x}$ ${\displaystyle p_{x}(a)}$ ${\displaystyle a\in \mathbb {F} ^{m}}$ ${\displaystyle n=q^{m}}$

Descripción mediante 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:

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

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

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

sobre subconjuntos por: ${\displaystyle A\subset X}$

${\displaystyle \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 , la operación binaria ${\displaystyle \mathbb {F} _{2}^{N}}$

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

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

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

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

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

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

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

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

La matriz generadora

El código RM( r , m ) de Reed–Muller de orden r y longitud N  = 2 ^m es el código generado por v ₀ y los productos de cuña de hasta r de los v _i , 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 ) , usando vectores y sus permutaciones de productos de cuña hasta r a la vez , como las filas de la matriz generadora, donde 1 ≤ i _k ≤ m . ${\displaystyle {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}})}}$

Ejemplo 1

Sea m = 3. Entonces N = 8, y

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

y

${\displaystyle {\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

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

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

${\displaystyle {\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) es generado por el conjunto:

${\displaystyle \{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:

${\displaystyle {\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:

1. El conjunto de todos los posibles productos de cuña de hasta m de v _i forman una base para . ${\displaystyle \mathbb {F} _{2}^{N}}$
2. El código RM ( r , m ) tiene rango

   ${\displaystyle \sum _{s=0}^{r}{m \choose s}.}$

3. RM ( r , m ) = RM ( r , m − 1) | RM ( r − 1, m − 1) donde '|' denota el producto de barras de dos códigos.
4. RM ( r , m ) tiene un peso Hamming mínimo de 2 ^{m − r} .

Prueba

1. Hay

   ${\displaystyle \sum _{s=0}^{m}{m \choose s}=2^{m}=N}$

   tales vectores y tienen dimensión N por lo que es suficiente comprobar que los N vectores abarcan; equivalentemente es suficiente comprobar que . ${\displaystyle \mathbb {F} _{2}^{N}}$ ${\displaystyle \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 . Definir

   ${\displaystyle 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 ${\displaystyle \mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}}$

   La expansión a través de la distributividad del producto de cuña da . Entonces, como los vectores son generadores, tenemos . ${\displaystyle \mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)}$ ${\displaystyle \{\mathbb {I} _{\{x\}}\mid x\in X\}}$ ${\displaystyle \mathbb {F} _{2}^{N}}$ ${\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}}$
2. 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.
3. Omitido.
4. 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 y tiene peso 1 = 2 ⁰ = 2 ^{m − r} . ${\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}}$

   El artículo producto de barras (teoría de codificación) proporciona una prueba de que el peso del producto de barras de dos códigos C ₁ , C ₂ está dado por

   ${\displaystyle \min\{2w(C_{1}),w(C_{2})\}}$

   Si 0 < r < m y si

   1. RM( r , m  − 1) tiene peso 2 ^{m −1− r}
   2. RM( r  − 1, m  − 1) tiene peso 2 ^{m −1−( r −1)} = 2 ^{m − r}

   Entonces el producto de la barra tiene peso.

   ${\displaystyle \min\{2\times 2^{m-1-r},2^{m-r}\}=2^{m-r}.}$

Descifrando códigos RM

Los códigos RM( r , m ) se pueden decodificar utilizando la decodificación de lógica mayoritaria . La idea básica de la decodificación de lógica mayoritaria es construir varias sumas de comprobación para cada elemento de palabra de código recibido. Dado que cada una de las diferentes sumas de comprobación debe tener el mismo valor (es decir, el valor del peso del elemento de palabra de mensaje), podemos utilizar una decodificación de lógica mayoritaria para descifrar el valor del elemento de palabra de 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 recibida final. Además, los valores de los bits del mensaje se calculan a través de este esquema; finalmente, podemos calcular la palabra de código multiplicando la palabra de mensaje (recién decodificada) con la matriz generadora.

Una pista de que la decodificación tuvo éxito es que se recibió una palabra modificada con todos los ceros al final de la etapa de decodificación ( r  + 1) a través de la decodificación de 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 mediante 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 código del universo ( ). 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. ${\displaystyle m\geq 0}$ ${\displaystyle 0\leq r\leq m}$ ${\displaystyle 2^{m},2^{m},1}$ ${\displaystyle 2^{m},0,\infty }$

${\displaystyle \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 y distancia mínima para . El código dual para 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 autoduales. ${\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)}$ ${\displaystyle d=2^{m-r}}$ ${\displaystyle r\geq 0}$

Casos especiales de códigos Reed-Muller

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

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

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 . ${\displaystyle {R={\tfrac {1}{N}}}}$ ${\displaystyle d_{\min }=N}$
• Los códigos RM(1,  m ) son códigos de verificación de paridad de longitud N  = 2 ^m , tasa y distancia mínima . ${\displaystyle R={\tfrac {m+1}{N}}}$ ${\displaystyle d_{\min }={\tfrac {N}{2}}}$
• Los códigos RM( m  − 1,  m ) son códigos de verificación de paridad simple con una longitud N  = 2 ^m , una tasa y una distancia mínimas . ${\displaystyle R={\tfrac {N-1}{N}}}$ ${\displaystyle d_{\min }=2}$
• 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] ${\displaystyle d_{\min }=4}$

Referencias

1. Massey, James L. (1992), "Comunicaciones y codificación en el espacio profundo: un matrimonio perfecto", Métodos avanzados para comunicaciones satelitales y en el espacio profundo , Notas de clase en ciencias de la información y el control, vol. 182, Springer-Verlag, págs. 1–17, CiteSeerX  10.1.1.36.4265 , doi :10.1007/bfb0036046, ISBN 978-3540558514pdf
2. "Informe final de la reunión 3GPP RAN1 nº 87". 3GPP . Consultado el 31 de agosto de 2017 .
3. Arikan, Erdal (2009). "Polarización de canal: un método para construir códigos que logren capacidad para canales sin memoria de entrada binaria simétricos - Revistas y revistas IEEE". IEEE Transactions on Information Theory . 55 (7): 3051–3073. arXiv : 0807.3917 . doi :10.1109/TIT.2009.2021379. hdl :11693/11695. S2CID  889822.
4. Muller, David E. (1954). "Aplicación del álgebra de Boole 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.
5. 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 de Teoría de la Información del IRE . 4 (4): 38–49. doi :10.1109/tit.1954.1057465. hdl : 10338.dmlcz/143797 . ISSN  2168-2690.
6. Prahladh Harsha et al., Límites de algoritmos de aproximación: PCP y juegos únicos (Notas de la clase del tutorial DIMACS), Sección 5.2.1.
7. Codificación Trellis y Turbo, C. Schlegel y L. Pérez, Wiley Interscience, 2004, p149.

Lectura adicional

• Shu Lin; Daniel Costello (2005). Codificación de control de errores (2.ª edición). 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, Notas de clase, sección 6.4
• Implementación de códigos RM en Matlab con licencia GPL
• Implementación Matlab de códigos RM en formato GPL
• 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.