La cota BCH

Un código BCH se diseña pidiendo raíces: $2 t$ potencias consecutivas de un elemento $β$ de orden $n$ . Nadie mira las palabras, y sin embargo la distancia mínima queda garantizada antes de escribir la primera. La garantía es la cota BCH, y su prueba entera cabe en un determinante.

01 · La H sobre el cuerpo de extensión

Sea $v (X)$ una palabra del código. Es múltiplo del generador, y el generador se anula en las $2 t$ raíces pedidas, así que $v (X)$ también:

v (β^{l_{0} + j}) = \sum_{i = 0}^{n - 1} v_{i} β^{(l_{0} + j) i} = 0, j = 0, 1, \dots, 2 t - 1

Son $2 t$ ecuaciones lineales en los bits $v_{i}$ , con coeficientes en $GF (2^{m})$ . Escritas como $v H^{T} = 0$ :

H = (\begin{matrix} 1 & β^{l_{0}} & β^{2 l_{0}} & \dots & β^{(n - 1) l_{0}} \\ 1 & β^{l_{0} + 1} & β^{2 (l_{0} + 1)} & \dots & β^{(n - 1) (l_{0} + 1)} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ 1 & β^{l_{0} + 2 t - 1} & β^{2 (l_{0} + 2 t - 1)} & \dots & β^{(n - 1) (l_{0} + 2 t - 1)} \end{matrix})

La fila $j$ son las potencias de $β^{l_{0} + j}$ , y la columna $i$ son las potencias de $β^{i}$ : la posición $i$ del bloque. Hace el trabajo de una matriz de paridad —las palabras son exactamente su núcleo— pero no es una en el sentido de la Unidad 3: sus entradas no son bits y sus filas pueden ser dependientes. Si una raíz pedida es conjugada de otra, su fila sobra: la fila de $β^{2 j}$ es la de $β^{j}$ elevada al cuadrado, y una palabra binaria que anula una anula la otra.

Escribiendo cada entrada como su columna de $m$ bits sale una matriz binaria de $2 t m$ filas, y su rango es $n - k$ . Medido sobre $GF (2^{4})$ : el (15,7) da 16 filas binarias de rango 8, y el (15,5), 24 de rango 10. Quedándose sólo con las filas de exponente impar, como en el ejemplo 6.2 de Lin y Costello, son 8 de rango 8 y 12 de rango 10: en el (15,5) la fila de $α^{5}$ aporta 2 bits y no 4, porque su polinomio mínimo tiene grado 2.

02 · El teorema

Al número $d_{0} = 2 t + 1$ se lo llama distancia diseñada. La cota BCH, el teorema 1 de la unidad, dice que es un piso:

d_{min} \geq d_{0} = 2 t + 1

El enunciado no depende de $l_{0}$ ni de que $β$ sea primitivo, y vale más allá de la familia: todo código cíclico cuyo generador tenga entre sus raíces $d - 1$ potencias consecutivas de un elemento de orden $n$ tiene $d_{min} \geq d$ . Por eso conviene mirar todas las raíces del generador y no sólo las pedidas: si la conjugación agregó otras, la tira consecutiva más larga puede ser más larga que $2 t$ .

03 · La prueba, paso a paso

Paso 1: alcanza con el peso. El código es lineal, así que su distancia mínima es el menor peso de una palabra no nula. Hay que probar que no existe ninguna palabra no nula de peso $w \leq 2 t$ . Se supone que existe y se llega a un absurdo.

Paso 2: quedarse con sus columnas. Sea $v$ esa palabra, con sus componentes no nulas en las posiciones $i_{1}, \dots, i_{w}$ . En cada ecuación de la sección 01 sólo sobreviven esos $w$ términos:

\sum_{l = 1}^{w} v_{i_{l}} β^{(l_{0} + j) i_{l}} = 0, j = 0, \dots, 2 t - 1

Paso 3: un sistema cuadrado. Como $w \leq 2 t$ , se pueden tomar sólo las primeras $w$ ecuaciones. Queda un sistema homogéneo de $w \times w$ , con la matriz

H^{'} = (\begin{matrix} β^{i_{1} l_{0}} & \dots & β^{i_{w} l_{0}} \\ β^{i_{1} (l_{0} + 1)} & \dots & β^{i_{w} (l_{0} + 1)} \\ ⋮ & ⋮ \\ β^{i_{1} (l_{0} + w - 1)} & \dots & β^{i_{w} (l_{0} + w - 1)} \end{matrix})

El sistema es $H^{'} (v_{i_{1}}, \dots, v_{i_{w}})^{T} = 0$ , y el vector de incógnitas no es nulo: sus componentes son, por definición, las no nulas de $v$ . Un sistema homogéneo con solución no trivial tiene determinante cero, así que $\det H^{'} = 0$ .

Paso 4: sacar un factor por columna. La columna $l$ de $H^{'}$ es $β^{i_{l} l_{0}} \cdot (1, β^{i_{l}}, β^{2 i_{l}}, \dots, β^{(w - 1) i_{l}})$ : de una fila a la siguiente el exponente crece en uno, y eso multiplica por $β^{i_{l}}$ . El determinante es lineal en cada columna:

\det H^{'} = (\prod_{l = 1}^{w} β^{i_{l} l_{0}}) \cdot \det (\begin{matrix} 1 & \dots & 1 \\ β^{i_{1}} & \dots & β^{i_{w}} \\ ⋮ & ⋮ \\ β^{i_{1} (w - 1)} & \dots & β^{i_{w} (w - 1)} \end{matrix})

Paso 5: es una Vandermonde. La matriz que quedó tiene en cada columna las potencias $0, 1, \dots, w - 1$ de un solo elemento, el nodo $β^{i_{l}}$ . Es una matriz de Vandermonde, y su determinante es el producto de las diferencias de los nodos. En $GF (2^{m})$ restar es sumar:

\det V = \prod_{1 \leq r < s \leq w} (β^{i_{s}} + β^{i_{r}})

Paso 6: los nodos son distintos. Las posiciones cumplen $0 \leq i_{r} < i_{s} \leq n - 1$ , y $β$ tiene orden exactamente $n$ : sus $n$ primeras potencias son distintas dos a dos. Ningún factor $β^{i_{s}} + β^{i_{r}}$ es cero, y en un cuerpo un producto de no nulos no es nulo. Los factores de columna tampoco: son potencias de $β$ .

Paso 7: el absurdo. Por los pasos 4 a 6, $\det H^{'} \neq 0$ ; por el paso 3, $\det H^{'} = 0$ . No hay palabra no nula de peso $\leq 2 t$ , y $d_{min} \geq 2 t + 1$ . Dicho en columnas: cualquier conjunto de $2 t$ o menos columnas de $H$ es linealmente independiente.

04 · Lo que la prueba usa

La fuerza del argumento está en un solo lugar: la consecutividad. Que los exponentes de las filas sean $l_{0}, l_{0} + 1, \dots$ es lo que deja, en el paso 4, el mismo multiplicador de fila a fila dentro de cada columna, y eso es lo que arma la Vandermonde. Con filas salteadas la cuenta no sale, y el determinante sí puede anularse. En el (15,5), con las filas de $α^{1}$ y $α^{4}$ y las columnas 0 y 5:

\det (\begin{matrix} 1 & α^{5} \\ 1 & α^{20} \end{matrix}) = α^{20} + α^{5} = α^{5} + α^{5} = 0

porque $α^{15} = 1$ . Recorridas todas las elecciones de columnas del (15,5), con las primeras $w$ filas y $w$ de 1 a 6, son 9948 submatrices y ninguna da cero. Con las filas $α^{1}$ y $α^{4}$ , 15 de los 105 pares de columnas dan cero. Con $α^{1}$ y $α^{3}$ , que también están salteadas, ninguno: son potencias consecutivas de $β^{2}$ , que tiene orden 15 igual que $β$ , y la prueba corre con $β^{2}$ en su lugar.

Y el límite del argumento está a la vista: de las $2 t$ ecuaciones usa sólo $w$ , y de las raíces del generador usa sólo una tira. Todo lo demás que dice $H$ se tira, y por eso la cota puede quedar floja.

Arranca sin columnas. Elegí dos o tres y mirá el determinante: después probá todas las del mismo tamaño. Prendé el interruptor, quedate con las filas de $α^{1}$ y $α^{4}$ , y buscá dos columnas que lo anulen; después cambiá a $α^{1}$ y $α^{3}$ . Al final pedí una palabra de peso $2 t + 1$ : sus columnas suman cero, pero ninguna submatriz cuadrada de $H$ lo puede mostrar, porque no hay $2 t + 1$ filas.

05 · Igualdad y desigualdad

La cota es una desigualdad, y hay tres situaciones. Las tres se midieron recorriendo las $2^{k}$ palabras de cada código.

Igualdad. El (15,7) tiene $d_{min} = 5$ y el (15,5), $d_{min} = 7$ : exactamente $2 t + 1$ . En los quince códigos BCH primitivos de sentido estricto de largo 15, 31 y 63 con $k \leq 24$ , la distancia mínima es justo la tira más larga de raíces consecutivas más uno.

Desigualdad estricta por conjugación. La distancia supera la $2 t + 1$ pedida, pero la cota la ve si se le da la tira entera. Sobre $GF (2^{5})$ , pedir $t = 1$ con $l_{0} = 2$ son las raíces $α^{2}$ y $α^{3}$ , pero sus clases traen también $α$ y $α^{4}$ : el (31,21) tiene una tira de cuatro y $d_{min} = 5$ , no 3. Pidiendo $t = 4$ sale el (31,11), con una tira de diez y $d_{min} = 11$ , no 9. Se detecta mirando las raíces del generador, contando la tira módulo $n$ .

Desigualdad estricta genuina. La distancia supera también a la tira más larga, y la cota no la ve de ninguna manera. Sobre $GF (2^{11})$ con $1 + X^{2} + X^{11}$ , $β = α^{89}$ tiene orden 23, porque $2047 = 23 \cdot 89$ . Pidiendo $t = 2$ , las cuatro raíces caen en una sola clase de once exponentes:

C_{1} = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}

El generador es $g (X) = 1 + X + X^{5} + X^{6} + X^{7} + X^{9} + X^{11}$ y el código es un (23,12). La tira más larga es 1, 2, 3, 4: la cota garantiza 5. Recorridas las 4096 palabras, $d_{min} = 7$ . Es el código de Golay: su generador es el recíproco de $1 + X^{2} + X^{4} + X^{5} + X^{6} + X^{10} + X^{11}$ , el mismo código leído al revés. Ver estos casos pide cotas más finas, que combinan varias tiras de raíces en lugar de una sola: las de Hartmann y Tzeng y la de Roos son las más conocidas.

En los tres casos la garantía de diseño sigue en pie: el decodificador que se construye sobre las $2 t$ raíces corrige $t$ errores, sea cual fuere la distancia verdadera. Lo que corrige de más una distancia mayor, ese decodificador no lo aprovecha.

06 · Al alargar el bloque

El teorema 3 de la unidad pone el límite de la familia: no existe una sucesión de códigos BCH primitivos con la tasa $k / n$ y la distancia relativa $d_{min} / n$ las dos acotadas lejos de cero cuando $n \to \infty$ . Al alargar el bloque con la tasa fija, la fracción de errores corregibles, $t / n$ , se va a cero.

La idea detrás es el costo de cada error. Mientras las clases de los exponentes impares hasta $2 t - 1$ son completas y distintas, cada error corregible cuesta exactamente $m$ bits de paridad: es el teorema 2, $n - k \leq m t$ , con igualdad. Con la tasa fija hay $(1 - R) n$ bits para gastar, y si cada error costara $m$ alcanzarían para

\frac{t}{n} \approx \frac{1 - R}{m} = \frac{1 - R}{\log_{2} (n + 1)}

Al crecer $t$ las clases empiezan a coincidir y algunos errores salen más baratos, pero no alcanza: el $m$ del denominador crece con el bloque. Medido sobre los BCH primitivos de sentido estricto, tomando para cada $m$ el de mayor $t$ con tasa al menos $1 / 2$ . La dimensión sale de contar las clases ciclotómicas de los exponentes 1 a $2 t$ , que no dependen del polinomio primitivo, y hasta $m = 8$ coincide con la del generador construido. $d_{0}$ es la tira más larga más uno, y en todas las filas resultó igual a $2 t + 1$ :

m	código	t	d₀	t/n	d₀/n	t·m/n
5	(31,16)	3	7	0,097	0,226	0,48
6	(63,36)	5	11	0,079	0,175	0,48
7	(127,64)	10	21	0,079	0,165	0,55
8	(255,131)	18	37	0,071	0,145	0,56
10	(1023,513)	57	115	0,056	0,112	0,56
11	(2047,1024)	106	213	0,052	0,104	0,57
12	(4095,2057)	198	397	0,048	0,097	0,58
14	(16383,8200)	691	1383	0,042	0,084	0,59
16	(65535,32771)	2477	4955	0,038	0,076	0,61

La última columna es la paridad que haría falta si cada error costara $m$ bits, como fracción de $n$ . Con tasa $1 / 2$ la paridad real no pasa de 0,5, y la columna apenas la supera: de 0,48 a 0,61 mientras $m$ va de 5 a 16. Los errores salen algo más baratos que $m$ bits, pero no tanto como para compensar que $m$ crece. Por eso $t / n$ baja de 0,097 a 0,038. El largo 15 queda afuera: el (15,7) ya tiene tasa 0,467, y arriba de un medio sólo está el (15,11), de $t = 1$ .

La comparación que importa es con lo que existe. La cota de Varshamov-Gilbert asegura que, con tasa $1 / 2$ , hay códigos binarios cuya distancia relativa tiende a 0,110, el $δ$ que cumple $H (δ) = 1 / 2$ . La distancia que garantiza la cota BCH la cruza hacia abajo entre $m = 10$ y $m = 11$ , y sigue bajando. Lo medido es la distancia garantizada. El teorema dice más: tampoco la distancia verdadera acompaña, y esa prueba es bastante más larga. El lugar de la familia son los bloques cortos y medianos con tasa alta, donde la garantía de distancia y la decodificación algebraica son difíciles de igualar.

07 · La cuenta en Python

Las submatrices del (15,5), recorridas todas, con $GF (2^{4})$ armado desde la tabla de potencias de $α$ y el determinante por eliminación. Lo de los comentarios es la salida de correrlo.

from itertools import combinations

# GF(2^4) con p(X) = 1 + X + X^4: exp[i] es α^i como entero de 4 bits.
exp = [1]
for _ in range(14):
    x = exp[-1] << 1
    exp.append(x ^ 0b10011 if x & 0b10000 else x)
log = {v: i for i, v in enumerate(exp)}

def mul(a, b):
    return 0 if a == 0 or b == 0 else exp[(log[a] + log[b]) % 15]

def inv(a):
    return exp[-log[a] % 15]

def det(M):
    """Determinante sobre GF(2^4) por eliminación: la suma es XOR."""
    M, d = [f[:] for f in M], 1
    for c in range(len(M)):
        p = next((i for i in range(c, len(M)) if M[i][c]), None)
        if p is None:
            return 0
        M[c], M[p] = M[p], M[c]
        d = mul(d, M[c][c])
        for i in range(c + 1, len(M)):
            f = mul(M[i][c], inv(M[c][c]))
            M[i] = [a ^ mul(f, b) for a, b in zip(M[i], M[c])]
    return d

def ceros(filas, n=15):
    """Cuántas elecciones de w = len(filas) columnas dan determinante cero."""
    w, total, nulos = len(filas), 0, 0
    for cols in combinations(range(n), w):
        M = [[exp[(e * i) % 15] for i in cols] for e in filas]
        total += 1
        nulos += det(M) == 0
    return nulos, total

# El (15,5): t = 3, las filas de H son β^1 ... β^6, con β = α.
for w in range(1, 7):
    print(w, ceros(range(1, w + 1)))
print('{1,3}', ceros([1, 3]))
print('{1,4}', ceros([1, 4]))
# 1 (0, 15)
# 2 (0, 105)
# 3 (0, 455)
# 4 (0, 1365)
# 5 (0, 3003)
# 6 (0, 5005)
# {1,3} (0, 105)
# {1,4} (15, 105)

Las seis primeras líneas son la cota: $15 + 105 + 455 + 1365 + 3003 + 5005 = 9948$ submatrices, ninguna singular. El determinante se calcula entero, sin usar la fórmula de la Vandermonde: que nunca dé cero no está puesto por construcción. Las dos últimas son la sección 04: salteadas de a dos, las filas siguen siendo una tira de potencias de $β^{2}$ ; de a tres, ya no.

Para tener a mano

$H$ sobre $GF (2^{m})$ : la fila $j$ son las potencias de $β^{l_{0} + j}$ , $2 t$ filas y $n$ columnas. En binario, $2 t m$ filas de rango $n - k$ ; las filas de raíces conjugadas sobran.
Cota BCH: $d_{min} \geq 2 t + 1$ . Vale para todo cíclico con $d - 1$ potencias consecutivas de un elemento de orden $n$ entre sus raíces.
La prueba: una palabra de peso $w \leq 2 t$ haría singular la submatriz de sus $w$ columnas y las primeras $w$ filas; sacando $β^{i_{l} l_{0}}$ de cada columna queda una Vandermonde de nodos $β^{i_{l}}$ , distintos porque $β$ tiene orden $n$ .
Lo que importa es la consecutividad: con filas $α^{1}$ y $α^{4}$ , 15 de 105 pares de columnas del (15,5) dan cero; con las primeras $w$ , ninguna de 9948.
Igualdad: (15,7) y (15,5). Por conjugación: el (31,21) pedido con $t = 1$ y $l_{0} = 2$ tiene $d_{min} = 5$ ; se ve en la tira de raíces. Genuina: el (23,12), tira de cuatro, $d_{min} = 7$ : es el Golay.
Teorema 3: con la tasa fija, $t / n \to 0$ , del orden de $1 / m$ . A tasa $1 / 2$ : 0,097 en largo 31, 0,038 en largo 65 535.