Las clases conjugadas y los polinomios mínimos

Un código BCH se especifica por las raíces que sus palabras tienen que anular. Las palabras son binarias; las raíces viven en una extensión, GF(2ᵐ). Para pasar de unas a otras hacen falta cuatro herramientas del cuerpo: el orden de un elemento, que dice qué longitudes se pueden construir; las clases conjugadas, que dicen qué raíces vienen juntas; el polinomio mínimo, que es lo que una clase le cuesta al generador; y el costo de cada operación, que decide cómo se arma el decodificador. Los ejemplos van en GF(2⁴) con $p(X)=1+X+X^4$, donde ${\alpha }^4=1+\alpha$: el cuerpo de las potencias de α.

01 · El orden de un elemento

El orden de un elemento no nulo $\gamma \in \text{GF}(2^m)$ es el menor entero positivo $n$ tal que ${\gamma }^n=1$. Todo elemento no nulo cumple ${\gamma }^{2^m-1}=1$, y por eso el orden divide a $2^m-1$: si ${\gamma }^N=1$ y $N=qn+r$ con $0\le r<n$, entonces ${\gamma }^r=1$, y como $n$ es el menor, $r=0$. Para una potencia de $\alpha$ el orden sale sin recorrer nada:

$$\text{ord}({\alpha }^i)=\frac{2^m-1}{\text{mcd}(i,2^m-1)}$$

Los de orden máximo, $2^m-1$, son los elementos primitivos. En GF(2⁴), con el orden de cada uno de los quince calculado por potencias sucesivas y contrastado con la fórmula:

Para lo que sigue, el orden importa por una razón: un elemento de orden $n$ habilita códigos de longitud $n$. Si $\beta$ tiene orden $n$, es raíz de $X^n+1$, y sus potencias $1,\beta ,\dots ,{\beta }^{n-1}$ son $n$ raíces distintas de ese polinomio: todas las que tiene. Las longitudes posibles en GF(2ᵐ) son los divisores de $2^m-1$. En GF(2⁶) son 1, 3, 7, 9, 21 y 63, y ${\alpha }^3$ tiene orden 21: es la raíz de un código de longitud 21 sobre un cuerpo cuyo elemento primitivo tiene orden 63. Contados uno por uno, GF(2⁶) tiene 12 elementos de orden 21 y 36 primitivos. En GF(2⁵) y GF(2⁷), donde 31 y 127 son primos, todo elemento distinto de 1 es primitivo, y la única longitud que no es trivial es la entera.

02 · Elevar al cuadrado es lineal

En un cuerpo de característica dos,

$${(a+b)}^2=a^2+ab+ba+b^2=a^2+b^2$$

porque $ab+ba=2ab=0$. La consecuencia es la que organiza toda la unidad.

Paso 1: un polinomio binario al cuadrado es el mismo polinomio en $X^2$. Si $f(X)=\sum f_i{X}^i$ tiene coeficientes en GF(2), la linealidad del cuadrado da $f{(X)}^2=\sum f_i^2{X}^{2i}$, y como cada $f_i$ es 0 o 1, $f_i^2=f_i$:

$$f{(X)}^2=f(X^2)$$

Paso 2: evaluado en una raíz. Si $f(\gamma )=0$ con $\gamma$ en GF(2ᵐ), entonces $f({\gamma }^2)={[f(\gamma )]}^2=0$: ${\gamma }^2$ también es raíz, y por lo mismo ${\gamma }^4$, ${\gamma }^8$, y así. El cuerpo es finito, así que la sucesión se cierra.

La linealidad también se ve en coordenadas. Si $a=\sum a_i{\alpha }^i$, entonces $a^2=\sum a_i{\alpha }^{2i}$, y una vez reducidos los ${\alpha }^{2i}$ cada bit del resultado es una suma fija de bits de la entrada. En GF(2⁴), con ${\alpha }^4=1+\alpha$ y ${\alpha }^6={\alpha }^2+{\alpha }^3$:

$$a^2=(a_0+a_2,a_2,a_1+a_3,a_3)$$

Dos XOR, comprobado sobre los dieciséis elementos. Y una caracterización que vuelve en la decodificación: $a$ está en GF(2) si y sólo si $a^2=a$, porque las únicas soluciones de $X^2+X=X(X+1)=0$ son 0 y 1.

03 · Las clases conjugadas

Los elementos $\gamma ,{\gamma }^2,{\gamma }^{2^2},\dots ,{\gamma }^{2^{e-1}}$, donde $e$ es el menor entero positivo con ${\gamma }^{2^e}=\gamma$, forman la clase conjugada de $\gamma$. Por la sección anterior, un polinomio binario que se anula en uno se anula en todos.

Con $\gamma ={\alpha }^i$, elevar al cuadrado es duplicar el exponente módulo $2^m-1$, y la clase queda descripta por sus exponentes, la clase ciclotómica de $i$:

$$C_i=\{i,2i,4i,\dots \}\text{módulo }{2}^m-1$$

En GF(2⁴), módulo 15, los exponentes de ${\alpha }^3$ van 3, 6, 12, 24 ≡ 9 y 18 ≡ 3: la clase se cierra en cuatro pasos. Las quince potencias se reparten en cinco clases: $C_0=\{0\}$, $C_1=\{1,2,4,8\}$, $C_3=\{3,6,9,12\}$, $C_5=\{5,10\}$ y $C_7=\{7,11,13,14\}$.

Tres propiedades, cada una con su porqué.

Las clases particionan los no nulos. Elevar al cuadrado es una biyección: si $a^2=b^2$, entonces ${(a+b)}^2=0$ y $a=b$. Una permutación de un conjunto finito se descompone en ciclos disjuntos, y las clases son esos ciclos.

Los conjugados tienen el mismo orden. El orden $n$ de $\gamma$ divide a $2^m-1$, que es impar, así que ${({\gamma }^2)}^k=1$ pide que $n$ divida a $2k$, y eso es que divida a $k$. En la tabla de la sección 01 cada fila es una unión de clases: la de orden 15 es $C_1\cup C_7$.

El tamaño de una clase divide a $m$. Todo elemento cumple ${\gamma }^{2^m}=\gamma$: a los $m$ cuadrados la sucesión volvió seguro, y una sucesión periódica que vuelve en $m$ pasos tiene un período que divide a $m$. En GF(2⁴) los tamaños son 1, 4, 4, 2 y 4. En GF(2⁵), con 31 primo, hay siete clases: la de 0 y seis de tamaño 5. En GF(2⁶) hay trece clases: la de 0, una de tamaño 2, dos de 3 y nueve de 6. En GF(2⁸), treinta y cinco: la de 0, una de 2, tres de 4 y treinta de 8.

Una clase corta dice que el elemento vive en un cuerpo más chico. ${\alpha }^5$ cumple ${({\alpha }^5)}^4={\alpha }^{20}={\alpha }^5$, y los elementos de GF(2⁴) con $a^4=a$ son exactamente cuatro: $0,1,{\alpha }^5,{\alpha }^{10}$. Son un GF(2²) adentro de GF(2⁴), y por eso pedir ${\alpha }^5$ como raíz va a costar sólo grado 2.

04 · El polinomio mínimo

El polinomio mínimo de $\gamma$ es el polinomio mónico de menor grado con coeficientes en GF(2) que tiene a $\gamma$ por raíz. Cuando $\gamma ={\alpha }^i$ se lo escribe ${\phi }_i(X)$, y se obtiene como producto sobre la clase entera:

$${\phi }_i(X)=\prod _{j\in C_i}(X+{\alpha }^j)$$

Los factores tienen coeficientes en GF(2ᵐ); el producto, no. La prueba en tres pasos, con $\phi (X)=\prod (X+{\gamma }^{2^j})$ y $j$ de 0 a $e-1$.

Paso 1: al cuadrado, el producto se reordena. Cada factor al cuadrado es $X^2+{\gamma }^{2^{j+1}}$. Cuando $j$ recorre la clase, $j+1$ también: el último pasa a ser el primero, porque ${\gamma }^{2^e}=\gamma$. Entonces $\phi {(X)}^2=\phi (X^2)$.

Paso 2: los coeficientes son sus propios cuadrados. Con $\phi (X)=\sum p_k{X}^k$, la linealidad da $\phi {(X)}^2=\sum p_k^2{X}^{2k}$, mientras $\phi (X^2)=\sum p_k{X}^{2k}$. Igualando, $p_k^2=p_k$, y por la caracterización de la sección 02 cada $p_k$ es 0 o 1.

Paso 3: es el de menor grado. Un polinomio binario que se anula en $\gamma$ se anula en los $e$ conjugados, que son distintos, así que tiene grado $\ge e$. El producto tiene grado $e$, es mónico y es binario: es el mínimo, y su grado es $|C_i|$. Además divide a todo polinomio binario $f(X)$ que tenga a $\gamma$ por raíz: el resto de dividir $f$ por $\phi$ es binario, se anula en $\gamma$ y tiene grado menor que $e$, así que es cero. Y es irreducible: un factor binario que tuviera a $\gamma$ por raíz se llevaría la clase entera.

El producto sobre $C_3$, factor por factor, en el orden en que los da el cuadrado:

Hasta el último factor los coeficientes son elementos cualesquiera del cuerpo, y con el último caen todos a la vez en GF(2). Los cinco polinomios mínimos de GF(2⁴):

${\phi }_1(X)$ es el $p(X)$ con que se construyó el cuerpo, como tenía que ser: $\alpha$ es su raíz por definición. La tabla no hace falta tenerla a mano: en el círculo de abajo se arma sola, elevando al cuadrado.

Arranca sin nada elegido. Empezá por ${\alpha }^3$ y mirá cuántos coeficientes quedan fuera de GF(2) en cada paso. Después tocá ${\alpha }^5$, que está a dos lugares de distancia en el círculo y tiene un mínimo de grado 2, y $1$, cuya clase se cierra en el primer cuadrado. Si cerrás las cinco clases, el producto deja de tener términos en el medio.

05 · El producto de todos los mínimos

Todo elemento no nulo de GF(2ᵐ) es raíz de $X^{2^m-1}+1$, y son $2^m-1$ raíces distintas para un polinomio de ese grado: no tiene otras. Las clases las particionan, cada clase son las raíces de su mínimo, y dos polinomios mónicos con las mismas raíces simples son el mismo:

$$X^{2^m-1}+1=\prod _i{\phi }_i(X)$$

con el producto sobre un representante de cada clase. En GF(2⁴),

Multiplicados los mínimos de cada clase, el producto da $X^{2^m-1}+1$ exacto para $m$ de 3 a 8, con 3, 5, 7, 13, 19 y 35 factores. Como los mínimos son irreducibles, ésta es la factorización completa en irreducibles, la que da los códigos cíclicos: cada polinomio generador de longitud 15 es un producto de algunos de estos cinco factores, y hay $2^5=32$ elecciones, contando las dos triviales.

La tabla también ordena lo que en la Unidad 2 eran tres polinomios sueltos de grado 4. Los tres son irreducibles, porque son mínimos, y no hay otros: un irreducible de grado 4 tiene sus raíces en GF(2⁴), así que es el mínimo de alguna clase de tamaño 4. Dos son primitivos, ${\phi }_1$ y ${\phi }_7$, porque sus raíces tienen orden 15. El tercero, ${\phi }_3=1+X+X^2+X^3+X^4$, tiene raíces de orden 5: es el $P(x)$ con el que el ciclo de α se cerraba en el paso cinco, y el LFSR que reparte los quince estados en tres órbitas de cinco. Su raíz no genera porque el orden de un elemento es el de toda su clase. Y ${\phi }_7$ es el recíproco de ${\phi }_1$, con los coeficientes al revés, porque $7\equiv -8$ módulo 15: sus raíces son las inversas de las de ${\phi }_1$.

La misma cuenta, más grande: en GF(2⁶) hay nueve mínimos de grado 6 y seis son primitivos; en GF(2⁸), treinta de grado 8 y dieciséis primitivos. Son $36/6$ y $128/8$: los elementos primitivos, agrupados en clases de $m$.

06 · Una raíz no se pide sola

Todo lo anterior se resume en una restricción: no se puede prescribir una raíz aisladamente. Un polinomio binario que se anula en ${\alpha }^i$ es múltiplo de ${\phi }_i$, y se anula en toda la clase $C_i$, se quiera o no. Lo que una raíz le cuesta al generador de un código no es grado 1: es el tamaño de su clase. Pedir $\alpha ,{\alpha }^2,{\alpha }^3,{\alpha }^4$ son cuatro raíces y trae ocho: las de $C_1$ y las de $C_3$, con un generador de grado 8. Es el (15,7) de los códigos BCH, y por eso el generador se arma como el mínimo común múltiplo de los mínimos y no como su producto.

El caso que lo muestra es cortar la clase a la mitad. Pedir sólo $\alpha$ y ${\alpha }^2$ da

$$(X+\alpha )(X+{\alpha }^2)={\alpha }^3+{\alpha }^{5}X+X^2$$

que tiene esas dos raíces, pero coeficientes fuera de GF(2). No genera un código binario: sus múltiplos no son palabras de ceros y unos. El binario de menor grado con esas raíces es ${\phi }_1$, de grado 4. Y si el elemento $\beta$ del código no es primitivo, las clases se toman sobre sus exponentes, módulo su orden. Con $\beta ={\alpha }^3$ en GF(2⁶), de orden 21, la clase de $\beta$ es $\{1,2,4,8,16,11\}$ módulo 21, y su mínimo, $1+X+X^2+X^4+X^6$, tiene grado 6.

07 · Lo que cuesta cada operación

Construir y decodificar un código BCH gasta casi todo su tiempo en cuatro operaciones del cuerpo, y no cuestan lo mismo.

Suma. En la representación vectorial es un XOR bit a bit: $m$ compuertas independientes, sin reducción.

Producto. Hay dos caminos. En potencias, ${\alpha }^i{\alpha }^j={\alpha }^{(i+j)\text{mod}(2^m-1)}$: una suma de enteros, a cambio de dos consultas a una tabla de logaritmos y una de antilogaritmos. En la representación polinómica, el producto de los dos polinomios y la reducción módulo $p(X)$: es la que se lleva a hardware, porque no pide memoria. Si una de las dos entradas es una constante, el producto vuelve a ser una matriz binaria fija.

Cuadrado. Por la sección 02, una matriz binaria fija: XOR sin lógica secuencial, mucho más barato que un producto general.

Inversión. Es la cara. Con tablas, ${({\alpha }^i)}^{-1}={\alpha }^{(2^m-1)-i}$, con dos tablas de $2^m$ entradas. Por Fermat, como $a^{2^m-1}=1$, es $a^{-1}=a^{2^m-2}$, y como $2^m-2=2+4+\cdots +2^{m-1}$, se calcula multiplicando los $m-1$ cuadrados sucesivos de $a$: $m-1$ cuadrados y $m-2$ productos. O por el algoritmo de Euclides extendido sobre $a(X)$ y $p(X)$.

Contadas las compuertas de cada una, con los $p(X)$ del apunte, $1+X+X^4$ y $1+X^2+X^3+X^4+X^8$, y cada matriz armada fila por fila, comprobada sobre todos los elementos del cuerpo:

El producto general son $m^2$ AND y ${(m-1)}^2$ XOR para los productos parciales, más los de la reducción: 6 en GF(2⁴) y 28 en GF(2⁸). Una inversión por Fermat en GF(2⁸) son seis productos generales en cadena. Esa diferencia condiciona los algoritmos: el decodificador tiene una versión de Berlekamp-Massey cuyo único propósito es no dividir, y el síndrome par sale de elevar al cuadrado el impar, que es casi gratis. Las dos cosas vuelven en el decodificador en hardware.

08 · La cuenta en Python

Con fec_algebra, la librería del curso. Las clases se arman elevando al cuadrado en el cuerpo, no duplicando exponentes, así que cruzan la tabla de la sección 03 por otro camino; cada mínimo se multiplica factor por factor, imprimiendo el producto acumulado. Lo de abajo es la salida de correrlo.

from fec_algebra import GF, GFPoly

F = GF(m=4, primitive_poly=0b0011)            # GF(2⁴), p(X) = 1 + X + X⁴
a = F(2)                                      # α
log = {int(a ** i): i for i in range(15)}     # α^i → i

def clase(g):
    """γ, γ², γ⁴, … hasta volver a γ: elevando al cuadrado en el cuerpo."""
    c = [g]
    while c[-1] * c[-1] != g:
        c.append(c[-1] * c[-1])
    return c

def texto(p):
    """De X⁰ hacia arriba; un coeficiente que no es 0 ni 1 va como α^i."""
    t = []
    for k in range(p.degree + 1):
        c = int(p[k])
        if c:
            x = "" if k == 0 else "X" if k == 1 else f"X^{k}"
            t.append((x or "1") if c == 1 else f"a^{log[c]}{x}")
    return " + ".join(t)

vistos, producto = set(), GFPoly(F, [1])
for i in range(15):
    if i in vistos:
        continue
    phi = GFPoly(F, [1])
    for g in clase(a ** i):
        phi = phi * GFPoly(F, [F(1), g])      # (·)(X + γ): de mayor a menor grado
        vistos.add(log[int(g)])
        print(f"   · (X + a^{log[int(g)]}) -> {texto(phi)}")
    binario = all(int(phi[k]) < 2 for k in range(phi.degree + 1))
    print(f"phi_{i}(X) = {texto(phi)}   binario: {binario}")
    producto = producto * phi
print("producto:", texto(producto))
#    · (X + a^0) -> 1 + X
# phi_0(X) = 1 + X   binario: True
#    · (X + a^1) -> a^1 + X
#    · (X + a^2) -> a^3 + a^5X + X^2
#    · (X + a^4) -> a^7 + a^1X + a^8X^2 + X^3
#    · (X + a^8) -> 1 + X + X^4
# phi_1(X) = 1 + X + X^4   binario: True
#    · (X + a^3) -> a^3 + X
#    · (X + a^6) -> a^9 + a^2X + X^2
#    · (X + a^12) -> a^6 + a^4X + a^7X^2 + X^3
#    · (X + a^9) -> 1 + X + X^2 + X^3 + X^4
# phi_3(X) = 1 + X + X^2 + X^3 + X^4   binario: True
#    · (X + a^5) -> a^5 + X
#    · (X + a^10) -> 1 + X + X^2
# phi_5(X) = 1 + X + X^2   binario: True
#    · (X + a^7) -> a^7 + X
#    · (X + a^14) -> a^6 + a^1X + X^2
#    · (X + a^13) -> a^4 + a^8X + a^12X^2 + X^3
#    · (X + a^11) -> 1 + X^3 + X^4
# phi_7(X) = 1 + X^3 + X^4   binario: True
# producto: 1 + X^15

Un detalle muerde. El constructor de GFPoly toma los coeficientes de mayor a menor grado, así que [F(1), g] es $X+\gamma$; pero p[k] devuelve el coeficiente de $X^k$, de menor a mayor. Con el factor escrito [g, F(1)], que es $\gamma X+1$, el programa corre igual, todos los mínimos salen binarios y el producto sigue dando $1+X^{15}$, pero cada ${\phi }_i$ sale invertido: ${\phi }_1$ da $1+X^3+X^4$, que es el recíproco. Ninguna de las dos comprobaciones lo ve; lo ve la tabla.

Para tener a mano

1. El orden de ${\alpha }^i$ es $(2^m-1)/\text{mcd}(i,2^m-1)$. Un elemento de orden $n$ habilita longitud $n$, y $n$ divide a $2^m-1$. En GF(2⁶), ${\alpha }^3$ tiene orden 21.
2. ${(a+b)}^2=a^2+b^2$, y para $f$ binario $f({\gamma }^2)=f{(\gamma )}^2$. $a$ está en GF(2) si y sólo si $a^2=a$.
3. $C_i=\{i,2i,4i,\dots \}$ módulo $2^m-1$. Particionan los no nulos, comparten el orden, y su tamaño divide a $m$.
4. ${\phi }_i(X)={\prod }_{j\in C_i}(X+{\alpha }^j)$: binario porque es igual a su propio cuadrado, de grado $|C_i|$, irreducible, y divide a todo binario que se anule en ${\alpha }^i$.
5. GF(2⁴): ${\phi }_0=1+X$, ${\phi }_1=1+X+X^4$, ${\phi }_3=1+X+X^2+X^3+X^4$, ${\phi }_5=1+X+X^2$, ${\phi }_7=1+X^3+X^4$, y su producto es $X^{15}+1$.
6. $X^{2^m-1}+1={\prod }_i{\phi }_i(X)$, un factor por clase: 5 para $m=4$, 13 para 6, 35 para 8.
7. Una raíz no se pide sola: cuesta el tamaño de su clase. Media clase da coeficientes fuera de GF(2).
8. Suma y cuadrado son XOR fijos; el producto general, $m^2$ AND y su árbol de XOR; la inversión por Fermat, $m-1$ cuadrados y $m-2$ productos. La inversión es la que se evita.