Los códigos BCH

La Unidad 5 arma todos los códigos cíclicos de un largo factorizando $X^n+1$, pero no dice cuál corrige más: la distancia se conoce recién al enumerar. Los códigos BCH dan vuelta el orden. Se fija cuántos errores $t$ se quieren corregir, se piden $2t$ raíces consecutivas en un cuerpo de extensión, y el polinomio generador sale de esas raíces con la garantía puesta. Los publicaron Hocquenghem en 1959 y Bose y Ray-Chaudhuri en 1960.

01 · La definición

Sea $\beta$ un elemento de orden $n$ de $\text{GF}(2^m)$, y $l_0$ un entero no negativo. El código BCH binario de longitud $n$ y distancia diseñada $d_0=2t+1$ es el código cíclico generado por el polinomio binario de menor grado que tiene por raíces a las $2t$ potencias consecutivas

$${\beta }^{l_0},{\beta }^{l_0+1},\dots ,{\beta }^{l_0+2t-1}$$

Un polinomio con coeficientes en $\text{GF}(2)$ que se anula en ${\beta }^j$ se anula también en todos sus conjugados, así que es múltiplo del polinomio mínimo ${\phi }_j$ de ${\beta }^j$. Para que $g(X)$ se anule en las $2t$ potencias tiene que ser múltiplo de cada uno de sus polinomios mínimos, y para que tenga el menor grado tiene que ser exactamente el mínimo común múltiplo:

$$g(X)=\text{MCM}\{{\phi }_{l_0}(X),{\phi }_{l_0+1}(X),\dots ,{\phi }_{l_0+2t-1}(X)\}$$

El mínimo común múltiplo y no el producto, porque las $2t$ potencias caen casi siempre en menos de $2t$ clases conjugadas, y dos potencias de la misma clase comparten polinomio mínimo: cada uno entra una sola vez.

El código es cíclico de verdad. Como $\beta$ tiene orden $n$, toda potencia de $\beta$ es raíz de $X^n+1$; sus polinomios mínimos dividen a $X^n+1$, y su mínimo común múltiplo también. Y un divisor de $X^n+1$ genera un código cíclico de largo $n$.

La definición se lee también al revés, como prueba de pertenencia: un polinomio binario $v(X)$ de grado menor que $n$ es palabra si y sólo si

$$v({\beta }^j)=0\text{para }j=l_0,\dots ,l_0+2t-1$$

Si se anula en las $2t$ potencias, se anula en sus conjugadas, es múltiplo de cada polinomio mínimo y por lo tanto de su MCM. Es la lectura que usa el decodificador: evaluar lo recibido en esas raíces da los síndromes.

Dos nombres. El código es de sentido estricto si $l_0=1$, y primitivo si $n=2^m-1$, o sea si $\beta$ es un elemento primitivo; entonces se escribe $\beta =\alpha$. Casi todos los BCH de uso práctico son las dos cosas.

02 · Los dos cuerpos

La construcción usa dos cuerpos con papeles distintos, y confundirlos es la fuente de error más frecuente de la unidad.

$\text{GF}(2)$, el cuerpo base, es donde viven los coeficientes de $g(X)$ y los bits de las palabras. El código es binario: por el canal pasan ceros y unos. $\text{GF}(2^m)$, el cuerpo de extensión, es donde viven las raíces de $g(X)$. Ningún elemento suyo aparece jamás en el canal.

De ahí una asimetría. Para codificar alcanza con el cuerpo base: es dividir polinomios binarios por $g(X)$, con el mismo registro de desplazamiento de cualquier cíclico, y el cuerpo de extensión no interviene. Para decodificar hace falta el de extensión, porque los síndromes son lo recibido evaluado en raíces que son elementos de $\text{GF}(2^m)$. El codificador de un BCH es un codificador cíclico común; el decodificador es un procesador aritmético entero.

03 · El diseño, en cuatro pasos

Paso 1: el cuerpo. Se fija la longitud $n$ y se busca el menor $m$ tal que $n$ divida a $2^m-1$. Se toma $\beta ={\alpha }^{(2^m-1)/n}$, que tiene orden $n$.

Paso 2: las raíces. Se fija $t$ y se escriben las $2t$ potencias consecutivas de $\beta$.

Paso 3: las clases. Se reparten esas potencias en clases conjugadas y se anota el polinomio mínimo de cada clase, sin repetir.

Paso 4: el producto. Se multiplican los polinomios mínimos distintos. El resultado es $g(X)$, y el código es un $(n,n-\mathrm{deg}g)$.

La dimensión $k$ no se elige: sale. Se especifican el largo y la capacidad, y la tasa queda determinada por cuántas clases hicieron falta para cubrir las raíces pedidas.

04 · Los cuatro ejemplos

El (15,7). En $\text{GF}(2^4)$ con $p(X)=1+X+X^4$, primitivo de sentido estricto con $t=2$. Las raíces pedidas son $\alpha$, ${\alpha }^2$, ${\alpha }^3$ y ${\alpha }^4$. Las clases módulo 15 son $C_1=\{1,2,4,8\}$ y $C_3=\{3,6,9,12\}$: tres de las cuatro pedidas están en $C_1$ y la otra en $C_3$. Entran dos polinomios mínimos:

De grado 8: un (15,7). Se pidieron cuatro raíces y $g(X)$ tiene ocho: las cuatro pedidas más ${\alpha }^6$, ${\alpha }^8$, ${\alpha }^9$ y ${\alpha }^{12}$, que entraron por estar en las mismas clases. Enumeradas sus 128 palabras, la distancia mínima es 5: la diseñada, justa.

El (15,5). Con $t=3$ se piden $\alpha$ a ${\alpha }^6$. A las dos clases anteriores se suma $C_5=\{5,10\}$, cuyo polinomio mínimo, $1+X+X^2$, tiene grado 2:

De grado 10: un (15,5), con $d_{\text{min}}=7$ y distribución de pesos $A_0=1,A_7=15,A_8=15,A_{15}=1$. Es el código de referencia de toda la decodificación, y el del ejercicio resuelto de la unidad.

El (21,12), no primitivo. 21 divide a $2^6-1=63$ y a ningún $2^m-1$ menor, así que se trabaja en $\text{GF}(2^6)$ con $p(X)=1+X+X^6$, y se toma $\beta ={\alpha }^3$, de orden 21. Con $t=2$ las raíces pedidas son $\beta$, ${\beta }^2$, ${\beta }^3$, ${\beta }^4$, o sea ${\alpha }^3$, ${\alpha }^6$, ${\alpha }^9$, ${\alpha }^{12}$. Módulo 63, las clases son $\{3,6,12,24,48,33\}$ y $\{9,18,36\}$: dos polinomios mínimos, de grados 6 y 3,

$${\phi }_{\beta }(X)=1+X+X^2+X^4+X^6,{\phi }_{{\beta }^3}(X)=1+X^2+X^3$$ $$g(X)=1+X+X^4+X^5+X^7+X^8+X^9$$

De grado 9: un (21,12), y $g(X)$ divide a $X^{21}+1$. Enumeradas sus 4096 palabras, $d_{\text{min}}=5$. Los no primitivos agregan largos al catálogo, a cambio de trabajar en un cuerpo más grande que el que el largo pediría.

El (255,239). En $\text{GF}(2^8)$ con $p(X)=1+X^2+X^3+X^4+X^8$, con $t=2$. Las cuatro raíces $\alpha$ a ${\alpha }^4$ se reparten en dos clases de ocho elementos cada una, y el generador tiene grado 16:

Un (255,239) de tasa 0,937, que corrige dos errores por bloque de 255 bits con dieciséis de redundancia. Su $g(X)$ tiene once coeficientes no nulos, y eso es lo que cuesta su codificador en compuertas.

Y el caso más chico ya era conocido. Con $t=1$ primitivo y de sentido estricto, $g(X)={\phi }_1$, el polinomio primitivo mismo: el BCH es el código de Hamming de ese largo, el (15,11) o el (31,26). En el widget se arranca de ahí.

Arranca en el Hamming (15,11): dos raíces pedidas, dos agregadas, una tira de dos. Subí $t$ de a uno en largo 15 y mirá cuánto crece $n-k$ en cada paso. Después pasá a largo 31 con $t=1$ y corré $l_0$ a 2: pedís un error y mirá la tira. Volvé a $l_0=1$ y subí $t$ hasta 4. Y probá $l_0=0$ en largo 15 con $t=2$, mirando las dos últimas lecturas.

05 · La elección de l₀ y la tira más larga

Nada obliga a tomar $l_0=1$. En largo 31, sobre $\text{GF}(2^5)$ con $p(X)=1+X^2+X^5$, con $t=1$ y $l_0=1$ las raíces pedidas son $\alpha$ y ${\alpha }^2$, de la misma clase: $g(X)={\phi }_1$ y el código es el Hamming (31,26). Con $t=1$ y $l_0=2$ se piden ${\alpha }^2$ y ${\alpha }^3$, que están en clases distintas:

$$g(X)={\phi }_1(X){\phi }_3(X)=1+X^3+X^5+X^6+X^8+X^9+X^{10}$$

Un (31,21): cinco bits más de redundancia para corregir un solo error, que parece un mal negocio. No lo es. Ese $g(X)$ es idéntico al de $l_0=1$ con $t=2$, porque la clase de ${\alpha }^2$ trajo a $\alpha$ y a ${\alpha }^4$ sin que nadie los pidiera, y entre las raíces quedan cuatro potencias consecutivas, de $\alpha$ a ${\alpha }^4$. Enumeradas sus $2^{21}$ palabras, $d_{\text{min}}=5$: el código diseñado para corregir uno corrige dos.

La regla que sale de ahí: obtenido $g(X)$, se busca la tira más larga de exponentes consecutivos entre todas sus raíces, no sólo la que se pidió. Si mide $\delta -1$, la cota BCH vale con esa tira y el código tiene $d_{\text{min}}\ge \delta$: esa es la distancia diseñada efectiva. La tira puede dar la vuelta por el cero, porque los exponentes se leen módulo $n$.

$l_0=1$ es la elección habitual porque, para una misma capacidad, tiende a dar el generador de menor grado: los pares de la tira pedida caen en las clases de los impares. Pero no siempre es la óptima, y mirar el conjunto entero de raíces es parte del diseño. Cuántas veces la tira resulta más larga que la pedida, y en qué códigos, es lo que mide el ensayo Pedir t puede darte más.

06 · El catálogo

Al subir $t$ con el largo fijo, $k$ baja a saltos, y varios $t$ seguidos pueden dar el mismo $g(X)$. Por ejemplo, en largo 31 $t=4$ y $t=5$ dan el mismo (31,11): con $t=4$ se piden $\alpha$ a ${\alpha }^8$, la clase $C_5$ trae a ${\alpha }^9$ y a ${\alpha }^{10}$, y la tira llega a 10. Pedir $t=5$ no agrega ninguna raíz.

Un código, entonces, tiene un rango de $t$ que lo producen, y el catálogo lo lista con el mayor: el que su tira de raíces de verdad garantiza. Los $t$ menores del rango dan el mismo código con una distancia diseñada menor. Enumeradas sus 2048 palabras, el (31,11) tiene $d_{\text{min}}=11$, la que corresponde a $t=5$. La tabla recorre $t$ en los BCH primitivos de sentido estricto de largo 15, 31 y 63; la columna «desde» es el menor $t$ que ya da el código, cuando no coincide con el mayor.

Calculada armando $g(X)$ para cada $t$, y verificado en cada fila que el mayor $t$ es la mitad de la tira más larga del código. Las filas $(n,1)$ son la repetición: $g(X)$ tiene por raíces todas las potencias de $\alpha$ menos ${\alpha }^0=1$, y la tira llega a $n-1$. En largo 255 las ocho primeras filas, del (255,247) al (255,191), van con $t$ de 1 a 8 y cumplen $n-k=mt=8t$; la primera que se despega es el (255,187), con $t=9$: 68 contra 72.

El catálogo no depende del polinomio primitivo elegido: las clases son conjuntos de exponentes módulo $n$, y $k$ sale de cuántos exponentes cubren. El primitivo cambia los coeficientes de $g(X)$, no su grado.

07 · La redundancia: n − k ≤ mt

Un BCH binario primitivo de sentido estricto con capacidad diseñada $t$ cumple

$$n-k\le mt$$

Es un resultado de Mann, y la prueba entra en tres pasos.

Paso 1: los pares sobran. ${\beta }^{2i}={({\beta }^i)}^2$ es conjugada de ${\beta }^i$, así que está en su clase y comparte su polinomio mínimo. De las $2t$ potencias pedidas, las de exponente par no agregan nada.

Paso 2: quedan $t$ impares. Los exponentes $1,3,\dots ,2t-1$ aportan a lo sumo $t$ polinomios mínimos distintos.

Paso 3: cada uno pesa a lo sumo $m$. La clase de $i$ se cierra en a lo sumo $m$ duplicaciones, porque $2^{m}i\equiv i$ módulo $2^m-1$. El grado del MCM es a lo sumo la suma de los grados: $mt$.

Vale con igualdad mientras las clases de los impares son todas de tamaño $m$ y distintas entre sí, y se despega por dos motivos que la prueba deja a la vista. Medido en el primer $t$ donde se despega cada largo:

En largo 31 no hay clases cortas, porque 31 es primo y todas las clases no nulas tienen cinco elementos. Ahí el despegue llega sólo por coincidencia: $C_5=\{5,9,10,18,20\}$, y el impar 9 no aporta nada nuevo. Para $t$ chico la cota es exacta, y es la forma rápida de estimar la redundancia: en largo 255, ocho bits por error corregido.

08 · Lo que la construcción no da

La cota pide $l_0=1$. La prueba de $n-k\le mt$ usa que los pares pedidos sean dobles de impares pedidos. Con $l_0=0$ entra además la raíz ${\alpha }^0=1$, cuya clase es $C_0=\{0\}$ y cuyo polinomio mínimo es $1+X$. En largo 15 con $t=2$ se piden ${\alpha }^0$ a ${\alpha }^3$, entran $C_0$, $C_1$ y $C_3$, y

de grado 9, uno más que $mt=8$. Es el (15,6): las palabras de peso par del (15,7). La tira va de ${\alpha }^0$ a ${\alpha }^4$, mide 5 y garantiza $d_{\text{min}}\ge 6$, y enumeradas sus 64 palabras la distancia es exactamente 6. Un bit más de redundancia compró un punto de distancia: el código detecta un error más, pero sigue corrigiendo dos.

La dimensión no se elige. Entre dos filas del catálogo no hay nada. En largo 31 no existe un BCH primitivo de sentido estricto con $k$ entre 16 y 11: si el (31,16) no alcanza, el siguiente cuesta cinco bits más de redundancia.

La tira es una cota inferior. Hay códigos BCH cuya distancia excede a la tira más larga de sus raíces, y verlo pide cotas más finas. Y al alargar el bloque con la tasa fija, la fracción de errores corregibles $t/n$ tiende a cero. Las dos cosas, con su prueba, están en la cota BCH.

09 · La cuenta en Python

El diseño entero, sin librerías: la tabla de potencias de $\alpha$, la clase de un exponente, el polinomio mínimo como producto de $(X+{\beta }^j)$ sobre la clase —con la comprobación de que sale binario—, el MCM y la tira más larga. Los polinomios binarios van como enteros, con el bit $i$ como coeficiente de $X^i$, y el primitivo con su término $X^m$ incluido. Lo de los comentarios es la salida de correrlo.

def tablas(m, p):
    """exp y log de GF(2^m); p es el primitivo con el bit m incluido."""
    N, exp, log, x = 2 ** m - 1, [], {}, 1
    for i in range(N):
        exp.append(x); log[x] = i
        x <<= 1
        if x >> m: x ^= p
    return exp, log

def clase(i, n):
    c, j = [], i % n
    while j not in c:
        c.append(j); j = 2 * j % n
    return c

def minimo(m, p, paso, c):
    """phi(X) = prod (X + beta^j) sobre la clase; sale con coeficientes 0 y 1."""
    exp, log = tablas(m, p)
    N = 2 ** m - 1
    mul = lambda a, b: 0 if a == 0 or b == 0 else exp[(log[a] + log[b]) % N]
    phi = [1]
    for j in c:
        r = exp[j * paso % N]
        phi = [(phi[i - 1] if i else 0) ^ (mul(phi[i], r) if i < len(phi) else 0)
               for i in range(len(phi) + 1)]
    assert set(phi) <= {0, 1}
    return sum(b << i for i, b in enumerate(phi))

def mul2(a, b):
    r = 0
    while b:
        if b & 1: r ^= a
        a, b = a << 1, b >> 1
    return r

def bch(m, p, n, t, l0=1):
    paso, raices, g = (2 ** m - 1) // n, set(), 1
    for j in range(l0, l0 + 2 * t):
        if j % n not in raices:
            c = clase(j, n)
            raices |= set(c)
            g = mul2(g, minimo(m, p, paso, c))
    return g, raices

def tira(raices, n):
    """La tira más larga de exponentes consecutivos (módulo n)."""
    if len(raices) == n: return n
    return max(next(l for l in range(n) if (r + l) % n not in raices)
               for r in raices if (r - 1) % n not in raices)

def texto(g):
    return ' + '.join('1' if i == 0 else 'X' if i == 1 else f'X^{i}'
                      for i in range(g.bit_length()) if g >> i & 1)

casos = [(4, 0b10011, 15, 2, 1), (4, 0b10011, 15, 3, 1),
         (6, 0b1000011, 21, 2, 1), (5, 0b100101, 31, 1, 2),
         (5, 0b100101, 31, 4, 1)]
for m, p, n, t, l0 in casos:
    g, R = bch(m, p, n, t, l0)
    L = tira(R, n)
    print(f'({n},{n - g.bit_length() + 1}) t={t} l0={l0} tira {L}: d >= {L + 1}')
    print('   g =', texto(g))
# (15,7) t=2 l0=1 tira 4: d >= 5
#    g = 1 + X^4 + X^6 + X^7 + X^8
# (15,5) t=3 l0=1 tira 6: d >= 7
#    g = 1 + X + X^2 + X^4 + X^5 + X^8 + X^10
# (21,12) t=2 l0=1 tira 4: d >= 5
#    g = 1 + X + X^4 + X^5 + X^7 + X^8 + X^9
# (31,21) t=1 l0=2 tira 4: d >= 5
#    g = 1 + X^3 + X^5 + X^6 + X^8 + X^9 + X^10
# (31,11) t=4 l0=1 tira 10: d >= 11
#    g = 1 + X^2 + X^4 + X^6 + X^7 + X^9 + X^10 + X^13 + X^17 + X^18 + X^20

Los cuatro primeros casos son los ejemplos de la sección 04 y el de $l_0=2$. El último es el (31,11) pedido con $t=4$: la tira de 10 dice que corrige cinco.

Para tener a mano

1. BCH de largo $n$ y distancia diseñada $d_0=2t+1$: el cíclico de $g(X)$ = MCM de los polinomios mínimos de ${\beta }^{l_0},\dots ,{\beta }^{l_0+2t-1}$, con $\beta$ de orden $n$.
2. MCM y no producto: cada clase conjugada entra una vez. Las raíces de $g(X)$ son las pedidas más todas sus conjugadas.
3. Coeficientes y bits en $\text{GF}(2)$; raíces y síndromes en $\text{GF}(2^m)$. Codificar es binario; decodificar no.
4. Diseño: el menor $m$ con $n$ que divida a $2^m-1$, $\beta ={\alpha }^{(2^m-1)/n}$, las $2t$ potencias, sus clases, el producto. $k$ sale, no se elige.
5. (15,7) = $1+X^4+X^6+X^7+X^8$, $d_{\text{min}}=5$. (15,5) = $1+X+X^2+X^4+X^5+X^8+X^{10}$, $d_{\text{min}}=7$. (21,12) con $\beta ={\alpha }^3$, $d_{\text{min}}=5$. (255,239) de grado 16 y once coeficientes.
6. Con $t=1$, primitivo y estricto, el BCH es el Hamming.
7. La distancia la garantiza la tira más larga de exponentes consecutivos entre todas las raíces, no la pedida: $l_0=2$ y $t=1$ en largo 31 dan el (31,21), que corrige dos.
8. El catálogo lista cada código con el mayor $t$ que lo produce: (31,11) con $t=5$, aunque sale desde 4; (63,18) con 10, aunque sale desde 8.
9. $n-k\le mt$ con $l_0=1$, igual mientras las clases de los impares sean de tamaño $m$ y distintas. Con $l_0=0$ puede pasarse: el (15,6) pide 9 contra 8.