Pedir t puede darte más

Un código BCH se diseña pidiendo cuántos errores tiene que corregir, $t$, y el procedimiento devuelve el código. Uno esperaría que el código corrija lo que pidió. A veces corrige más. Lo que garantiza un BCH no lo decide la $t$ que pedís sino la tira más larga de raíces consecutivas que dejó la conjugación, y en los códigos de tasa baja suele ser más larga. En largo 255, 31 de los 64 valores de $t$ posibles dan un código que garantiza más: pedís 32 y el (255,47) corrige 42. En largo 31, el (31,11) sale pidiendo 4 y corrige 5. En los códigos de tasa alta no pasa nunca.

01 · Las raíces vienen de a clases

Un código cíclico $(n,k)$ queda determinado por su polinomio generador $g(X)$, binario y de grado $n-k$. Sus coeficientes son ceros y unos, pero sus raíces, en general, no están en GF(2): están en el cuerpo de extensión $\mathrm{GF}(2^m)$, cuyos elementos no nulos son las potencias ${\alpha }^0,{\alpha }^1,\dots ,{\alpha }^{2^m-2}$ de un elemento primitivo $\alpha$. Acá todo es de largo $n=2^m-1$, y una raíz se nombra por su exponente: la raíz 3 es ${\alpha }^3$.

Las raíces de un polinomio binario no se eligen de a una. En un cuerpo de característica dos, elevar al cuadrado es lineal, $(a+b{)}^2=a^2+b^2$, y los coeficientes de $f$ cumplen $0^2=0$ y $1^2=1$. Por eso, si $f$ es binario,

$$f({\gamma }^2)={[f(\gamma )]}^2$$

y una raíz $\gamma$ arrastra a ${\gamma }^2,{\gamma }^4,{\gamma }^8,\dots$ hasta que la sucesión se cierra. Ese conjunto es la clase conjugada de $\gamma$. Para $\gamma ={\alpha }^i$, en exponentes, es la clase ciclotómica

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

y el binario de menor grado que se anula en ${\alpha }^i$ es su polinomio mínimo, el producto sobre la clase entera:

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

En $\mathrm{GF}(2^4)$ las clases son $C_1=\{1,2,4,8\}$, $C_3=\{3,6,9,12\}$, $C_5=\{5,10\}$ y $C_7=\{7,11,13,14\}$, más $C_0=\{0\}$. Pedir que $g$ se anule en ${\alpha }^3$ es pedirlo en ${\alpha }^6,{\alpha }^9,{\alpha }^{12}$ también, quiera uno o no.

Hay una forma de leer las clases sin hacer cuentas. Con $n=2^m-1$, multiplicar un exponente por 2 módulo $n$ es rotar sus $m$ bits un lugar a la izquierda: el bit que se cae por arriba vuelve por abajo, porque $2^m\equiv 1$. El 3 es 0011, y rota a 0110 = 6, 1100 = 12, 1001 = 9. Una clase es un patrón de bits con todas sus rotaciones. La encabeza la rotación menor, que es la que tiene más ceros adelante. Y tiene $m$ elementos salvo que el patrón se repita: el 5 es 0101 y su clase tiene dos.

02 · Un BCH pide una tira de raíces

El código BCH primitivo de sentido estricto con distancia diseñada $d_0=2t+1$ es el cíclico de largo $2^m-1$ cuyo generador es el binario de menor grado con raíces en las $2t$ potencias consecutivas $\alpha ,{\alpha }^2,\dots ,{\alpha }^{2t}$. Tiene que ser múltiplo de cada polinomio mínimo, y para ser el de menor grado, de cada uno una sola vez:

$$g(X)=\mathrm{MCM}\{{\phi }_1(X),{\phi }_2(X),\dots ,{\phi }_{2t}(X)\}$$

La $t$ se elige; $k$ sale. Los exponentes pares no aportan nada, porque $2i$ está en la clase de $i$: alcanza con las clases de $1,3,\dots ,2t-1$, cada una de a lo sumo $m$ elementos, y por eso $n-k\le mt$. Con $m=4$ y $t=2$, $C_1$ y $C_3$ dan ocho raíces y el (15,7).

Lo que el código garantiza lo dice la cota BCH: si entre las raíces de $g$ hay $L$ potencias consecutivas de $\alpha$, la distancia mínima es al menos $L+1$. La prueba arma con esas $L$ filas de $H$ una Vandermonde, y sólo usa que los exponentes son consecutivos: no le importa si la raíz la pidió alguien o la trajo una clase. Así que la cota no se aplica a la tira pedida sino a la tira más larga de raíces consecutivas que tenga $g$, y si esa tira mide $L$, la capacidad de corrección garantizada es

$$t^{\prime }=\lfloor \frac{L}{2}\rfloor ,d_{\text{min}}\ge L+1$$

Las raíces pedidas son $1,\dots ,2t$, así que $L\ge 2t$. La pregunta es cuándo la conjugación la estira.

03 · La tira se estira si 2t + 1 no encabeza su clase

El exponente que sigue a la tira pedida es $2t+1$. Si no es raíz, la tira se corta ahí. Es raíz sólo si está en la clase de algún impar menor que ya se pidió, o sea, si no encabeza su clase: si alguna rotación de sus $m$ bits da un número más chico. Si entra, el siguiente, $2t+2=2(t+1)$, es par y ya está, porque es conjugado de $t+1$; y la pregunta pasa a $2t+3$. Se recorrieron los 124 valores de $t$ de los cinco largos de 15 a 255, comparando la tira más larga del generador con ese criterio: la tira pasa de $2t$ exactamente en los casos en que $2t+1$ no encabeza su clase.

En largo 31, con $t=4$, se piden las raíces 1 a 8 y entran cuatro clases de cinco:

$$\begin{array}{l}{C}_1=\{1,2,4,8,16\},C_3=\{3,6,12,17,24\},\\ C_5=\{5,9,10,18,20\},C_7=\{7,14,19,25,28\}\end{array}$$

El 9 es 01001, y una rotación lo lleva a 00101 = 5: está en $C_5$, que se pidió por el 5. Entra el 9, y el 10 por ser el doble del 5. El 11 es 01011, la menor de sus rotaciones, y ahí se corta. La tira es $1,\dots ,10$, de largo 10: el código es el (31,11) y garantiza $t^{\prime }=5$. Pedir 5 da el mismo generador. Las 20 raíces son las mismas; lo que cambia es la cuenta de cuántas se pidieron.

Arranca en largo 255 con $t=2$: el (255,239), donde la tira se corta justo después de lo pedido. Apostá antes de subir. La grilla tiene dieciséis exponentes por fila; las raíces en gris las trajo una clase y no tocan la tira, las azules la alargan.

04 · En tasa alta, los conjugados caen lejos

Un exponente chico tiene sus ceros adelante: el 5 en ocho bits es 00000101. Rotarlo sube unos a los bits altos y lo agranda, así que encabeza su clase, y sus otros siete miembros, 10, 20, 40, 80, 160, 65 y 130, quedan lejos de la tira. Un exponente pierde contra una rotación sólo si adentro tiene una racha de ceros más larga que la que tiene adelante. El primer impar que lo cumple tiene la forma 10…01, con más ceros en el medio que adelante: $2^{\lfloor m/2\rfloor +1}+1$, que es 9 en largo 15 y 31, 17 en 63 y 127, y 33 en 255. Mientras $2t+1$ no llegue ahí, todos los impares encabezan su clase y la conjugación no regala nada.

Medido sobre todos los $t$ de cada largo:

En los cinco largos, el primer $t$ que da más es $2^{\lfloor m/2\rfloor }$, y por debajo no hay ninguno. Ningún código con tasa mayor que 0,56 recibe nada: el de tasa más alta que sí recibe es el (127,71), con 0,559. En los de tasa alta las clases que entran tienen tamaño $m$ y no se tocan: en largo 31 y 127, hasta el último sin regalo, $n-k$ es exactamente $mt$. Cada clase aporta un impar pedido y $m-1$ conjugados que caen arriba, salteados, sin pegarse a la tira. En los otros tres largos la cuenta se despega de $mt$ por alguna clase corta, como la del 17 en largo 255, 00010001, que tiene cuatro elementos; pero una clase corta achica la redundancia, no alarga la tira.

05 · En tasa baja, la tira salta

Al subir $t$ los exponentes crecen, los ceros de adelante se acaban, y cada vez más impares tienen un hueco interno más largo que el de adelante. Ya no encabezan su clase: llegan solos, traídos por un impar más chico. En largo 255, con $t=32$ se piden las raíces 1 a 64, y los diez impares siguientes son todos rotaciones de algo pedido:

La tira llega hasta el 84 y se corta en el 85, que encabeza su propia clase de dos elementos. Mide 84: el (255,47) garantiza $t^{\prime }=42$, diez más que lo pedido. Pedir cualquier $t$ de 32 a 42 da el mismo generador, con 208 raíces repartidas en 27 clases. Recontado en cada largo:

Los valores de $t$ van desde 1 hasta el primero que deja $k=1$. En largo 255, los 31 regalos caen todos de $t=16$ en adelante: de esos 49 valores, casi dos de cada tres dan más. Y los 64 pedidos producen sólo 34 códigos: los otros 30 repiten un generador que ya había salido con una $t$ menor.

06 · Lo que se cita es la tira

Un código se nombra por la mayor $t$ que lo produce, que es la de su tira: el (31,11) es un código de $t=5$, el (63,18) de $t=10$, y el (255,47) de $t=42$. Las $t$ intermedias dan el mismo código con una distancia diseñada menor, y no tiene sentido listarlas.

El regalo no llega solo al decodificador. Un decodificador BCH arma $2t$ síndromes, $S_i=r({\alpha }^i)$, y corrige hasta la $t$ con la que se lo construyó. Si el (255,47) se decodifica con 64 síndromes, corrige 32. Para corregir 42 hay que calcular 84, que valen cero sobre toda palabra porque ${\alpha }^1,\dots ,{\alpha }^{84}$ son todas raíces de $g$. El codificador es el mismo: lo que se gana es leer bien el generador antes de dimensionar el decodificador.

Y la tira sigue siendo una cota. La distancia mínima real puede pasarla por razones que no tienen nada que ver con la conjugación, y detectarlo pide cotas más finas que la de la Vandermonde. Lo que la tira da es lo seguro.

Todo esto vale con $l_0=1$, la tira pedida desde $\alpha$. Si se la empieza en otro lado, el regalo aparece también en tasa alta, pero por otro motivo. En largo 31, pedir $t=1$ con $l_0=2$ es pedir ${\alpha }^2$ y ${\alpha }^3$: la clase de ${\alpha }^2$ trae a $\alpha$ y a ${\alpha }^4$, la tira queda $1,\dots ,4$, y sale el (31,21), que corrige dos. Ahí no hay suerte: el pedido pagó dos clases enteras para un solo error, y la conjugación devolvió lo que se había pagado.