La distribución de pesos de los códigos BCH

Un código BCH garantiza su distancia diseñada y no dice nada más. Pero usado como detector, un código falla cuando el canal escribe justo otra palabra, y cuántas veces pasa eso depende de cuántas palabras hay de cada peso. La distribución de pesos de un BCH cualquiera no se conoce en forma cerrada. Hay dos caminos parciales: contarla desde el dual, cuando el dual es chico, y aproximarla con una binomial, cuando el código es largo. De ella sale la probabilidad de error no detectado, que tiene dos cotas.

01 · La definición

La distribución de pesos de un código $(n,k)$ es la lista $A_0,A_1,\dots ,A_n$, donde $A_i$ cuenta las palabras de peso $i$. Se la guarda en un polinomio, el enumerador de pesos:

$$A(z)=\sum _{i=0}^n{A}_i{z}^i,A_0=1,A(1)=2^k$$

En un código lineal, el menor $i>0$ con $A_i\ne 0$ es la distancia mínima. La cota BCH asegura que $A_1=\cdots =A_{2t}=0$, y de los demás coeficientes no dice nada.

Para qué sirven. Sobre el canal binario simétrico con probabilidad de transición $p$, se transmite $v$ y llega $r=v+e$. Si el patrón de error $e$ es una palabra no nula, $r$ es otra palabra, el síndrome da cero y el error pasa sin que nadie lo vea. Y sólo así: si $e$ no es palabra, el síndrome no es cero. Un patrón de peso $i$ tiene probabilidad $p^i{(1-p)}^{n-i}$, y hay $A_i$ palabras de ese peso:

$$P_u(E)=\sum _{i=1}^n{A}_i{p}^i{(1-p)}^{n-i}$$

Es la probabilidad de error no detectado. Con $p$ chico manda el primer término, $A_{d_{\text{min}}}{p}^{d_{\text{min}}}$, y con $p=1/2$ todos los patrones pesan lo mismo y queda $P_u(E)=(2^k-1)/2^n$: una palabra no nula cualquiera, sobre todos los vectores.

02 · El dual del (31,21), paso a paso

El (31,21) es el BCH de largo 31 que corrige dos errores. Sobre $GF(2^5)$, con $P(x)=1+x^2+x^5$, las cuatro raíces $\alpha ,{\alpha }^2,{\alpha }^3,{\alpha }^4$ caen en dos clases conjugadas, la de $\alpha$ y la de ${\alpha }^3$, y el generador es el producto de sus dos polinomios mínimos:

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

con ${\phi }_1=1+X^2+X^5$ y ${\phi }_3=1+X^2+X^3+X^4+X^5$. El código tiene $2^{21}=\mathrm{2\; 097\; 152}$ palabras. Su dual es un (31,10): tiene 1024. Un BCH de tasa alta tiene un dual chico, y ésa es la asimetría que se aprovecha.

Paso 1: el polinomio de paridad. Como $g(X)$ divide a $X^{31}+1$, el cociente $h(X)=(X^{31}+1)/g(X)$ es el polinomio de paridad, de grado $k=21$:

$$\begin{array}{rl}h(X)=& 1+X^3+X^5+X^8+X^{11}+X^{12}\\ & +X^{13}+X^{14}+X^{16}+X^{18}+X^{20}+X^{21}\end{array}$$

Paso 2: el dual lo genera el recíproco. El dual de un cíclico es cíclico, y su generador es $h^{\ast }(X)=X^{k}h(X^{-1})$, el mismo polinomio leído al revés (está en el polinomio generador):

$$\begin{array}{rl}{h}^{\ast }(X)=& 1+X+X^3+X^5+X^7+X^8+X^9\\ & +X^{10}+X^{13}+X^{16}+X^{18}+X^{21}\end{array}$$

Paso 3: contar. Las palabras del dual son los $u(X)h^{\ast }(X)$ con $u(X)$ de grado menor que 10. Recorridas las 1024, los pesos que aparecen son cuatro:

$$B(z)=1+310z^{12}+527z^{16}+186z^{20}$$

Paso 4: la forma cerrada. Para los BCH primitivos de sentido estricto con $t=2$ y $m$ impar, el dual tiene siempre esos tres pesos no nulos, alrededor de $2^{m-1}$, y se sabe cuántas palabras hay de cada uno. Con $m=5$:

El recuento palabra por palabra y la fórmula dan lo mismo, y los cuatro números suman $1024=2^{10}$. Para $m$ par y para $t=3$ también hay tablas cerradas; para un BCH cualquiera, no.

03 · Del dual al código: MacWilliams

La identidad de MacWilliams pasa del enumerador del dual al del código:

$$A(z)=2^{-(n-k)}{(1+z)}^{n}B\left(\frac{1-z}{1+z}\right)$$

con $k$ la dimensión del código, así que el factor de adelante es uno sobre la cantidad de palabras del dual: acá, $2^{-10}$. Se comprueba en $z=1$: $B(0)=B_0=1$ y queda $A(1)=2^{-10}·2^{31}=2^{21}$, las palabras del (31,21).

Coeficiente a coeficiente: cada palabra del dual de peso $i$ aporta ${(1-z)}^i{(1+z)}^{n-i}$, y el coeficiente de $z^j$ en ese producto es el polinomio de Krawtchouk

$$A_j=2^{-(n-k)}\sum _i{B}_i{K}_j(i)$$ $$K_j(i)=\sum _{l=0}^j{(-1)}^l\left(\genfrac{}{}{0ex}{}{i}{l}\right)\left(\genfrac{}{}{0ex}{}{n-i}{j-l}\right)$$

Con un dual de cuatro pesos, cada $A_j$ es una suma de cuatro términos dividida por 1024. Hechas las 32 sumas:

$$\begin{array}{rl}A(z)=& 1+186z^5+806z^6+2635z^7+7905z^8+\cdots \\ & +\mathrm{301\; 971}{z}^{15}+\mathrm{301\; 971}{z}^{16}+\cdots +186z^{26}+z^{31}\end{array}$$

La lista entera está en la tabla de la sección 04. Enumeradas una por una las 2 097 152 palabras del (31,21), la distribución sale idéntica, coeficiente por coeficiente.

Se lee así. El menor peso no nulo es 5: la distancia mínima real es la diseñada, $2t+1$. La lista es simétrica, $A_{31-i}=A_i$, porque la palabra de todos unos está en el código: ${\alpha }^0=1$ no es raíz de $g(X)$, así que $X+1$ no lo divide, y $(X^{31}+1)/(X+1)=1+X+\cdots +X^{30}$ es múltiplo suyo. Sumarle esa palabra a otra de peso $i$ da una de peso $31-i$. Por eso al hueco de los pesos 1 a 4 le corresponde otro, del 27 al 30.

Y el hueco sale de una cancelación. En $j=3$, por ejemplo, los cuatro términos son

$$A_3=\frac{4495-\mathrm{15\; 190}+7905+2790}{1024}=0$$

El primero, el de la palabra nula del dual, es $K_3(0)=\left(\genfrac{}{}{0ex}{}{31}{3}\right)$; los otros tres, los de las 1023 palabras restantes, lo anulan exacto. En el widget de abajo se ve, peso por peso, qué hace cada término.

04 · Contra la binomial

El segundo camino es una aproximación. Para un BCH primitivo de largo $n=2^m-1$ con $n-k=mt$ bits de paridad, y $m$ suficientemente grande,

$$A_i\simeq \{\begin{array}{ll}0& 0<i\le 2t\\ (1+{\lambda }_0{n}^{-1/10})\left(\genfrac{}{}{0ex}{}{n}{i}\right)2^{-(n-k)}& i>2t\end{array}$$

con ${\lambda }_0$ acotado por una constante, de modo que el factor de corrección tiende a 1 cuando el código se alarga. De los $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ vectores de peso $i$, al código le toca la fracción $2^{-(n-k)}$ que le corresponde por su tamaño: salvo en los pesos bajos, un BCH largo reparte sus palabras como si las hubieran elegido al azar. La estructura algebraica se ve en el hueco, y en nada más.

La binomial no sale de la nada: es el primer término de MacWilliams. La palabra nula del dual tiene $B_0=1$ y $K_j(0)=\left(\genfrac{}{}{0ex}{}{n}{j}\right)$, así que aporta exactamente $\left(\genfrac{}{}{0ex}{}{n}{j}\right)2^{-(n-k)}$. Lo demás es la corrección que traen las otras palabras del dual. La aproximación dice que en un BCH largo esa corrección es chica, salvo donde borra los pesos bajos. En el (31,21), con la mitad de la lista, porque la otra mitad es su espejo:

La binomial es $\left(\genfrac{}{}{0ex}{}{31}{i}\right)2^{-10}$, y la razón, $A_i$ sobre ella. Del peso 5 al 26 la razón queda entre 0,961 y 1,121, y la peor está en el borde del hueco. Adentro del hueco, la binomial pone 35,6 palabras entre los pesos 1 y 4 —30,7 de peso 4— y el código no tiene ninguna. En un código más corto la aproximación ajusta peor: en el (15,7), con

Ahí la razón va de 0,597, en los pesos 7 y 8, a 1,534, en el 5, el 6, el 9 y el 10.

Arranca en el peso 15, el del medio, donde la barra y la binomial casi se tocan y el primer término se lleva el 97 % de la suma. Bajá hacia el 5 y mirá cómo crecen los otros tres. Después pasá al 4: el primer término sigue ahí, y los otros tres lo anulan.

05 · La probabilidad de error no detectado

Con la aproximación de la sección 04 en la fórmula de $P_u(E)$, los pesos de 1 a $2t$ no aportan y la redundancia sale como factor:

$$P_u(E)\simeq (1+{\lambda }_0{n}^{-1/10})2^{-(n-k)}\sum _{i=2t+1}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)p^i{(1-p)}^{n-i}$$

La suma es la probabilidad de que ocurran más de $2t$ errores, y no pasa de uno. De ahí la cota general:

$$P_u(E)\lesssim 2^{-(n-k)}$$

La probabilidad de dejar pasar un error queda acotada por la redundancia, sea cual sea el canal. Es la probabilidad de que un vector elegido al azar caiga en el código: $2^k/2^n$. Para el (255,239) vale $2^{-16}\approx \mathrm{1,53}·{10}^{-5}$.

Con $p$ chico es muy pesimista. En el (31,21), con la distribución exacta de la sección 03 y $p={10}^{-2}$,

$$P_u(E)=\mathrm{1,497}·{10}^{-8}\text{contra}{2}^{-10}=\mathrm{9,77}·{10}^{-4}$$

65 230 veces menos: 4,8 órdenes de magnitud. Recién en $p=1/2$, con un canal que no transporta nada, las dos coinciden: $(2^{21}-1)/2^{31}=2^{-10}(1-2^{-21})$.

06 · La cota exponencial

La suma de la sección 05 es la cola de una binomial, y la cola se acota con la desigualdad de Chernoff. Con $\epsilon =(2t+1)/n$ y $p<\epsilon$,

$$\sum _{i=n\epsilon }^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)p^i{(1-p)}^{n-i}\le 2^{-nE(\epsilon ,p)}$$ $$E(\epsilon ,p)=H(p)+(\epsilon -p)H^{\prime }(p)-H(\epsilon )$$

con $H(x)=-x{\log }_{2}x-(1-x){\log }_2(1-x)$ la entropía binaria y $H^{\prime }(x)={\log }_2(1-x)/x$. Desarmado, el exponente es

$$E(\epsilon ,p)=\epsilon {\log }_2\frac{\epsilon }{p}+(1-\epsilon ){\log }_2\frac{1-\epsilon }{1-p}$$

que es positivo siempre que $\epsilon \ne p$, y crece a medida que $p$ se aleja de $\epsilon$ hacia abajo. Juntando con la sección 05:

$$P_u(E)\lesssim 2^{-nE(\epsilon ,p)}{2}^{-(n-k)}$$

que decae exponencialmente en el largo además de en la redundancia. En el (31,21), $\epsilon =5/31\approx \mathrm{0,161}$. Las dos cotas contra la cuenta exacta:

La general es plana y la exponencial sigue la pendiente: con $p$ chico, $2^{-nE}$ va como $p^{n\epsilon }=p^5$, igual que el término $186p^5$ que manda en la exacta, y queda a un factor 4,5 arriba. Al acercarse a $\epsilon$ las dos cotas se juntan. Las dos llevan $\lesssim$ porque se tiró el factor $(1+{\lambda }_0{n}^{-1/10})$; en el (31,21) la exponencial queda arriba de la exacta en todo ${10}^{-5}<p<\epsilon$, por un factor de al menos 1,62.

Arranca en $p=1/2$, donde la exacta y la cota general son la misma cosa. Bajá $p$ y mirá cuánto se abre la distancia, y dónde aparece la exponencial. Apostá antes de ver el (15,7), y después recorré su curva de punta a punta.

07 · Dos bits de paridad: cuatro veces arriba, diez abajo

El (15,7) es el BCH de largo 15 que corrige dos errores: ocho bits de paridad, dos menos que el (31,21), y la misma distancia mínima, 5. En la zona plana su cota general es $2^{-8}$ contra $2^{-10}$, y la curva exacta lo sigue: en $p=1/2$ el (15,7) deja pasar 3,97 veces más que el (31,21), que es $2^2$ salvo por el $-1$ de $2^k-1$.

Pero el orden se invierte. Las dos curvas exactas se cruzan en $p\approx \mathrm{0,186}$, y debajo de ahí el (31,21), con más redundancia, deja pasar más: en $p={10}^{-3}$, $\mathrm{1,820}·{10}^{-13}$ contra $\mathrm{1,785}·{10}^{-14}$, 10,2 veces más por palabra. Con $p$ chico manda $A_5{p}^5$, y el (31,21) tiene 186 palabras de peso 5 donde el (15,7) tiene 18: una palabra más larga ofrece más maneras de que cinco errores formen otra palabra. La redundancia fija el techo; el piso lo fijan la distancia mínima y cuántas palabras hay a esa distancia. La cota general no ve ninguna de las dos.

08 · Lo que la cota general no promete

El $\lesssim$ no es un adorno. $P_u(E)\le 2^{-(n-k)}$ sale de suponer la binomial, y un código que se aparta mucho de ella puede pasarla. El (15,5) de $g(X)=1+X^5+X^{10}$, un cíclico que no es BCH, repite tres veces un bloque de cinco bits: $A(z)=1+5z^3+10z^6+10z^9+5z^{12}+z^{15}$. Barriendo $p$ de ${10}^{-5}$ en ${10}^{-5}$ hasta $1/2$, su $P_u(E)$ pasa a $2^{-10}$ por un factor de hasta 2,91, en $p\approx \mathrm{0,207}$.

Los dos BCH de la sección 07 no la pasan en ningún punto de ese barrido: el máximo de $P_u(E)·2^{n-k}$ está en $p=1/2$ y vale $1-2^{-k}$. Para saberlo de un código hay que tener su distribución, y ése es todo el punto: la cota BCH no la da, el dual la da sólo cuando es chico, y la binomial la adivina sólo cuando el código es largo. Lo que pasa con un error más que $t$, cuando el código corrige en vez de detectar, también lo deciden las palabras de peso mínimo: está en pasado t, la cuenta la hacen las palabras livianas.

09 · La cuenta en Python

El camino entero para el (31,21), con enteros como polinomios binarios: el bit $i$ es el coeficiente de $X^i$. Divide para sacar $h(X)$, lo invierte, recorre el dual, aplica MacWilliams con los polinomios de Krawtchouk y evalúa $P_u(E)$. Lo de los comentarios es la salida de correrlo.

from math import comb

def mul(a, b):
    """Producto de polinomios binarios guardados como enteros (bit i = X^i)."""
    r = 0
    while b:
        if b & 1:
            r ^= a
        a, b = a << 1, b >> 1
    return r

def div(a, b):
    q = 0
    while a.bit_length() >= b.bit_length():
        s = a.bit_length() - b.bit_length()
        q, a = q | 1 << s, a ^ b << s
    return q, a

n, k = 31, 21
g = 0b11101101001                         # 1 + X³ + X⁵ + X⁶ + X⁸ + X⁹ + X¹⁰
h, resto = div(1 << n | 1, g)             # h(X) = (X³¹ + 1) / g(X)
hr = int(f'{h:0{k + 1}b}'[::-1], 2)       # h*(X) = X²¹ h(1/X)

B = [0] * (n + 1)                         # el dual: los 1024 múltiplos de h*(X)
for u in range(1 << (n - k)):
    B[bin(mul(u, hr)).count('1')] += 1
print(resto, {i: b for i, b in enumerate(B) if b})
# 0 {0: 1, 12: 310, 16: 527, 20: 186}

def K(j, i):                              # Krawtchouk: el coeficiente de z^j
    return sum((-1) ** l * comb(i, l) * comb(n - i, j - l) for l in range(j + 1))

S = [sum(B[i] * K(j, i) for i in range(n + 1)) for j in range(n + 1)]
A = [s // 2 ** (n - k) for s in S]
print(A[:9], sum(A) == 2 ** k, all(s % 2 ** (n - k) == 0 for s in S))
# [1, 0, 0, 0, 0, 186, 806, 2635, 7905] True True

Pu = lambda p: sum(A[i] * p ** i * (1 - p) ** (n - i) for i in range(1, n + 1))
print(f'{Pu(1e-2):.4e} {2.0 ** -(n - k):.4e} {Pu(0.5) * 2 ** (n - k):.7f}')
# 1.4971e-08 9.7656e-04 0.9999995

El 0 del primer renglón es el resto de la división: $g(X)$ divide a $X^{31}+1$. El segundo True dice que las 32 sumas son múltiplos exactos de 1024, así que la división entera no redondea nada. El 0.9999995 del final es $1-2^{-21}$.

Para tener a mano

1. $P_u(E)={\sum }_{i\ge 1}{A}_i{p}^i{(1-p)}^{n-i}$: el error pasa si y sólo si es una palabra no nula. La distribución de un BCH cualquiera no se conoce en forma cerrada.
2. Dual chico, MacWilliams: $A(z)=2^{-(n-k)}{(1+z)}^{n}B((1-z)/(1+z))$, con $2^{n-k}$ las palabras del dual. El dual de un cíclico lo genera $X^{k}h(X^{-1})$.
3. (31,21): $B(z)=1+310z^{12}+527z^{16}+186z^{20}$, y $A(z)=1+186z^5+806z^6+\cdots +z^{31}$, simétrica porque la palabra de todos unos es del código.
4. La binomial $\left(\genfrac{}{}{0ex}{}{n}{i}\right)2^{-(n-k)}$ es el término de la palabra nula del dual. En el (31,21) ajusta entre 0,961 y 1,121 del peso 5 al 26; en el (15,7), entre 0,597 y 1,534.
5. Cota general: $P_u\lesssim 2^{-(n-k)}$, alcanzada en $p=1/2$. Exponencial, para $p<\epsilon =(2t+1)/n$: $P_u\lesssim 2^{-nE(\epsilon ,p)}{2}^{-(n-k)}$.
6. (31,21) en $p={10}^{-2}$: $\mathrm{1,497}·{10}^{-8}$, 4,8 órdenes debajo de $2^{-10}$; la exponencial, a un factor 4,46.
7. (15,7) contra (31,21): dos bits de paridad menos valen un factor $2^2$ en la zona plana (3,97 en $p=1/2$), pero debajo de $p\approx \mathrm{0,186}$ el (31,21) deja pasar más: 10,2 veces en ${10}^{-3}$, por 186 palabras de peso 5 contra 18.
8. La cota general no es un teorema para todo código: el (15,5) de $1+X^5+X^{10}$ la pasa por 2,91.