Como dijimos ayer, este año se cumplen 75 años del artículo “A mathematical theory of communication”, piedra fundacional de la teoría de la información y obra cumbre de Claude Shannon, que es el de la foto (por lo visto, era muy aficionado a hacer malabares y andar en monociclo). El artículo es muy ameno, se recomienda su lectura; lo pueden encontrar acá. Uno de los principales resultados del artículo es el teorema de “source-coding”, que es el que discutimos ayer en la práctica y hace unos días en la teórica: el mínimo número de bits por caracter necesarios para codificar los mensajes de una fuente es la entropía por caracter de esa fuente. El otro resultado principal es el teorema de “noisy channel coding”, que ayer en la práctica comentamos muy por arriba. De este teorema quiero hablar en este post.

La idea es la siguiente: un emisor envía mensajes a través de un canal ruidoso, de forma que los mensajes se pueden corromper por el camino. Cómo hacemos para asegurarnos de que el receptor recibe el mensaje correcto? La idea más sencilla es la de la repetición: si le quiero mandar un bit a alguien (0 o 1) y quiero asegurarme de que va a recibir la información correctamente, le mando por ejemplo tres copias del mensaje (000 o 111). Así, si una de las copias se corrompe por el camino, el receptor va a poder leer el mensaje igualmente. Por ejemplo, si recibe 010 va a interpretar que yo le había mandado 000 y el segundo bit se corrompió, y va a tener una buena probabilidad de acertar. Pero está claro que no va a poder estar 100% seguro de acertar. Quién te dice que no se corrompieron 2 bits en el camino, que en realidad el mensaje original era 111 y fueron el primero y el tercero los que se corrompieron? Bueno, para reducir la probabilidad de error podemos enviar cuatro copias del mensaje en lugar de tres, o más aún. Claro que cuando aumentamos la redundancia, si bien reducimos la probabilidad de error, la comunicación se vuelve más lenta, menos eficiente. Surge entonces la pregunta: si queremos que la probabilidad de error sea cero, tenemos que mandar un mensaje infinitamente redundante? Nótese que, a más redundancia, más previsible se vuelve el caracter promedio, o menos informativo, y por lo tanto disminuye la entropía por caracter. Entonces, podemos reformular la pregunta de la siguiente forma: si queremos que la probabilidad de error sea cero, tenemos que mandar un mensaje con entropía cero, es decir, que no sea nada informativo? La respuesta es no: hay un umbral, llamado la capacidad del canal de comunicación, tal que, si la entropía cae por debajo de ese umbral, existe una forma de codificar el mensaje con la que la probabilidad de errores es despreciable. Ése es el segundo teorema de Shannon.

La capacidad del canal es algo simple. El canal está caracterizado por una distribución de probabilidad condicionada: la probabilidad p(x|y) de que el mensaje enviado por el emisor sea x dado que el receptor leyó y (si no hubiera ruido, esta probabilidad sería 1 para x=y, y 0 para cualquier otro x). Con esta distribución, junto con la distribución de probabilidad que caracteriza al emisor (cuya entropía nos da el mínimo número de bits necesarios para codificar sus mensajes) nos podemos calcular la entropía condicional S(X|Y), la incertidumbre acerca del mensaje enviado (X) conocido el mensaje recibido (Y). La información mutua

I(X,Y)=S(X)-S(X|Y)

es una medida de cuánta información sobrevive al ruido: es la información contenida en el mensaje enviado (S(X)) menos la incertidumbre del receptor sobre cuál es ese mensaje (S(X|Y)). Bueno, la capacidad del canal es el máximo de la información mutua sobre todos los posibles emisores.

El teorema de Shannon nos dice que, siempre que la entropía del emisor caiga por debajo de la capacidad del canal, habrá alguna forma de codificar el mensaje que garantice que no va a haber errores. Ahora, cuál es ese código es otra historia, y por lo visto tuvieron que pasar muchos años hasta que se encontraron los primeros ejemplos.