Desplazar, factorizar, elegir

Los tres ejercicios trabajan con una sola herramienta: los polinomios módulo $X^{15}+1$ y su factorización, que la clase práctica da en su segunda diapositiva:

El primero muestra que girar una palabra de un código cíclico es multiplicar por $X$ y tomar un resto. El sexto, que el código más redundante que contiene a una palabra sale de un máximo común divisor. El séptimo, que con la misma redundancia la distancia depende de qué factores se eligen.

01 · Ejercicio 1: girar es tomar un resto

El enunciado, textual: «Sea la 15-tupla sobre $GF(2)$, con el bit de la izquierda como coeficiente de $X^0$,

$$v=101000000000011$$

1. Escribir $v(X)$.
2. Obtener $v^{(1)}$ y $v^{(3)}$ desplazando directamente la tupla.
3. Obtener $v^{(1)}(X)$ y $v^{(3)}(X)$ por vía algebraica, como el resto de $X^{i}v(X)$ módulo $X^{15}+1$.
4. Verificar que ambos caminos coinciden e indicar qué componentes dieron la vuelta.»

Antes de resolver. Hay que entregar un polinomio, dos tuplas, dos polinomios y una lista de componentes. Lo único que hay que leer bien es la primera línea: el bit de la izquierda es $v_0$, el coeficiente de $X^0$. Los unos están en las posiciones 0, 2, 13 y 14, y las dos últimas son las que van a dar la vuelta.

Las herramientas. El desplazamiento cíclico mueve cada componente un lugar a la derecha y lleva la última al principio:

$$v^{(1)}=(v_{14},v_0,v_1,\dots ,v_{13})$$

En polinomios es la ecuación (5) del apunte, y aplicada $i$ veces da el desplazamiento de orden $i$:

$$v^{(i)}(X)=R_{X^{15}+1}\{X^{i}v(X)\}$$

El resto módulo $X^{15}+1$ se toma sin dividir: como $X^{15}+1\equiv 0$, vale $X^{15}\equiv 1$, y toda potencia $X^{15+j}$ se reemplaza por $X^j$. Está en el concepto de los códigos cíclicos.

El razonamiento. Multiplicar por $X$ suma uno a cada exponente, que es mover cada bit un lugar a la derecha. El bit de la posición 14 pasaría a la 15, que no existe; la reducción $X^{15}\equiv 1$ lo devuelve a la 0. Así que los dos caminos tienen que coincidir, y lo que dio la vuelta es exactamente lo que, después de multiplicar, quedó con exponente 15 o más. En el giro de orden 3 son los términos que estaban en 12, 13 o 14: acá, $v_{13}$ y $v_{14}$.

La resolución.

1. Con un término por cada uno de la tupla:

$$v(X)=1+X^2+X^{13}+X^{14}$$

2. Corriendo la tupla un lugar, y tres:

$$v^{(1)}=110100000000001,v^{(3)}=011101000000000$$

3. Multiplicando y reduciendo con $X^{15}\equiv 1$, $X^{16}\equiv X$ y $X^{17}\equiv X^2$:

4. Leídos como tuplas, $1+X+X^3+X^{14}$ es $110100000000001$ y $X+X^2+X^3+X^5$ es $011101000000000$: los dos caminos dan lo mismo. En el primer giro dio la vuelta $v_{14}$, que pasó a ser el término independiente. En el tercero dieron la vuelta $v_{13}$ y $v_{14}$, que cayeron en $X$ y $X^2$.

02 · Ejercicio 6: el generador más redundante es un máximo común divisor

El enunciado, textual: «Los polinomios siguientes son palabras de códigos cíclicos binarios de longitud $n=15$. Para cada uno, determinar el polinomio generador de mayor grado posible, es decir, el código más redundante que puede contener a esa palabra.

1. $c(X)=1+X^4+X^5$.
2. $c(X)=1+X^8$.

Sugerencia. El generador divide a $c(X)$, y también divide a $X^{15}+1$.»

Antes de resolver. Se entrega un polinomio generador $g(X)$ por palabra, y con él el código: su grado es $n-k$. «Más redundante» es «de mayor grado»: entre todos los códigos cíclicos de largo 15 que tienen a $c(X)$ como palabra, el de menos bits de información.

Las herramientas. Tres teoremas del apunte, en una línea cada uno.

• Teorema 2. Un polinomio de grado menor que $n$ es una palabra del código si y sólo si es múltiplo de $g(X)$.
• Teoremas 3 y 4. $g(X)$ genera un código cíclico $(n,k)$ si y sólo si divide a $X^n+1$ y tiene grado $n-k$.
• La factorización. Con $n$ impar, los factores irreducibles de $X^n+1$ son distintos, así que sus divisores son exactamente los productos de un subconjunto de factores, cada uno a lo sumo una vez.

Lo que se busca es entonces un divisor común de $c(X)$ y $X^{15}+1$, y el de mayor grado es el máximo común divisor. Por la factorización, ese máximo común divisor es el producto de los factores de $X^{15}+1$ que dividen a $c(X)$.

El razonamiento. Hay dos caminos: Euclides, o probar los cinco factores. El segundo es más corto, porque la factorización ya está dada, y cada prueba es una reducción: para tomar el resto módulo $p(X)$ se despeja su potencia más alta y se la reemplaza cada vez que aparece. Para $c(X)=1+X^4+X^5$:

• $1+X$: con $X\equiv 1$, $c\equiv 1+1+1=1$. No divide; es lo mismo que decir que $c(X)$ tiene peso impar.
• $1+X+X^2$: con $X^2\equiv 1+X$ sale $X^3\equiv X+X^2\equiv 1$, así que $X^4\equiv X$ y $X^5\equiv X^2\equiv 1+X$. Queda $c\equiv 1+X+1+X=0$. Divide.
• $1+X+X^4$: con $X^4\equiv 1+X$ y $X^5\equiv X+X^2$, $c\equiv 1+(1+X)+(X+X^2)=X^2$. No divide.
• $1+X^3+X^4$: con $X^4\equiv 1+X^3$ y $X^5\equiv X+X^4\equiv 1+X+X^3$, $c\equiv 1+(1+X^3)+(1+X+X^3)=1+X$. No divide.
• $1+X+X^2+X^3+X^4$: divide a $X^5+1$, así que $X^5\equiv 1$ y $X^4\equiv 1+X+X^2+X^3$. Queda $c\equiv 1+X+X^2+X^3$. No divide.

Uno solo de los cinco. Dividiendo, $c(X)=(1+X+X^2)(1+X+X^3)$, y el segundo factor es irreducible pero no está en la lista: es la parte de $c(X)$ que ningún código cíclico de largo 15 puede absorber.

Para $c(X)=1+X^8$ la primera prueba ya da: $c(1)=1+1=0$, así que $1+X$ divide. Sobre $GF(2)$ el cuadrado de una suma es la suma de los cuadrados, y entonces $1+X^8=(1+X{)}^8$: el factor $1+X$ está ocho veces en $c(X)$, pero una sola en $X^{15}+1$, y el máximo común divisor lo toma una sola vez. Los otros cuatro dejan resto: $X$, $X^2$, $1+X+X^2+X^3$ y $1+X^3$, por las mismas reducciones (por ejemplo, módulo $1+X+X^4$, $X^8=(X^4{)}^2\equiv (1+X{)}^2=1+X^2$).

El camino de Euclides llega a lo mismo sin usar la factorización. Para la primera palabra son cuatro divisiones:

$$1+X^4+X^5=(1+X)(1+X^2+X^4)+(X+X^2+X^3)$$ $$1+X^2+X^4=(1+X)(X+X^2+X^3)+(1+X+X^2)$$ $$X+X^2+X^3=X(1+X+X^2)+0$$

El último resto no nulo es $1+X+X^2$.

Arranca con la palabra del ejercicio 1, que tiene peso par. Cargá después las dos del ejercicio 6 y apostá antes de dividir. Y girá cualquiera de ellas: los restos que no eran cero cambian con cada giro, y los que eran cero siguen en cero. Es porque $X$ es invertible módulo $X^{15}+1$, ya que $X·X^{14}=X^{15}\equiv 1$; entonces $p(X)$ divide a $Xv(X)$ módulo $X^{15}+1$ exactamente cuando divide a $v(X)$. Girar una palabra nunca la saca de un código cíclico: es la definición, vista desde los factores.

La hipótesis del enunciado no es gratis. Recorridos los 32 767 vectores no nulos de largo 15, en 10 125 el máximo común divisor con $X^{15}+1$ da 1: esos no son palabra de ningún código cíclico no trivial de largo 15.

La resolución. El generador buscado es $\mathrm{mcd}(c(X),X^{15}+1)$.

1. $\mathrm{mcd}(1+X^4+X^5,X^{15}+1)=1+X+X^2$: el código es el $(15,13)$ generado por $1+X+X^2$. Es el único cíclico no trivial de largo 15 que contiene a $c(X)$, porque $1+X+X^2$ es irreducible y no tiene otro divisor que sirva.
2. $\mathrm{mcd}(1+X^8,X^{15}+1)=1+X$: el código es el $(15,14)$ de paridad simple, también el único. Se podía anticipar: $c(X)$ tiene peso par, y todo polinomio de peso par tiene a $1+X$ como factor.

Por qué el máximo común divisor: cualquier divisor común de $c(X)$ y $X^{15}+1$ genera un código cíclico que contiene a $c(X)$, y el de mayor grado es el de mayor redundancia.

03 · Ejercicio 7: con la misma redundancia, distancia 5 o 3

El enunciado, textual: «A partir de la factorización de $X^{15}+1$ de la segunda diapositiva:

1. Determinar cuántos códigos cíclicos no triviales de longitud 15 existen.
2. Construir los tres polinomios generadores posibles con redundancia $n-k=8$.
3. Sabiendo que sus distancias mínimas son 5, 5 y 3, indicar cuál conviene y qué se concluye de ello.
4. Verificar que el código $(15,5)$ de referencia se obtiene como producto de tres de los factores.»

Antes de resolver. Se entregan un número, tres polinomios, una elección con su conclusión y una multiplicación. El código $(15,5)$ de referencia es el de la clase práctica, con $g(X)=1+X+X^2+X^4+X^5+X^8+X^{10}$ y distancia mínima $d_{\text{min}}=7$.

Las herramientas. Las del ejercicio 6, más dos. Si $X^n+1$ tiene $f$ factores irreducibles distintos, hay $2^f-2$ códigos cíclicos no triviales de largo $n$: uno por subconjunto, menos el vacío ($g=1$, el $(15,15)$ que acepta todo) y el completo ($g=X^{15}+1$, que sólo tiene la palabra nula). Y en un código lineal la distancia mínima es el menor peso de una palabra no nula.

El razonamiento. Con cinco factores, $2^5-2=30$. Los grados son 1, 2, 4, 4 y 4, y el grado de un producto es la suma de los grados. Para llegar a 8 no sirve el de grado 1 ni el de grado 2: $1+2=3$, $1+2+4=7$, $1+4=5$, $2+4=6$, y con dos de grado 4 ya se llegó. La única forma es $4+4$, dos de los tres factores de grado 4, y hay tres maneras de elegir dos de tres: tres generadores, como dice el enunciado.

Multiplicar es sumar copias corridas: un factor por cada término del otro. Para el primero,

y $X^4$, que aparece tres veces, queda una: $1+X+X^3+X^4+X^5+X^7+X^8$.

La distancia de los tres la da el enunciado, pero la del tercero se puede ver sin enumerar. Como $X^{15}+1=(X^5+1)(1+X^5+X^{10})$ y $X^5+1=(1+X)(1+X+X^2+X^3+X^4)$, el trinomio $1+X^5+X^{10}$ es el producto de los otros tres factores:

Todo generador hecho sólo con $1+X+X^2$, $1+X+X^4$ y $1+X^3+X^4$ divide a $1+X^5+X^{10}$, que tiene grado 10 y, por el Teorema 2, es entonces una palabra de su código: una palabra de peso 3. El tercer generador es $(1+X+X^4)(1+X^3+X^4)$, así que su distancia es a lo sumo 3. Medido sobre el catálogo, son siete los generadores que dividen a $1+X^5+X^{10}$, y los siete tienen $d_{\text{min}}\le 3$. Los otros dos generadores de grado 8 llevan $1+X+X^2+X^3+X^4$ y escapan a ese argumento; su 5 sale de recorrer las 127 palabras no nulas de cada uno.

En los dos de distancia 5, la palabra más liviana de menor grado es el propio $g(X)$, que pesa 5. En el de distancia 3, $g(X)$ pesa 7, y las cinco palabras de peso 3 son $1+X^5+X^{10}$ y sus giros: el patrón tiene período 5, así que sólo hay cinco distintos. Los dos generadores de distancia 5 son además recíprocos uno del otro, $1+X^4+X^6+X^7+X^8$ y $1+X+X^2+X^4+X^8$: el mismo código leído al revés, con la misma distribución de pesos (18 palabras de peso 5, 30 de peso 6, 15 de peso 7).

La resolución.

1. $X^{15}+1$ tiene cinco factores irreducibles distintos, así que hay $2^5-2=30$ códigos cíclicos no triviales de longitud 15.

2. Ocho se descompone sólo como $4+4$, tomando dos de los tres factores de grado 4:

3. Conviene cualquiera de los dos primeros: $d_{\text{min}}=5$ da una capacidad de corrección $t=2$, y el tercero, con $d_{\text{min}}=3$, corrige uno solo con los mismos ocho bits de paridad. La conclusión: la redundancia no determina la distancia mínima; la elección del polinomio generador sí. El tercero pierde porque divide a $1+X^5+X^{10}$.

4. Primero el producto de dos, sumando copias corridas de $1+X+X^4$:

Después, ese resultado por $1+X+X^2+X^3+X^4$: cinco copias de $a(X)=1+X^3+X^4+X^5+X^6$, corridas 0, 1, 2, 3 y 4 lugares. Cada exponente queda si aparece una cantidad impar de veces:

que es el $g(X)$ del $(15,5)$. Los dos factores que quedaron afuera dan su polinomio de paridad, el mismo que da la clase práctica:

$$h(X)=(1+X)(1+X^3+X^4)=1+X+X^3+X^5$$

04 · Lo que se lleva a otros ejercicios

Reducir es reemplazar la potencia más alta. Módulo $X^{15}+1$ es $X^{15}\equiv 1$; módulo $1+X+X^2$ es $X^2\equiv 1+X$. Es la misma jugada que calcula la paridad de un codificador sistemático, $R_{g(X)}\{X^{n-k}u(X)\}$, y el síndrome, $R_{g(X)}\{r(X)\}$: está hecha ciclo a ciclo en el registro ciclo a ciclo.

La factorización es el menú. Toda pregunta sobre los cíclicos de largo 15 es una pregunta sobre qué subconjunto de los cinco factores se toma: el generador es lo que entra, el polinomio de paridad es lo que queda afuera, y el código más redundante que contiene a una palabra son los factores que la dividen.

Un trinomio de peso 3 es una cota. Si $g(X)$ divide a un polinomio de grado menor que $n$ con pocos términos, ese polinomio es una palabra y $d_{\text{min}}$ no puede superar su peso. Buscar un múltiplo liviano de $g(X)$ es la forma más rápida de acotar la distancia sin enumerar. Con $n-k=10$ pasa lo mismo: $1+X^5+X^{10}$ es en sí un generador, el de un $(15,5)$ con distancia 3, contra el 7 del $(15,5)$ de referencia. Lo que la redundancia hace con la mejor distancia, redundancia por redundancia, está en un bit más de redundancia puede costar distancia.

05 · Las trampas

Cuál es la posición 0. El enunciado lo dice: el bit de la izquierda es $X^0$. Leída al revés, $101000000000011$ sería $1+X+X^{12}+X^{14}$, otro polinomio. Para los ejercicios de registros importa lo mismo: el mensaje entra al registro empezando por el coeficiente de mayor orden, el que está escrito más a la derecha.

Hacia dónde gira. $v^{(1)}$ es multiplicar por $X$: cada bit va a la derecha y el de mayor orden, $v_{14}$, vuelve al principio. Girar hacia la izquierda es multiplicar por $X^{14}$, que módulo $X^{15}+1$ es el inverso de $X$.

La multiplicidad. $1+X^8=(1+X{)}^8$, pero el máximo común divisor con $X^{15}+1$ es $1+X$ a la primera, no a la octava. Un generador de largo 15 no puede tener un factor repetido, porque $X^{15}+1$ no lo tiene. La cuenta $2^f-2$ usa justamente eso: con $n$ impar los factores son distintos.

Grado contra distancia. Que los tres generadores tengan grado 8 dice que los tres códigos son $(15,7)$ y nada sobre su distancia. Quien elige por la redundancia elige a ciegas entre 5 y 3.

Para tener a mano

1. $v^{(i)}(X)=R_{X^n+1}\{X^{i}v(X)\}$, con $X^n\equiv 1$. Dan la vuelta los términos que, multiplicados, quedan con exponente $n$ o más.
2. Ejercicio 1: $v(X)=1+X^2+X^{13}+X^{14}$, $v^{(1)}(X)=1+X+X^3+X^{14}$, $v^{(3)}(X)=X+X^2+X^3+X^5$; dan la vuelta $v_{14}$, y después $v_{13}$ y $v_{14}$.
3. El generador más redundante que contiene a $c(X)$ es $\mathrm{mcd}(c(X),X^n+1)$: el producto de los factores de $X^n+1$ que dividen a $c(X)$, cada uno una vez.
4. Ejercicio 6: $1+X+X^2$, el $(15,13)$; y $1+X$, el $(15,14)$ de paridad simple.
5. $2^f-2$ cíclicos no triviales; para largo 15, 30. Con $n-k=8$ hay tres, de distancias 5, 5 y 3.
6. $1+X^5+X^{10}$ es el producto de $1+X+X^2$, $1+X+X^4$ y $1+X^3+X^4$: todo generador que lo divide tiene una palabra de peso 3.
7. El $(15,5)$ de referencia, con $d_{\text{min}}=7$, tiene $g(X)=1+X+X^2+X^4+X^5+X^8+X^{10}$, el producto de $1+X+X^2$, $1+X+X^4$ y $1+X+X^2+X^3+X^4$; lo que queda afuera da $h(X)=1+X+X^3+X^5$.