Codificación de la información¶
Códigos y codificación¶
La transmisión de la información¶
Se define alfabeto como cualquier conjunto finito, e información como cualquier sucesión de elementos de un alfabeto.
El esquema general de un proceso de transmisión de información es el siguiente: un emisor envía información (o mensaje) a un receptor a través de cierto canal:
A menudo la forma en que la información está escrita originalmente no es conveniente para su transmisión: puede ocupar demasiado espacio o ser vulnerable a interferencias. Se codifica entonces para adaptarla a las características del canal y a las necesidades de emisor y receptor. Los objetivos perseguidos con la codificación son los siguientes:
- comprimir la información,
- detectar y corregir los posibles errores aparecidos durante la transmisión,
- garantizar la privacidad de la información.
Si se transmite de forma codificada, a la salida del canal, la información debe descodificarse, para llegar al receptor en su forma original. Por tanto el esquema anterior queda en la forma:
Codificación¶
Los alfabetos en que está escrita originalmente la información y en que será codificada no tienen porqué coincidir. El primero recibe el nombre de alfabeto fuente y el segundo de alfabeto código. Dado un alfabeto cualquiera \(\mathcal{A}\), se llama palabra escrita en el alfabeto \(\mathcal{A}\) a cualquier secuencia finita de elementos de \(\mathcal{A}\). Se denota por \(\mathcal{P(A)}\) al conjunto de palabras escritas en \(\mathcal{A}\).
Codificación de alfabetos¶
Codificar el alfabeto fuente \(\mathcal{A}=\{a_1,\cdots,a_m\}\) en el alfabeto código \(\mathcal{B}=\{b_1,\cdots,b_q\}\) es dar una aplicación inyectiva \(c:\mathcal{A} \rightarrow \mathcal{P(B)}\). Para cada \(a_i\in\mathcal{A}\), \(c(a_i)\) es la codificación de \(a_i\), y el subconjunto \(\mathcal{C}=img(c)\) de \(\mathcal{P(B)}\) es el código empleado. Se dice que \(\mathcal{C}\) es un código de \(\mathcal{A}\) sobre \(\mathcal{B}\) y cada uno de sus elementos se llama palabra código.
Se llama longitud de una palabra al número de símbolos que la componen.
Si todas las palabras de un código son de la misma longitud \(n\), se dice que es un código en bloque de longitud \(n\). En otro caso se dice que el código es de longitud variable.
Los códigos usados para la compresión de información han de ser de longitud variable, mientras que los códigos en bloque son adecuados para la detección y corrección de errores.
Codificación de mensajes¶
En la práctica no es interesante la codificación de letras de \(\mathcal{A}\), sino de mensajes escritos en el alfabeto \(\mathcal{A}\). Esto se hace concatenando la codificación de cada letra del mensaje. Es decir, la aplicación \(c\) se extiende a una aplicación \(c':\mathcal{P(A)}\rightarrow \mathcal{P(B)}\) mediante \(c'(a_{i_1}a_{i_2}\dots a_{i_n})=c(a_{i_1})c(a_{i_2})\cdots c(a_{i_n})\).
Decodificación¶
Una vez recibido el mensaje es preciso descodificarlo, es decir traducirlo al alfabeto fuente. Esto siempre es posible en el caso de mensajes formados por una sola letra, ya que la aplicación \(c\) es inyectiva, pero puede no serlo en el caso de mensajes de más de una letra.
Un código tiene decodificación única si la aplicación \(c'\) es inyectiva.
Medida de la información¶
Fuentes de información¶
Es cómodo suponer que los mensajes a codificar provienen de un objeto abstracto llamado fuente de información.
Una fuente de información \(\mathcal{F}\) es un alfabeto fuente \(\mathcal{A}=\{a_1,\dots,a_m\}\), junto con una distribución de probalidades \(p_1,\dots,p_m\) sobre \(\mathcal{A}\).
La probabilidad de que la fuente produzca un mensaje \(a_{i_1}\dots a_{i_r}\) se calcula en términos de probabilidades elementales \(\operatorname{prob}(a_{i_1}\cdots a_{i_r})=p_{i_1}\cdots p_{i_r}\); asumiendo que las emisiones de cada uno de los símbolos de la fuente son sucesos independientes, es decir, que la fuente no tiene memoria.
Dada una fuente de información \(\mathcal{F}\) asociada al alfabeto fuente \(\mathcal{A}=\{a_1,\dots,a_m\}\) con distribución de probabilidades \(p_1,\dots,p_m\), se llama extensión \(k\)-ésima de \(\mathcal{F}\) a la fuente de información \(\mathcal{F}^k\) que tiene como alfabeto fuente \(\mathcal{A}^k\) y cuya distribución de probabilidades se obtiene mediante la regla \(\(\operatorname{prob}(a_{i_1},\dots,a_{i_k})=p_{i_1}\cdots p_{i_k}.\)\)
Medida de la información. Entropía¶
Se llama bit a la cantidad de información que contiene cada uno de los dos símbolos de una fuente de información que consta de dos símbolos equiprobables.
Una vez fijada la unidad de medida, se va a determinar la cantidad de información para una fuente genérica, de alfabeto \(\mathcal{A}=\{a_1,\dots,a_m\}\) y probabilidades \(p_1,\dots,p_m\). Se denota por \(I(a_i)\) la cantidad de información del símbolo \(a_i\). Algunas propiedades que debe cumplir \(I(a_i)\) son las siguientes:
-
\(I(a_i)\) debe depender solamente de la probabilidad \(p_i\) de \(a_i\); por tanto, la función \(I\) estará definida en el intervalo (0,1]. Teniendo en cuenta esta propiedad se suele escribir \(I(p_i)\) en vez de \(I(a_i)\).
-
\(I\) ha de ser decreciente. La información que aporta un suceso es mayor cuanto más improbable es éste.
-
Para cada par de símbolos \(a_i,a_j\in \mathcal{A}\) debe verificarse que \(I(a_i,a_j)=I(a_i)+I(a_j)\). Como \(\operatorname{prob}(a_i,a_j)=p_ip_j\) se puede escribir esta condición como \(I(p_ip_j)=I(p_i)+I(p_j)\).
Estas condiciones, elegida la unidad de medida, determinan unívocamente el valor \(I(p_i)\) como demuestra la siguiente proposición.
Si \(f:(0,1]\rightarrow R\) es una función que verifica:
(1) \(f\) es decreciente en \((0,1]\), y
(2) \(f(x+y)=f(x)+f(y)\) para cada \(x,y \in (0,1]\);
entonces existe una constante \(k<0\) tal que \(f(x)=k\ln(x)\).
Como consecuencia de la proposición, \(I(p_i)=k\ln(p_i)\), y sólo falta por determinar la constante \(k\), que dependerá de la unidad de medida. Fijado como tal el bit, se tendrá \(1=I(1/2)=-k\ln(2)\), luego \(k=-\frac{1}{\ln(2)}\).
Fijando como unidad de medida el bit, se tiene que la cantidad de información del símbolo \(a_i\) es \(\(I(p_i)=-\log_2(p_i).\)\)
Entropía¶
Sea \(\mathcal{F}\) una fuente de información asociada al alfabeto \(\mathcal{A}=\{a_1,\dots,a_m\}\) con distribución de probabilidades \(p_1,\dots,p_m\).
Se llama entropía de la fuente \(\mathcal{F}\) al número \(\(H(\mathcal{F})=\sum_{i=1}^m p_i I(p_i)=\sum_{i=1}^m p_i \lg(\frac{1}{p_i}) \;\;\; \mbox{(bits/símbolo)},\)\) donde \(\lg\) es el logaritmo en base 2.
La entropía de \(\mathcal{F}\) es un promedio ponderado de la cantidad de información de los símbolos de \(\mathcal{A}\). como depende únicamente de la distribución de probabilidades en \(\mathcal{F}\), a veces se escribe \(H(p_1,\dots,p_m)\) en lugar de \(H(\mathcal{F})\).
En el caso de que alguna de las probabilidades de la distribución en \(\mathcal{F}\) fuera nula, no tendría sentido la definición. Así, por convenio, se acuerda que \(\(0\lg(\frac{1}{0})=0.\)\)
Si \(\mathcal{F}\) es una fuente de información asociada al alfabeto \(\mathcal{A}\) con \(m\) símbolos y distribución de probabilidades \(p_1,\dots,p_m\), entonces \(\(0\leq H(\mathcal{F})\leq \lg(m).\)\) Además,
- \(H(\mathcal{F})=0\) si, y sólo si, existe un \(i\) con \(p_i=1\);
- \(H(\mathcal{F})=\lg(m)\) si, y sólo si, \(p_i=1/m\) para todo \(i\).
Entropía de una fuente extendida¶
Para cada fuente de información \(\mathcal{F}\) y cada entero positivo \(k\), se verifica que \(\(H(\mathcal{F}^k)=kH(\mathcal{F}).\)\)
Canales sin ruido¶
Si el canal por el que circula la información la transmite fielmente (esto es, sin alterarla con interferencias o ruidos), la codificación debe intentar reducir los mensajes a su forma más concisa. Los códigos adecuados para este fin son los de longitud variable con decodificación única.
Códigos óptimos¶
Códigos instantáneos¶
Se dice que un código es instantáneo si ninguna palabra código es prefijo de otra.
Todo código instantáneo tiene decodificación única.
Los códigos instantáneos presentan una ventaja adicional, y es que se puede iniciar la codificación simultánemente a la recepción del mensaje (es decir, se puede decodificar el mensaje en tiempo real).
Teoremas de Kraft y McMillan¶
La condición necesaria y suficiente para que exista un código \(q\)-ario instantáneo con \(m\) palabras código de longitudes \(l_1,\dots,l_m\) (\(l_i\geq1\)) es que se verifique la desigualdad \(q^{-l_1}+\cdots+q^{-l_m}\leq 1.\)
Todo código \(q\)-ario con \(m\) palabras código de longitudes \(l_1,\dots,l_m\) (\(l_i\geq1\)), que tenga decodificación única verifica la desigualdad de Kraft \(q^{-l_1}+\cdots+q^{-l_m}\leq 1.\)
Las desigualdades de McMillan y Kraft demuestran que si existe un código con decodificación única y ciertas longitudes de palabra, entonces también existe un código instantáneo con las mismas longitudes. Este hecho garantiza que se pueda limitar el estudio a los códigos instantáneos.
Longitud media de un código¶
Sea \(\mathcal{F}\) una fuente asociada al alfabeto \(\mathcal{A}=\{a_1,\dots,a_m\}\) con distribución de probabilidades \(p_1,\dots,p_m\), y \(\mathcal{C}\) un código instantáneo \(q\)-ario de \(\mathcal{F}\). Sean \(l_1,\dots,l_m\) las longitudes de las palabras de \(\mathcal{C}\).
Se llama longitud media de \(\mathcal{C}\) a \(l(\mathcal{C})=\sum_{i=1}^mp_i l_i.\)
Así, un mensaje formado por \(n\) símbolos fuente se codificará con \(nl(\mathcal{C})\) símbolos código, como media.
Se denota por \(l_q(\mathcal{F})\) a la menor longitud media posible de un código instantáneo \(q\)-ario de la fuente \(\mathcal{F}\). Se dice que un código instantáneo \(q\)-ario de \(\mathcal{F}\), \(\mathcal{C}\), es óptimo si \(l(\mathcal{C})=l_q(\mathcal{F})\).
También se utilizan los términos compactos o de Huffman para designar los códigos óptimos.
Teorema de Shannon¶
Si \(\mathcal{C}\) es un código instantáneo \(q\)-ario de la fuente \(\mathcal{F}\), entonces
Si \(\mathcal{C}\) es un código instantáneo binario de la fuente \(\mathcal{F}\), entonces \(l(\mathcal{C})\geq H(\mathcal{F})\).
Para toda fuente \(\mathcal{F}\) se verifica que
Para toda fuente
Así, aumentando el número de símbolos que se codifican simultáneamente, podemos acercarnos arbitrariamente a la longitud mínima permitida por el teorema de Shannon.
Se llama eficacia de un código \(q\)-ario \(\mathcal{C}\) de la fuente \(\mathcal{F}\) al cociente
La eficacia de un código está comprendida entre 0 y 1, y mide su capacidad para comprimir información en relación con la cota de Shannon. Considerando fuentes de información extendidas, se pueden conseguir códigos de eficacia tan cercana a 1 como se quiera. Esta propiedad puede llevar a pensar en la utilización de fuentes extendidas con \(k\) grande; sin embargo, los códigos así obtenidos son difíciles de manipular y el tiempo empleado para su codificación y decodificación crece muy rápidamente con \(k\). Por tanto, en la práctica, será preciso mantener un quilibrio entre la eficacia teórica y las necesidades y limitaciones técnicas.
Construcción de códigos óptimos¶
Códigos óptimos binarios¶
Sea \(\mathcal{F}\) una fuente de información asociada al alfabeto con \(m\) símbolos \(\mathcal{A}=\{a_1,\dots,a_m\}\) con distribución de probabilidades \(p_1,\dots,p_m\). Se puede suponer que \(p_1 \geq \cdots \geq p_m\). El objetivo es construir un código óptimo binario para \(\mathcal{F}\). Este proceso se llevará a cabo de forma inductiva, siguiendo el llamado método de Huffman.
Se llama fuente reducida de \(\mathcal{F}\) a la fuente \(\mathcal{F}_{(1)}\)
asociada al alfabeto con \(m-1\) símbolos \(A_{(1)}=\{a_1, \dots, a_{m-1,m} \}\)
con distribución de probabilidades
\(prob(a_1)=p_1,\dots,prob(a_{m-2})=p_{m-2},prob(a_{m-1,m})=p_{m-1}+p_m\).
Si \(C_{(1)}\) es un código óptimo para \(\mathcal{F}_{(1)}\) dado por cierta codificación \(c_{(1)}\), se considera la codificación \(c\) de \(\mathcal{F}\):
El código \(\mathcal{C}\) dado por esta codificación es instantáneo por serlo \(\mathcal{C}_{(1)}\). Además, es óptimo.
Si \(C_{(1)}\) es un código óptimo para \(\mathcal{F}_{(1)}\), entonces \(\mathcal{C}\) es un código óptimo para \(\mathcal{F}\).
Si se conoce un código óptimo para \(F_{(1)}\), con el método de Huffman, se puede encontrar el código buscado para \(\mathcal{F}\). en caso contrario, se debe repetir el procedimiento con \(\mathcal{F}_{(1)}\), obteniendo una nueva fuente reducida \(\mathcal{F}_{(2)}\). Iterando el proceso se llegará (en el peor de los casos) a una fuente \(\mathcal{F}_{(m-2)}\) con sólo dos elementos. Esta fuente tiene una codificación óptima evidente, con palabras código 0 y 1.
El código \(\mathcal{C}\) así obtenido es óptimo y tiene longitud media \(l(\mathcal{C})=2.1\). Como la entropía de la fuente es \(H(\mathcal{F})\approx 2.046\), la eficacia del código es \(\eta(\mathcal{C})\approx 0.974\).
Códigos óptimos no binarios¶
La construcción de códigos óptimos sobre alfabetos no binarios sigue las mismas ideas que se han visto, con las adaptaciones obvias. Si el alfabeto código tiene \(q\) elementos, en cada reducción se pueden colapsar los \(q\) símbolos menos probables en uno solo de la fuente conocida. Esto puede hacerse en todas las reducciones si y sólo si \(q-1\) divide al cardinal \(m\) del código.
Apéndice: Algoritmos dinámicos¶
El método de Huffman resuelve completamente el problema de encontrar codificaciones óptimas de fuentes cuyas estadísticas son conocidas de antemano. Cuando no se dispone de estos datos los métodos de compresión utilizados son algo diferentes y se basan en una aproximación ‘dinámica’ a las estadísticas de la fuente, a partir de cieras secuencias tomadas del propio mensaje a comprimir.
Uno de los métodos dinámicos más conocidos es el algoritmo LZ-77 de J. Ziv y A. Lempel, que es la base matemática de los programas de ordenador personal de tipo ‘zip’. Su funcionamiento es el siguiente:
Se desea comprimir en lenguaje binario una sucesión \(\alpha_1,\alpha_2,\alpha_3,\dots\), de símbolos (no necesariamente binarios) emitidos por una fuente \(\mathcal{F}\). Para ello se fija un entero \(n\) y, como aproximación a la fuente, se toman secuencias de \(n\) símbolos de la sucesión original, llamados ventanas.
La primera ventana estará formada por los \(n\) primeros símbolos de la sucesión \(\alpha_1,\alpha_2,\alpha_3,\dots\). Se codifican en alfabeto binario sin compresión, ya que será preciso conocerlos en la decodificación.
Se comienza la compresión determinando el mayor entero positivo \(l\) tal que exista una secuencia de longitud \(l\), \(\alpha_{n+1},\dots,\alpha_{n+l}\) contenida en la primera ventana, es decir, tal que \(\{\alpha_{n+1},\dots,\alpha_{n+l}\}=\{\alpha_m,\dots,\alpha_{m+l-1}\}\) con \(m+l-1 \leq n\). La secuencia \(\alpha_{n+1},\dots,\alpha_{n+l}\) se codifica por:
una codificación binaria de la longitud \(l\); y
una codificación binaria de \(m\).
El proceso se itera tantas veces como sea preciso hasta acabar el mensaje a comprimir, tomando en cada iteración como ventana los últimos \(n\) símbolos codificados. Así, por ejemplo, la segunda ventana es \(\alpha_{1+l},\dots,\alpha_{n+l}\).
La decodificación se realiza del modo obvio. Al comenzar, el decodificador conoce la primera ventana y los números \(l\) y \(m\). Con ellos puede rescatar la primera secuencia codificada, cuya longitud y posición son \(l\) y \(m\). Por ejemplo, si \(n=6, l=3,m=2\) y la primera ventana es \(a,b,c,d,e,f\), la primera secuencia comprmida es \(b,c,d\). Recuperada la primera secuencia, se repite el proceso con la segunda ventana, etc.
Referencias¶
- Carlos Munuera, Juan Tena: Codificación de la información. Universidad de Valladolid,1997