Teoría de la información
Un canal telefónico de 3100 Hz con 35 dB de relación señal a ruido admite como máximo unos 36 kbit/s. Los últimos módems de voz llegaron a 33,6: la teoría puso el techo antes de que existieran.
01Medir la información
Claude Shannon propuso en 1948 medir la información de un mensaje por lo improbable que es: un mensaje que se esperaba no informa nada. La información de un símbolo de probabilidad \( p \), y el promedio sobre todos los símbolos de una fuente, la entropía, son:
La entropía no es una definición arbitraria: el teorema de codificación de fuente dice que es la cantidad mínima de bits por símbolo con la que se puede representar la fuente sin pérdidas. Ningún código lo hace mejor, y codificando bloques de símbolos cada vez más largos es posible acercarse tanto como se quiera.
02Codificación de fuente: Huffman
Un código de longitud variable asigna palabras cortas a los símbolos frecuentes y largas a los raros, como el código Morse. Para que se pueda decodificar sin separadores, ninguna palabra puede ser el comienzo de otra: es un código de prefijo. El algoritmo de Huffman construye el mejor código de prefijo posible: une repetidamente los dos símbolos menos probables en uno nuevo, hasta que queda uno solo, y lee los códigos recorriendo el árbol.
Seis símbolos con probabilidades proporcionales a los pesos elegidos. Las barras llenas son las longitudes del código de Huffman; los contornos, la información de cada símbolo, \( \log_2(1/p) \). Encima de cada barra está la palabra de código.
03Capacidad de un canal
Un canal con ruido confunde algunos símbolos. La información mutua entre la entrada y la salida mide cuánto se aprende de la entrada al ver la salida, y su máximo sobre todas las distribuciones de entrada es la capacidad del canal. En el canal binario simétrico, que invierte cada bit con probabilidad \( p \):
El teorema de codificación de canal es el resultado más sorprendente de Shannon: si la velocidad es menor que la capacidad, existen códigos con una probabilidad de error tan chica como se quiera. No hay que elegir entre velocidad y confiabilidad, sino agregar redundancia de la forma correcta. Por encima de la capacidad, en cambio, ningún código lo consigue.
04El canal gaussiano: la fórmula de Shannon y Hartley
Para un canal de ancho de banda \( B \) con ruido blanco gaussiano, la capacidad es:
La fórmula fija un límite que ninguna modulación ni código puede superar, y permite medir qué tan buenos son los sistemas reales: los códigos turbo y LDPC, usados en la telefonía celular y la televisión digital, operan a menos de 1 dB de él. La comparación de los sistemas con ese límite es el tema de la intercomparación de sistemas.
05En el laboratorio
Contar las frecuencias de las letras de un texto largo en castellano con un programa, calcular su entropía y construir el código de Huffman. Comparar el tamaño con el de un código de 5 bits por letra.
Comprimir con un compresor general archivos de texto, de audio y de datos al azar, y comparar las tasas de compresión con la entropía estimada.
Simular un canal binario simétrico con un código de repetición de tres bits y votación, y comparar la tasa de error con la del canal sin código.
06Errores frecuentes
- Confundir bit de información con dígito binario. Un dígito binario lleva a lo sumo un bit de información, y menos si no es equiprobable.
- Creer que la compresión puede bajar de la entropía. Sin pérdidas, es imposible en promedio.
- Leer la capacidad como una velocidad alcanzable con cualquier sistema. Es un límite: alcanzarla exige códigos largos y complejos.
- Usar la fórmula de Shannon con la S/N en dB. Va en veces: 30 dB son 1000.
07Autoevaluación
¿Qué entropía tiene una fuente de cuatro símbolos con probabilidades 1/2, 1/4, 1/8 y 1/8?
1,75 bits, y el código de Huffman 0, 10, 110, 111 la alcanza.
¿Cuál es la capacidad de un canal binario simétrico con p = 0,1?
\( 1 - H_b(0{,}1) = 1 - 0{,}469 = 0{,}531 \) bits por uso.
¿Qué capacidad tiene un canal de 1 MHz con 20 dB de relación señal a ruido?
\( 10^6 \log_2 101 \approx 6{,}66 \) Mbit/s.
¿Por qué Huffman no sirve para una fuente binaria con p = 0,95?
Porque no puede usar menos de 1 bit por símbolo y la entropía es 0,29 bits: hay que codificar bloques de símbolos.
08Para ampliar
- Thomas M. Cover y Joy A. Thomas. Elements of Information Theory. 2.ª ed., Wiley, 2006. La referencia de la materia: entropía, codificación de fuente y capacidad de canal.
- Claude E. Shannon y Warren Weaver. The Mathematical Theory of Communication. University of Illinois Press, 1949. El trabajo original de Shannon, con una introducción de Weaver para lectores no especialistas.
- David J. C. MacKay. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003. Un enfoque moderno, con los códigos que se acercan al límite de Shannon.