Códigos cíclicos: palabras que son polinomios

En la lección anterior decodificamos con una tabla de síndromes. Cuando $n$ crece, guardar $G$ o una tabla grande es incómodo. ¿Hay códigos que se describan con muy poca información y se codifiquen con circuitos sencillos?

Sí: los códigos cíclicos. Son la base de los CRC que protegen las tramas de red y los archivos ZIP, y (lo verás en la lección 9) de los códigos Reed-Solomon de los QR. Hace falta una idea nueva: tratar las palabras como polinomios.

La idea

Toma $1101000$ y desplázala una posición a la derecha, de forma que el último símbolo vuelva al principio: $0110100$. Otro desplazamiento da $0011010$. Tras 7 desplazamientos vuelves a la original: es girar una rueda con 7 casillas.

Un código es cíclico si es lineal y, cada vez que una palabra está en el código, sus desplazamientos también lo están. Parece una condición caprichosa, pero el código queda determinado por una sola palabra. El truco: escribir cada palabra como los coeficientes de un polinomio. Entonces desplazar es multiplicar por $x$, y el álgebra de polinomios hace el trabajo.

Aviso de numeración. Solo en las lecciones de códigos cíclicos, las posiciones de una palabra se numeran desde 0: $c = (c_0, c_1, \dots, c_{n-1})$. Así el coeficiente de $x^i$ es $c_i$ y no hay que restar unos.

Palabras como polinomios

A cada palabra $c = (c_0, c_1, \dots, c_{n-1})$ de $\mathbb{F}_q^n$ le asociamos el polinomio

$$c(x) = c_0 + c_1 x + \dots + c_{n-1}x^{n-1}.$$

Por ejemplo, $1101000$ se corresponde con $1 + x + x^3$. El polinomio de una palabra de longitud $n$ tiene grado menor que $n$.

Ahora multiplica por $x$:

$$x\,c(x) = c_0 x + c_1 x^2 + \dots + c_{n-2}x^{n-1} + c_{n-1}x^{n}.$$

Casi es el desplazamiento, pero el último coeficiente ha quedado en $x^n$, fuera de rango. Para devolverlo al principio declaramos que $x^n = 1$, es decir, trabajamos con los restos de dividir entre $x^n - 1$ (el recuadro lo explica). Ese conjunto se escribe $\mathbb{F}_q[x]/(x^n-1)$. En él,

$$x\,c(x) \equiv c_{n-1} + c_0 x + c_1 x^2 + \dots + c_{n-2}x^{n-1},$$

que es exactamente la palabra desplazada. Multiplicar por $x$ es desplazar.

Repaso Polinomios módulo xⁿ − 1: un reloj de polinomios

En la lección 2 viste la aritmética del reloj: en $\mathbb{Z}_7$, $7 = 0$ y los números dan la vuelta, como las horas. Con polinomios hacemos lo mismo: para $n = 7$ declaramos $x^7 = 1$. Cada $x^7$ se cambia por $1$; $x^8$ es $x$ y $x^9$ es $x^2$. Todo polinomio se reduce a uno de grado menor que 7, es decir, a una palabra de 7 símbolos.

Al multiplicar por $x$, el coeficiente de $x^6$ pasa a $x^7 = 1$ y da la vuelta al principio: es la rueda de 7 casillas. Y $x^n - 1$ vale $0$ en este reloj.

Repaso División de polinomios y restos módulo 2

Dividir polinomios es como dividir números, quitando el término de mayor grado. Con coeficientes en $\mathbb{F}_2$, restar es lo mismo que sumar, porque $1 + 1 = 0$.

Divide $x^5 + x^3 + 1$ entre $g(x) = x^3 + x + 1$:

1. El primer término del cociente es $x^2$, porque $x^2 \cdot x^3 = x^5$.
2. Calcula $x^2 \cdot g(x) = x^5 + x^3 + x^2$ y réstalo (súmalo, en módulo 2): $(x^5 + x^3 + 1) + (x^5 + x^3 + x^2) = x^2 + 1$.
3. El resto $x^2 + 1$ tiene grado 2, menor que el de $g$ (grado 3): ya hemos terminado.

Cociente $x^2$ y resto $x^2 + 1$. Se escribe $x^5 + x^3 + 1 \equiv x^2 + 1 \pmod{g(x)}$. Si el resto es 0, se dice que $g$ divide al polinomio.

El polinomio generador

Un código cíclico es cerrado por multiplicar por $x$, y por tanto por multiplicar por cualquier polinomio $a(x)$ (multiplicar por $x^2$ es desplazar dos veces; sumar palabras es linealidad). Entre todos los polinomios no nulos del código, escoge el de menor grado y hazlo mónico (coeficiente principal igual a 1). Es el polinomio generador $g(x)$ del código. Tiene tres propiedades:

• Todas las palabras son múltiplos de $g(x)$, y todo múltiplo de $g$ de grado menor que $n$ está en el código (es una combinación de desplazamientos de $g$). Es decir, $C = \{\,m(x)g(x) : \deg m < n - \deg g\,\}$.
• $g(x)$ divide a $x^n - 1$. Si divides, $x^n - 1 = q(x)g(x) + s(x)$. En nuestro reloj $x^n - 1$ vale 0, así que el resto cumple $s \equiv -q\,g$ en el reloj: es un múltiplo de $g$, es decir, una palabra del código. Pero tiene grado menor que $g$, que es la palabra no nula de menor grado: luego $s = 0$.
• La dimensión es $k = n - \deg g$. Hay un polinomio $m(x)$ de grado menor que $k$ por cada palabra, así que $|C| = q^k$.

Y al revés: cada divisor mónico $g$ de $x^n-1$ genera un código cíclico de dimensión $n - \deg g$. Por eso, para encontrar todos los códigos cíclicos de longitud $n$ basta factorizar $x^n - 1$ y combinar los factores.

Los códigos cíclicos binarios de longitud 7

Sobre $\mathbb{F}_2$, el polinomio $x^7 - 1 = x^7 + 1$ se factoriza en irreducibles (no se puede romper más) como

$$x^7 - 1 = (x+1)(x^3+x+1)(x^3+x^2+1).$$

(Compruébalo: $(x^3+x+1)(x^3+x^2+1) = x^6+x^5+\dots+x+1$, y al multiplicar por $x+1$ queda $x^7+1$.) Tiene 3 factores irreducibles distintos, luego hay $2^3 = 8$ divisores mónicos y 8 códigos cíclicos binarios de longitud 7:

generador $g(x)$	$k$	$d$	qué es
$1$	7	1	todo $\mathbb{F}_2^7$
$x+1$	6	2	palabras de peso par
$x^3+x+1$	4	3	Hamming
$x^3+x^2+1$	4	3	Hamming (otro)
$(x+1)(x^3+x+1) = x^4+x^3+x^2+1$	3	4	dual de un Hamming
$(x+1)(x^3+x^2+1) = x^4+x^2+x+1$	3	4	dual del otro
$(x^3+x+1)(x^3+x^2+1) = x^6+\dots+x+1$	1	7	repetición
$x^7+1$	0	no hay	solo la palabra $0$

Los extremos son triviales. El de $g = x + 1$ es el código de paridad (palabras de peso par) de longitud 7, la versión larga del de la primera lección. El de $g=x^6+x^5+\dots+1$ repite el mismo bit 7 veces. Lo interesante está en medio: para buscar buenos códigos ya no exploras subespacios a ciegas, factorizas un polinomio.

Un código de Hamming cíclico

Toma $g(x) = 1 + x + x^3$. Como $\deg g = 3$, la dimensión es $k = 4$. Sus palabras son los $m(x)g(x)$ con $\deg m < 4$: hay 1 de peso 0, 7 de peso 3, 7 de peso 4 y 1 de peso 7. Es la distribución de pesos del Hamming $[7,4,3]$ del hilo, y no por casualidad: este código es equivalente al del hilo, es decir, se obtiene de él reordenando las posiciones. Ojo: el código del hilo, con la $G$ de las lecciones 3 a 6, no es cíclico; lo es su versión reordenada. Tiene $d = 3$ y corrige 1 error.

Este $g$ ya lo conoces: $x^3+x+1$ es el polinomio con el que construimos $\mathbb{F}_8$ en la lección 2, y $\alpha$ es una raíz suya ($\alpha^3 = \alpha + 1$). Raíces y códigos volverán a juntarse con Reed-Solomon.

Las siete palabras de peso 3 son los siete desplazamientos de $g = 1101000$:

$$1101000,\ 0110100,\ 0011010,\ 0001101,\ 1000110,\ 0100011,\ 1010001.$$

Las cuatro primeras son las filas de la matriz generatriz cíclica ($g, xg, x^2g, x^3g$). Las de peso 4 se obtienen sumando $1111111$ a estas (cambia ceros por unos), y faltan $0000000$ y $1111111$.

Ejemplo resuelto

Pregunta: ¿es $r = (1,1,0,1,0,0,1)$ una palabra del código cíclico de generador $g(x) = 1 + x + x^3$?

1. Pasa a polinomio, con índices desde 0: $r(x) = 1 + x + x^3 + x^6$.
2. Está en el código si y solo si $g(x)$ divide a $r(x)$. Divide: el término principal es $x^6 = x^3 \cdot x^3$, así que resta $x^3 g(x) = x^3 + x^4 + x^6$. Queda $x^4 + x + 1$.
3. Ahora el término principal es $x^4 = x \cdot x^3$. Resta $x\,g(x) = x + x^2 + x^4$. Queda $x^2 + 1$, de grado menor que 3.

El resto no es 0: $r$ no es palabra del código.

Y una que sí: $c = (1,0,0,1,0,1,1)$, es decir, $c(x) = 1 + x^3 + x^5 + x^6$. Resta $x^3g$: queda $1 + x^4 + x^5$. Resta $x^2g = x^2+x^3+x^5$: queda $1 + x^2 + x^3 + x^4$. Resta $x\,g$: queda $1 + x + x^3$. Resta $g$: queda $0$. El resto es 0, así que $c$ sí está en el código (es $(1+x+x^2+x^3)\,g$).

Ejercicios

Ejercicio 1

Halla todos los códigos cíclicos binarios de longitud 3. Para cada uno, da el generador, $k$ y las palabras. Pista: $x = 1$ es raíz de $x^3 + 1$, luego $x + 1$ lo divide.

Ver la solución

Al dividir $x^3+1$ entre $x+1$ sale $x^2+x+1$, que no tiene raíces en $\mathbb{F}_2$ (vale 1 en 0 y en 1). Así, $x^3 + 1 = (x+1)(x^2+x+1)$. Hay 2 factores irreducibles distintos, luego $2^2 = 4$ divisores y 4 códigos:

• $g = 1$: $k = 3$, es todo $\mathbb{F}_2^3$.
• $g = x+1$: $k = 2$, palabras $000, 011, 101, 110$ (las de peso par).
• $g = x^2+x+1$: $k = 1$, palabras $000$ y $111$ (el código de repetición).
• $g = x^3+1$: $k = 0$, solo la palabra $000$.

Ejercicio 2

Considera el código cíclico de longitud 7 con $g(x) = 1 + x^2 + x^3 + x^4$. Calcula su dimensión, escribe sus palabras y halla su distancia mínima.

Ver la solución

Como $\deg g = 4$, la dimensión es $k = 7 - 4 = 3$ y hay $2^3 = 8$ palabras. Como $g = 1011100$, sus desplazamientos son

$$1011100,\ 0101110,\ 0010111,\ 1001011,\ 1100101,\ 1110010,\ 0111001,$$

siete palabras distintas; con $0000000$ completan las 8. Todas las no nulas tienen peso 4, así que $d = 4$ y el código es un $[7,3,4]$. Es el que aparece en la tabla como «dual de un Hamming».

Comprobación: $g = (x+1)(x^3+x+1)$, y en efecto $(x+1)(x^3+x+1) = x^4 + x^3 + x^2 + 1$.

En resumen

• Un código es cíclico si es lineal y cerrado por desplazamientos cíclicos. Con polinomios, desplazar es multiplicar por $x$ módulo $x^n - 1$.
• Todo código cíclico tiene un polinomio generador $g(x)$, divisor de $x^n - 1$, y sus palabras son los múltiplos de $g$. La dimensión es $k = n - \deg g$.
• Los códigos cíclicos de longitud $n$ se obtienen factorizando $x^n - 1$. Sobre $\mathbb{F}_2$ y $n = 7$ hay 8, entre ellos dos $[7,4,3]$.
• Un código de Hamming $[7,4,3]$ (equivalente al del hilo: el mismo con las posiciones reordenadas) es cíclico, con $g(x) = 1 + x + x^3$.
• Una palabra está en el código si y solo si el resto de dividirla entre $g$ es 0.

Siguiente lección: Codificar un código cíclico, y de ahí los CRC