Con dos errores, el decodificador empeora

El Hamming $(7,4)$ manda cuatro bits de mensaje y tres de paridad, y corrige un error. Con dos, uno espera que se rinda: que los deje como llegaron, o que arregle uno y se le escape el otro. No hace ninguna de las dos cosas. Con dos errores, el decodificador agrega un tercero. Pasa en los 21 patrones dobles, sin una excepción, y lo que entrega es una palabra válida a tres bits de la que se mandó.

01 · Lo que el decodificador sabe hacer

Una palabra de código es cada uno de los 16 vectores de 7 bits que el código acepta: los cuatro bits del mensaje y, detrás, los tres de paridad que se calculan con ellos. El mensaje 1001 viaja como 1001 011, con la posición 0 a la izquierda. En el camino, el canal le suma un patrón de error $e$: un vector con un 1 en cada posición que dio vuelta. Llega $r=v+e$.

El receptor no conoce $v$, pero puede calcular el síndrome, $s=r{H}^T$: tres bits que salen de multiplicar lo recibido por la matriz de paridad $H$, la que anula a toda palabra de código. Como $v{H}^T=0$, el síndrome vale $e{H}^T$: depende sólo del error, no de lo que se mandó. Y se lee como una suma: el síndrome es la suma de las columnas de $H$ en las posiciones que el canal dio vuelta. La $H$ del $(7,4)$ es la del apunte:

$$H=\left[\begin{array}{ccccccc}1& 0& 1& 1& 1& 0& 0\\ 1& 1& 1& 0& 0& 1& 0\\ 0& 1& 1& 1& 0& 0& 1\end{array}\right]$$

Leídas de arriba abajo, sus columnas son $h_0=110$, $h_1=011$, $h_2=111$, $h_3=101$, $h_4=100$, $h_5=010$ y $h_6=001$: los siete vectores no nulos de tres bits, cada uno una vez. Un error en la posición $i$ da como síndrome $h_i$, y como no hay dos columnas iguales, el síndrome dice dónde fue. El decodificador por síndrome no hace otra cosa: busca en una tabla de ocho entradas el patrón que le toca a cada síndrome —el líder de coset, el patrón de menor peso, o sea con menos unos, entre todos los que dan ese síndrome— y lo suma a lo recibido. En el $(7,4)$ los ocho líderes son el vector nulo y los siete errores simples.

Ésa es la garantía. La distancia mínima del código, la menor cantidad de posiciones en que difieren dos palabras, es $d_{\text{min}}=3$, y de ahí sale la capacidad de corrección, $t=\lfloor (d_{\text{min}}-1)/2\rfloor =1$: un error, en cualquier posición, se corrige siempre. La garantía no dice nada de dos.

02 · Dos columnas suman una tercera

Con errores en las posiciones $i$ y $j$, el síndrome es $h_i+h_j$. Dos vectores de tres bits distintos y no nulos suman otro no nulo, distinto de los dos. Y como las columnas de $H$ son todos los no nulos, esa suma es una columna: la de una tercera posición $k$.

$$s=h_i+h_j=h_k$$

El decodificador recibe el síndrome de un error simple en $k$, porque lo es, y da vuelta el bit $k$. Ahora hay tres bits mal: los dos del canal y el que puso él.

Con la palabra del ejemplo del apunte, 1001 011, y el canal dando vuelta las posiciones 0 y 1, llega 0101 011. El síndrome es $h_0+h_1=110+011=101=h_3$. El decodificador da vuelta el bit 3 y entrega 0100 011: una palabra de código, válida, a tres bits de la que se mandó. Del mensaje 1001, el canal había roto dos bits; el receptor se queda con 0100, que tiene tres mal.

Con un solo error, la apuesta segura es «menos»: el síndrome cae en la columna del error y la palabra sale limpia. Con dos, probá cualquier par: el síndrome cae siempre en una tercera columna, que se marca en rojo, y a la salida hay tres bits mal. La grilla de los 21 pares va guardando qué posición agregó el decodificador en cada par que probaste. Cambiar el mensaje no mueve nada de eso: el síndrome no depende de él.

03 · Los veintiún pares

Hay $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$ maneras de elegir dos posiciones de siete, y las 21 terminan igual. Medido decodificando los 21 pares sobre los 16 mensajes, 336 casos, la palabra entregada queda a distancia 3 de la transmitida —difiere en tres posiciones— en los 336. Y la simulación del corrector en SystemVerilog del curso, sobre los mismos 336, entrega los mismos mensajes.

El error final, además, no es cualquier vector de peso 3: es siempre una palabra de código. Lo que termina sumado a $v$ son los dos bits del canal más el que agrega el decodificador, y su síndrome es $h_i+h_j+h_k=0$. El $(7,4)$ tiene siete palabras de peso 3, y cada una tiene tres pares adentro: $7\times 3=21$. Por eso lo que sale siempre pasa por válido.

Lo que el receptor se queda es el mensaje, las cuatro primeras posiciones, y ahí el tercer bit a veces cae y a veces no. Contando, en cada par, cuántos de los cuatro bits de mensaje llegaron mal y cuántos salen mal:

A la salida, el mensaje tiene 1 bit mal en 9 pares, 2 en 9 y 3 en 3. En ningún par mejora: en 9 queda igual, porque el bit que agrega el decodificador cae en la paridad, y en los otros 12 empeora en uno. El caso más feo es el primero: con los dos errores en la paridad el mensaje había llegado intacto, y el decodificador lo rompe. En promedio, un par trae $8/7\approx \mathrm{1,14}$ bits de mensaje mal y sale con $12/7\approx \mathrm{1,71}$: la mitad más.

04 · No es un defecto: es la mejor apuesta

Parece un decodificador mal hecho, y es el mejor posible. Sobre el canal binario simétrico, que da vuelta cada bit por separado con probabilidad $p$, un patrón dado de peso $w$ tiene probabilidad $p^w{(1-p)}^{n-w}$. El error simple en $k$ y el doble en $i$ y $j$ dan el mismo síndrome, y el simple es más probable:

$$\frac{p{(1-p)}^6}{p^2{(1-p)}^5}=\frac{1-p}{p}$$

En $p={10}^{-2}$, 99 veces más. Quedarse con el patrón de menor peso es la decisión de máxima verosimilitud: ninguna regla se equivoca menos. Y la cuenta no cambia si se juntan los tres dobles que comparten cada síndrome: los tres suman $3p^2{(1-p)}^5$, y el simple les gana mientras $p<1/4$. El tercer bit no es una falla de la regla. Es lo que la regla cuesta cuando el canal hizo lo menos probable.

Tampoco se le puede pedir que se abstenga. El síndrome de un doble es idéntico al de un simple: el decodificador no tiene con qué distinguirlos. La decodificación incompleta, la que corrige sólo los patrones de peso hasta $t$ y para el resto declara falla, acá no cambia nada: el $(7,4)$ es un código perfecto, sus ocho síndromes alcanzan justo para el vector nulo y los siete simples, $8=1+7$, y no queda ninguno libre para avisar. Para que la bandera se levante hace falta un código que deje síndromes sin un error simple que los explique, como el $(8,4)$: en un código perfecto la bandera no se levanta.

Y como lo que entrega es una palabra de código, un chequeo que vuelva a calcular el síndrome a la salida da cero. No queda rastro: un síndrome cero no prueba nada.

05 · Con más errores, tampoco

Decodificando los 128 patrones posibles, uno por uno, y contando cuántos bits salen mal según cuántos entraron:

De los 120 patrones con dos errores o más, el decodificador no acierta ninguno: sólo corrige los ocho líderes. La salida es siempre una palabra de código, así que lo que queda mal también lo es, y por eso a la salida sólo hay 0, 3, 4 o 7 bits mal. Con tres errores que ya forman una palabra, 7 de los 35, el síndrome es cero y no toca nada; con los otros 28 agrega un cuarto. Con cuatro, en 28 de 35 da vuelta uno de los errados y quedan tres: menos bits mal, y la palabra igual equivocada. Y con seis, el síndrome es la columna del único bit que llegó bien —las siete columnas suman cero—, y el decodificador da vuelta justo ése.

06 · Cuánto pesa

Con $p$ chico, casi todo lo que sale mal entró con dos errores. Sumando la probabilidad exacta de cada uno de los 128 patrones sobre el canal binario simétrico: en $p={10}^{-2}$, el decodificador entrega mal $\mathrm{2,03}·{10}^{-3}$ de los bloques, y el 98,3 % de esos son dobles; en $p={10}^{-3}$, el 99,8 %. Los dobles no son un caso de borde: son la forma en que el $(7,4)$ se equivoca.

Y se ve en la tasa de error del mensaje. A primer orden la ponen los 21 pares, cada uno con $12/7$ bits mal en promedio repartidos entre cuatro: $21·\frac{12}{7}·\frac{1}{4}=9$, o sea $\text{BER}\approx 9p^2$. Si el decodificador dejara los dobles como llegaron serían $8/7$ por par, $6p^2$: a primer orden, uno de cada tres bits de mensaje que salen mal lo puso él. La cuenta exacta en $p={10}^{-2}$ da $\mathrm{8,74}·{10}^{-4}$ contra los $9·{10}^{-4}$ de la aproximación.

Decodificar igual conviene, por lejos: en el mismo canal, leer los cuatro bits de mensaje sin corregir da ${10}^{-2}$. El tercer bit no cambia qué bloques salen mal: encarece los que ya iban a salir mal. Cuánto cuesta corregir en vez de sólo detectar está en corregir uno cuesta 3/p, y si el código paga lo que gasta en paridad, medido en $E_b/N_0$, en el código que todos inventan primero no paga nunca.