Pasado t, la cuenta la hacen las palabras livianas

Un BCH que corrige $t$ errores, con $t + 1$ , a veces avisa que no puede y a veces entrega otra palabra sin avisar. En el $(15, 5)$ , de los 1365 patrones de cuatro errores, 840 terminan en falla y 525 en una palabra equivocada: el 38,5 %. Ese porcentaje no es de los BCH. Es de cada código, y lo fija una sola cifra: cuántas palabras tiene de peso $2 t + 1$ . Las de peso $2 t + 2$ en adelante no aportan ni un patrón. El $(31, 16)$ corrige lo mismo que el $(15, 5)$ y se equivoca en el 17,2 %.

01 · Fallar o equivocarse

Un código BCH $(n, k)$ se construye para corregir $t$ errores, y en los cuatro códigos de esta nota esa $t$ es exactamente su capacidad de corrección: la distancia mínima vale $d_{min} = 2 t + 1$ , ni más ni menos. El decodificador calcula los síndromes, saca el polinomio localizador $σ (X)$ con Berlekamp-Massey y busca sus raíces con la búsqueda de Chien. Antes de corregir hace dos comprobaciones: que el grado de $σ (X)$ no pase de $t$ , y que Chien encuentre tantas raíces distintas como ese grado.

De ahí salen tres desenlaces. Si el patrón de error $e$ tiene hasta $t$ unos, el decodificador lo corrige. Si tiene más, puede pasar una de dos cosas. O alguna comprobación no se cumple y el decodificador declara falla: sabe que el bloque llegó dañado, aunque no lo pueda arreglar. O las dos se cumplen y entrega, con toda confianza, una palabra de código que no es la que se mandó: una decodificación errónea. Esta nota cuenta cuántas veces pasa lo segundo cuando hay $t + 1$ errores, uno solo de más.

Para contar hace falta saber qué hace el decodificador sin mirar sus cuentas por dentro. Se recorrieron los cuatro códigos con todos los patrones de $t + 1$ errores, y cada vez que no declaró falla, lo que entregó fue una palabra de código a distancia $t$ o menos de lo recibido. Es lo que se llama un decodificador de distancia acotada: corrige hacia la palabra que está a $t$ o menos, si la hay, y si no la hay, avisa. Es la misma regla que la decodificación incompleta de la Unidad 3, ahora hecha con álgebra en vez de tabla.

02 · Con un error de más, sólo cuenta el peso mínimo

El código es lineal, así que se puede suponer que se mandó la palabra nula: lo recibido es el propio $e$ , y cualquier palabra que el decodificador entregue en su lugar es una palabra no nula $c$ . El decodificador se equivoca exactamente cuando hay una $c$ con $d (e, c) \leq t$ . Cuatro pasos alcanzan para contar esos $e$ .

Paso 1: las de peso $2 t + 2$ o más no llegan. Entre dos vectores, la distancia es al menos la diferencia de sus pesos:

d (e, c) \geq w (c) - w (e) = w (c) - (t + 1)

Para que eso sea a lo sumo $t$ , $c$ tiene que pesar a lo sumo $2 t + 1$ . Una palabra de peso $2 t + 2$ queda a $t + 1$ o más de cualquier patrón de $t + 1$ errores, y el decodificador nunca la elige. Y como ninguna palabra no nula pesa menos que $d_{min} = 2 t + 1$ , las únicas candidatas son las de peso exactamente $2 t + 1$ .

Paso 2: el patrón tiene que caer adentro de la palabra. Si $c$ pesa $2 t + 1$ y comparte $j$ unos con $e$ , la distancia es $2 t + 1 + (t + 1) - 2 j$ . Para que valga $t$ o menos hace falta $j \geq t + 1$ : los $t + 1$ errores están todos en posiciones donde $c$ tiene un uno. Entonces $d (e, c) = t$ justo, y el decodificador da vuelta los $t$ bits sanos que le faltan a $e$ para ser $c$ .

Paso 3: cada patrón cae adentro de una sola. Si $e$ estuviera adentro de dos palabras $c_{1}$ y $c_{2}$ , las dos estarían a $t$ de $e$ y a lo sumo a $2 t$ entre sí, menos que $d_{min}$ . No puede ser.

Paso 4: se cuenta. Cada una de las $A_{2 t + 1}$ palabras de peso $2 t + 1$ contiene $(\binom{2 t + 1}{t + 1})$ patrones de $t + 1$ errores, y ninguno se repite entre dos palabras. Sobre los $(\binom{n}{t + 1})$ patrones posibles, la fracción que sale equivocada es

P = \frac{A_{2 t + 1} (\binom{2 t + 1}{t + 1})}{(\binom{n}{t + 1})}

Del código entra un solo número, $A_{2 t + 1}$ : el primer término no nulo de su distribución de pesos. Las $A_{2 t + 2}$ palabras siguientes, que pueden ser muchas más, quedan afuera por el paso 1.

Arranca en el $(15, 5)$ sin errores. Con cuatro, la raya roja marca la palabra que el decodificador entregó cuando se equivoca: siete posiciones que tapan las cuatro azules. Al contar, el recuento junta las palabras entregadas y las compara con lo que da el código dual por MacWilliams, que no pasa por el decodificador.

03 · Medido en los cuatro códigos

Se decodificaron todos los patrones de $t + 1$ errores de los cuatro códigos de la unidad. Las $A_{2 t + 1}$ y $A_{2 t + 2}$ salen de enumerar las $2^{k}$ palabras de cada código:

código	t	patrones	falla	equivocadas	A₂ₜ₊₁	A₂ₜ₊₁·C(2t+1, t+1)	fracción	A₂ₜ₊₂
(15,7)	2	455	275	180	18	18 · 10 = 180	39,6 %	30
(15,5)	3	1 365	840	525	15	15 · 35 = 525	38,5 %	15
(31,21)	2	4 495	2 635	1 860	186	186 · 10 = 1 860	41,4 %	806
(31,16)	3	31 465	26 040	5 425	155	155 · 35 = 5 425	17,2 %	465

La forma cerrada da los cuatro recuentos exactos. Y no por casualidad de suma: en cada código las palabras distintas que el decodificador entregó son exactamente las $A_{2 t + 1}$ de peso mínimo, todas de peso $2 t + 1$ , y cada una entregada $(\binom{2 t + 1}{t + 1})$ veces, ni una más ni una menos. Las de peso $2 t + 2$ no aparecen nunca, aunque en el $(31, 21)$ sean 806 contra 186 y en el $(31, 16)$ 465 contra 155.

04 · La misma t, dos cifras

El $(15, 5)$ y el $(31, 16)$ corrigen tres errores, tienen $d_{min} = 7$ y salen del mismo procedimiento de diseño. Con cuatro errores, el primero se equivoca en el 38,5 % de los patrones y el segundo en el 17,2 %. Lo que los separa es cuánto tapan sus palabras de peso 7. En el $(15, 5)$ , 15 palabras con 35 patrones cada una cubren 525 de 1365. En el $(31, 16)$ , 155 palabras cubren 5425, pero el largo 31 deja 31 465 patrones de cuatro errores, veintitrés veces más, y las palabras de peso 7 crecieron sólo diez veces.

Con $t = 2$ pasa lo contrario: el $(15, 7)$ da 39,6 % y el $(31, 21)$ da 41,4 %. Alargar el bloque no baja la fracción por sí solo. Cada código trae su cifra, y para saberla hay que contar sus palabras más livianas.

05 · Lo que sí fija la familia: 1/t! en los largos

Hay una regularidad, pero aparece en el largo, no en $t$ solo. En un BCH primitivo largo, las palabras de peso bajo se reparten casi como si el código fuera al azar: $A_{w} \approx (\binom{n}{w}) / 2^{n - k}$ , la aproximación binomial. Con $n - k = m t$ es $2^{n - k} = {(n + 1)}^{t}$ , y al reemplazar en la fracción, para $n$ grande,

P \approx \frac{(\binom{2 t + 1}{t + 1}) (\binom{n}{2 t + 1})}{(\binom{n}{t + 1}) {(n + 1)}^{t}} \to \frac{1}{t!}

La mitad con dos errores corregibles, un sexto con tres. Las $A_{2 t + 1}$ exactas de los BCH primitivos más largos salen de su código dual, que tiene pocas palabras, por la identidad de MacWilliams; las de largo 63, y el $(127, 113)$ , se cruzaron además decodificando todos sus patrones:

código	t	A₂ₜ₊₁	equivocadas	patrones	fracción	1/t!
(15,7)	2	18	180	455	39,6 %	50 %
(31,21)	2	186	1 860	4 495	41,4 %	50 %
(63,51)	2	1 890	18 900	39 711	47,6 %	50 %
(127,113)	2	16 002	160 020	333 375	48,0 %	50 %
(255,239)	2	134 946	1 349 460	2 731 135	49,4 %	50 %
(15,5)	3	15	525	1 365	38,5 %	16,7 %
(31,16)	3	155	5 425	31 465	17,2 %	16,7 %
(63,45)	3	3 411	119 385	595 665	20,0 %	16,7 %
(127,106)	3	48 387	1 693 545	10 334 625	16,4 %	16,7 %
(255,231)	3	856 035	29 961 225	172 061 505	17,4 %	16,7 %

Los de $t = 3$ oscilan alrededor de un sexto desde largo 31. El $(15, 5)$ es el que se sale: con largo 15 y $d_{min}$ 7, el código está lejos de parecerse al azar, y la cuenta de arriba supone $n - k = m t$ , que en él no vale: tiene 10 bits de paridad, no 12. Su 38,5 % es más del doble de lo que la familia da en el largo, y es el número de ese código, no una regla.

06 · El (7,4) y el (8,4), en la misma cuenta

La fórmula no pide nada de los BCH: vale para cualquier decodificador de distancia acotada. Con $t = 1$ da $\frac{1}{1!} = 1$ , y en un Hamming es exacta para cualquier largo: el $(7, 4)$ tiene 7 palabras de peso 3, con 3 pares de errores cada una, y $7 \cdot 3 = 21$ son todos los patrones dobles. Es lo que pasa en un código perfecto, visto desde las palabras livianas.

El $(8, 4)$ tiene $d_{min} = 4$ , así que $A_{3} = 0$ y la fórmula da cero: ningún doble sale equivocado, los 28 levantan la bandera. Son las dos filas que en un código perfecto, la bandera no se levanta sacó recorriendo patrones, ahora en una línea.

Y dice cómo llevar a cero la decodificación errónea con $t + 1$ errores: que no haya palabras de peso $2 t + 1$ , o sea, $d_{min} \geq 2 t + 2$ . Es lo que hace el código extendido, con un bit de paridad global. Se extendieron los cuatro BCH y se recorrieron sus patrones de $t + 1$ errores con un decodificador de distancia acotada: en el $(16, 7)$ , el $(16, 5)$ , el $(32, 21)$ y el $(32, 16)$ , cero equivocadas. Un bit más no corrige ningún error más; compra que el primer error de más avise siempre.