Preludio: Teoría de la Información
¿Cómo una computadora entiende los caracteres que estás leyendo ahora? Bueno, se sabe que las computadoras son dispositivos digitales que solamente entienden ceros y unos, así que de alguna manera deben estar representadas estas letras internamente. Seguramente el lector conoce el código ASCII o el formato UTF-8, y es muy probable que así estén representados estos caracteres.
ASCII se introdujo en la década de los 60 con el propósito de estandárizar las comunicaciones telegráficas y facilitar el intercambio de información desde una fuente hasta un receptor mediante un canal. La idea es poder representar en 7 bits los caracteres del alfabeto latino y signos de puntuación, como un grupo de caracteres no imprimibles y especiales (códigos desde 0 a 31 y 127). Así, solamente hay que transmitir una secuencia de bits y para decodificar un mensaje hay que emparejar grupos de 7 bits al caracter correspondiente dicho en una tabla con la asociación: caracter-código.
UTF-8 hace algo similar, pero con codificaciones de longitud variable y capaz de representar muchos más símbolos no latinos. Puede representar todos los caracteres Unicode y esto incluye los alfabetos griego, cirílico, armenio, hebreo, árabe; los silabarios japoneses; pictogramas del chino mandarín, cantonés y muchos más.
¿Qué otras cosas se pueden representar? ¿Cuántos bits se necesitan para codificar un mensaje? ¿Qué es un código? Todo esto se responderá en esta sección
El propósito de Bitte ein Bit es dar una introducción a las distintas codificaciones que existen para representar información, siendo las mencionadas anteriormente unas de las más famosas e importantes. Antes de seguir, hay que definir exactamente a qué nos referimos por codificación y comenzaremos dando una pincelada por los conceptos básicos de la Teoría de la Información que formaliza lo que intentamos hacer.
Orígenes
A principios del siglo XX ya habían nociones básicas de Teoría de la Información cómo un sistema de comunicaciones, pero fue en 1948 cuando Shannon publica su Magnum Opus, A Mathematical Theory of Communication en donde describe el grueso de la teoría y establece su formalización y fundamento matemático. Efectivamente desarrolla toda la teoría en una sola publicación y sigue siendo la mejor referencia del tema hasta la fecha.
En este describe que "el problema fundamental de la comunicación es transmitir exactamente o aproximadamente un mensaje hacia otro punto".
Esta cita viene con mucho peso: describe exactamente qué es lo que se quiere hacer, comunicar mensajes, y estos deben ser transmitidos por un canal. Pero antes de transmitirse deben ser codificados y luego ser enviados, luego se deben decodificar para poder leerse. Shannon explica cómo esto ocurre y cuáles son las limitaciones teóricas. A demás, propone que todo puede ser codificado con solo dos símbolos, y así definió al bit. Ya el lector puede hacerse una idea de lo revolucionaria que es esta publicación.
A continuación describimos nociones básicas de la Teoría de Información de Shannon.
Codificación
Shannon primero define un sistema de comunicaciones como una fuente que genera mensajes los cuales son codificados en un transmisor y luego enviados por un canal (que puede potencialmente tener ruido) hasta llegar a un receptor, el cual decodifica el mensaje para que sea recibido por el destino.
Para formalizar lo que ocurre en este sistema hay que plantear todo esto matemáticamente, lo que se hace usando teoría de probabilidad (que no es muy avanzada, así que no cunda el pánico). Un mensaje es una variable aleatoria discreta
donde \(\Omega\) es un espacio de mensajes y \(\mathcal{X}\) un espacio de representaciones de este.
Es como el lenguaje, uno puede decir "sol" en muchos idiomas "sun", "sole", "Sonne", "eguzkia", "nap", "zon"; pero sin cambiar fundamentalmente su significado. La idea del "sol" son los elementos de \(\Omega\) y la palabra en cada idioma corresponde a un elemento de \(\mathcal{X}\).
Estos mensajes se escribirán sobre un alfabeto \(\Sigma\), comúnmente tomado como \(\lbrace 0, 1 \rbrace\) mediante un código \(c\), que es una función desde \(\mathcal{X}\) hasta \(\Sigma^{*}\), donde \(\Sigma^{*}\) es la estrella de Kleene del alfabeto. Así, \(c(x)\) es la codificación de \(x \in \mathcal{X}\).
La idea acerca de qué codificación usar depende del contexto y de su aplicación particular. Si se quiere transmitir información rápidamente, vale la pena usar un código que minimize la longitud esperada, que es, con \(p(x) = \mathbb{P}(X = x)\),
Esto lo logran los códigos de Huffman, si es que se conoce la distribución de masa de probabilidad de \(X\). En la práctica, esta se estima de manera frecuencial.
A lo mejor se busca cómo representar números enteros para facilitar hacerles aritmética, en este caso la representación en complemento a dos que usan la mayoría de las computadoras es conveniente.
En general, se debe balancear la utilidad del acceso y operaciones que se pueden hacer sobre una secuencia codificada y su largo. Qué hacer exactamente depende del caso y vale la pena darle varias vueltas hasta encontrar una representación correcta. Los autores recomiendan ver los códigos descritos en la Wiki para que vean si alguno de estos códigos es apropiado para alguna de las aplicaciones del lector.
Contenido de información y entropía
El concepto fundamental de la Teoría de la Información es, evidentemente, la información. Los mensajes transmiten información, y esto de manera dependiente de su contenido. Así que un mensaje \(x\) que viene de una variable aleatoria discreta \(X\) tiene un contenido de información
La idea intuitiva de qué es la información es que a medida que un mensaje diga algo sorprendente: "la luna está hecha de queso", contendrá más información que un mensaje no tan sorprendente: "la luna está hecha de materiales rocosos". La noción de sorpresa es exactamente la de probabilidad, si esta es alta, la sorpresa es baja y viceversa. Es claro que esto es lo que ocurre con la fórmula anterior, pues \(p(x) \in \left] 0, 1 \right]\) y en 1, no hay información porque no hay sorpresa.
Con esto definimos la entropía de la variable aleatoria \(X\), que es simplemente la información esperada de ella:
Sus unidades son bits. Y tiene todo un formalismo matemático que explican por qué es la función "correcta" para estudiar en este contexto. Básicamente se reduce a que es continua, invariante bajo permutaciones, cóncava (lo que implica un único máximo, el cual ocurre cuando \(X\) es uniformemente distribuida), que en monótona con respecto al rango de \(X\) y que es aditiva. Estas cinco propiedades caracterizan \(\mathrm{H}\) completamente. Notar que si \(p(x) = 0\), entonces decimos que \(p(x) \lg p(x) = 0\) lo cual está avalado por el límite de \(\varepsilon \lg \varepsilon\) cuando \(\varepsilon\) tiende a cero por la derecha, que es cero.
Lo que representa la variable aleatoria \(X\) es a la fuente generadora de mensajes. Es como si estuviéramos recibiendo un mensaje letra por letra sin saber cuál es la que sigue, a medida que sigamos recibiendo letras podemos hacer análisis de frecuencias y estimar cuál será el siguiente caracter que recibiremos. En efecto lo que se está haciendo es aproximar \(p\).
Así que hemos descrito cómo se generan los mensajes. ¡Pero falta transmitirlos!
Esto se hace mediante un canal, primero habiendo codificado el mensaje. Exactamente qué tanto se puede comprimir el mensaje lo discutiremos en la siguiente sección, así que simplemente asumamos que se logró. Lo que se va a hacer es transmitirlo por el canal a cierta "velocidad", si vamos muy rápido puede que todo se mezcle y no se distinga nada, así que hay que transmitir "razonablemente". En este proceso puede que el mensaje se vea alterado y lo que llegue al receptor no sea exactamente lo que se envió: este es el efecto del ruido. Luego se decodifica lo que llegue y se obtiene una aproximación del mensaje enviado. Hay maneras de verificar si hubo algún error. Estos son los códigos detectores de errores y hay muchos de estos. Aún más sorprendente es que existen los códigos correctores de errores, como los de Hamming y los Reed-Solomon.
Entropía conjunta y condicional
Formalicemos a lo que nos referíamos por "velocidad". La idea es que la razón de transmisión sea tal que no se pierda información inherentemente por el proceso del envío del mensaje. Así que hay que ver cómo se relaciona el mensaje enviado con el recibido en un canal sin ruido, esto solamente depende el canal y de la fuente y se llama capacidad del canal, que denotaremos por \(C\).
Antes de decir exactamente qué es, debemos ver cómo relacionar la entropía de dos variables aleatorias discretas.
Sean \(X : \Omega \to \mathcal{X},\ Y : \Omega \to \mathcal{Y}\) dos variables aleatorias discretas y \(p(x, y) = \mathbb{P}(X = x \land Y = y)\) su distribución de probabilidad conjunta. Luego, su entropía conjunta \(\mathrm{H}(X, Y)\) representa la información esperada al observar ambas variables:
También existe la entropía condicional \(\mathrm{H}(Y \mid X)\) que indica cuánta información es esperada que sea necesaria para describir \(Y\) dado que se observó \(X\), está dada por:
Con estas nociones que relacionan las observaciones de variables aleatorias vamos a poder determinar cuánta información se comparten entre ellas a continuación.
Información mutua y capacidad del canal
Para poder relacionar al mensaje enviado con el recibido, y así poder determinar \(C\), debemos primero intentar maximizar la información transmitida entre ellos asumiendo que no hay ruido en el canal. La información mutua \(\mathrm{I}(X, Y)\) cuantifica cuánta información \(X\) e \(Y\) comparten; indica la dependencia entre conocer una variable y la reducción de incertidumbre a la hora de medir la otra. Está dada por
Con esto estamos listos para definir a la capacidad del canal de la siguiente manera:
Donde el supremo se toma sobre todas las codificaciones \(c\) posibles. Y lo que representa es la máxima razón de transmisión de información sobre el canal. Además existe la noción de razón de entropía \(R\), que representa la entropía promedio por símbolo transmitido.
Con esto se tiene todo lo necesario para enunciar los dos teoremas fundamentales de la Teoría de la Información: el de codificación de fuente y el de codificación de canal.
Teorema de codificación de fuente
¿Qué codificación de fuente es óptima? Esto lo responde este teorema e indica el límite de la compresión de información. La idea es tener compresión lossless, es decir sin pérdida de información al codificar un mensaje \(X\) de \(n\) símbolos. Ahora enunciamos formalmente el teorema.
Teorema: sean \(X_{1}, \dots, X_{n} : \Omega \to \mathcal{X}\) variables aleatorias discretas independientes e idénticamente distribuidas cada una con entropía \(\mathrm{H}\). Estas pueden ser comprimidas con más de \(n \mathrm{H}\) bits con una pérdida despreciable de información (esto es \(o(1)\) a medida que \(n \to \infty\)) y es prácticamente seguro que se perderá información si se codifican en menos bits.
Shannon demostró lo anterior en 1948 y describe exactamente lo que queremos. Cada uno de los símbolos del mensaje se debe codificar en un número de bits igual a su entropía. Si se usan menos símbolos, es prácticamente seguro que habrá pérdida de información y si se usan más, existe redundancia mas no se pierde información (con alta probabilidad). En la práctica lo que se quiere es llegar a \(\lceil n \mathrm{H}(X) \rceil\) si uno es optimista, pero uno también se puede satisfacer con \(n \lceil \mathrm{H}(X) \rceil\).
Resulta que las cotas sí se pueden lograr en la práctica con codificación Huffman, que es uno de los códigos descritos aquí en Bitte ein Bit. Es clara la relevancia de este teorema pues nos indica cuándo una codificación es lo más corta posible y nos permite transmitir de manera eficiente mensajes sobre canales sin ruidos, pues usando códigos que logren la optimalidad se transmiten usando mínimo espacio y lo más rápido posible.
Teorema de codificación de canal
Definimos la capacidad del canal como la máxima razón de transmisión de información sobre este y dijimos que a esa razón se podían transmitir mensajes lo más rápido posible si asumimos que no hay ruido. Y si hay ruido, resulta que existe cierta razón que permite transmitir mensajes libres de errores con cierto threshold. Aquí se define que en el sistema de comunicación, cierto mensaje \(x\) se transmite y que se recibe otro mensaje \(\hat{x}\) que es una estimación del mensaje enviado, luego la probabilidad de error es \(\mathbb{P}(x \neq \hat{x})\). De nuevo, en 1948 Shannon demostró que
Teorema: para todo \(\varepsilon > 0\) y razón de entropía \(R < C\), para \(n\) suficientemente grande existe un código de este largo y razón \(R' \geq R\) tal que la probabilidad de error en la transmisión es menor o igual que \(\varepsilon\). Además, las razones \(R'\) se obtienen en la práctica y están acotadas superiormente por
Algo interesante es que si \(R > C\), entonces es virtualmente seguro que habrán errores, pues lo que definimos como capacidad de canal es justamente la razón máxima de transferencia de información.
Con esto tenemos lo básico de la teoría de la información. Consiste en entender que los mensajes vienen con cierta distribución y que a partir de ella se define la entropía y con esta se llegan a cotas óptimas de codificación y de transferencia de información.
Referencias
- ASCII | ANSI X3.4-1977. (1977). National Institute for Standards.
- Berlekamp, Elwyn (2014). Algebraic Coding Theory. World Scientific.
- RFC 3628. UTF-8 Standard.
- Shannon, C. (1948). A Mathematical Theory of Communication. Bell System Technical Journal. 27: 379-423, 623-656.