Los códigos cíclicos

Un código lineal se decodifica con una tabla que asocia cada síndrome con su líder de coset, y esa tabla tiene $2^{n - k}$ entradas: ocho en el (7,4), más de cuatro mil millones con 32 bits de paridad. La salida no es abandonar la linealidad sino agregarle una simetría: que el código no cambie al girar sus palabras. Con esa sola condición, la tabla se reemplaza por un circuito. Los BCH, los Reed-Solomon y los CRC son todos cíclicos o salen de uno.

01 · La definición

Sea $v = (v_{0}, v_{1}, \dots, v_{n - 1})$ una $n$ -tupla sobre $GF (2)$ . Su desplazamiento cíclico es

v^{(1)} = (v_{n - 1}, v_{0}, v_{1}, \dots, v_{n - 2})

Cada componente se corre un lugar a la derecha y la última vuelve al principio. Aplicado $i$ veces da el desplazamiento de orden $i$ , $v^{(i)}$ , y con $i = n$ la tupla vuelve a ser la misma: las $n$ posiciones se leen como un anillo.

Definición. Un código de bloque lineal $(n, k)$ es cíclico si el desplazamiento cíclico de toda palabra de código es también una palabra de código.

Alcanza con pedirlo para un lugar: $v^{(i)}$ es el desplazamiento de un lugar aplicado $i$ veces, y cada vez se cae adentro del código. Girar no cambia la cantidad de unos, así que una palabra y sus giros tienen el mismo peso. Las palabras de un código cíclico se agrupan entonces en órbitas: cada una con todos sus giros, que son a lo sumo $n$ distintos.

La condición es fuerte. Un código lineal puede ser cualquier conjunto de $2^{k}$ palabras cerrado bajo la suma; ser cíclico pide además un cierre que depende del orden de las posiciones, algo que a la suma y a las distancias les da igual.

02 · La palabra como polinomio

En notación de vectores el desplazamiento es incómodo. A la $n$ -tupla $v$ se le asocia el polinomio

v (X) = v_{0} + v_{1} X + v_{2} X^{2} + \dots + v_{n - 1} X^{n - 1}

de grado menor que $n$ y coeficientes en $GF (2)$ . La posición $i$ es el coeficiente de $X^{i}$ . La correspondencia es biunívoca y la suma de vectores es la suma de polinomios, así que nada se pierde. Lo que se gana es una cuenta para el desplazamiento.

Paso 1: multiplicar por $X$ . Cada coeficiente sube un grado:

X v (X) = v_{0} X + v_{1} X^{2} + \dots + v_{n - 2} X^{n - 1} + v_{n - 1} X^{n}

Casi es el desplazamiento, salvo por el último término, que llegó a grado $n$ y no corresponde a ninguna posición.

Paso 2: sumar dos veces $v_{n - 1}$ . Sobre $GF (2)$ sumar dos veces lo mismo es sumar cero. Agrupando una de las copias con el término de grado $n$ y la otra con el resto:

X v (X) = v_{n - 1} (X^{n} + 1) + \underset{v^{(1)} (X)}{\underset{⏟}{(v_{n - 1} + v_{0} X + \dots + v_{n - 2} X^{n - 1})}}

El paréntesis tiene los coeficientes $(v_{n - 1}, v_{0}, \dots, v_{n - 2})$ : es exactamente el polinomio de $v^{(1)}$ .

Paso 3: leer un resto. La igualdad tiene la forma de una división por $X^{n} + 1$ , con cociente $v_{n - 1}$ y un resto de grado menor que $n$ . Ese resto es el desplazamiento:

v^{(1)} (X) = R_{X^{n} + 1} {X v (X)}, v^{(i)} (X) = R_{X^{n} + 1} {X^{i} v (X)}

donde $R_{d (X)} {f (X)}$ es el resto de dividir $f (X)$ por $d (X)$ . Girar es multiplicar por $X$ módulo $X^{n} + 1$ . En la práctica se cuenta con $X^{n} \equiv 1$ : el término que llega a grado $n$ vuelve a grado 0.

Con $n = 7$ y $v = 1001011$ , la posición 0 a la izquierda:

\begin{array}{l} v (X) = 1 + X^{3} + X^{5} + X^{6} \\ X v (X) = X + X^{4} + X^{6} + X^{7} \\ \equiv 1 + X + X^{4} + X^{6} (\mod X^{7} + 1) \end{array}

o sea $v^{(1)} = 1100101$ : el 1 de la posición 6 dio la vuelta a la posición 0, y los demás se corrieron un lugar.

03 · Un polinomio describe el código

La cuenta del paso 3 tiene una consecuencia que la notación de vectores escondía. En un código cíclico, $R_{X^{n} + 1} {X^{i} v (X)}$ es una palabra para todo $i$ , y la suma de palabras es una palabra. Un polinomio cualquiera $a (X) = \sum a_{i} X^{i}$ es una suma de potencias de $X$ , así que

R_{X^{n} + 1} {a (X) v (X)} = \sum_{i} a_{i} v^{(i)} (X)

también es una palabra. Un código cíclico es cerrado bajo el producto por cualquier polinomio, módulo $X^{n} + 1$ . De ahí sale que una sola palabra alcanza para generarlo todo: la no nula de menor grado, el polinomio generador $g (X)$ . Es única, tiene grado $n - k$ , las palabras son sus múltiplos de grado menor que $n$ , divide a $X^{n} + 1$ , y todo divisor de $X^{n} + 1$ genera un cíclico. Las pruebas están en el polinomio generador.

Con eso, buscar los cíclicos de un largo es factorizar. Para $n = 7$ ,

X^{7} + 1 = (1 + X) (1 + X + X^{3}) (1 + X^{2} + X^{3})

tres factores irreducibles. Cada producto de algunos de ellos, sin tomar ninguno ni todos, es un generador: $2^{3} - 2 = 6$ códigos. Con la distancia mínima de cada uno, sacada enumerando sus palabras:

g(X)	(n, k)	d_min
1 + X	(7, 6)	2
1 + X + X³	(7, 4)	3
1 + X² + X³	(7, 4)	3
1 + X + X² + X⁴	(7, 3)	4
1 + X² + X³ + X⁴	(7, 3)	4
1 + X + X² + X³ + X⁴ + X⁵ + X⁶	(7, 1)	7

El primero es el de paridad par; el último, la repetición. Una matriz $k \times n$ pasa a ser un polinomio de $n - k + 1$ coeficientes, y la ganancia es de implementación: codificar es una división y el síndrome es un resto, las dos cosas con un registro de desplazamiento de $n - k$ etapas, sin tablas. Está en el codificador cíclico y en el síndrome cíclico.

04 · El (7,4) del curso ya era cíclico

El Hamming (7,4) que se usa desde la Unidad 3 tiene la matriz generadora en forma sistemática $G = [I_{4} P]$ , con el mensaje adelante y tres ecuaciones de paridad:

\begin{array}{l} p_{0} = u_{0} + u_{2} + u_{3} \\ p_{1} = u_{0} + u_{1} + u_{2} \\ p_{2} = u_{1} + u_{2} + u_{3} \end{array}

Nada en esa construcción habla de giros. Y sin embargo, comparadas una por una, sus 16 palabras son exactamente las mismas que las del cíclico de $g (X) = 1 + X + X^{3}$ . No es casualidad, y se ve en cuatro pasos.

Paso 1: las filas de $G$ son múltiplos de $g (X)$ . Leídas como polinomios y divididas por $g (X)$ , las cuatro dan resto cero:

\begin{array}{lll} 1000110 & = 1 + X^{4} + X^{5} & = (1 + X + X^{2}) g (X) \\ 0100011 & = X + X^{5} + X^{6} & = (X + X^{2} + X^{3}) g (X) \\ 0010111 & = X^{2} + X^{4} + X^{5} + X^{6} & = (X^{2} + X^{3}) g (X) \\ 0001101 & = X^{3} + X^{4} + X^{6} & = X^{3} g (X) \end{array}

Paso 2: entonces generan el mismo código. Los múltiplos de $g (X)$ de grado menor que 7 son palabras del cíclico, así que las 16 combinaciones de esas cuatro filas también lo son. Las filas de una $G$ son independientes, y dan 16 palabras distintas; el cíclico tiene $2^{4} = 16$ . No queda ninguna afuera.

Paso 3: las ecuaciones de paridad son las mismas. La forma sistemática de un cíclico pone la paridad adelante y el mensaje al final:

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

Con $n - k = 3$ , el mensaje entra multiplicado por $X^{3}$ , y hacen falta los restos de $X^{3}$ a $X^{6}$ . Como módulo $g (X)$ vale $X^{3} \equiv 1 + X$ , cada uno sale del anterior multiplicando por $X$ y volviendo a reemplazar, siempre módulo $g (X)$ :

\begin{array}{ll} X^{3} \equiv 1 + X & X^{4} \equiv X + X^{2} \\ X^{5} \equiv 1 + X + X^{2} & X^{6} \equiv 1 + X^{2} \end{array}

Entonces

\begin{array}{l} b (X) = u_{0} (1 + X) + u_{1} (X + X^{2}) \\ + u_{2} (1 + X + X^{2}) + u_{3} (1 + X^{2}) \end{array}

y juntando por potencias:

\begin{array}{l} b_{0} = u_{0} + u_{2} + u_{3} \\ b_{1} = u_{0} + u_{1} + u_{2} \\ b_{2} = u_{1} + u_{2} + u_{3} \end{array}

Son las tres ecuaciones de la Unidad 3, letra por letra. La $P$ de aquel (7,4) tiene por filas los restos de $X^{3}$ , $X^{4}$ , $X^{5}$ y $X^{6}$ módulo $g (X)$ .

Paso 4: lo único que cambia es dónde va el mensaje. El cíclico escribe $(b_{0} b_{1} b_{2} u_{0} u_{1} u_{2} u_{3})$ ; la Unidad 3, $(u_{0} u_{1} u_{2} u_{3} p_{0} p_{1} p_{2})$ . Mismo conjunto, otra asignación: de los 16 mensajes, sólo 0000 y 1111 van a parar a la misma palabra en las dos. El mensaje 1000 es 110 1000 en el cíclico —el propio $g (X)$ — y 1000 110 en la Unidad 3. De una a otra hay un giro: la palabra de la Unidad 3 es la cíclica girada cuatro lugares, $R_{X^{7} + 1} {X^{4} v (X)}$ , comprobado en los 16 mensajes. Ese atajo sólo existe porque el código es cíclico.

Las órbitas. Las siete palabras de peso 3 son los siete giros de $g (X) = 1101000$ , y las siete de peso 4, los siete giros de $(1 + X) g (X) = 1011100$ . Con 0000000 y 1111111, que giran sobre sí mismas, el código entero son cuatro órbitas: $1 + 7 + 7 + 1 = 16$ . La distribución de pesos del Hamming, $A_{0} = 1$ , $A_{3} = 7$ , $A_{4} = 7$ , $A_{7} = 1$ , es la lista de esas órbitas.

Arranca en el orden natural, con 0011001. Apostá y girá: la girada, 1001100, sigue en el código. Girá otra vez. Después pasá al (7,4) del curso y buscá una palabra que se salga.

05 · El mismo Hamming, en otro orden, no es cíclico

El orden natural pone en la posición $i$ la columna de $H$ que vale $i + 1$ en binario. Es el mismo Hamming (7,4) con las posiciones en otro orden: las mismas columnas en $H$ , los mismos pesos, la misma distancia. Y de sus 16 palabras, sólo 4 siguen en el código al girarlas: 0000000, 1111111, 0011001 y 1100110. Medido con giros de 1 a 6 lugares, la cuenta da 4 en todos. Ser cíclico no es una propiedad de las distancias: es una propiedad del orden.

Cuánto pide ese orden se puede contar. Las $7! = 5040$ maneras de reordenar las posiciones del (7,4) dan 30 códigos distintos, todos con los mismos pesos. Dos son cíclicos: el de $1 + X + X^{3}$ , que es el del curso, y el de $1 + X^{2} + X^{3}$ . Entre esos dos sólo hay dos palabras en común, 0000000 y 1111111. Entre los reordenamientos del (7,4), uno de cada quince es cíclico; que el del curso lo sea depende de cómo se armó su $P$ en la Unidad 3.

La estructura también restringe qué parámetros existen. Los generadores de largo 7 tienen grado 1, 3, 4 o 6, que son las sumas posibles de los grados de los factores de $X^{7} + 1$ : no hay ningún cíclico (7,5) ni (7,2). Y para una misma redundancia puede haber varios cíclicos con distancias distintas, o uno solo, y malo: en largo 15, un bit más de redundancia puede costar distancia. Cuando el largo que se necesita no es uno con buena factorización, el cíclico se acorta, y deja de ser cíclico sin perder el circuito: está en los CRC y los códigos acortados.

Para tener a mano

Un código lineal $(n, k)$ es cíclico si el giro de toda palabra es una palabra. Girar es $v^{(1)} = (v_{n - 1}, v_{0}, \dots, v_{n - 2})$ , con la posición 0 a la izquierda.
La palabra es $v (X) = v_{0} + v_{1} X + \dots + v_{n - 1} X^{n - 1}$ , y $v^{(i)} (X) = R_{X^{n} + 1} {X^{i} v (X)}$ : se cuenta con $X^{n} \equiv 1$ .
Cerrado bajo giros y sumas es cerrado bajo el producto por cualquier $a (X)$ módulo $X^{n} + 1$ . Por eso un solo $g (X)$ , divisor de $X^{n} + 1$ y de grado $n - k$ , describe el código.
$X^{7} + 1 = (1 + X) (1 + X + X^{3}) (1 + X^{2} + X^{3})$ : seis cíclicos de largo 7, con $k = 6$ , 4, 4, 3, 3 y 1.
El (7,4) del curso es, palabra por palabra, el cíclico de $1 + X + X^{3}$ : sus filas son múltiplos de $g (X)$ y su $P$ son los restos de $X^{3}$ a $X^{6}$ . Cambia la asignación: el cíclico pone la paridad adelante, y las dos palabras de un mensaje difieren en un giro de cuatro lugares.
Órbitas del (7,4): $1 + 7 + 7 + 1$ ; las de peso 3 son los giros de $g (X)$ .
El mismo Hamming en orden natural no es cíclico: 4 de sus 16 palabras sobreviven al giro. De los 30 reordenamientos distintos del (7,4), sólo 2 son cíclicos.