Un síndrome cero no prueba nada

Un código de bloque lineal $(n,k)$ toma $k$ bits de mensaje y manda $n$. De los $2^n$ vectores de $n$ bits, sólo $2^k$ son palabras de código: los que el codificador puede producir. En el Hamming (7,4) son 16 de 128. El canal da vuelta algunos bits, y lo que da vuelta se anota como un patrón de error $e$, un vector con un 1 en cada posición invertida. Lo que llega es $r=v+e$, con $v$ la palabra mandada y la suma bit a bit, sin acarreo.

El receptor no conoce $v$. Lo que sí puede calcular es el síndrome, $s=r{H}^T$, con $H$ la matriz de paridad del código: $n-k$ bits, tres en el (7,4). Si $s$ no es cero, hubo error, seguro. Si es cero, el receptor acepta $r$ como si fuera lo mandado. Las dos ramas no valen lo mismo: un síndrome no nulo prueba que hubo error, y uno nulo no prueba que no lo hubo.

01 · Lo que el síndrome ve

Toda palabra de código cumple $v{H}^T=0$; es lo que define a $H$. Por eso el síndrome no ve lo mandado:

Depende sólo del error. Y $e{H}^T$ es la suma de las columnas de $H$ en las posiciones que el canal dio vuelta. En el (7,4) del apunte esas columnas, de $h_0$ a $h_6$, son 110 011 111 101 100 010 001: los siete vectores no nulos de tres bits, cada uno una vez.

Entonces $s=0$ cuando $e{H}^T=0$, que es exactamente la condición de ser palabra de código. Un error pasa sin ser visto si y sólo si el patrón de error es él mismo una palabra de código no nula. En el (7,4) hay $2^k-1=15$. No hay otra forma de engañar al síndrome, y ninguna de esas quince deja de engañarlo nunca: sumarle una palabra a $v$ da otra palabra, y el receptor no tiene cómo distinguirla de una que llegó limpia.

02 · La garantía: hasta dos errores

El peso de un vector, $w(e)$, es su cantidad de unos: para un patrón de error, cuántos bits se dieron vuelta. La distancia mínima $d_{\text{min}}$ de un código es la menor cantidad de posiciones en que difieren dos palabras distintas, y en un código lineal coincide con el menor peso de una palabra no nula. En el (7,4), $d_{\text{min}}=3$.

De ahí sale la garantía. Un patrón de peso menor que $d_{\text{min}}$ no puede ser palabra, así que el síndrome lo ve siempre: el código detecta todo patrón de hasta $d_{\text{min}}-1=2$ errores. Son los 7 simples y los 21 dobles, los 28 sin excepción. Desde las columnas es lo mismo dicho de otro modo: una columna sola no es cero, y dos columnas distintas no suman cero. Hace falta juntar tres para que se anulen, como $h_0+h_1+h_3$ $=110+011+101=000$.

Es una garantía de peor caso: dice qué pasa con el patrón más desfavorable de cada peso. Para tres errores o más no promete nada. Pero que no prometa no quiere decir que no vea.

03 · Los quince que pasan

Patrones de peso 3 o más hay 99: 35 de peso 3, 35 de peso 4, 21 de peso 5, 7 de peso 6 y uno de peso 7. El (7,4) detecta 84. Pasan 15, y son exactamente las 15 palabras no nulas: 7 de peso 3, 7 de peso 4 y la de peso 7, 1111 111. La distribución de pesos del código, $A_i=1,0,0,7,7,0,0,1$ para $i$ de 0 a 7, es la lista de lo que se escapa.

Lo raro está en las filas vacías. Con 5 bits mal, o con 6, el síndrome no falla nunca: detecta los 21 y los 7. Con los siete bits mal no ve nada. Lo que se le escapa no es el error grande: es el que cae justo sobre otra palabra. Detectar no es contar cuántos bits se dieron vuelta, es preguntar si lo que llegó es una palabra, y para eso da igual si el camino fue corto o largo.

Abajo se mandó el mensaje 1001, la palabra 1001 011. Arranca sin errores. Los botones de $e$ dan vuelta un bit cada uno, y cada patrón que armes queda marcado en la grilla de los 127: gris si el síndrome lo vio, rojo si pasó. Buscá los quince.

Cada uno de los quince deja al receptor con un mensaje legítimo en la mano, y equivocado. Con $e=v$, es decir 1001 011, llega 0000 000 y acepta 0000. Con 1111 111 llega 0110 100 y acepta 0110: los cuatro bits de mensaje mal, y ninguna alarma. El síndrome no tiene cómo saberlo, porque lo que mide es si $r$ es una palabra, y lo es.

04 · Cuánto se escapa en un canal

En el canal binario simétrico, que da vuelta cada bit con probabilidad $p$ y sin mirar a los demás, un patrón de peso $i$ aparece con probabilidad $p^i{(1-p)}^{n-i}$. La probabilidad de error no detectado suma la de los quince, agrupados por peso:

En el (7,4), con sus siete palabras de peso 3, siete de peso 4 y una de peso 7:

Con $p$ chico manda el primer término, y $P_u\approx 7p^3$: el exponente lo pone $d_{\text{min}}=3$ y el 7 lo pone $A_3$, la cantidad de palabras de ese peso. La tabla es la fórmula exacta evaluada, y al lado la pregunta que de verdad tiene el receptor: llegó $s=0$, ¿qué tan probable es que igual haya habido error? Es $P_u$ sobre la probabilidad de ver un síndrome nulo, que es ${(1-p)}^7+P_u$.

En $p={10}^{-2}$ un síndrome nulo miente siete veces en un millón, y la aproximación $7p^3$ está a un 3 % de la cuenta exacta. En $p=\mathrm{0,5}$, donde el canal ya no transmite nada, los 128 patrones son igual de probables: 16 dan $s=0$, y quince de esos dieciséis son error. Es el mismo 000 en los dos casos. Lo que vale como evidencia no lo pone el código: lo pone el canal.

Y en $p=1$, el canal que da vuelta todo, el patrón es siempre 1111 111, que es palabra. El (7,4) no detecta un solo bloque, y entrega el complemento del mensaje cada vez.