El producto cíclico y los quasi-cíclicos

El código producto arma un código grande con dos chicos: un arreglo con cada fila en uno y cada columna en el otro. Si los dos son cíclicos, el producto puede serlo o no, y no depende de los códigos: depende del orden en que se leen las celdas. Leído en diagonal, con largos coprimos, el arreglo entero queda descripto por un solo polinomio generador.

01 · Dos maneras de leer el arreglo

Sean $C_{1}$ un código cíclico $(n_{1}, k_{1})$ con generador $g_{1} (X)$ y $C_{2}$ uno $(n_{2}, k_{2})$ con generador $g_{2} (X)$ . El producto $C_{1} \otimes C_{2}$ son los arreglos de $n_{2}$ filas por $n_{1}$ columnas con cada fila en $C_{1}$ y cada columna en $C_{2}$ : un código $(n_{1} n_{2}, k_{1} k_{2})$ con $d_{min} = d_{1} d_{2}$ .

Como conjunto de arreglos, el producto no depende de ningún orden. Pero ser cíclico es una propiedad del vector: girar $v (X)$ una posición, $X v (X)$ módulo $X^{n} + 1$ , y ver si cae en el código. Para eso hay que decir qué celda es la posición $m$ del vector, y hay dos respuestas naturales.

Por filas. La posición $m$ va a la fila $⌊ m / n_{1} ⌋$ , columna $m \mod n_{1}$ : una fila entera, después la siguiente. Girar una posición pasa el último bit de cada fila al principio de la siguiente, y una fila queda armada con pedazos de dos. Girar $n_{1}$ posiciones, en cambio, baja cada fila un lugar y la última sube a la primera: las filas no cambian y cada columna gira una posición, así que todo sigue en el código. Con la paridad (5,4) en las filas y la (3,2) en las columnas, un código (15,8): los únicos giros que dejan las 256 palabras adentro son el de 5 y el de 10, y el de una posición saca a 192.

El orden del teorema chino del resto. La posición $m$ va a la celda

fila m \mod n_{2}, columna m \mod n_{1}

Si $mcd (n_{1}, n_{2}) = 1$ , el teorema chino del resto dice que los dos restos determinan a $m$ entre $0$ y $n_{1} n_{2} - 1$ , y que todo par de restos aparece una vez: cada celda recibe exactamente una posición. Con $n_{1} = 5$ y $n_{2} = 3$ , el arreglo de 3 × 5 se numera así:

	col 0	col 1	col 2	col 3	col 4
fila 0	0	6	12	3	9
fila 1	10	1	7	13	4
fila 2	5	11	2	8	14

Seguidas en orden, las posiciones bajan en diagonal: una fila abajo y una columna a la derecha por paso. Cuando el camino sale por abajo vuelve por arriba, cuando sale por la derecha vuelve por la izquierda, y recorre las quince celdas antes de volver a la 0.

02 · Por qué el giro queda adentro

Proposición. Si $C_{1}$ y $C_{2}$ son cíclicos y $mcd (n_{1}, n_{2}) = 1$ , el producto leído en el orden del teorema chino del resto es un código cíclico de largo $n = n_{1} n_{2}$ .

Paso 1: el giro mueve cada celda en diagonal. Girar una posición lleva el bit de la posición $m$ a la $m + 1$ , módulo $n$ . Los dos restos suben uno: el bit de la celda $(i, j)$ pasa a la $(i + 1, j + 1)$ , la fila módulo $n_{2}$ y la columna módulo $n_{1}$ . Como $n$ es múltiplo de los dos, la vuelta de $n - 1$ a $0$ también respeta la regla.

Paso 2: cada fila nueva es una fila vieja girada. La fila $i + 1$ del arreglo girado es la fila $i$ del original con cada bit corrido una columna, la última a la primera: su giro cíclico. Como $C_{1}$ es cíclico, sigue en $C_{1}$ .

Paso 3: lo mismo con las columnas. La columna $j + 1$ nueva es la $j$ vieja girada una fila, y sigue en $C_{2}$ . Un arreglo con todas sus filas en $C_{1}$ y todas sus columnas en $C_{2}$ es una palabra del producto.

Leído por filas, el Paso 1 falla: $m + 1$ cambia de fila sólo cuando $m$ termina una, y el bit que cruza no cae en la misma columna para todas. La diagonal es justamente el orden en que un paso del vector es un paso en las dos direcciones a la vez.

Arranca leyendo por filas, con la paridad en los dos lados. Apostá y girá; después pasá a la diagonal y apostá de nuevo. Probá cinco giros seguidos por filas, y mirá el resto por g(X) en los dos órdenes: el generador describe una sola de las dos lecturas. Con la repetición (3,1) en las columnas pasa algo distinto, y vale la pena ver por qué.

03 · El generador, en una fórmula

Si el producto es cíclico, tiene un polinomio generador: la palabra no nula de menor grado, de grado $n - k$ , de la que todas las demás son múltiplos. Como $n_{1}$ y $n_{2}$ son coprimos, hay enteros $a$ y $b$ con $a n_{1} + b n_{2} = 1$ , y con ellos

g (X) = mcd [X^{n_{1} n_{2}} + 1, g_{1} (X^{b n_{2}}) g_{2} (X^{a n_{1}})]

que es la ecuación (32) del apunte. Los exponentes se reducen módulo $n$ , porque $X^{n} = 1$ en las cuentas módulo $X^{n} + 1$ ; por eso $a$ o $b$ negativos no molestan. Por qué es así, en tres pasos.

Paso 1: dos exponentes que son las dos direcciones. El número $b n_{2}$ deja resto 1 al dividirlo por $n_{1}$ (porque $b n_{2} = 1 - a n_{1}$ ) y resto 0 al dividirlo por $n_{2}$ : es la posición de la celda (fila 0, columna 1), un paso a lo largo de la fila. Del mismo modo $a n_{1}$ es la celda (fila 1, columna 0), un paso a lo largo de la columna. Y la celda (fila $i$ , columna $j$ ) es la posición $j b n_{2} + i a n_{1}$ módulo $n$ , que tiene los dos restos que corresponden.

Paso 2: un producto exterior es un producto de polinomios. Sean $u (X)$ una palabra de $C_{1}$ y $w (X)$ una de $C_{2}$ , y el arreglo que tiene $u$ en cada fila donde $w$ tiene un 1. Por el Paso 1, su bit de la celda $(i, j)$ es el coeficiente de $X^{j b n_{2} + i a n_{1}}$ , así que el arreglo, como polinomio, es

v (X) = u (X^{b n_{2}}) w (X^{a n_{1}}) mód X^{n} + 1

Toda palabra del producto es suma de arreglos así.

Paso 3: los ceros. Sea $γ$ una raíz de $X^{n} + 1$ , en el cuerpo $GF (2^{m})$ donde se parte en factores de grado uno. Evaluada ahí, la palabra del Paso 2 vale $u (γ^{b n_{2}}) w (γ^{a n_{1}})$ . Si $γ^{b n_{2}}$ es raíz de $g_{1}$ , el primer factor se anula para toda $u$ de $C_{1}$ , que son múltiplos de $g_{1}$ ; lo mismo con $g_{2}$ y el segundo. Si ninguna de las dos cosas pasa, $u = g_{1}$ y $w = g_{2}$ dan una palabra que no se anula en $γ$ . Las raíces comunes de todo el código, que son las de $g$ , son entonces las raíces de $X^{n} + 1$ que anulan a $g_{1} (X^{b n_{2}}) g_{2} (X^{a n_{1}})$ : el mcd. Con $n$ impar, $X^{n} + 1$ no tiene raíces repetidas y el argumento cierra así.

El polinomio de paridad sale del mismo razonamiento al revés: $γ$ es raíz de $h$ cuando no es raíz de $g$ , o sea cuando $γ^{b n_{2}}$ es raíz de $h_{1}$ y $γ^{a n_{1}}$ es raíz de $h_{2}$ . Las dos condiciones a la vez son un mcd, no un producto:

h (X) = mcd [X^{n} + 1, h_{1} (X^{b n_{2}}), h_{2} (X^{a n_{1}})]

Con los exponentes ya reducidos, $X^{n} + 1$ tiene que estar en el mcd. Las dos fórmulas, la de $g$ y la de $h$ , se compararon con el código armado celda por celda en 64 productos: todos los pares de cíclicos no triviales con largos (5, 3), (3, 5), (7, 3), (7, 2), (5, 2), (3, 4), (5, 4), (7, 4) y (9, 2), pares incluidos. Coinciden en los 64.

Un ejemplo entero. La paridad (5,4) en las filas, $g_{1} = 1 + X$ , y la (3,2) en las columnas, $g_{2} = 1 + X$ . Como $2 \cdot 5 + (- 3) \cdot 3 = 1$ , $a = 2$ y $b = - 3$ : $b n_{2} = - 9 \equiv 6$ y $a n_{1} = 10$ , que en la tabla de la sección 01 son la celda (0, 1) y la (1, 0). Entonces

\begin{matrix} g_{1} (X^{6}) g_{2} (X^{10}) & = (1 + X^{6}) (1 + X^{10}) \\ = 1 + X^{6} + X^{10} + X^{16} \\ \equiv 1 + X + X^{6} + X^{10} \end{matrix}

módulo $X^{15} + 1$ , y el mcd con $X^{15} + 1$ es

\begin{matrix} g (X) & = 1 + X + X^{2} + X^{5} + X^{6} + X^{7} \\ = (1 + X) (1 + X + X^{2}) (1 + X + X^{2} + X^{3} + X^{4}) \end{matrix}

de grado 7 = 15 − 8, como tiene que ser. Se lee también por los ceros: $1 + X^{6}$ comparte con $X^{15} + 1$ el factor $1 + X^{3}$ , y $1 + X^{10}$ comparte $1 + X^{5}$ ; $g$ es su mínimo común múltiplo, $(1 + X + X^{2}) (1 + X^{5})$ . Y $h (X) = (1 + X + X^{4}) (1 + X^{3} + X^{4})$ , los dos factores de $X^{15} + 1$ que quedan. Enumeradas las 256 palabras en orden diagonal, la no nula de menor grado es ese $g$ .

Un código hecho en dos dimensiones queda descripto por un solo polinomio, y hereda todo lo de la unidad: se codifica con un registro de desplazamiento de $n - k$ etapas, y el síndrome es un resto. Del lado del receptor sigue sirviendo la estructura: la palabra recibida se reacomoda en el arreglo y se decodifica por filas con el decodificador de $C_{1}$ y por columnas con el de $C_{2}$ , con el equipamiento de los dos códigos chicos y no el de uno de largo $n_{1} n_{2}$ .

04 · Donde la construcción no alcanza

Sin largos coprimos no hay diagonal. Con $mcd (n_{1}, n_{2}) = d > 1$ , los dos restos vuelven a ser 0 a la vez en $mcm (n_{1}, n_{2}) = n_{1} n_{2} / d$ , y la diagonal se cierra antes de pasar por todas las celdas. En un arreglo de 3 × 3 recorre la diagonal principal, tres celdas de nueve; en uno de 4 filas por 6 columnas, 12 de 24. La regla $m \mapsto (m \mod n_{2}, m \mod n_{1})$ deja de ser un orden de lectura: le asigna la misma celda a varias posiciones y ninguna a otras.

La distancia es la del producto, no la mejor. La construcción garantiza $d_{min} = d_{1} d_{2}$ y nada más, y ser cíclico no la mejora: el código es el mismo conjunto de arreglos, leído de otra manera. La paridad (5,4) por la repetición (3,1) da un cíclico (15,4) con $d_{min} = 2 \cdot 3 = 6$ , generado por $1 + X + X^{5} + X^{6} + X^{10} + X^{11}$ . De largo 15 hay tres cíclicos (15,4), y enumerados dan distancias 8, 6 y 8: el producto es justo el peor. Lo que compra es otra cosa: un decodificador hecho con dos chicos.

05 · Los quasi-cíclicos

Definición. Un código lineal es quasi-cíclico si hay un entero $n_{0} \neq 1$ tal que girar cualquier palabra $n_{0}$ posiciones, o un múltiplo de $n_{0}$ , da otra palabra. A $n_{0}$ se lo llama la restricción de desplazamiento. Los cíclicos son el caso $n_{0} = 1$ . El dual de un quasi-cíclico vuelve a ser quasi-cíclico, con el mismo $n_{0}$ .

El producto de la sección 01, leído por filas, ya era uno: se cierra con giros de $n_{0} = n_{1}$ , una fila entera, y no con giros de uno. Cambia cuando todas las filas son iguales, como con la repetición (3,1) en las columnas: entonces el vector leído por filas es la misma fila tres veces, coincide con el leído en diagonal, y es cíclico en los dos órdenes. El ejemplo mínimo del apunte es el (9, 3) de la ecuación (33), con $n_{0} = 3$ :

G = (\begin{array}{l} 111 100 110 \\ 110 111 100 \\ 100 110 111 \end{array})

con la posición 0 a la izquierda. Cada fila es la anterior girada tres posiciones: la matriz generadora está hecha de bloques de tres que giran juntos. Enumeradas sus ocho palabras, tres pesan 4 y cuatro pesan 6, así que $d_{min} = 4$ . Giradas tres posiciones, las ocho caen en el código; giradas una o dos, la única que se queda es la nula.

Por qué se cierra con tres. Con el mensaje $(u_{0}, u_{1}, u_{2})$ , la palabra son tres bloques, y el bloque $j$ , de las posiciones $3 j$ a $3 j + 2$ , es

(u_{0} + u_{1} + u_{2}, u_{j} + u_{j + 1}, u_{j})

con los índices módulo 3: dos bits de paridad y uno de información, intacto, al final del bloque. Los tres mensajes con un solo 1 dan las tres filas de $G$ , y la regla reproduce las ocho palabras. Es una forma sistemática por bloques. Y la regla es la misma para los tres bloques, con $j$ corrido: girar tres posiciones pasa el bloque $j$ al lugar del $j + 1$ , que es la palabra del mensaje $(u_{2}, u_{0}, u_{1})$ . Girar una posición, en cambio, mete un bit de información en un lugar de paridad.

En general, un quasi-cíclico $(m n_{0}, m k_{0})$ tiene $m$ bloques de $n_{0}$ símbolos, cada uno con $k_{0}$ de información y $n_{0} - k_{0}$ de paridad, y su $G$ se lleva a filas de bloques en las que cada una es la anterior girada un bloque. La matriz entera queda dada por su primera fila de bloques. Su dual, el (9, 6), también se cierra con giros de 3 y no de 1, y tiene $d_{min} = 2$ .

La simetría parcial se paga con menos estructura que un cíclico, pero da algo que el cíclico no: los bloques se procesan en paralelo, y el catálogo de largos y tasas es mucho más amplio. Es la forma en que se usan hoy los códigos LDPC de los estándares, que son quasi-cíclicos por esta razón.

Para tener a mano

Ser cíclico depende del orden de lectura. Por filas, el producto se cierra con giros de $n_{1}$ ; con la (5,4) por la (3,2), el giro de uno saca 192 de las 256 palabras.
Orden chino: la posición $m$ va a la fila $m \mod n_{2}$ , columna $m \mod n_{1}$ . Exige $mcd (n_{1}, n_{2}) = 1$ . Un giro mueve cada celda una fila abajo y una columna a la derecha: gira cada fila y cada columna.
$g = mcd [X^{n} + 1, g_{1} (X^{b n_{2}}) g_{2} (X^{a n_{1}})]$ con $a n_{1} + b n_{2} = 1$ ; $b n_{2}$ es un paso por la fila y $a n_{1}$ uno por la columna. Exponentes módulo $n$ .
$h$ es el mcd de los tres, $X^{n} + 1$ , $h_{1} (X^{b n_{2}})$ y $h_{2} (X^{a n_{1}})$ , no su producto.
(5,4) ⊗ (3,2) en diagonal: $g = (1 + X + X^{2}) (1 + X^{5})$ , un (15,8) con $d_{min} = 4$ .
La distancia sigue siendo $d_{1} d_{2}$ : (5,4) ⊗ (3,1) es el (15,4) cíclico de distancia 6, contra 8 de los otros dos.
Quasi-cíclico: se cierra con giros de $n_{0} \neq 1$ . El (9, 3): bloque $j$ = $(u_{0} + u_{1} + u_{2}, u_{j} + u_{j + 1}, u_{j})$ , $d_{min} = 4$ , cerrado con giros de 3; con uno o dos sólo queda la palabra nula.