Un bit más de redundancia puede costar distancia

En un código de bloque, cada bit de paridad de más se paga con tasa y se cobra, en principio, en distancia. Entre los códigos cíclicos de largo 15 esa cuenta se rompe. Con 11 bits de paridad, el mejor tiene $d_{\text{min}}=8$; con 12, el mejor tiene 5. No es que el de 12 esté mal elegido: es el único que hay, y sus palabras son un patrón de tres bits repetido cinco veces. Con 8 bits, en cambio, hay tres para elegir, de distancias 5, 5 y 3, y equivocarse de polinomio cuesta dos de distancia sin ahorrar un bit.

01 · Un código que gira

Sea $v=(v_0,v_1,\dots ,v_{n-1})$ una palabra de $n$ bits. Su desplazamiento cíclico es $v^{(1)}=(v_{n-1},v_0,\dots ,v_{n-2})$: cada bit avanza un lugar y el último vuelve al principio, como sobre un anillo de $n$ posiciones. Un código lineal $(n,k)$ es cíclico si el desplazamiento de toda palabra del código es otra palabra del código.

El desplazamiento se escribe mejor con polinomios. A la palabra se le asocia

$$v(X)=v_0+v_{1}X+\cdots +v_{n-1}{X}^{n-1}$$

y multiplicar por $X$ corre todos los coeficientes un lugar. El único que se pasa es $v_{n-1}{X}^n$, y vuelve a la posición 0 si se cuenta $X^n=1$, o sea, si se toma el resto de dividir por $X^n+1$:

$$v^{(1)}(X)=R_{X^n+1}\{Xv(X)\}$$

$R_d\{f\}$ es el resto de dividir $f$ por $d$. Desplazar es multiplicar por $X$ módulo $X^n+1$, y todo lo que sigue sale de ahí.

02 · Un polinomio decide el código

En todo código cíclico no trivial hay una sola palabra no nula de grado mínimo. Es el polinomio generador $g(X)$, tiene grado $n-k$ y término independiente 1. Lo hacen generador tres hechos, demostrados en El polinomio generador:

Las palabras son sus múltiplos. $v(X)$ es una palabra del código si y sólo si $v(X)=u(X)g(X)$, con $u(X)$ de grado menor que $k$. Son $2^k$ palabras, una por mensaje.

Divide a $X^n+1$. Y al revés: todo divisor de $X^n+1$ de grado $n-k$ genera un código cíclico $(n,k)$. Elegir un código cíclico de largo $n$ es elegir un divisor de $X^n+1$, y su grado es la redundancia.

Lo que sobra es el polinomio de paridad. $h(X)=(X^n+1)/g(X)$, de grado $k$. Como $v(X)h(X)=u(X)g(X)h(X)=u(X)(X^n+1)$, toda palabra cumple

$$v(X)h(X)\equiv 0(\text{mód}{X}^n+1)$$

Esta condición es la que va a explicar la caída. Mientras $g(X)$ dice qué palabras hay, $h(X)$ dice qué ecuaciones cumplen todas.

03 · Los cinco factores de X¹⁵ + 1

Con $n=15$, los divisores salen de factorizar $X^{15}+1$ en polinomios irreducibles sobre GF(2):

Son cinco factores distintos, de grados 1, 2, 4, 4 y 4. Cada subconjunto da un generador, su producto. Sacando el conjunto vacío, que da $g=1$, y el completo, que da el código de una sola palabra, quedan $2^5-2=30$ códigos cíclicos de largo 15. La redundancia $n-k$ de cada uno es la suma de los grados que eligió, y $k$ es la suma de los que dejó para $h(X)$.

Hay algo más que distingue a los factores: su orden, el menor $N$ tal que el factor divide a $X^N+1$. Para $1+X$ es 1. Para $1+X+X^2$ es 3, y para $1+X+X^2+X^3+X^4$ es 5, porque

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

Los otros dos, $1+X+X^4$ y $1+X^3+X^4$, tienen orden 15: son primitivos. $1+X+X^2+X^3+X^4$ es irreducible y de grado 4 igual que ellos, pero no es primitivo. Un factor de orden chico es un factor que también divide a un $X^3+1$ o a un $X^5+1$, y eso, en un código de largo 15, tiene consecuencias.

Arranca con el mejor código de 11 bits de paridad, un $(15,4)$ de distancia 8. Buscá ahora uno con 12: no hay un factor de grado 1 para agregar, así que hay que cambiar el reparto entero. Después probá los tres de 8 bits, que se arman con dos factores de grado 4, y mirá cuál de los tres pares deja una palabra de peso 3.

04 · De once a doce bits, de 8 a 5

Medido sobre los 30 códigos, enumerando las $2^k$ palabras de cada uno, la mejor $d_{\text{min}}$ para cada redundancia:

Hasta 11 la mejor distancia sube o se queda quieta. En 12 cae de 8 a 5, y vuelve a subir a 10 y a 15 en las dos siguientes. La primera pista está en la segunda columna: con 12 bits de paridad hay un solo código.

Con 11, $k=4$, y $h(X)$ es el factor de grado 4 que quedó afuera de $g(X)$. Hay tres maneras. Cuando $h(X)$ es uno de los dos primitivos, el código es el símplex $(15,4)$, el dual del Hamming $(15,11)$: sus quince palabras no nulas pesan 8, todas. Con $h=1+X+X^2+X^3+X^4$ la distancia es 6.

Con 12, $k=3$, y $h(X)$ tiene que tener grado 3. Con factores de grados 1, 2, 4, 4 y 4, la única forma de sumar 3 es 1 + 2:

$$h(X)=(1+X)(1+X+X^2)=1+X^3$$ $$g(X)=1+X^3+X^6+X^9+X^{12}$$

Ahora la condición de la sección 02. Con $h=1+X^3$, dice $v(X)+X^{3}v(X)\equiv 0$, o sea

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

Toda palabra es igual a su desplazamiento de orden 3: $v_i=v_{i+3}$ para todo $i$ módulo 15. La palabra la decide su primer tramo, $v_0{v}_1{v}_2$, y el resto lo repite: cada palabra es un patrón de tres bits repetido cinco veces. Hay ocho patrones y ocho palabras, que es $2^3$, así que están todas. El peso de cada una es cinco veces el de su patrón:

La distancia mínima es 5, y la palabra de peso 5 con la posición 0 en uno es el propio $g(X)$. El código es, en el fondo, una repetición: cada uno de los tres bits de información sale cinco veces. Doce bits de paridad compran exactamente lo que compra repetir cinco veces, y nada más.

Lo que hace caer la distancia no es el bit de más sino el orden de $h(X)$. $1+X^3=X^3+1$ tiene orden 3, y un $h(X)$ de orden $m$ obliga a toda palabra a repetirse con período $m$. Lo mismo explica la otra fila de la tabla con $h(X)$ de orden chico: con 11 bits y $h=1+X+X^2+X^3+X^4$, de orden 5, las palabras son un patrón de cinco bits de peso par repetido tres veces, y la distancia es $3·2=6$.

05 · Con ocho bits: 5, 5 y 3

Ocho bits de paridad sólo se juntan con dos factores de grado 4, y hay tres pares. Los tres códigos son $(15,7)$, con la misma tasa, 7/15:

El tercero tiene cinco palabras de peso 3, y son los giros de una sola:

Es la palabra de período 5, 10000 10000 10000. Está en el código cuando $g(X)$ la divide, y eso pasa cuando $g(X)$ no se queda con ninguno de los dos factores de $X^5+1$: ni con $1+X$ ni con $1+X+X^2+X^3+X^4$. Los dos primeros pares llevan a $1+X+X^2+X^3+X^4$ adentro de $g(X)$ y la excluyen; el tercero se lo deja a $h(X)$, junto con $1+X$, y la palabra entra.

La regla vale para los tres divisores chicos de 15. La palabra de período $m$, $(X^{15}+1)/(X^m+1)$, pesa $15/m$ y está en el código si y sólo si $g(X)$ no comparte factores con $X^m+1$. Comprobado sobre los 30 códigos con $m=1,3,5$: 90 casos de 90. Es la misma caída que la de 12 bits, vista desde la otra punta: allá todas las palabras eran periódicas; acá basta con una.

Distancia 3 en vez de 5 es corregir un error en vez de dos, con los mismos ocho bits de paridad. Elegir el par es elegir qué factor de orden chico queda en $h(X)$.

06 · La que falla es la estructura, no la redundancia

Entre los códigos lineales, un bit más de paridad nunca obliga a perder distancia. Del símplex $(15,4)$ se puede sacar cualquier subcódigo de dimensión 3, y como todas sus palabras no nulas pesan 8, el subcódigo también tiene distancia 8: un $(15,3)$ con $d_{\text{min}}=8$, tres más que el cíclico. Medido: el símplex tiene 15 subcódigos de dimensión 3, todos de distancia 8, y ninguno es cíclico. En cada uno hay una palabra cuyo giro cae afuera, en el resto del símplex.

La distancia no cae porque falte redundancia. Cae porque la condición de ser cíclico deja pocos códigos para elegir, y en $n-k=12$ deja uno solo. La salida es salir de la familia: cambiar el largo, o acortar un código de otra redundancia. El símplex acortado en un bit da un $(14,3)$ de distancia 8, medido sobre sus ocho palabras, que deja de ser cíclico pero se sigue codificando con el mismo circuito.