Unidad 1 · El canal binario simétrico
El canal binario simétrico (BSC) es el modelo más pobre que se puede escribir para algo que corrompe información: da vuelta cada bit con probabilidad p, independiente del bit y de todos los demás. No hay ráfagas, no hay memoria, no hay nada más. Y sin embargo alcanza para hacer la pregunta que abre el curso entero: cuánta información se puede pasar por un canal así sin equivocarse.
La respuesta tiene nombre —la capacidad del canal, C = 1 − H(p), donde H(p) es la entropía de una fuente binaria con esa probabilidad— y una forma que no se adivina mirando la fórmula. En p = 0 vale 1: un canal que nunca se equivoca transmite todo. En p = 0,5 vale 0: cada bit que sale es una moneda, y una moneda no informa nada de la que entró. Hasta ahí, nada raro. La fórmula, además, es simétrica respecto de 0,5 —lo mismo lejos de ese punto hacia cualquiera de los dos lados—, y esa simetría deja abierta una pregunta incómoda: ¿qué pasa en el otro extremo, cuando el canal miente siempre?
La curva gris es H(p): cuánta incertidumbre tiene el resultado de un bit que pasó por el canal. Sube desde 0 en p = 0, llega a su máximo —un bit entero de incertidumbre— justo en p = 0,5, y baja otra vez a 0 en p = 1. Tiene sentido porque en los dos extremos el resultado ya no sorprende a nadie: en p = 0 el bit sale como entró, y en p = 1 sale siempre dado vuelta, así que también se sabe de antemano cuál va a ser.
La curva azul, C = 1 − H(p), es la que importa, y es la reflejada: donde H sube, la capacidad baja, porque cada bit de incertidumbre es un bit que el canal no transmite. Fijate en la simetría: la capacidad en p es exactamente la misma que en 1 − p, así que a p = 0,11 y a p = 0,89 —tan lejos de 0,5 como de los extremos, uno de cada lado— la capacidad da el mismo número: 0,5001. Ya se comió la mitad de lo que el canal podía dar, y en 0,89 el error nominal es altísimo. Lo que arruina un canal no es cuántos bits se dan vuelta: es cuánto se sabe de antemano sobre cuáles.
Es la función que ya usaste en el práctico, con el chequeo de los extremos escrito a mano y no dejado en manos del punto flotante: log2(0) da -Infinity, y 0 · (-Infinity) no da 0, da NaN.
from math import log2
def entropia(p):
# En los dos extremos H vale cero, y así el log2(0) no se calcula nunca.
if p <= 0 or p >= 1:
return 0.0
return -p * log2(p) - (1 - p) * log2(1 - p)
def capacidad_bsc(p):
"""La capacidad del canal binario simétrico, en bits por uso."""
return 1 - entropia(p)
capacidad_bsc(0.5) # 0,0000: el canal no transmite nada
capacidad_bsc(1.0) # 1,0000: y este canal, que siempre miente, es perfecto
Todo lo de arriba es exacto porque es matemática: H(p) se calcula, no se mide. Pero un canal de verdad no te entrega p; te entrega bits, y de ahí en más lo único que hay es contar cuántos llegaron dados vuelta. Con un mensaje largo esa cuenta se acerca a p — es la ley de los grandes números, funcionando a favor. Con un mensaje corto, no hay ninguna garantía de que se parezca.
Con HOLA —32 bits— y una p chica, es normal que salga 0 bits dados vuelta varias veces seguidas, o que de golpe salgan 3 o 4: con tan pocos bits la varianza es enorme y la tasa observada puede estar lejísimos de p. Estirá el mensaje a una frase larga y mandala varias veces: la tasa empieza a temblar cada vez menos alrededor de p. El BSC no promete nada sobre este mensaje. Promete algo sobre el promedio de infinitos mensajes, y esa es la primera vez en el curso en que una cota aparece como lo que realmente es: asintótica.
Guardá esta idea para la nota que sigue, porque ahí vuelve con otro disfraz: la ganancia de un código de corrección también es un límite al que dos curvas se acercan, no un número que se cumple bit a bit.