El Golay por dentro

En la Unidad 4 el Golay (23,12) apareció por su distribución de pesos y por ser perfecto; eso, y sus octadas, está en el código de Golay. Acá se lo mira como código cíclico: todo el código queda guardado en un polinomio de grado 11, y las tres cuentas de estos ejercicios —un polinomio de paridad, una palabra sistemática, un código acortado— salen de multiplicar, dividir y leer coeficientes al revés. Los tres usan los mismos datos, los de la clase práctica:

X^{23} + 1 = (X + 1) g_{1} (X) g_{2} (X)

\begin{aligned} g_{1} (X) & = 1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10} + X^{11} \\ g_{2} (X) & = 1 + X + X^{5} + X^{6} + X^{7} + X^{9} + X^{11} \end{aligned}

Los vectores se escriben con la posición 0 a la izquierda: el bit $i$ es el coeficiente de $X^{i}$ .

01 · Ejercicio 2: los dos generadores son recíprocos

El enunciado, textual:

«Verificar que $g_{2} (X)$ es el polinomio recíproco de $g_{1} (X)$ , es decir, que $g_{2} (X) = X^{11} g_{1} (X^{- 1})$ .
Sabiendo que $X^{23} + 1 = (X + 1) g_{1} (X) g_{2} (X)$ , obtener el polinomio de paridad $h (X)$ del código generado por $g_{1} (X)$ , sin efectuar la división.
Justificar por qué $g_{1} (X)$ y $g_{2} (X)$ generan códigos (23,12) y por qué ambos son equivalentes.»

Antes de resolver. Son tres entregas de naturaleza distinta. La primera es una comprobación: una igualdad entre dos polinomios, que se ve en los exponentes. La segunda es un polinomio, $h (X)$ , que tiene que salir de grado $k = 12$ . La tercera son dos argumentos, sin cuentas: uno por los parámetros y otro por la equivalencia. «Sin efectuar la división» es una pista: la factorización ya la trae hecha.

Las herramientas. Cuatro resultados de la teoría, los de el polinomio generador:

El recíproco de un polinomio $p (X)$ de grado $m$ es $X^{m} p (X^{- 1})$ : los mismos coeficientes leídos al revés. El término $X^{e}$ pasa a $X^{m - e}$ .
Teorema 3: el polinomio generador de un cíclico $(n, k)$ divide a $X^{n} + 1$ y tiene grado $n - k$ . Teorema 4, el recíproco: todo divisor de $X^{n} + 1$ de grado $n - k$ genera un cíclico $(n, k)$ .
El polinomio de paridad es $h (X) = (X^{n} + 1) / g (X)$ , de grado $k$ .
Dos códigos son equivalentes si una misma permutación de las posiciones lleva las palabras de uno a las del otro. Una permutación no cambia pesos: tienen la misma distribución y la misma $d_{min}$ .

Paso 1: el recíproco se ve en los exponentes. Los de $g_{1} (X)$ son ${0, 2, 4, 5, 6, 10, 11}$ . Restados de 11 dan ${11, 9, 7, 6, 5, 1, 0}$ , que son exactamente los de $g_{2} (X)$ . Es la comprobación entera: un polinomio y su recíproco tienen la misma cantidad de términos, siete acá, y los exponentes se reflejan alrededor de 5,5.

Paso 2: $h (X)$ es lo que queda al sacar $g_{1} (X)$ de la factorización. La factorización dice $X^{23} + 1 = g_{1} (X) \cdot (X + 1) g_{2} (X)$ , así que el cociente por $g_{1} (X)$ es el resto de los factores, $(X + 1) g_{2} (X)$ . Multiplicar por $X + 1$ es sumar el polinomio con su copia corrida un lugar:

\begin{aligned} g_{2} (X) & = 1 + X + X^{5} + X^{6} + X^{7} + X^{9} + X^{11} \\ X g_{2} (X) & = X + X^{2} + X^{6} + X^{7} + X^{8} + X^{10} + X^{12} \\ h (X) & = 1 + X^{2} + X^{5} + X^{8} + X^{9} + X^{10} + X^{11} + X^{12} \end{aligned}

$X$ , $X^{6}$ y $X^{7}$ aparecen en los dos renglones y se cancelan. Queda grado 12, como tenía que ser, y multiplicado por $g_{1} (X)$ da $X^{23} + 1$ .

Paso 3: los parámetros salen del grado. $g_{1} (X)$ y $g_{2} (X)$ son factores de $X^{23} + 1$ y tienen grado 11. Por el Teorema 4, cada uno genera un cíclico con $n = 23$ y $n - k = 11$ : un (23,12).

Paso 4: leer al revés lleva un código al otro. Una palabra del código de $g_{1} (X)$ es $v (X) = a (X) g_{1} (X)$ , con $a (X)$ de grado a lo sumo 11. Leerla al revés, de la posición 22 a la 0, es formar $v^{*} (X) = X^{22} v (X^{- 1})$ , y el 22 se reparte en 11 y 11:

v^{*} (X) = [X^{11} a (X^{- 1})] [X^{11} g_{1} (X^{- 1})] = a^{*} (X) g_{2} (X)

Como $a (X)$ tiene grado a lo sumo 11, $a^{*} (X)$ es un polinomio, y $v^{*} (X)$ es un múltiplo de $g_{2} (X)$ de grado menor que 23: una palabra del otro código, con el mismo peso. La permutación es $i \mapsto 22 - i$ , y por eso los dos códigos son equivalentes.

Equivalentes no quiere decir iguales. Una palabra que estuviera en los dos sería múltiplo de $g_{1} (X)$ y de $g_{2} (X)$ , dos irreducibles distintos, y por lo tanto de su producto $g_{1} (X) g_{2} (X)$ , que es $(X^{23} + 1) / (X + 1)$ : la suma de todas las potencias de $X$ hasta $X^{22}$ , de grado 22. Los únicos múltiplos de grado menor que 23 son el cero y él mismo: los dos códigos comparten exactamente dos palabras, la nula y la de todos unos. Enumeradas las 4096 palabras del código de $g_{1} (X)$ , las 4096 leídas al revés caen en el de $g_{2} (X)$ , las dos distribuciones de pesos coinciden término a término, y las comunes son esas dos.

La resolución, como se entrega.

Los exponentes de $g_{1} (X)$ son ${0, 2, 4, 5, 6, 10, 11}$ ; restados de 11, ${11, 9, 7, 6, 5, 1, 0}$ , los de $g_{2} (X)$ . Luego $g_{2} (X) = X^{11} g_{1} (X^{- 1})$ .
$h (X) = (X^{23} + 1) / g_{1} (X) = (X + 1) g_{2} (X)$ , que desarrollado es $1 + X^{2} + X^{5} + X^{8} + X^{9} + X^{10} + X^{11} + X^{12}$ , de grado $12 = k$ .
$g_{1} (X)$ y $g_{2} (X)$ dividen a $X^{23} + 1$ y tienen grado $11 = n - k$ : por el Teorema 4 generan cíclicos (23,12). Si $v (X) = a (X) g_{1} (X)$ , su lectura al revés es $X^{22} v (X^{- 1}) = [X^{11} a (X^{- 1})] g_{2} (X)$ , palabra del código de $g_{2} (X)$ con el mismo peso. La permutación $i \mapsto 22 - i$ lleva un código al otro: son equivalentes.

02 · Ejercicio 3: codificar es una división

«Se transmite el mensaje $u = 100100000000$ , es decir $u (X) = 1 + X^{3}$ , con el código generado por $g_{1} (X)$ .

Escribir $X^{n - k} u (X)$ .
Dividir por $g_{1} (X)$ y obtener el polinomio de paridad $b (X)$ .
Armar la palabra de código $v$ en forma sistemática.
Calcular el peso de $v$ y comentar el resultado.»

Antes de resolver. De las cuatro entregas, la que cuesta es la segunda: un resto de grado menor que 11. Las otras son acomodar —correr el mensaje, pegar paridad y mensaje— y un número, el peso, con una lectura: compararlo con la distancia mínima. Lo que se entrega al final es una cadena de 23 bits.

Las herramientas. La forma sistemática cíclica del codificador cíclico, la ecuación (15) del apunte:

v (X) = b (X) + X^{n - k} u (X), b (X) = R_{g (X)} {X^{n - k} u (X)}

La paridad ocupa las posiciones 0 a $n - k - 1$ y el mensaje, las últimas $k$ . Y del Golay se usa su enumerador de pesos: $d_{min} = 7$ , con 253 palabras de peso 7 entre las 4096.

Paso 1: correr el mensaje. Con $n - k = 11$ , $X^{11} u (X) = X^{11} + X^{14}$ . El mensaje queda en las posiciones 11 y 14, donde va a quedar en la palabra.

Paso 2: dividir, restando el generador corrido debajo del uno más alto. Sobre $GF(2)$ restar es sumar. Cada paso suma $g_{1} (X)$ corrido hasta que su $X^{11}$ caiga sobre el término de mayor grado, que se cancela. Con un bit por columna se ve qué se va:

posición	1	2	3	4	5	6	7	8	9	11	12	13	14
$X^{11} u (X)$	0	0	0	0	0	0	0	0	0	1	0	0	1
$+ X^{3} g_{1} (X)$	0	0	1	0	1	0	1	1	1	0	0	1	1
$=$	0	0	1	0	1	0	1	1	1	1	0	1	0
$+ X^{2} g_{1} (X)$	0	1	0	1	0	1	1	1	0	0	1	1	0
$=$	0	1	1	1	1	1	0	0	1	1	1	0	0
$+ X g_{1} (X)$	1	0	1	0	1	1	1	0	0	1	1	0	0
$= b (X)$	1	1	0	1	0	0	1	0	1	0	0	0	0

Tres restas, con $X^{3}$ , $X^{2}$ y $X$ : el cociente es $X + X^{2} + X^{3}$ , que no se pide. Cuando el grado baja de 11 la división terminó, y lo que queda es $b (X) = X + X^{2} + X^{4} + X^{7} + X^{9}$ .

El mismo resto sale sin dividir, reduciendo término a término. Como $g_{1} (X) \equiv 0$ , $X^{11} \equiv 1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10}$ , y cada potencia más alta se baja multiplicando por $X$ y volviendo a reemplazar. Es lo que se hace en el ejercicio 11.

Paso 3: armar la palabra. Paridad primero, en las posiciones 0 a 10, y el mensaje detrás, en las 11 a 22.

Paso 4: el peso, y lo que dice. La paridad aporta 5 unos y el mensaje 2: $w (v) = 7$ , la distancia mínima. Es una de las 253 palabras de peso mínimo. Que salga una no es raro con un mensaje de peso 2: la palabra pesa por lo menos 7, el mensaje pone 2, y a la paridad le alcanza con poner 5. Medido sobre los 66 mensajes de peso 2, 30 dan una palabra de peso 7; sobre los 12 de peso 1, siete. Un mensaje de peso 1 pide por lo menos 6 unos de paridad, y los restos $R_{g_{1} (X)} {X^{11 + j}}$ pesan 6 o 7: está en la tabla de la sección 04.

Arranca con el mensaje del ejercicio y la división sin hacer: el mensaje ya está en su lugar, y la paridad no. Tres restas la terminan. Después probá $u (X) = 1$ , un solo bit, y mirá cuántos unos pone la paridad. Con $g_{2} (X)$ el mismo mensaje da otra palabra, y leída al revés cae en el código de $g_{1} (X)$ , nunca en el suyo, salvo un caso: el mensaje de todos unos.

La resolución, como se entrega.

$X^{11} u (X) = X^{11} + X^{14}$ .
$b (X) = R_{g_{1} (X)} {X^{11} + X^{14}}$ , que da $b (X) = X + X^{2} + X^{4} + X^{7} + X^{9}$ , con cociente $X + X^{2} + X^{3}$ .
$v = 01101001010 100100000000$ : once bits de paridad y doce de mensaje.
$w (v) = 7 = d_{min}$ : es una de las 253 palabras de peso mínimo del Golay. No es casualidad: con un mensaje de peso 2, a la paridad le alcanzan 5 unos para llegar a 7.

03 · Ejercicio 11: acortar sin perder distancia

«Se acorta el Golay (23,12) suprimiendo las $l = 3$ posiciones de información de mayor orden.

Indicar los parámetros del código acortado y qué ocurre con su distancia mínima.
Justificar si el código acortado sigue siendo cíclico.
Al ingresar la palabra recibida por el extremo derecho del registro de síndrome hacen falta $l$ desplazamientos adicionales. Calcular el polinomio $ρ (X)$ , resto de $X^{n - k + l}$ módulo $g_{1} (X)$ , que permite evitarlos.»

Antes de resolver. Tres entregas: un par $(n, k)$ con una afirmación sobre $d_{min}$ ; un sí o un no, con su porqué; y un polinomio de grado menor que 11. El tercer punto trae su propia fórmula, así que la cuenta es directa; lo que hay que entender es por qué hacen falta esos desplazamientos.

Las herramientas. Las del código acortado, que en la Unidad 4 se armaban sacando columnas de una matriz y acá salen de un cíclico, como en los CRC y los códigos acortados:

De un cíclico $(n, k)$ se toman las palabras con las $l$ posiciones de información de mayor orden en cero, y esas posiciones no se transmiten: queda un $(n - l, k - l)$ .
Es un subconjunto del código original, así que su distancia mínima no puede bajar.
El codificador y el circuito de síndrome del original sirven sin cambios, y con la entrada por la derecha se corrige la espera con $ρ (X) = R_{g (X)} {X^{n - k + l}}$ , la ecuación (31).

Paso 1: los parámetros. Con $l = 3$ sale un (20,9), de tasa $9 / 20 = 0,45$ contra los $12 / 23 \approx 0,522$ del Golay. Las tres posiciones que se suprimen son las del mensaje de mayor orden, $u_{9}$ , $u_{10}$ y $u_{11}$ , que en la palabra están en las posiciones 20, 21 y 22: el final de la cadena.

Paso 2: la distancia no baja, y acá tampoco sube. Por ser un subconjunto, $d_{min} \geq 7$ . Para saber si es exactamente 7 alcanza con una palabra de peso 7 que sobreviva, y ya hay una a mano: la del ejercicio 3 tiene su último uno en la posición 14, así que sus posiciones 20 a 22 son cero y está en el (20,9). La distancia es 7. Enumeradas las 512 palabras del acortado, sobreviven 80 de las 253 de peso 7:

peso	0	7	8	11	12	15	16	23
(23, 12)	1	253	506	1288	1288	506	253	1
(20, 9)	1	80	130	160	120	16	5	0

Lo que sí se pierde es la perfección. Una esfera de radio 3 en 20 bits tiene $1 + 20 + 190 + 1140 = 1351$ vectores, y las 512 esferas cubren $691 712$ de los $2^{20} = 1 048 576$ : el 65,97 %. El acortado sigue corrigiendo tres errores, pero un tercio de lo que puede llegar queda a más de tres de toda palabra.

Paso 3: deja de ser cíclico. Girar una palabra $v$ del (20,9) es calcular $X v (X)$ módulo $X^{20} + 1$ . Si $v_{19} = 0$ , el giro es $X v (X)$ , un múltiplo de $g_{1} (X)$ de grado menor que 20: sigue en el código. Si $v_{19} = 1$ , el giro es $X v (X) + X^{20} + 1$ , y su síndrome es

R_{g_{1} (X)} {X^{20} + 1} = 1 + X^{2} + X^{4} + X^{5} + X^{7} + X^{8} + X^{9} + X^{10} \neq 0

El giro se cae del código. Como $v_{19}$ es el bit de mensaje $u_{8}$ , eso le pasa a la mitad: de las 512 palabras, 256 siguen y 256 no. Con $u (X) = X^{8}$ , la palabra es $X + X^{3} + X^{4} + X^{6} + X^{7} + X^{8} + X^{9} + X^{19}$ , y girada da $1 + X^{2} + X^{4} + X^{5} + X^{7} + X^{8} + X^{9} + X^{10}$ , que tiene grado 10: es su propio resto, y no es cero. En el anillo original de 23 posiciones se ve lo mismo de otro modo: ese giro lleva el uno de la posición 19 a la 20, que en el acortado no existe.

Paso 4: por qué hacen falta $l$ desplazamientos. Entrar la palabra recibida por el extremo derecho del registro equivale a multiplicarla por $X^{11}$ : después de los $n - l = 20$ ciclos, el registro tiene $R_{g_{1} (X)} {X^{11} r (X)}$ . Pero el decodificador del (23,12) —un Meggitt, por ejemplo— examina primero la posición $n - 1 = 22$ , y en la palabra acortada el dígito de mayor orden, $r_{19}$ , está tres lugares más abajo. Hay que llevarlo arriba, multiplicando por $X^{3}$ : lo que hace falta es $R_{g_{1} (X)} {X^{14} r (X)}$ , y por la derecha eso son tres desplazamientos más. Con $ρ (X) = R_{g_{1} (X)} {X^{14}}$ como segundo juego de conexiones de entrada, cada bit entra ya multiplicado por $X^{14}$ y el síndrome queda listo al ciclo 20.

La cuenta de $ρ (X)$ es la del paso 2 del ejercicio 3: arrancar de $X^{11} \equiv 1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10}$ y, en cada renglón, multiplicar por $X$ y reemplazar el $X^{11}$ que aparezca. Es lo mismo que hace el registro en cada ciclo:

\begin{matrix} X^{12} & \equiv & X + X^{3} + X^{5} + X^{6} + X^{7} + X^{11} \equiv 1 + X + X^{2} + X^{3} + X^{4} + X^{7} + X^{10} \\ X^{13} & \equiv & X + X^{2} + X^{3} + X^{4} + X^{5} + X^{8} + X^{11} \equiv 1 + X + X^{3} + X^{6} + X^{8} + X^{10} \\ X^{14} & \equiv & X + X^{2} + X^{4} + X^{7} + X^{9} + X^{11} \equiv 1 + X + X^{5} + X^{6} + X^{7} + X^{9} + X^{10} \end{matrix}

El último renglón es $ρ (X)$ . El mismo cálculo, para el (28,23) que sale de acortar un Hamming, está en el ejemplo del apunte.

La resolución, como se entrega.

Un (20,9) lineal. Sus palabras son un subconjunto de las del Golay, así que $d_{min} \geq 7$ ; la palabra de peso 7 del ejercicio 3 tiene ceros en las posiciones 20 a 22, así que $d_{min} = 7$ y sigue corrigiendo $t = 3$ .
No es cíclico. Si $v_{19} = 1$ , el giro de $v$ es $X v (X) + X^{20} + 1$ , con síndrome $R_{g_{1} (X)} {X^{20} + 1} \neq 0$ : no es palabra.
$n - k + l = 14$ : $ρ (X) = R_{g_{1} (X)} {X^{14}}$ , que es $1 + X + X^{5} + X^{6} + X^{7} + X^{9} + X^{10}$ .

04 · Lo que se lleva a otros ejercicios

La tabla de restos. Todo resto módulo $g_{1} (X)$ de un polinomio de grado menor que 23 es una suma de filas de esta tabla, más los términos de grado menor que 11, que quedan como están:

potencia	resto · posiciones 0 a 10	peso
$X^{11}$	10101110001	6
$X^{12}$	11111001001	7
$X^{13}$	11010010101	6
$X^{14}$	11000111011	7
$X^{15}$	11001101100	6
$X^{16}$	01100110110	6
$X^{17}$	00110011011	6
$X^{18}$	10110111100	7
$X^{19}$	01011011110	7
$X^{20}$	00101101111	7
$X^{21}$	10111000110	6
$X^{22}$	01011100011	6

El ejercicio 3 y el 11 se cruzan acá. El resto es lineal, así que $R_{g_{1} (X)} {X^{11} + X^{14}} = R_{g_{1} (X)} {X^{11}} + R_{g_{1} (X)} {X^{14}}$ : la suma de las dos filas destacadas, $10101110001 + 11000111011 = 01101001010$ , es la paridad del ejercicio 3, y la segunda fila es el $ρ (X)$ del 11.

El recíproco da un código equivalente, siempre. El argumento del paso 4 del ejercicio 2 no usa nada del Golay: para cualquier cíclico, el generado por el recíproco del generador es el mismo código leído al revés. Y de ahí sale el dual: el apunte dice que lo genera el recíproco de $h (X)$ , $X^{12} h (X^{- 1})$ . El recíproco de $(X + 1) g_{2} (X)$ es $(X + 1) g_{1} (X)$ , y sus múltiplos son las palabras del Golay de peso par: el dual del (23,12) es un (23,11) metido adentro de él, con $1 + 506 + 1288 + 253 = 2048$ palabras, las de peso 0, 8, 12 y 16 de la tabla.

Acortar no cambia el circuito. El codificador del (20,9) es el del Golay con tres ceros de más en el mensaje, que no alteran la división. Del lado del síndrome lo único que cambia es por dónde entran los bits: $ρ (X)$ es cableado, no un circuito nuevo. Ciclo a ciclo, el registro está en el registro ciclo a ciclo.

05 · Las trampas

La posición 0 está a la izquierda. $u = 100100000000$ es $1 + X^{3}$ , no $X^{8} + X^{11}$ .
La paridad va primero y el mensaje al final, al revés que en la forma sistemática de la Unidad 3. La palabra del ejercicio 3 empieza con los once bits de $b (X)$ .
«De mayor orden» es el final de la cadena. Acortar en $l = 3$ suprime $u_{9}$ , $u_{10}$ y $u_{11}$ , las posiciones 20 a 22, no los tres primeros bits que se escriben.
El registro recibe primero el bit de mayor orden: $u_{11}$ al codificar, $r_{22}$ al calcular el síndrome, $r_{19}$ en el acortado. Por eso la espera del ejercicio 11 es de $l$ ciclos.
Dos «al revés» distintos. El recíproco de un polinomio de grado 11 manda el exponente $e$ a $11 - e$ ; leer una palabra al revés manda la posición $i$ a $22 - i$ , porque se refleja en el largo $n - 1$ , no en el grado.
«Polinomio de paridad» nombra dos cosas. En el ejercicio 2 es $h (X)$ , de grado $k = 12$ ; en el 3 es $b (X)$ , la paridad de una palabra, de grado menor que $n - k = 11$ .

Para tener a mano

$X^{23} + 1 = (X + 1) g_{1} (X) g_{2} (X)$ , con $g_{2} (X) = X^{11} g_{1} (X^{- 1})$ : los exponentes de uno son 11 menos los del otro.
$h (X) = (X + 1) g_{2} (X)$ , sin dividir: es el resto de la factorización. Vale $1 + X^{2} + X^{5} + X^{8} + X^{9} + X^{10} + X^{11} + X^{12}$ .
Los códigos de $g_{1} (X)$ y $g_{2} (X)$ son el mismo leído al revés ( $i \mapsto 22 - i$ ): equivalentes, y comparten sólo la palabra nula y la de todos unos.
$b (X) = R_{g_{1} (X)} {X^{11} u (X)}$ ; con $u (X) = 1 + X^{3}$ , $v = 01101001010 100100000000$ , de peso 7.
$X^{11} \equiv 1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10}$ , y cada potencia siguiente es multiplicar por $X$ y volver a reemplazar.
Acortado en 3: (20,9), $d_{min} = 7$ , ya no perfecto ni cíclico; $ρ (X) = R_{g_{1} (X)} {X^{14}}$ , que es $1 + X + X^{5} + X^{6} + X^{7} + X^{9} + X^{10}$ .