El producto corrige más de lo que promete

Con dos Hamming $(7, 4)$ se arma un código de 49 bits que corrige cuatro errores. Para no decodificarlo entero, se lo corrige por partes: primero cada fila, después cada columna. A ese decodificador el apunte le garantiza un error. Decodificando todos los patrones de error, uno por uno, corrige los 49 de un error, los 1176 de dos, los 18 424 de tres y 202 615 de los 211 876 de cuatro, el 95,6 %. El producto corrige más de lo que promete. La garantía no cuenta ningún patrón que falle: el primero que falla tiene cuatro errores y una forma precisa, dos filas con dos errores cada una.

01 · Un código hecho con dos

El Hamming $(7, 4)$ es el código de Hamming más chico: siete bits por palabra de código, cuatro de información y tres de paridad. Su distancia mínima, la menor cantidad de posiciones en que difieren dos palabras, es $d_{min} = 3$ , y su capacidad de corrección es $t = 1$ : un error, en cualquier posición.

Un código producto $C_{1} \otimes C_{2}$ toma dos códigos y arma arreglos de $n_{2}$ filas por $n_{1}$ columnas en los que cada fila es una palabra de $C_{1}$ y cada columna una de $C_{2}$ . Se codifica en dos tiempos: los $k_{1} k_{2}$ bits de información se acomodan en un rectángulo, cada fila recibe su paridad de $C_{1}$ , y después cada columna, también las de paridad, la suya de $C_{2}$ . Los parámetros salen de contar:

n = n_{1} n_{2}, k = k_{1} k_{2}, R = R_{1} R_{2}

Con el $(7, 4)$ en las filas y en las columnas, el arreglo es de 7 × 7: 49 bits, 16 de información en un cuadrado de 4 × 4, y una tasa de $16 / 49 \approx 0,327$ .

La distancia se multiplica. Un arreglo no nulo del código tiene alguna fila no nula; esa fila es una palabra del $(7, 4)$ y tiene al menos tres unos. Cada una de esas tres columnas es, a su vez, una palabra no nula, con al menos tres unos. Son nueve por lo menos, y nueve se alcanzan: una palabra de peso 3, con tres unos, puesta en tres filas, las de otra palabra de peso 3, da un arreglo de exactamente nueve unos.

d_{min} = d_{1} d_{2} = 9, t = ⌊ (9 - 1) / 2 ⌋ = 4

El resultado es un $(49, 16, 9)$ : un código que corrige cuatro errores, hecho con dos que corrigen uno.

02 · Corregir por partes

Decodificarlo como cualquier código lineal pide una tabla con un líder de coset para cada síndrome, y el $(49, 16)$ tiene $2^{33} \approx 8,6 \cdot 10^{9}$ síndromes. La decodificación por etapas aprovecha que el código está hecho de piezas chicas:

cada una de las siete filas se decodifica con el decodificador del $(7, 4)$ ;
después, cada una de las siete columnas, con el mismo.

Son catorce decodificaciones de siete bits, cada una con una tabla de ocho entradas. Lo que hay que saber de cada una es qué hace el decodificador del $(7, 4)$ según cuántos errores le lleguen. Con uno, lo corrige. Con dos, agrega un tercero: el síndrome de dos errores es el de un error simple en otra posición, y la fila sale con tres bits mal que forman una palabra de peso 3. Con más, también entrega una palabra de código, equivocada. Y una fila con dos errores o más nunca sale limpia: el decodificador sólo da vuelta un bit, así que de dos errores para arriba siempre queda alguno, y lo que queda es una palabra no nula del $(7, 4)$ , de tres unos por lo menos.

03 · Lo que promete

El apunte le da a la decodificación por etapas esta garantía: corrige todo patrón de a lo sumo $t_{1} t_{2}$ errores, con $t_{1}$ y $t_{2}$ las capacidades de corrección de los dos códigos. La prueba cuenta filas malas, las que traen más de $t_{1}$ errores. Cada una aporta por lo menos $t_{1} + 1$ , así que con $t_{1} t_{2}$ errores hay menos de $t_{2}$ filas malas. Las buenas salen limpias de la primera etapa, y lo que sobrevive queda en menos de $t_{2}$ filas: ninguna columna tiene más errores de los que su decodificador corrige.

Para el $(49, 16, 9)$ la cuenta da

t_{1} t_{2} = 1 \cdot 1 = 1, contra ⌊ (d_{1} d_{2} - 1) / 2 ⌋ = 4

Un error garantizado donde la distancia permitiría cuatro. El apunte lo lee como el costo de decodificar por partes. Antes de seguir, buscá vos un patrón de dos o de tres errores que el decodificador no corrija.

En los arreglos de la derecha, el contorno azul es un error que la etapa ya sacó y el relleno rojo un bit que sigue mal o que la etapa agregó. Con un error por fila, la primera etapa limpia todo. Con dos en una fila, la fila sale con tres bits mal, pero en tres columnas distintas, y la segunda etapa los saca de a uno. Los triples no fallan nunca. El primero que falla tiene cuatro errores.

04 · Por qué los triples salen siempre

El argumento no necesita casos. Con tres errores, a lo sumo una fila puede tener dos o más: dos filas así sumarían cuatro. Las filas con un solo error salen limpias de la primera etapa. Todo lo que sobrevive a ella, haya corregido bien o mal esa fila, haya agregado un bit o no, quedó en una sola fila. Entonces cada columna tiene a lo sumo un bit mal, y eso es exactamente lo que el decodificador de columnas corrige.

Es la prueba del apunte con un paso menos de cautela. La segunda etapa no necesita menos de $t_{2}$ filas malas: corrige cualquier columna con hasta $t_{2}$ errores, así que se banca hasta $t_{2}$ filas malas. Para que haya $t_{2} + 1$ filas malas, cada una con $t_{1} + 1$ errores por lo menos, hacen falta $(t_{1} + 1) (t_{2} + 1)$ errores. Con uno menos, la decodificación por etapas corrige siempre:

(t_{1} + 1) (t_{2} + 1) - 1 = t_{1} t_{2} + t_{1} + t_{2}

En el $(49, 16, 9)$ da 3, no 1. Y no es una casualidad de $t = 1$ : con el $(7, 4)$ en las filas y la repetición $(5, 1)$ en las columnas, que corrige dos, el apunte promete $1 \cdot 2 = 2$ y la cuenta de arriba da 5. Decodificando todos los patrones de ese arreglo de 5 × 7, corrige los 324 632 de cinco errores, y con seis aparecen los primeros que no: 47 250 de 1 623 160.

En el producto de dos Hamming, decodificando cada patrón de error sobre el arreglo, filas primero:

errores	patrones	corregidos	proporción
1	49	49	100 %
2	1176	1176	100 %
3	18 424	18 424	100 %
4	211 876	202 615	95,6 %
5	1 906 884	1 555 407	81,6 %

Con las columnas primero las cuentas son idénticas, fila por fila de la tabla: los dos códigos son el mismo, y el arreglo es simétrico. Un decodificador que usara toda la distancia corregiría los 211 876 de cuatro.

05 · Los de cuatro que fallan

Con cuatro errores ya puede haber dos filas malas, y de una sola manera: dos errores en cada una. Es exactamente donde falla. Separando los 211 876 patrones por cómo se reparten entre las filas:

reparto por fila	patrones	corregidos
4 en una	245	245
3 y 1	10 290	10 290
2, 1 y 1	108 045	108 045
1, 1, 1 y 1	84 035	84 035
2 y 2	9261	0

Todos los repartos con una sola fila mala salen, por el argumento de los triples. Los de dos y dos son $21 \cdot 21 \cdot 21 = 9261$ : 21 pares de filas, y en cada fila 21 pares de posiciones. No se corrige ninguno, y la razón está en el $(7, 4)$ . Cada una de las dos filas sale de la primera etapa con una palabra de peso 3. Dos palabras de peso 3 del $(7, 4)$ se cruzan siempre. Si comparten $c$ posiciones, su suma tiene peso $6 - 2 c$ , y la suma también es palabra de código. El $(7, 4)$ sólo tiene palabras de peso 0, 3, 4 y 7: $c$ no puede ser 0, que daría peso 6, ni 2, que daría peso 2. O comparten una posición, o son la misma palabra. En esa columna compartida hay dos bits mal, y el decodificador de columnas hace con ellos lo que hace con dos: agrega un tercero.

Termina de dos maneras. Si las dos filas dejan palabras distintas, comparten una sola columna: las otras cuatro tienen un bit mal y salen limpias, y en la compartida quedan tres. Salen tres bits mal, en una columna, en 7938 de los 9261. Si dejan la misma palabra, son tres columnas con dos bits mal cada una, y las tres reciben su tercero: salen nueve bits mal, en los 1323 restantes.

El ejemplo que dan Lin y Costello es el segundo caso: cuatro errores en las esquinas de un rectángulo. Con las esquinas en las filas 1 y 4 y las columnas 2 y 5, las dos filas tienen el mismo par, así que dejan la misma palabra, la de las posiciones 2, 3 y 5. Las columnas 2, 3 y 5 tienen entonces dos bits mal, en las filas 1 y 4, y cada una agrega la fila 2. Salen nueve bits mal, en un cuadrado de 3 × 3. Los rectángulos son 441 de los 9261: el peor caso no es sólo el rectángulo, es cualquier par de filas con dos errores cada una.

Con cinco errores pasa lo mismo un nivel más arriba. Fallan 351 477 de 1 906 884, y todos tienen dos filas malas: 27 342 de los 30 870 que se reparten tres y dos, y los 324 135 que se reparten dos, dos y uno. Los repartos con una sola fila mala, los otros 1 551 879, salen todos. La garantía $t_{1} t_{2}$ cuenta errores. Lo que decide es cuántas filas malas hay.

06 · Otra pasada

Los 7938 que terminan con tres bits mal en una columna tienen arreglo. Esos tres bits están en tres filas distintas, uno en cada una, y una segunda pasada por filas los corrige. Es la decodificación iterativa: repetir filas y columnas mientras algo cambie. Repitiéndolas hasta que nada cambia se corrigen 210 553 de los 211 876 de cuatro.

Los 1323 que terminan con nueve bits mal no se mueven. Lo que queda es el producto de una palabra de peso 3 por otra: un arreglo con cada fila y cada columna en el $(7, 4)$ , una palabra del propio $(49, 16, 9)$ de peso mínimo. Ningún decodificador de fila ni de columna ve nada que corregir, y la salida pasa por válida aunque esté a nueve bits de la que se mandó: un síndrome cero no prueba nada.

La decodificación por etapas paga la distancia que no usa en patrones con una forma precisa, no en una cantidad de errores. Qué patrones llegan con esa forma depende del canal y del orden en que los bits salen del arreglo. Contra las ráfagas, ese orden es todo: la ráfaga la corrige el orden.