Los códigos producto

Todas las familias de esta unidad salen de elegir una matriz de paridad. El código producto sale de otro lado: se toman dos códigos que ya se saben decodificar y se los cruza. Con dos Hamming (7,4), que corrigen un error cada uno, se arma uno que podría corregir cuatro. Lo que no se multiplica es lo que el decodificador sencillo garantiza.

01 · La definición

Sean $C_{1}$ un código $(n_{1}, k_{1}, d_{1})$ y $C_{2}$ un código $(n_{2}, k_{2}, d_{2})$ . El código producto $C_{1} \otimes C_{2}$ es el conjunto de arreglos de $n_{2}$ filas por $n_{1}$ columnas en los que cada fila es una palabra de $C_{1}$ y cada columna es una palabra de $C_{2}$ . Leído en algún orden, el arreglo es un vector de $n_{1} n_{2}$ bits, y la suma de dos arreglos así sigue siendo uno así: el producto es un código lineal. Lo introdujo Elias en 1954.

La construcción, en tres pasos:

Paso 1: la información en un rectángulo. Los $k_{1} k_{2}$ bits de mensaje se disponen en $k_{2}$ filas de $k_{1}$ .

Paso 2: cada fila con $C_{1}$ . Cada fila gana $n_{1} - k_{1}$ bits de paridad. El arreglo queda de $k_{2}$ por $n_{1}$ .

Paso 3: cada columna con $C_{2}$ . Las $n_{1}$ columnas ganan $n_{2} - k_{2}$ bits cada una, también las que ya eran de paridad.

Quedan cuatro regiones: la información arriba a la izquierda, las paridades de fila a su derecha, las de columna debajo, y en la esquina de abajo a la derecha las paridades calculadas sobre paridades, las checks on checks. Con $C_{1} = C_{2}$ el Hamming (7,4) del curso, en forma sistemática, el mensaje $0101$ , $1110$ , $0011$ , $1000$ (una fila de información cada cuatro bits) da

V = (\begin{array}{l} 0101 110 \\ 1110 010 \\ 0011 010 \\ 1000 110 \\ 1110 010 \\ 1000 110 \\ 0101 110 \end{array})

con la posición 0 de cada fila a la izquierda. Las cuatro primeras filas son las del mensaje codificadas; las tres últimas son paridad de columna, y sus tres últimos bits son las checks on checks.

Esa esquina admite dos cuentas: aplicar $C_{2}$ a las columnas de paridad de fila, o aplicar $C_{1}$ a las filas de paridad de columna. Dan lo mismo. En forma sistemática, codificar las filas es multiplicar el arreglo por una matriz a la derecha, y codificar las columnas es multiplicarlo por otra a la izquierda; las dos multiplicaciones actúan sobre índices distintos y conmutan. Por eso la definición puede ser la simétrica —filas en $C_{1}$ , columnas en $C_{2}$ — sin decir cuál se codificó primero. Codificados los 65 536 mensajes del ejemplo por los dos órdenes, los arreglos coinciden todos, y en todos cada fila y cada columna tiene síndrome nulo.

02 · Los parámetros

Tres salen de contar:

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

La tasa es el producto de las tasas porque $k / n = (k_{1} / n_{1}) (k_{2} / n_{2})$ . La cuarta, la distancia mínima, pide prueba, en dos mitades: que ningún arreglo no nulo pese menos, y que alguno pese exactamente eso. En un código lineal la distancia mínima es el menor peso no nulo.

Paso 1: una fila no nula. Sea $V$ un arreglo del código distinto de cero. Tiene al menos una fila no nula, que es una palabra no nula de $C_{1}$ : tiene al menos $d_{1}$ unos. Sea $J$ el conjunto de sus columnas, con $| J | \geq d_{1}$ .

Paso 2: cada una de esas columnas pesa al menos $d_{2}$ . Cada columna con índice en $J$ tiene un 1, así que es una palabra no nula de $C_{2}$ , con al menos $d_{2}$ unos. Sumando sólo sobre esas columnas, $w (V) \geq d_{1} d_{2}$ .

Paso 3: el producto exterior alcanza la cota. Sean $a$ una palabra de peso $d_{1}$ de $C_{1}$ y $b$ una de peso $d_{2}$ de $C_{2}$ , y el arreglo $V_{i j} = b_{i} a_{j}$ . La fila $i$ es $a$ o cero, la columna $j$ es $b$ o cero: está en el código, y tiene exactamente $d_{1} d_{2}$ unos, en $d_{2}$ filas por $d_{1}$ columnas.

Para $(7, 4) \otimes (7, 4)$ sale el $(49, 16, 9)$ , con tasa $16 / 49 \approx 0,327$ contra los $4 / 7 \approx 0,571$ de cada factor. Su capacidad de corrección es $t = ⌊ (9 - 1) / 2 ⌋ = 4$ : un código que corrige cuatro errores, hecho con dos que corrigen uno, sin ninguna construcción algebraica nueva. Enumeradas sus $2^{16}$ palabras, la distribución de pesos arranca así:

peso	0	9	12	16	17	20	21	24	25
palabras	1	49	98	931	1764	5292	7826	16 807	16 807

y sigue simétrica hasta la palabra de peso 49, porque el arreglo de todos unos está en el código. Las 49 de peso 9 son $7 \cdot 7$ : las siete palabras de peso 3 del (7,4) en las columnas, por las siete en las filas. Toda palabra de peso mínimo es un producto exterior, el del Paso 3.

03 · La decodificación por etapas

Decodificar el (49,16) como un código lineal cualquiera pediría una tabla de $2^{49 - 16} = 2^{33}$ líderes, más de ocho mil millones. La estructura ofrece otra cosa:

Etapa 1: cada una de las $n_{2}$ filas se decodifica con el decodificador de $C_{1}$ .
Etapa 2: cada una de las $n_{1}$ columnas, ya corregidas por filas, se decodifica con el de $C_{2}$ .

Son $n_{1} + n_{2}$ decodificaciones chicas, catorce síndromes de tres bits en el ejemplo, en vez de una grande. Lo que se paga es algo de garantía:

Proposición. La decodificación por etapas corrige todo patrón de a lo sumo

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

errores, con $t_{i}$ la capacidad de corrección de $C_{i}$ . Contiene a la cota de $t_{1} t_{2}$ errores con que suele enunciarse, que sale de la misma prueba con un paso de más cautela.

Paso 1: a lo sumo $t_{2}$ filas se pasan de $t_{1}$ . Una fila con más de $t_{1}$ errores aporta al menos $t_{1} + 1$ al total. Si fueran $t_{2} + 1$ filas así, sumarían por lo menos $(t_{1} + 1) (t_{2} + 1)$ errores, uno más de los que hay.

Paso 2: la etapa de filas deja errores sólo en esas filas. Las filas con a lo sumo $t_{1}$ errores salen limpias. Las otras pueden salir peor que como entraron —el decodificador de la fila apuesta a un patrón liviano y agrega un error—, pero cada una aporta a lo sumo un bit malo a cada columna.

Paso 3: la etapa de columnas termina. Cada columna tiene entonces a lo sumo $t_{2}$ errores, uno por fila mala, y el decodificador de $C_{2}$ los corrige todos.

La cota es ajustada: con $(t_{1} + 1) (t_{2} + 1)$ errores repartidos en $t_{2} + 1$ filas, $t_{1} + 1$ en cada una, la etapa de filas puede dejar $t_{2} + 1$ errores en una misma columna, y ahí la de columnas se equivoca. En el (49,16,9) la proposición da $2 \cdot 2 - 1 = 3$ , contra los $⌊ (d_{1} d_{2} - 1) / 2 ⌋ = 4$ que la distancia permitiría, y el caso que la rompe son cuatro errores, dos en cada una de dos filas. Lo que eso significa medido patrón por patrón está en el producto corrige más de lo que promete.

Arranca con dos errores en filas y columnas distintas: la etapa de filas los corrige y la de columnas no tiene nada que hacer. Agregá un segundo error en la fila 0: la fila se corrige mal y queda con tres errores, uno en cada una de tres columnas, y la etapa de columnas los levanta uno por uno. Ahora probá dos filas con dos errores cada una, en las mismas columnas: es el caso de la sección 05.

04 · La decodificación iterativa

Cuando la etapa de columnas corrige algo, las filas cambian, y una fila que antes tenía dos errores puede quedar con uno. Repetir el ciclo —filas, columnas, filas, columnas— hasta que una pasada no cambie nada es la decodificación iterativa. No llega en general al decodificador óptimo del producto, pero se le acerca.

Medido en el (49,16,9) enumerando todos los patrones, iterando hasta que el arreglo no se mueve:

errores	patrones	una pasada	iterando
4	211 876	202 615	210 553
5	1 906 884	1 555 407	1 838 529

Una pasada es una etapa de filas y una de columnas. Con 4 errores la iteración rescata 7938 patrones; con 5, 283 122, y el 81,6 % corregido pasa a ser el 96,4 %. En los dos casos todo lo que se rescata se rescata en la segunda pasada: la tercera ya no cambia nada. Con decisión blanda, en la que cada etapa le pasa a la siguiente una medida de confianza en vez de un bit decidido, el mismo esquema da los turbo product codes.

El ejemplo más corto de lo que hace la segunda pasada: errores en las posiciones (0, 0), (0, 1), (1, 0) y (1, 2), por (fila, columna). Las filas 0 y 1 tienen dos errores cada una y se corrigen mal; la etapa de columnas deja tres errores, todos en la columna 0 y en filas distintas. La segunda etapa de filas los ve de a uno y los corrige.

05 · Lo que ninguna pasada arregla

Quedan 1323 patrones de cuatro errores que la iteración no toca, aunque la distancia 9 asegura que lo transmitido es la palabra más cercana. Tienen todos la misma forma: dos filas con dos errores cada una, y los dos pares dentro de la misma palabra de peso 3 del (7,4). Hay 1323 así.

Seguido paso a paso, con errores en (0, 1), (0, 4), (3, 1) y (3, 4):

Paso 1: las dos filas se completan. Las filas 0 y 3 tienen síndrome $h_{1} + h_{4} = 011 + 100 = 111 = h_{2}$ , y el decodificador da vuelta la columna 2 en las dos. Cada fila queda con errores en ${1, 2, 4}$ , que es una palabra de peso 3: seis errores.

Paso 2: las tres columnas se completan. Las columnas 1, 2 y 4 tienen errores en las filas 0 y 3, con síndrome $h_{0} + h_{3} = 110 + 101 = 011 = h_{1}$ . Las tres dan vuelta la fila 1.

Paso 3: lo que sale es una palabra. Quedan nueve errores, en las filas ${0, 1, 3}$ por las columnas ${1, 2, 4}$ : el producto exterior de dos palabras de peso 3, una palabra de peso 9 del código. Todas las filas y todas las columnas tienen síndrome nulo, y ninguna pasada más tiene nada que corregir.

El decodificador entrega, en silencio, una palabra que está a distancia 5 de lo recibido, cuando la transmitida estaba a distancia 4. No es un empate ni un caso dudoso: es una de las palabras de peso mínimo del código, armada por el propio decodificador con los errores del canal. Los 1323 terminan así, en una de las 49 palabras de peso 9. El cuadrado de cuatro esquinas, el ejemplo que suele darse, es el caso en que las dos filas eligen el mismo par: 441 de los 1323.

La otra limitación es la tasa: cada factor la multiplica por algo menor que 1, y componer códigos para ganar distancia la hace caer rápido. Y contra ráfagas, lo que importa no es el código sino el orden en que salen del arreglo los símbolos al canal: está en la ráfaga la corrige el orden, y llevado a una técnica propia, en el intercalador.

Para tener a mano

$C_{1} \otimes C_{2}$ : arreglos de $n_{2}$ filas por $n_{1}$ columnas, cada fila en $C_{1}$ y cada columna en $C_{2}$ . Las checks on checks salen iguales codificando filas o columnas primero.
$n = n_{1} n_{2}$ , $k = k_{1} k_{2}$ , $R = R_{1} R_{2}$ , $d_{min} = d_{1} d_{2}$ . Cota: una fila no nula y sus columnas. Igualdad: el producto exterior de dos palabras de peso mínimo.
(7,4) ⊗ (7,4) = (49,16,9), tasa 0,327, $t = 4$ . Sus 49 palabras de peso 9 son los $7 \cdot 7$ productos exteriores.
Por etapas: filas con $C_{1}$ , después columnas con $C_{2}$ . Corrige todo patrón de hasta $(t_{1} + 1) (t_{2} + 1) - 1$ errores, porque a lo sumo $t_{2}$ filas se pasan de $t_{1}$ . En el (49,16,9) son 3, contra los 4 de la distancia; falla con dos filas de dos errores.
Iterar rescata: con 4 errores quedan sin corregir 1323 de 211 876; con 5, lo corregido pasa del 81,6 % al 96,4 %. Todo en la segunda pasada.
Ninguna pasada arregla los 1323 patrones de dos filas con dos errores dentro de la misma palabra de peso 3: el decodificador los completa hasta una palabra de peso 9.