Corregir uno en vez de detectar dos cuesta 3/p

El Hamming (7,4) manda 4 bits de mensaje en 7 bits de canal. De los 128 vectores de 7 bits, sólo 16 son palabras de código: los que el código declara válidos. El canal le suma a la palabra enviada $v$ un patrón de error $e$, con un 1 en cada bit que dio vuelta, y llega $r=v+e$. Su peso es la cantidad de unos: cuántos bits erró el canal.

El receptor no ve $e$. Ve el síndrome, $s=r{H}^T$: tres bits que dependen sólo del patrón de error, y que valen cero exactamente cuando $r$ es una palabra de código. Y el código tiene distancia mínima $d_{\text{min}}=3$: dos palabras distintas difieren, como mínimo, en tres bits.

Con ese síndrome hay dos cosas para hacer, y no se pueden hacer las dos a la vez. Se puede detectar: si $s\ne 0$, tirar el bloque y pedirlo de nuevo. O se puede corregir: adivinar el error y entregar algo siempre. Parece una opción de configuración. No lo es: sobre un canal que da vuelta cada bit con probabilidad $p$, corregir entrega en silencio unas $3/p$ veces más palabras equivocadas que detectar. Con $p={10}^{-2}$, 299 veces. Con $p={10}^{-3}$, 2999. Lo que se compra con eso es no pedir nunca una retransmisión.

01 · Dos usos del mismo síndrome

Detectando. Un bloque se acepta si $s=0$ y se pide otra vez si no. La garantía es de peor caso: ningún patrón de hasta $d_{\text{min}}-1=2$ errores da síndrome cero, porque sumarle a una palabra uno o dos bits no alcanza para caer en otra. El detector se equivoca en silencio sólo cuando $e$ es él mismo una palabra de código no nula: ahí $r$ es otra palabra válida, y no hay nada que lo delate. La más liviana pesa 3.

Corrigiendo. El decodificador busca, para cada síndrome, el líder: el patrón de error de menor peso que da ese síndrome. Lo suma a $r$ y entrega el resultado. En el (7,4) los ocho líderes son la palabra nula y los siete errores simples, así que corrige $t=\lfloor (d_{\text{min}}-1)/2\rfloor =1$ error: su capacidad de corrección. Con dos errores, el líder que encuentra es un error simple que no ocurrió, y entrega otra palabra. No tiene forma de saberlo: el (7,4) es un código perfecto, todo vector de 7 bits está a distancia 1 o menos de exactamente una palabra, y ningún síndrome le da motivo para dudar. Por eso tampoco levanta bandera la decodificación incompleta, la que corrige sólo hasta $t$ y avisa el resto: en este código no avisa nunca.

El apunte deja un tercer camino: corregir hasta $\lambda$ errores y detectar hasta $\ell$, con $\lambda <\ell$, siempre que $\lambda +\ell +1\le d_{\text{min}}$. Con $d_{\text{min}}=3$ la única solución es $\lambda =0$, $\ell =2$, que es detectar a secas. Corregir uno y además avisar los dobles pediría $\lambda =1$, $\ell =2$, y $1+2+1=4$ no entra en 3. En el (7,4) no hay término medio: se elige uno de los dos extremos.

02 · De dónde sale el 3/p

Las dos fallas silenciosas tienen forma cerrada, y las dos salen de contar patrones por peso. Un patrón de peso $i$ ocurre con probabilidad $p^i{(1-p)}^{n-i}$. Detectando, falla en silencio si el patrón es una de las palabras no nulas; con $A_i$ la cantidad de palabras de peso $i$, es la ecuación (19) del apunte:

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

con la distribución de pesos del (7,4), $A(z)=1+7z^3+7z^4+z^7$. Corrigiendo, acierta sólo si el patrón es un líder; con ${\alpha }_i$ la cantidad de líderes de peso $i$ (uno de peso 0, siete de peso 1), es la ecuación (20), y como en un código perfecto los líderes son todos los patrones de peso hasta $t$, falla con todo patrón de peso 2 o más:

$$P(E)=1-\sum _{i=0}^n{\alpha }_i{p}^i{(1-p)}^{n-i}=\sum _{i=2}^7\left(\genfrac{}{}{0ex}{}{7}{i}\right)p^i{(1-p)}^{7-i}$$

Con $p$ chico manda el primer término de cada suma. Detectando, el primer patrón que se escapa pesa $d_{\text{min}}$, y hay siete: $P_u\approx 7p^3$. Corrigiendo, el primero que se escapa pesa $t+1=2$, y son los 21 patrones dobles: $P(E)\approx 21p^2$. Una potencia de $p$ de diferencia, porque corregir falla con un error menos:

$$\frac{P(E)}{P_u(E)}\approx \frac{21p^2}{7p^3}=\frac{3}{p}$$

El 3 no es una casualidad de la aritmética. Cada par de posiciones está en exactamente una de las siete palabras de peso 3: contado sobre los 21 pares, todos caen en una y en una sola. Siete palabras de tres bits tienen $7·3=21$ pares, y no sobra ni se repite ninguno. Un error doble es una palabra de peso 3 a la que le falta un bit, y el decodificador se lo completa: cada uno de los tres pares de una palabra de peso 3 termina en esa palabra. A primer orden, los dos modos fallan hacia las mismas siete palabras, y corregir llega a cada una por tres caminos un error antes.

El término siguiente también es limpio. Desarrollando las dos sumas, $P(E)=21p^2-70p^3+\dots$ y $P_u(E)=7p^3-21p^4+\dots$, y el cociente queda $3/p-1$ más algo del orden de $p$. Por eso las razones exactas son 299,03 y 2999,003, y no 300 y 3000.

03 · Un millón de bloques

Las dos fórmulas exactas, evaluadas. La de corrección se suma por la cola, desde el peso 2: escrita como 1 menos los términos de peso 0 y 1, resta dos números casi iguales y pierde cifras cuando $p$ es chico.

from math import comb

A = [1, 0, 0, 7, 7, 0, 0, 1]   # palabras de cada peso: A(z) = 1 + 7z³ + 7z⁴ + z⁷

def silencio_detectando(p):
    """ec. (19): el patrón de error es una palabra no nula y el síndrome da cero."""
    return sum(A[i] * p**i * (1 - p)**(7 - i) for i in range(1, 8))

def silencio_corrigiendo(p):
    """ec. (20) en un código perfecto: falla todo patrón de peso 2 o más.
    Se suma la cola; 1 - (los de peso 0 y 1) cancela cifras con p chico."""
    return sum(comb(7, i) * p**i * (1 - p)**(7 - i) for i in range(2, 8))

def retransmite(p):
    """Detectando: síndrome no nulo, se pide el bloque otra vez."""
    return 1 - (1 - p)**7 - silencio_detectando(p)

for p in (1e-2, 1e-3, 0.3, 0.5):
    pu, pe = silencio_detectando(p), silencio_corrigiendo(p)
    print(f"p = {p:<6}  detectando: {pu:.3e} en silencio, {retransmite(p):.4f} retransmite"
          f"  |  corrigiendo: {pe:.3e}  |  razón {pe / pu:8.2f}  contra 3/p = {3 / p:7.2f}")

# p = 0.01    detectando: 6.792e-06 en silencio, 0.0679 retransmite  |  corrigiendo: 2.031e-03  |  razón   299.03  contra 3/p =  300.00
# p = 0.001   detectando: 6.979e-09 en silencio, 0.0070 retransmite  |  corrigiendo: 2.093e-05  |  razón  2999.00  contra 3/p = 3000.00
# p = 0.3     detectando: 6.505e-02 en silencio, 0.8526 retransmite  |  corrigiendo: 6.706e-01  |  razón    10.31  contra 3/p =   10.00
# p = 0.5     detectando: 1.172e-01 en silencio, 0.8750 retransmite  |  corrigiendo: 9.375e-01  |  razón     8.00  contra 3/p =    6.00

Puesto por millón de bloques transmitidos:

Detectar retransmite el 6,8 % de los bloques con $p={10}^{-2}$, que es casi $7p$: la probabilidad de que alguno de los siete bits se dé vuelta. Corregir se ahorra todas esas retransmisiones, y cada una que se ahorra la paga con unas $21p^2/7p=3p$ palabras malas. Medido con las fórmulas exactas, 0,0299 en $p={10}^{-2}$, una cada 33 retransmisiones evitadas. Otra vez el mismo 3.

Las razones de la tabla son por bloque transmitido. Si el detector pide cada bloque hasta aceptarlo, lo justo es contar por mensaje entregado: la falla silenciosa del detector se divide por la probabilidad de aceptar, 0,932, y la razón baja a 278,7 en $p={10}^{-2}$ y a 2978 en $p={10}^{-3}$. El orden no cambia: sigue siendo $3/p$, y el precio de detectar es mandar en promedio 1,073 bloques por mensaje.

Con $p\approx \mathrm{0,3}$ las dos curvas de arriba están cerca: corregir entrega mal el 67 % de los bloques y detectar el 6,5 %, una razón de 10. Bajando $p$, la azul cae con pendiente 2 y la gris con pendiente 3, y la distancia vertical entre las dos crece una década por cada década de $p$: eso es $3/p$ dibujado. La línea cortada de las retransmisiones cae con pendiente 1, y es la que corregir se ahorra.

04 · Dónde deja de valer

Cada aproximación, sola, dura poco. Barriendo $p$ desde ${10}^{-4}$, $7p^3$ se pasa del valor exacto en más de un 10 % desde $p=\mathrm{0,031}$, y $21p^2$ desde $p=\mathrm{0,028}$. Con $p=\mathrm{0,1}$ ya se pasan un 37 % y un 40 %: las dos olvidan que los otros bits también tienen que llegar bien, y que con $p$ grande eso deja de ser casi seguro.

Su cociente dura mucho más. Las dos se pasan en el mismo sentido y casi en la misma proporción, y el error se cancela: $3/p$ está a menos del 1 % de la razón exacta hasta $p=\mathrm{0,033}$, a menos del 3 % en todo el tramo hasta $p=\mathrm{0,3}$ —el peor punto de ese tramo es 0,3 mismo, con 3,0 %, y cerca de $p=\mathrm{0,25}$ es exacto—, y recién pasa el 10 % en $p=\mathrm{0,379}$. La versión con el término siguiente, $3/p-1$, es mejor con $p$ chico —menos del 1 % hasta 0,094— y peor con $p$ grande: pasa el 10 % en 0,270.

Donde se rompe del todo es en $p=\mathrm{0,5}$. Ahí los 128 patrones son igual de probables, y la cuenta es exacta: corregir falla con 120 de 128 (todos menos el nulo y los siete simples) y detectar con 15 de 128 (las palabras no nulas). La razón es 8, y $3/p$ dice 6. Pero ese canal ya no transmite nada, y ningún código se opera ahí. En el rango donde un código de bloque tiene sentido, $3/p$ es la razón, y lo que no hay que hacer es usar $7p^3$ o $21p^2$ sueltas pasado $p\approx \mathrm{0,03}$.

05 · Lo que se elige

Con la misma $G$, la misma $H$ y el mismo síndrome, lo que cambia es qué se hace con un síndrome no nulo, y la cuenta de esa decisión es $3/p$ palabras malas a cambio de $7p$ bloques retransmitidos. Cuanto mejor es el canal, más cara en proporción es la corrección: con $p={10}^{-3}$ hay menos de todo, pero por cada palabra mala que deja pasar el detector, el corrector deja pasar 2999. Si no hay canal de retorno, no hay elección: corregir es lo único posible. Si lo hay y una palabra equivocada cuesta caro, detectar gana por un factor que crece al mejorar el canal.

Y el término medio que el (7,4) no tiene lo da un bit más. El (8,4), el mismo código con un bit de paridad global, tiene $d_{\text{min}}=4$, y ahí $\lambda =1$, $\ell =2$ cumple la condición: corrige los simples y avisa los dobles. Con $p={10}^{-2}$ entrega mal y en silencio $\mathrm{5,34}·{10}^{-5}$, entre los dos extremos del (7,4). Es lo que sigue en la bandera que no se levanta.