Los códigos de Reed-Muller

Los códigos de Hamming tienen un solo parámetro libre: cada $m$ da un código, y siempre con $t=1$. Para corregir más hace falta otra construcción. La de Reed-Muller, de 1954, tiene dos parámetros: la longitud $2^m$ y el orden $r$, que recorre toda la escala entre la repetición y la paridad simple. Y trae un decodificador que no calcula síndromes ni consulta una tabla: vota.

01 · Un vector es una tabla de verdad

Se toma un bloque de $n=2^m$ posiciones, y a la posición $j$ se le asocia el punto $(j_1,\dots ,j_m)$ de ${\{0,1\}}^m$ que da su representación binaria, con $j_1$ el bit menos significativo. Con esa numeración, un vector de $V_n$ es la tabla de verdad de una función booleana de $m$ variables: la componente $j$ es lo que la función vale en el punto $j$. La correspondencia es biunívoca, porque hay $2^{2^m}$ funciones y otros tantos vectores.

Toda función booleana se escribe de una sola manera como polinomio sobre $\mathrm{GF}(2)$, como suma de monomios sin exponentes —en $\{0,1\}$ vale $x^2=x$—:

$$f(x_1,\dots ,x_m)=\sum _{S\subseteq \{1,\dots ,m\}}{a}_S{x}_S,x_S=\prod _{i\in S}{x}_i$$

con cada coeficiente $a_S$ en 0 o 1. El grado de $f$ es el del monomio más grande que aparece. Los vectores base son las tablas de los monomios: $v_0$, la de la constante 1, que es todos unos; $v_i$, la de $x_i$, que vale 1 en las posiciones cuyo bit $i$ es 1; y sus productos componente a componente. Con $m=3$, de la posición 0 a la 7:

La tabla de un monomio de grado $s$ vale 1 donde sus $s$ variables valen 1 a la vez: en $2^{m-s}$ posiciones. Ese conteo vuelve en todas las pruebas de abajo.

02 · La definición

Para $0\le r\le m$, el código de Reed-Muller de orden $r$ y longitud $2^m$, $\mathrm{RM}(r,m)$, es el subespacio de $V_{2^m}$ generado por $v_0$ y los productos de a lo sumo $r$ de los $v_i$. Dicho de otro modo: las tablas de verdad de todas las funciones booleanas de $m$ variables de grado $\le r$. Sus parámetros son

$$n=2^m,k=\sum _{s=0}^r\left(\genfrac{}{}{0ex}{}{m}{s}\right),d_{\text{min}}=2^{m-r}$$

La dimensión sale de contar: hay $\left(\genfrac{}{}{0ex}{}{m}{s}\right)$ monomios de grado $s$, y son linealmente independientes porque la escritura como polinomio es única: dos combinaciones distintas de monomios son funciones distintas, y por lo tanto tablas distintas. Las filas de la matriz generadora son esas tablas, ordenadas por grado, y la distancia mínima se prueba en la sección 04.

El ejemplo del apunte es RM(1,3): $v_0$ y las tres variables,

$$G=\left(\begin{array}{cccccccc}1& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 0& 1& 0& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 1& 1& 1& 1\end{array}\right)\begin{array}{l}\leftarrow v_0\\ \leftarrow v_1\\ \leftarrow v_2\\ \leftarrow v_3\end{array}$$

con $n=8$, $k=1+3=4$ y $d_{\text{min}}=2^{3-1}=4$. El mensaje son los cuatro coeficientes $(a_0,a_1,a_2,a_3)$, y la palabra de código vale en la posición $j$

$$a_0+a_1{j}_1+a_2{j}_2+a_3{j}_3$$

una función afín evaluada en el punto $j$. Enumeradas las dieciséis palabras, hay una de peso 0, catorce de peso 4 y una de peso 8. Que las catorce pesen exactamente 4 no es casualidad: una función afín que no es constante vale 1 en exactamente la mitad de los puntos.

03 · Equivalente al (8,4) extendido, no el mismo

RM(1,3) es un (8,4,4) con catorce palabras de peso 4: los parámetros y la distribución de pesos del Hamming extendido (8,4). Pero no es el mismo conjunto de palabras. El (8,4) del curso, que se arma desde el (7,4) sistemático con un bit de paridad global, comparte con RM(1,3) sólo cuatro de sus dieciséis palabras: $00000000$, $01101001$, $10010110$ y $11111111$.

Lo que tienen en común está en las columnas. RM(1,3) es su propio dual: las filas de la $G$ de arriba son ortogonales entre sí y $k=n/2$, así que esa $G$ es también su matriz de paridad. Sus columnas son $(1,j_1,j_2,j_3)$: un 1 arriba y debajo la posición en binario, los ocho vectores de tres bits. La $H$ del (8,4) es la del (7,4) con una columna de ceros agregada y una fila de unos debajo: sus columnas son las siete del (7,4) y la nula, cada una con un 1 abajo. Otra vez los ocho vectores de tres bits con un 1 agregado, en otro orden.

Reordenar las columnas de $H$ es reordenar las posiciones de todas las palabras. La posición $i$ del (8,4) va a la posición de RM(1,3) cuyo número en binario es la columna $i$ de la $H$ del (7,4), leída con la primera fila como bit menos significativo: las posiciones 0 a 7 van a 3, 6, 7, 5, 1, 2, 4 y 0, y las dieciséis palabras del (8,4) caen, todas, en RM(1,3). Son códigos equivalentes. Probadas las 40 320 permutaciones de ocho posiciones, 1344 llevan uno sobre el otro.

Para todo lo que depende sólo de los pesos —$d_{\text{min}}$, $t$, la probabilidad de error sobre el BSC— da lo mismo cuál se use. Para un circuito no: el bit 3 de una palabra de RM(1,3) no es el bit 3 de la palabra del (8,4), y un decodificador de uno no sirve para el otro sin recablear.

04 · La construcción (u, u + v)

La fórmula de la distancia sale de una descripción recursiva de la familia, que se debe a Plotkin.

Paso 1: separar por la última variable. Agrupando los monomios que contienen $x_m$ y los que no, toda función de grado $\le r$ se escribe de una sola manera como

$$f(x_1,\dots ,x_m)=g(x_1,\dots ,x_{m-1})+x_{m}h(x_1,\dots ,x_{m-1})$$

con $g$ de grado $\le r$ y $h$ de grado $\le r-1$, porque $x_m$ ya pone un grado.

Paso 2: evaluar en las dos mitades. Las posiciones 0 a $2^{m-1}-1$ tienen $x_m=0$, y ahí $f$ vale $g$; en la segunda mitad $x_m=1$ y $f$ vale $g+h$. Con $u$ la tabla de $g$ y $v$ la de $h$, para $1\le r\le m-1$:

$$\begin{array}{rl}\mathrm{RM}(r,m)=& \{(u,u+v):\\ & u\in \mathrm{RM}(r,m-1),v\in \mathrm{RM}(r-1,m-1)\}\end{array}$$

RM(1,3), por ejemplo, son los pares $(u,u+v)$ con $u$ en RM(1,2), que es la paridad simple (4,3,2), y $v$ en RM(0,2), la repetición (4,1,4): ocho por dos, dieciséis palabras. Armados los pares desde los dos códigos de $m-1$, sale exactamente $\mathrm{RM}(r,m)$ en los cinco casos de $m=3$ y 4.

Paso 3: la dimensión. Cada palabra es un par $(u,v)$ elegido libremente, así que $k(r,m)=k(r,m-1)+k(r-1,m-1)$: la identidad de Pascal sobre la suma de binomiales.

Paso 4: la distancia, por inducción en $m$. Los extremos son inmediatos: RM(0, m) es la repetición, de distancia $2^m$, y RM(m, m) es todo $V_{2^m}$, de distancia 1. Para el resto, se toma una palabra no nula $(u,u+v)$. Si $v=0$, la palabra es $(u,u)$ con $u$ no nula, y pesa

$$2w(u)\ge 2·2^{(m-1)-r}=2^{m-r}$$

Si $v\ne 0$, toda posición donde $v$ vale 1 tiene un 1 en $u$ o en $u+v$, así que

$$w(u)+w(u+v)\ge w(v)\ge 2^{(m-1)-(r-1)}=2^{m-r}$$

Las dos cotas se alcanzan, así que $d_{\text{min}}=2^{m-r}$ exacto. La tabla del monomio $x_1\cdots x_r$ es una palabra de ese peso.

05 · La familia

Anidamiento. Los generadores de orden $r-1$ son parte de los de orden $r$, así que

$$\mathrm{RM}(0,m)\subset \mathrm{RM}(1,m)\subset \cdots \subset \mathrm{RM}(m,m)=V_{2^m}$$

Para cada longitud, una sola familia contiene toda la escala de tasas, ordenada por inclusión: subir un orden suma $\left(\genfrac{}{}{0ex}{}{m}{r}\right)$ filas a $G$ y divide la distancia por dos. La capacidad de corrección que da esa distancia es $t=2^{m-r-1}-1$, y la familia, en $(n,k,d_{\text{min}})$:

Las columnas de $m=3$ y 4 están contadas enumerando las palabras de cada código; las de $m=5$ salen de la fórmula, y RM(1,5) y RM(2,5) además se enumeraron.

Dualidad. El código dual de $\mathrm{RM}(r,m)$ es otro de la familia:

$$\mathrm{RM}{(r,m)}^{\perp }=\mathrm{RM}(m-r-1,m)$$

Por qué: un monomio de grado $a\le r$ por uno de grado $b\le m-r-1$ da un monomio de grado a lo sumo $m-1$, cuya tabla pesa $2^{m-\text{grado}}$: un número par. El producto interno de dos tablas es el peso de su producto módulo 2, así que es 0, y por linealidad los dos códigos son ortogonales. Las dimensiones suman $2^m$, porque $\left(\genfrac{}{}{0ex}{}{m}{s}\right)=\left(\genfrac{}{}{0ex}{}{m}{m-s}\right)$ reparte los binomiales entre los dos: ortogonales y de dimensiones complementarias, uno es el dual del otro. Comprobado en los siete casos de $m=3$ y 4. Con $m$ impar, $\mathrm{RM}((m-1)/2,m)$ es su propio dual, de tasa $1/2$: RM(1,3) y el (32,16,8). La consecuencia práctica es que la $H$ de un Reed-Muller es la $G$ de otro.

Los casos particulares. RM(0, m) es la repetición $(2^m,1,2^m)$, y su dual RM(m − 1, m) es la paridad simple $(2^m,2^m-1,2)$. Y RM(m − 2, m) es, salvo el orden de las posiciones, el Hamming extendido de longitud $2^m$. Que las dimensiones coincidan no alcanza para decirlo; lo que lo prueba es la dualidad. La $H$ de RM(m − 2, m) es la $G$ de RM(1, m): una fila de unos y debajo las $m$ variables. Sus columnas son $(1,j_1,\dots ,j_m)$ para las $2^m$ posiciones: todos los vectores de $m$ bits con un 1 agregado, que son las columnas de la $H$ del Hamming extendido. Es el argumento de la sección 03, para toda $m$, y deja lo mismo: el mismo conjunto de columnas en otro orden. Con $m=4$, RM(2,4) y el (16,11) extendido desde el (15,11) sistemático tienen la misma distribución de pesos —140 palabras de peso 4, 448 de peso 6, 870 de peso 8— y comparten 128 de sus 2048 palabras.

Mariner 9. En 1971, la sonda Mariner 9 mandó sus imágenes de Marte con RM(1,5), el (32,6,16): seis bits de información en treinta y dos transmitidos, $R=6/32=\mathrm{0,1875}$, y hasta 7 errores corregidos por bloque. Enumeradas sus 64 palabras, las 62 que no son constantes pesan exactamente 16: cualquier par de palabras que no son complementarias está a distancia 16. En el espacio profundo lo que escasea es la potencia, no el ancho de banda, así que gastar redundancia sale barato. Para las imágenes en color de Júpiter y Saturno, Voyager pasó al Golay (24,12): tasa $1/2$ contra $3/16$, porque el volumen de datos pasó a mandar.

06 · El algoritmo de Reed

El decodificador de Reed, contemporáneo de la construcción, no pasa por el síndrome: recupera los coeficientes $a_S$ del mensaje, del grado mayor al menor, cada uno por mayoría de votos. Se ve entero en RM(1,3).

Paso 1: sumar dos posiciones vecinas. En la posición $j$ la palabra vale $a_0+a_1{j}_1+a_2{j}_2+a_3{j}_3$. Dos posiciones que difieren sólo en $j_1$ tienen los mismos $a_0$, $a_2{j}_2$ y $a_3{j}_3$; sumadas, eso se cancela y queda $a_1$.

Paso 2: hay cuatro pares así, y no se tocan. Las ocho posiciones se parten en cuatro pares, cada posición en uno solo:

$$\begin{array}{rcllll}{a}_1& =& r_0+r_1& =r_2+r_3& =r_4+r_5& =r_6+r_7\\ a_2& =& r_0+r_2& =r_1+r_3& =r_4+r_6& =r_5+r_7\\ a_3& =& r_0+r_4& =r_1+r_5& =r_2+r_6& =r_3+r_7\end{array}$$

Sin errores, las cuatro sumas de cada fila dan lo mismo. Con un error, la posición equivocada está en un solo par de cada fila: de cada coeficiente se arruina un voto, quedan tres contra uno y la mayoría acierta.

Paso 3: restar y votar el resto. Decididos $a_1$, $a_2$ y $a_3$, se calcula $r^{\prime }=r+a_1{v}_1+a_2{v}_2+a_3{v}_3$, que debería ser $a_0{v}_0$ con el mismo error encima: ocho copias de $a_0$, y se decide por mayoría entre las ocho.

En general. Para un monomio $x_S$ de grado $r$, el máximo, se fijan las variables que no están en $S$ y se recorren las $2^r$ combinaciones de las que sí: un subcubo de $2^r$ posiciones. Sumada sobre él, la tabla de cualquier otro monomio de grado $\le r$ da 0, porque le falta alguna variable de $S$ y cada valor aparece dos veces; la de $x_S$ vale 1 en un solo punto del subcubo. Queda $a_S$. Hay un subcubo por cada valor de las variables de afuera: $2^{m-r}$ votos disjuntos. Se restan los términos de grado $r$, queda una palabra de $\mathrm{RM}(r-1,m)$ con el mismo error, y se repite. Son $r+1$ etapas, y $a_0$ se vota al final entre las $2^m$ posiciones.

Por qué alcanza $t$. Cada posición está en un solo subcubo, así que cada error arruina a lo sumo un voto de cada coeficiente. Con $t=2^{m-r-1}-1$ errores, los votos malos son menos de la mitad de $2^{m-r}$, y la mayoría acierta. Las etapas siguientes tienen más votos —en RM(2,4), cuatro por coeficiente de grado 2, ocho de grado 1 y dieciséis para $a_0$— con los mismos errores, así que el límite lo pone la primera. Enumerados todos los mensajes por todos los patrones de peso $\le t$ en RM(1,3), RM(1,4) y RM(2,4), el algoritmo los corrige a todos: alcanza exactamente la capacidad del código, sin tabla y con sumas de pocos bits.

Arranca en el ejemplo de RM(1,3) con el mensaje $(a_0,a_1,a_2,a_3)=(1,0,1,1)$ y sin errores: todos los votos coinciden. Prendé un bit de $e$ y mirá cuántos votos se ponen en rojo en cada fila: uno solo, siempre, porque la posición cae en un solo par de cada coeficiente. Pasá a RM(1,4): cada coeficiente tiene ocho votos y aguanta tres errores; el cuarto ya deja algún cuatro a cuatro. En RM(2,4), los coeficientes de grado 2 votan de a cuatro sumas de cuatro bits y los de grado 1 de a ocho: con un error, la primera etapa es la que tiene menos margen.

07 · Un error más que t

Con $t+1=2^{m-r-1}$ errores, puede haber exactamente la mitad de los votos malos, y entonces no hay mayoría. Con el mismo mensaje de antes y errores en las posiciones 5 y 6, llega $r=11000101$ y los votos son $0,0,1,1$ para $a_1$, $1,1,0,0$ para $a_2$ y $1,0,0,1$ para $a_3$: tres empates.

No es mala suerte. En RM(1,3), dos errores en las posiciones $p$ y $q$ caen en el mismo par de $a_i$ sólo si $p$ y $q$ difieren únicamente en el bit $i$; en cualquier otro coeficiente arruinan dos votos distintos y dejan dos contra dos. Enumerados todos los mensajes por todos los patrones de peso $t+1$, la primera etapa empata en algún coeficiente siempre: en los 28 patrones dobles de RM(1,3), en los 1820 cuádruples de RM(1,4) y en los 120 dobles de RM(2,4).

Un empate se rompe con una regla, y la regla es arbitraria: acá decide 0, y con otra el mismo $r$ sale decodificado distinto. Lo que el algoritmo garantiza termina en $t$. Más allá, votar y buscar la palabra más cercana dejan de dar lo mismo, y cuánto se separan en el código de Mariner está en votar no es buscar la más cercana. Para $r=1$ la búsqueda de la más cercana tiene atajo: la transformada rápida de Hadamard la hace en $O(n\log n)$ operaciones.

Para tener a mano

1. La posición $j$ es el punto $(j_1,\dots ,j_m)$, con $j_1$ el bit menos significativo; una palabra es la tabla de verdad de una función booleana.
2. $\mathrm{RM}(r,m)$: las tablas de las funciones de grado $\le r$. $n=2^m$, $k={\sum }_{s=0}^r\left(\genfrac{}{}{0ex}{}{m}{s}\right)$, $d_{\text{min}}=2^{m-r}$, $t=2^{m-r-1}-1$.
3. $\mathrm{RM}(r,m)=\{(u,u+v)\}$ con $u\in \mathrm{RM}(r,m-1)$ y $v\in \mathrm{RM}(r-1,m-1)$: de ahí $d_{\text{min}}$, por inducción.
4. Anidados: $\mathrm{RM}(r-1,m)\subset \mathrm{RM}(r,m)$. Duales: $\mathrm{RM}{(r,m)}^{\perp }=\mathrm{RM}(m-r-1,m)$.
5. RM(0, m) es la repetición, RM(m − 1, m) la paridad simple y RM(m − 2, m) el Hamming extendido salvo una permutación: RM(1,3) comparte sólo 4 de sus 16 palabras con el (8,4) del curso.
6. Mariner 9: RM(1,5) = (32,6,16), $R=\mathrm{0,1875}$, $t=7$; sus 62 palabras no constantes pesan 16.
7. Algoritmo de Reed: de grado $r$ a 0, cada coeficiente por mayoría de $2^{m-\text{grado}}$ sumas disjuntas, restando lo decidido. Cada error arruina un voto por coeficiente: corrige hasta $t$ exacto, y con $t+1$ siempre hay algún empate.