El polinomio generador

Un código cíclico $(n,k)$ tiene $2^k$ palabras, y todas salen de una sola: la de menor grado. Con ese polinomio se codifica, se verifica si algo es palabra y se construyen códigos nuevos sin escribir una matriz. Cuatro teoremas dicen qué es y cuáles hay.

01 · La palabra de menor grado

Las palabras se escriben como polinomios, $v(X)=v_0+v_{1}X+\cdots +v_{n-1}{X}^{n-1}$, y girar una palabra un lugar es multiplicarla por $X$ módulo $X^n+1$: la potencia $X^n$ que se pasa vuelve como $1$.

Teorema 1. Sea $C$ un código cíclico $(n,k)$ no trivial. Entre sus palabras no nulas hay una sola de grado mínimo. Ese polinomio, el polinomio generador $g(X)$, tiene término independiente $g_0=1$ y grado $n-k$.

Sea $g(X)=g_0+g_{1}X+\cdots +g_r{X}^r$ una palabra no nula de grado mínimo $r$. El grado se prueba en la sección siguiente, porque usa el Teorema 2; las otras dos partes salen ya.

Paso 1: el término independiente es 1. Si fuera $g_0=0$, sería $g(X)=X\tilde{g}(X)$, con $\tilde{g}$ de grado $r-1$. Girar $g(X)$ unos $n-1$ lugares da $X^{n-1}g(X)=X^n\tilde{g}(X)\equiv \tilde{g}(X)$: el giro de una palabra es una palabra, y ésta tendría grado menor que $r$.

Paso 2: es única. Si hubiera dos palabras distintas de grado $r$, sobre $\mathrm{GF}(2)$ las dos tienen un 1 en $X^r$. Su suma es una palabra, porque el código es lineal, no es nula, porque son distintas, y tiene grado menor que $r$.

02 · Las palabras son sus múltiplos

Teorema 2. Un polinomio $v(X)$ de grado menor que $n$ es palabra de $C$ si y sólo si es múltiplo de $g(X)$.

Paso 1: los $X^{i}g(X)$ son palabras. Para $i\le n-1-r$, el producto $X^{i}g(X)$ tiene grado a lo sumo $n-1$: es el giro de $g(X)$ en $i$ lugares, sin que nada dé la vuelta. Por linealidad, $a(X)g(X)$ es palabra para todo $a(X)$ de grado a lo sumo $n-1-r$.

Paso 2: el resto de una palabra es cero. Dividiendo una palabra por $g(X)$ queda $v(X)=a(X)g(X)+b(X)$, con grado de $b(X)$ menor que $r$. Entonces $b(X)=v(X)+a(X)g(X)$ es suma de dos palabras, y es palabra. Como su grado está por debajo del mínimo, $b(X)=0$.

Paso 3: la vuelta. Si $v(X)=u(X)g(X)$ con grado menor que $n$, es una suma de polinomios $X^{i}g(X)$ con $i\le n-1-r$, todos palabras.

El grado, que cierra el Teorema 1. Las palabras son entonces los productos $u(X)g(X)$ con grado de $u(X)$ a lo sumo $n-1-r$: hay $2^{n-r}$, todos distintos. El código tiene $2^k$, así que $r=n-k$.

Dos consecuencias. La primera es un codificador: el mensaje $u(X)=u_0+\cdots +u_{k-1}{X}^{k-1}$ va a la palabra $v(X)=u(X)g(X)$. La segunda es una prueba de pertenencia: $r(X)$ es palabra si y sólo si $R_g\{r(X)\}=0$. Ese resto es el síndrome de un código cíclico, y la división se hace con un registro de desplazamiento de $n-k$ etapas.

03 · Divide a Xⁿ + 1, y todo divisor genera

Teorema 3. El polinomio generador de un código cíclico $(n,k)$ divide a $X^n+1$.

Paso 1: un giro de $k$ lugares. El producto $X^{k}g(X)$ tiene grado exactamente $n$. Reducirlo módulo $X^n+1$ es restarle $X^n+1$ una vez, y lo que queda es el giro de $g(X)$ en $k$ lugares:

$$X^{k}g(X)=(X^n+1)+g^{(k)}(X)$$

Paso 2: el giro es múltiplo. $g^{(k)}(X)$ es palabra, y por el Teorema 2 vale $a(X)g(X)$. Despejando,

$$X^n+1=[X^k+a(X)]g(X)$$

Teorema 4, el recíproco. Si $g(X)$ divide a $X^n+1$ y tiene grado $n-k$, sus múltiplos de grado menor que $n$ forman un código cíclico $(n,k)$.

Paso 1: es lineal y tiene dimensión $k$. Los múltiplos $u(X)g(X)$ con grado de $u(X)$ menor que $k$ son $2^k$, distintos, y la suma de dos es otro.

Paso 2: es cerrado bajo el giro. Girar $v(X)=u(X)g(X)$ un lugar es multiplicar por $X$ y, si $v_{n-1}$ era 1, restar $X^n+1$. Con $X^n+1=h(X)g(X)$,

$$\begin{array}{rl}{v}^{(1)}(X)& =Xv(X)+v_{n-1}(X^n+1)\\ & =[Xu(X)+v_{n-1}h(X)]g(X)\end{array}$$

que es múltiplo de $g(X)$ y tiene grado menor que $n$: está en el código.

Los dos juntos dicen que los códigos cíclicos de largo $n$ son exactamente los divisores de $X^n+1$, uno por divisor. La pregunta «¿qué códigos cíclicos hay?» se vuelve una factorización.

04 · Construir es factorizar

La receta: se fija $n$, se factoriza $X^n+1$ en irreducibles sobre $\mathrm{GF}(2)$, y cada producto de algunos de esos factores es un polinomio generador. Su grado, que es la redundancia $n-k$, es la suma de los grados de los factores elegidos. Si hay $f$ factores distintos, hay $2^f$ divisores; dos son triviales —$g(X)=1$, que da todos los vectores, y $g(X)=X^n+1$, que deja sólo el cero—, y quedan

$$2^f-2$$

códigos cíclicos no triviales de largo $n$. Para $n=15$ son cinco factores:

$$\begin{array}{rl}{X}^{15}+1& =(1+X)(1+X+X^2)(1+X+X^4)\\ & ·(1+X^3+X^4)(1+X+X^2+X^3+X^4)\end{array}$$

y $2^5-2=30$ códigos. Los tres de grado 4 son irreducibles, pero sólo dos son primitivos: $1+X+X^4$ y $1+X^3+X^4$, que además son recíprocos uno del otro. El tercero, $1+X+X^2+X^3+X^4$, divide a $X^5+1$ y su $X$ tiene orden 5, no 15.

Elegir $1+X+X^4$ y $1+X+X^2+X^3+X^4$ da

$$\begin{array}{rl}g(X)& =(1+X+X^4)(1+X+X^2+X^3+X^4)\\ & =1+X^4+X^6+X^7+X^8\end{array}$$

de grado $4+4=8$: un (15,7). Su distancia mínima no se lee en los grados: enumeradas sus $2^7$ palabras, $d_{\text{min}}=5$. Lo que la factorización fija es $k$; la distancia depende de cuáles factores entran, y con la misma redundancia hay cíclicos mejores y peores. Hasta dónde llega eso en largo 15 está en un bit más de redundancia puede costar distancia.

Arranca sin factores: $g(X)=1$ genera todos los vectores y no corrige nada. Elegí $1+X+X^4$ sola: es el Hamming (15,11), con $d_{\text{min}}=3$. Cambiala por $1+X+X^2+X^3+X^4$, del mismo grado: la redundancia no se mueve y la distancia baja a 2. Volvé a $1+X+X^4$ y pasá al dual: no aparecen los cuatro factores que faltaban, aparece uno cambiado por su recíproco. Después pasá al código de $h(X)$ y mirá la última lectura.

05 · La matriz generadora de Toeplitz

El código es lineal, así que tiene una matriz generadora. Los $k$ polinomios $g(X),Xg(X),\dots ,X^{k-1}g(X)$ son palabras, tienen grados distintos y por eso son independientes: son una base. Escritos como filas,

$$G=\left[\begin{array}{ccccccc}{g}_0& g_1& \cdots & g_{n-k}& 0& \cdots & 0\\ 0& g_0& g_1& \cdots & g_{n-k}& \cdots & 0\\ ⋮& & \ddots & \ddots & \ddots & \ddots & ⋮\\ 0& \cdots & 0& g_0& g_1& \cdots & g_{n-k}\end{array}\right]$$

Es una matriz de Toeplitz: cada fila es la anterior corrida un lugar, y las $kn$ entradas quedan dichas por los $n-k+1$ coeficientes de $g(X)$. Para el (7,4) de $g(X)=1+X+X^3$, a la izquierda; a la derecha, la misma después de sumar filas hasta dejar el mensaje intacto:

$$G=\left[\begin{array}{l}1101000\\ 0110100\\ 0011010\\ 0001101\end{array}\right]G_{\text{sis}}=\left[\begin{array}{l}1101000\\ 0110100\\ 1110010\\ 1010001\end{array}\right]$$

con la posición 0 a la izquierda. La primera no es sistemática: el mensaje $u(X)$ no aparece en $u(X)g(X)$. La segunda está en forma sistemática a la manera cíclica, con la paridad en las primeras $n-k$ posiciones y el mensaje en las últimas $k$, al revés que en la Unidad 3. Las dos generan las mismas 16 palabras, comparadas una por una. A la sistemática no hace falta llegar sumando filas: sale de una sola división por $g(X)$, y eso es el codificador cíclico.

06 · El polinomio de paridad y el dual

El cociente

$$h(X)=\frac{X^n+1}{g(X)}$$

tiene grado $k$ y se llama polinomio de paridad. Toda palabra lo anula: si $v(X)=u(X)g(X)$, entonces $v(X)h(X)=u(X)(X^n+1)\equiv 0$ módulo $X^n+1$. De ahí salen las ecuaciones de paridad, en tres pasos.

Paso 1: un producto con un hueco. Sin reducir, $v(X)h(X)=u(X)+X^{n}u(X)$. Como $u(X)$ tiene grado menor que $k$, los coeficientes de $X^k,\dots ,X^{n-1}$ son cero.

Paso 2: cada coeficiente es una ecuación. El coeficiente de $X^j$ en el producto es una suma de productos $h_i{v}_{j-i}$, y anularlo da

$$\sum _{i=0}^k{h}_i{v}_{j-i}=0,j=k,\dots ,n-1$$

que son $n-k$ ecuaciones.

Paso 3: cada ecuación es el recíproco corrido. La ecuación $j$ toca las posiciones $j-k$ a $j$, con los coeficientes de $h(X)$ al revés: $h_k$ en la primera y $h_0$ en la última. Escrita como fila es el recíproco

$$h^{\ast }(X)=X^{k}h(X^{-1})=h_k+h_{k-1}X+\cdots +h_0{X}^k$$

corrido $j-k$ lugares. Las $n-k$ filas forman una matriz de paridad $H$ que es la $G$ de Toeplitz de $h^{\ast }(X)$. Y como $H$ genera al dual:

El dual de un código cíclico es cíclico, y lo genera el recíproco de $h(X)$, $X^{k}h(X^{-1})$, de grado $k$: es un $(n,n-k)$. Divide a $X^n+1$ porque los recíprocos se multiplican, y el de $X^n+1$ es él mismo. En el (7,4),

$$h(X)=1+X+X^2+X^4,h^{\ast }(X)=1+X^2+X^3+X^4$$ $$H=\left[\begin{array}{l}1011100\\ 0101110\\ 0010111\end{array}\right]$$

La primera fila es la ecuación $j=4$: $v_0+v_2+v_3+v_4=0$. El código que genera $h^{\ast }(X)$ es un (7,3) cuyas siete palabras no nulas pesan 4: el símplex, el dual del Hamming.

La trampa está en el recíproco. El código que genera $h(X)$ mismo es otro (7,3) con las siete palabras de peso 4 —las del dual leídas al revés— y no es ortogonal al (7,4). Tiene los parámetros del dual y no es el dual. Medido sobre los 30 cíclicos de largo 15: el código de $h^{\ast }(X)$ es ortogonal al original y de dimensión $n-k$ en los 30, y el de $h(X)$ tiene la misma distancia mínima en los 30, pero es ortogonal sólo en 14, exactamente los 14 en que $h(X)$ es su propio recíproco. En factores, el recíproco intercambia $1+X+X^4$ con $1+X^3+X^4$ y deja los otros tres como están.

07 · Donde la receta deja de valer

Un $g(X)$ que no divide. Los múltiplos de cualquier polinomio, con grado menor que $n$, forman un código lineal. Lo que los hace cíclicos es el Teorema 4, y pide que $g(X)$ divida a $X^n+1$. Con $g(X)=1+X+X^3$ y $n=15$ el resto de dividir $X^{15}+1$ es $1+X$, no cero. Los múltiplos forman un (15,12) lineal, y su palabra $X^{11}g(X)=X^{11}+X^{12}+X^{14}$, girada un lugar, da $1+X^{12}+X^{13}$, que no es múltiplo de $g(X)$. Contadas, 2048 de las 4096 palabras salen del código al girarlas una vez. En el Paso 2 del Teorema 4 es el término $v_{n-1}(X^n+1)$ el que deja de ser múltiplo.

Un largo par. La cuenta $2^f-2$ supone factores distintos, y eso pasa con $n$ impar. Con $n$ par, sobre $\mathrm{GF}(2)$ vale $X^{2m}+1={(X^m+1)}^2$, y los factores se repiten:

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

Cada factor entra cero, una o dos veces: $3^3=27$ divisores, que son los que da probar todos los polinomios de grado hasta 14, y 25 códigos cíclicos no triviales de largo 14. No son $2^3-2=6$ ni $2^6-2=62$. Los teoremas valen igual; lo que deja de valer es contar subconjuntos.

Para tener a mano

1. $g(X)$ es la palabra no nula de menor grado de un cíclico $(n,k)$: única, con $g_0=1$ y grado $n-k$.
2. Las palabras son los múltiplos $u(X)g(X)$ con grado de $u(X)$ menor que $k$. Pertenecer es $R_g\{r(X)\}=0$.
3. $g(X)$ divide a $X^n+1$, y todo divisor de grado $n-k$ genera un cíclico $(n,k)$. Con $n$ impar y $f$ factores irreducibles hay $2^f-2$ no triviales: 30 de largo 15, 6 de largo 7.
4. La redundancia es la suma de los grados elegidos; la distancia mínima depende de cuáles, y se enumera.
5. $G$ de Toeplitz: filas $X^{i}g(X)$, $i=0,\dots ,k-1$. La sistemática cíclica lleva la paridad primero y el mensaje al final.
6. $h(X)=(X^n+1)/g(X)$, de grado $k$, con $v(X)h(X)\equiv 0$. El dual lo genera $X^{k}h(X^{-1})$, no $h(X)$: el de $h(X)$ tiene los mismos parámetros y es ortogonal sólo si $h(X)$ es su propio recíproco.
7. Si $g(X)$ no divide a $X^n+1$, sus múltiplos son un código lineal que no es cíclico. Con $n$ par los factores se repiten y la cuenta de subconjuntos no vale.