Votar no es buscar la más cercana

El código de la Mariner 9 manda seis bits en treinta y dos y corrige siete errores. Hay dos maneras de decodificarlo. Una vota: decide cada bit del mensaje por mayoría entre varias estimaciones. La otra busca, entre las 64 palabras posibles, la más cercana a lo que llegó. Hasta siete errores dan lo mismo, siempre. Con uno más se separan. Con ocho errores, la palabra más cercana es única en el 92,4 % de los patrones, y la votación decide sin empatar en el 14,5 %. Son cuentas exactas, sobre los 10 518 300 patrones de ocho errores.

01 · El código y las dos reglas

Un código de Reed-Muller lee cada palabra como la tabla de verdad de una función booleana. En el $\text{RM}(1,5)$ hay 32 posiciones, numeradas de 0 a 31, y cada una es un punto de cinco variables: los bits de su índice, $j=(j_5{j}_4{j}_3{j}_2{j}_1)$ en binario, con $j_1$ el menos significativo. El mensaje son seis coeficientes, $a_0,\dots ,a_5$, y la función es de grado 1:

$$v_j=a_0+a_1{j}_1+a_2{j}_2+a_3{j}_3+a_4{j}_4+a_5{j}_5$$

La suma es módulo 2. Cada una de las $2^6=64$ elecciones de coeficientes da una palabra de código de 32 bits: es un $(32,6)$, con tasa $R=6/32=\mathrm{0,1875}$. Fuera de la nula y la de todos unos, las 62 palabras restantes tienen peso 16: dieciséis unos y dieciséis ceros. La distancia mínima es $d_{\text{min}}=16$, y la capacidad de corrección, $t=\lfloor 15/2\rfloor =7$.

El canal le suma a la palabra $v$ un patrón de error $e$, con un 1 en cada posición que dio vuelta, y llega $r=v+e$. Las dos reglas para recuperar el mensaje son éstas:

La más cercana. Medir la distancia de $r$ a cada una de las 64 palabras —en cuántas posiciones difieren— y quedarse con la menor. Sobre un canal que da vuelta cada bit por separado, con probabilidad menor que ½, es la regla de máxima verosimilitud: ninguna se equivoca menos. Si dos palabras quedan a la misma distancia, la regla empata y tiene que elegir a la suerte.

La votación. El algoritmo de Reed no compara palabras: estima cada coeficiente por separado, con varias sumas de símbolos recibidos que en ausencia de errores darían todas lo mismo, y decide por mayoría. Es la lógica mayoritaria.

02 · Dieciséis votos por coeficiente

Dos posiciones $j$ y $j^{\prime }$ que difieren sólo en el bit $j_i$ tienen todos los términos iguales menos uno, así que al sumarlas se cancela todo y queda $v_j+v_{j^{\prime }}=a_i$. Las 32 posiciones se reparten en 16 pares así, sin que ninguna esté en dos: dieciséis estimaciones disjuntas de $a_i$. Sobre lo recibido, cada par vota

$$r_j+r_{j^{\prime }}=a_i+e_j+e_{j^{\prime }}$$

y el voto sale mal exactamente cuando una de las dos posiciones tiene error y la otra no. Si las dos lo tienen, los errores se cancelan y el voto sale bien. Decididos $a_1$ a $a_5$, se resta su aporte y queda $a_0+e_j$ en cada una de las 32 posiciones: $a_0$ se vota con 32.

De ahí sale la garantía. Cada error estropea a lo sumo un voto de cada coeficiente. Con siete errores hay, como mucho, siete votos malos de dieciséis, y la mayoría gana siempre; con $a_0$ son siete de 32. Con ocho, como mucho ocho votos malos: la votación no puede perder, pero puede empatar ocho a ocho. Pasa cuando los ocho errores caen en ocho pares distintos. Con errores en las posiciones 0, 3, 6, 9, 13, 18, 24 y 29, los votos malos de $a_1$ a $a_5$ son 8, 8, 6, 8 y 6: tres coeficientes empatados, y la votación tiene que tirar tres monedas.

Que una dirección empate es contar: elegir 8 de los 16 pares y, en cada uno, cuál de las dos posiciones tiene el error. Son $\left(\genfrac{}{}{0ex}{}{16}{8}\right)·2^8=3294720$ de los $\left(\genfrac{}{}{0ex}{}{32}{8}\right)=10518300$ patrones, el 31,3 %, y hay cinco direcciones. Enumerando los patrones uno por uno, al menos un coeficiente empata en el 85,5 %, y la votación decide los seis sin moneda sólo en 1 521 920, el 14,5 %.

03 · La más cercana casi nunca duda

Con ocho errores, $r$ queda a distancia 8 de la palabra transmitida. ¿Puede haber otra más cerca? La distancia a $v+c$ es el peso de $e+c$. Si $c$ es la de todos unos, 24. Si $c$ es una de las 62 de peso 16, y $s$ de los ocho errores caen sobre sus unos,

$$w(e+c)=8+16-2s\ge 8$$

con igualdad sólo si $s=8$: si los ocho errores caen todos adentro de los dieciséis unos de una misma palabra. Entonces lo recibido está justo a mitad de camino entre dos palabras, y la regla empata. Nunca hay una palabra estrictamente más cerca que la transmitida. Hay $62·\left(\genfrac{}{}{0ex}{}{16}{8}\right)=797940$ maneras de meter ocho errores en una de esas palabras, con repeticiones: 620 patrones caben en tres palabras a la vez. Enumerados, los que empatan son 796 700, el 7,6 %. En los otros 9 721 600, el 92,4 %, la más cercana es única y es la transmitida.

Las dos reglas, entonces, tienen con ocho errores la misma forma: ninguna se equivoca nunca, las dos a veces empatan. Lo que las separa es cuánto. La más cercana duda en el 7,6 % de los patrones; la votación, en el 85,5 %. Contando cada empate como una moneda —acierta con probabilidad ½ por coeficiente empatado—, la votación acierta en promedio el 42,5 %, y la más cercana, con la misma moneda, el 96,2 %.

Con siete errores las dos aciertan siempre: buscá un patrón de siete que haga empatar algo y no lo vas a encontrar. Con ocho, pedí unos cuantos al azar: la votación casi siempre tiene algún coeficiente ocho a ocho, y el espectro casi siempre tiene una sola barra más alta que todas. Para que la más cercana dude hay que poner los ocho errores en una mitad del arreglo, por ejemplo la fila de arriba entera. Elegir el mensaje no cambia nada: las dos reglas dependen sólo del patrón de error.

04 · Lo que compraba la transformada de Hadamard

Buscar la más cercana por fuerza bruta son 64 distancias de 32 posiciones: 2048 comparaciones por bloque. La transformada de Hadamard hace lo mismo con mucho menos. Se escribe lo recibido como $+1$ donde hay un 0 y $-1$ donde hay un 1, y para cada $b$ de cinco bits se suma

$$F(b)=\sum _{j=0}^{31}{(-1)}^{r_j+b_1{j}_1+\cdots +b_5{j}_5}$$

Cada posición suma $+1$ si $r_j$ coincide con la palabra de coeficientes $(0,b)$ y $-1$ si no. Con $d$ desacuerdos, $F(b)=32-2d$, y la palabra complementaria, la de $a_0=1$, está a $32-d$. Las 32 sumas dan las 64 distancias: la palabra más cercana es la barra más alta en valor absoluto, y el signo dice $a_0$. Y las 32 sumas no se hacen una por una: por mariposas, como una FFT, son cinco etapas de 32 sumas y restas, 160 operaciones. Es máxima verosimilitud a un costo del orden del de la votación, y según el apunte era lo que la electrónica de 1971 podía hacer.

La votación también se lee en el espectro, y ahí se ve qué tira. Cada voto de $a_i$ compara dos posiciones de $r$, y contar cuántos pares coinciden es una autocorrelación, que es lo que la transformada convierte en energía. La cuenta da exacta:

$$\text{votos por }{a}_i=0-\text{votos por }{a}_i=1=\frac{E_0-E_1}{64}$$

donde $E_0$ es la suma de $F{(b)}^2$ sobre las 16 barras con $b_i=0$ y $E_1$ sobre las otras 16. Verificada sobre los 10 518 300 patrones de ocho errores, sin una excepción. La votación pregunta en qué mitad del espectro hay más energía; la más cercana pregunta dónde está la barra más alta.

Con ocho errores la diferencia es todo. La energía total es siempre la misma, ${32}^2=1024$, y la barra de la palabra transmitida mide $32-2·8=16$: se lleva 256, un cuarto. Las otras 31 barras no pueden medir más de 16 —son el doble de una diferencia entre cuántos errores caen a cada lado de una palabra de peso 16— y miden 16 sólo en el caso de la sección anterior. En el ejemplo de las posiciones 0, 3, 6, 9, 13, 18, 24 y 29, la verdadera mide 16 y la siguiente, 12: la más cercana no duda. Pero los 768 que no son del pico se reparten en las dos mitades como quieren, y en $a_1$ le tocan a la mitad del pico 256 y a la otra 512. Las dos mitades suman 512: empate.

05 · Con nueve, las dos se equivocan

Se enumeraron todos los patrones de cada peso, y para cada uno se contó si la más cercana es única y es la transmitida, y si la votación decide bien los seis coeficientes. Cuando hay empate, la columna «con moneda» lo cuenta como acierto a medias por cada coeficiente empatado, o como acierto en una de $k$ si son $k$ las palabras empatadas:

Con nueve errores la votación ya no empata: cada voto malo es un par con un solo error, los pares con dos se llevan los errores de a dos, y con nueve la cantidad de votos malos es impar, nunca ocho. Gana o pierde. Y la más cercana puede quedar en otra palabra, a distancia 7 de lo recibido, más cerca que la transmitida: pasada la mitad de $d_{\text{min}}$, ninguna regla puede acertar siempre. Pero no se equivocan igual: la más cercana cae en otra palabra en el 2,5 % de los patrones de nueve, y la votación en el 69,0 %.

La garantía de las dos es la misma, $t=7$, y por eso el apunte puede decir que la votación «alcanza exactamente la capacidad de corrección del código». Es cierto: la alcanza y no pasa de ahí. Lo que la votación tira es lo que hay más allá de $t$, y en un canal real esos patrones no son raros: son los que deciden cuántos bloques salen mal. Que decodificar por la más cercana sea la mejor apuesta posible está en con dos errores, el decodificador empeora; cómo se construye la familia entera y cómo vota con más de un grado, en los códigos de Reed-Muller.