Unidad 4 Teoría de la Información y Codificación

Vista previa del material en texto

UNIDAD 4 Teoría de la Información y Codificación
Teoría de la Información
La Teoría de la Información es una teoría matemática creada por Claude E. Shannon y Warren Weaver en
el año 1948 y que forma la piedra angular sobre la que se ha desarrollado toda la teoría actual de la
comunicación y la codificación.
La Teoría de la Información se encuentra aún hoy en día en relación con una de las tecnologías en boga,
Internet. Desde el punto de vista social, Internet representa unos significativos beneficios potenciales, ya
que ofrece oportunidades sin precedentes para dar poder a los individuos y conectarlos con fuentes cada
vez más ricas de información digital.
En general, el problema que se plantea de resolver con la Teoría de la Información es la de:
“Poder transmitir información a la máxima velocidad posible por un canal de comunicaciones, con una
mínima cantidad de errores posible”
Shannon se planteó el siguiente problema:
“Dado un conjunto de mensajes posibles que una fuente puede producir, ¿Cómo deben representarse
estos mensajes para que la información sea conducida de la mejor manera sobre un sistema dado con sus
limitaciones físicas inherentes?”
La idea es poder determinar la forma en que esto es posible y si existe alguna cota máxima posible de
alcanzar
La Teoría de la Información es un tema matemático que trata con tres conceptos básicos:
1. La medida de la información
2. La capacidad de un canal de comunicación para transferir información
3. La codificación como un medio de utilizar los canales a toda su capacidad.
Teorema Fundamental de la Teoría de la Información
Estos conceptos están ligados al teorema fundamental de la teoría de la información, que puede resumirse
de la siguiente manera:
“Dada una Fuente de información y un canal de comunicación, existe una técnica de codificación tal que la
información puede ser transmitida sobre el canal a cualquier rapidez menor que la capacidad del canal y
con una frecuencia de errores arbitrariamente pequeña a pesar de la presencia de ruido”
El aspecto sorprendente de este teorema es la transmisión libre de errores sobre un canal ruidoso, lo que
se obtiene por medio de la codificación.
Teoría matemática de las comunicaciones
Shannon desarrolló la “Teoría matemática de las comunicaciones” que tenía como objetivo:
Hacer lo más eficiente posible la transmisión de información, con un número mínimo de errores.
La codificación se emplea para adaptar la fuente al canal para una transferencia de información con un
máximo de confiabilidad. Nos limitaremos a los conceptos de medida de la información y a la capacidad
del canal. Con lo cual se responderá a las siguientes preguntas:
¿Cómo restringen a la transmisión de información las limitaciones físicas fundamentales (ancho de banda
y ruido, etc.)?
¿Existe algo así como un sistema de comunicación ideal y de haberlo cuales serían sus características?
Principios de la transmisión de Información
La Comunicación: es el proceso mediante el cual se transfiere información desde un punto en el espacio y
en el tiempo, denominado “fuente de información”, hasta otro punto denominado “destino de la
información, con el mínimo de pérdidas o perturbaciones.
La reproducción perfecta del mensaje no es posible, pero desde un punto de vista práctico es suficiente
que la reproducción sea hecha con una aproximación o fidelidad que depende de la calidad o fin que se
persiga (QoS?)
En todo caso, en el proceso de transmisión, la información experimentara siempre una cierta degradación,
cuyos límites dependerán del empleo que se haga de dicha información.
Modelo de un Sistema de Transmisión de Información
Fuente de Información: La información o inteligencia a transmitir se origina en la fuente de información.
Esta se materializa como un conjunto (sin entrar en detalles) finito y discreto, de N símbolos o mensajes
distintos e independientes cuyo significado es conocido en el destino.
Hay muchas clases de fuentes de información, incluyendo personas y maquinas, de manera que los
símbolos o mensajes pueden tomar una gran variedad de formas: secuencias de símbolos, letras, una
magnitud que varía en el tiempo, etc. Pero sin importar la naturaleza del mensaje el propósito del sistema
de comunicación es el de proporcionar una réplica más o menos exacta del mismo en el destino.
Transductor de Entrada: Como regla general, el mensaje que se produce en la fuente de información no es
de naturaleza eléctrica y por lo tanto se necesita un transductor o codificador que convierta el mensaje en
una señal compatible con el tipo particular del sistema de transmisión que se empleara. Entonces:
Información es la inteligencia o significado que se va a transmitir, es una entidad INTANGIBLE
Mensaje es la materialización de la información en una cantidad
MENSURABLE.
O sea el mensaje es el soporte de la información y que el número de elementos del conjunto de las
señales de salida del transductor debe ser igual al número de elementos del conjunto de símbolos o
mensajes de la fuente de información.
Ancho de Banda y Potencia de Transmisión: Son dos parámetros de gran importancia. Los sistemas de
comunicación deben diseñarse para utilizar estos dos recursos en la forma más eficiente posible. En
general, es difícil optimizar ambos recursos simultáneamente, o sea, un recurso puede considerarse más
importante o más escaso que el otro. Los canales se los puede así clasificar como “limitados en potencia”
o “limitados en ancho de banda”.
Ejemplos: Los canales telefónicos son canales limitados en ancho de banda, los canales de RF
(inalámbricos) son limitados más en potencia.
La meta ideal en el diseño de un sistema de comunicación es la de transmitir información a la máxima
velocidad con el mínimo de potencia y ancho de banda.
Concepto de Información
Entonces…el propósito de un sistema de comunicación es el de TRANSMITIR INFORMACION.
Sin embargo no se ha especificado lo que realmente significa el término “Información”, y mucho menos
como se la puede cuantificar o medir.
Considérese una situación hipotética que se presenta:
A. Mañana saldrá el sol.
B. Mañana caerá granizo
C. Mañana habrá un sismo
¿Cuál es la información más probable?
Obviamente la declaración A aporta poca información, pues es la más probable.
Intuitivamente, se sabe que el enunciado C contiene gran cantidad de información, pues tiene muy poca
probabilidad de ocurrencia, es decir P(C) << 1
A. Mañana saldrá el sol.
B. Mañana caerá granizo
C. Mañana habrá un sismo
Por consiguiente, P(C) < P(B) < P(A) y la información I(C)> I(B) > I(A) Se observa que cuando menor sea
la probabilidad de un enunciado, mayor es la información aportada por el mismo‚ y por tanto una mayor
incertidumbre o sorpresa en el mensaje.
Es decir que la información es una función inversa a la probabilidad de ocurrencia de un evento.
I = f (1/P), donde f es una función matemática a determinar. Esto conduce a expresar que la medida de la
información esta relacionada con la incertidumbre, la incertidumbre de parte del usuario acerca de cual
será el mensaje.
INCERTIDUMBRE:
refiere a lo desconocido
No se sabe si sucederá
A lo inesperado
A lo imprevisible
LA INFORMACIÓN DISMINUYE LA INCERTIDUMBRE PORQUE APORTA MAYOR CONOCIMIENTO
SOBRE UN TEMA.
PROBABILIDAD:
Se encarga de evaluar todas aquellas actividades en donde se tiene incertidumbre, acerca de los
resultados que se puede esperar.
La probabilidad es una escala entre 0 y 1
Al suceso imposible le corresponde el valor “0”
Al suceso seguro le corresponde el valor “1”
El resto de los sucesos estarán comprendidos entre la escala de 0 y 1. LA PROBABILIDAD
NUNCA PUEDE SER UN VALOR NEGATIVO
LA SUMA DE TODAS LAS PROBABILIDADES EN IGUAL A 1
Concepto de Información: Resumen
En el extremo Transmisor la medida de la información es una indicación de la libertad de elección ejercida
por la fuente en la selección de un mensaje.
Si la fuente puede elegir libremente entre muchos mensajes diferentes, el usuario tendrá una gran
incertidumbreacerca de cuál será el mensaje seleccionado.
Pero si no hay posibilidad de elección, si solo hay un mensaje posible, no hay incertidumbre y en
consecuencia tampoco información.
Es evidente que la medida de información incluye las probabilidades.
Los mensajes de alta probabilidad indican poca incertidumbre del usuario y llevan una pequeña cantidad
de información
Medida de la Información
Entonces la auto información asociada con un evento A seria:
Se debería determinar la función que cumpla los siguientes requerimientos:
Cuando se transmite el mensaje A, el usuario recibe IA unidades de información. Si se transmite también
un segundo mensaje B, la información total recibida debe ser la suma de las auto informaciones: IA+ IB
Podemos hablar entonces de un mensaje compuesto: C = A B
Si A y B son estadísticamente independiente: PC= PA .PB y IC= f (PA .PB)
Pero la información recibida es aun IC= IA+ IB
IC= f (PA) + f (PB)
Por lo tanto: f (PA .PB) = f (PA) + f (PB)
Hartley-1928, demostró que la única función que satisface las cuatro condiciones es una función
logarítmica de la forma:
Así la auto información o información mutua se define como:
La base del logaritmo define la unidad de información. La más usada es la base 2 y su unidad es el bit
(contracción de “binary digit”)
Existen muchas razones para usar esta base 2 para medir información, ya que el experimento aleatorio
más simple que uno puede imaginarse es aquel con dos resultados igualmente probables, como por
ejemplo el de arrojar una moneda no defectuosa al aire y observar los resultados:
El conocimiento de cada resultado tiene asociado a: 1 bit de información
Ejemplo: Una fuente de memoria nula genera dos símbolos cuyas probabilidades son PA=1/4 y PB=3/4,
determinar la auto información de cada símbolo y la cantidad total de información de la fuente.
Ejemplo: Supongamos que una fuente produce los símbolos A, B, C y D con probabilidades:
Si los símbolos son independiente, calcular la información contenida en el mensaje BACA:
Ejemplo: Si se lanza una moneda tres veces seguidas, los ocho resultados (mensajes) equiprobables
podrían ser:
Ejemplo: Consideremos una imagen de televisión formada por una estructura de puntos negros, blancos y
grises, dispuestos en 500 filas y 600 columnas aproximadamente. Admitiremos que cada uno de esos
500 X 600 = 300.000 puntos puede adoptar uno de 10 niveles de brillo diferentes, de manera que puede
haber 10300.000 imágenes distintas de TV. Si todas son igualmente probables, la probabilidad de una imagen
cualquier es igual a 1/ 10300.000 y la cantidad de información que contiene:
IIMG= log21/PIMG = 300.000log2 10 = 996.578 bit ≈ 106 bit
IIMG = 1Mbit
A resolver:
¿Qué cantidad de información contienen la observación de los siguientes objetos?
La tirada de un dado equilibrado.
Hallar la información que se tiene cuando se conoce que la carta de un mazo de 52 cartas es de:
corazones, una figura, una figura de corazones
La elección de una letra de alfabeto español (27 letras)
Enviar la palabra MIGUEL
Entropía
La cantidad de información definida en la ecuación: IA =log2 1/PA(bits)
Ha sido obtenida para un solo mensaje, o sea cuanta información brinda (da) un cierto evento o mensaje,
pero no describe a una fuente que produce un conjunto de diferentes mensajes.
Un sistema de comunicación no está diseñado para transmitir un mensaje en particular, sino para transmitir
TODOS los mensajes posibles producidos por la fuente.
Por consiguiente cuando el flujo de instantáneo de información producido por una fuente es aleatorio, es
mejor describir la información de la fuente en términos de la “información promedio” producida.
Definición. Es un parámetro que nos permite determinar el contenido promedio de información de una
fuente o un mensaje en particular. En un proceso de comunicación, transmitimos usualmente secuencias
largas de símbolos, y estamos más interesados en el contenido promedio de información que la fuente
produce, que en la información contenida en cada símbolo
Un sistema de comunicación está diseñado para aceptar todos los mensajes probables sin distinción de
ocurrencia, por lo tanto, la información promedio que produce una fuente se denomina ENTROPÍA DE LA
FUENTE
Entropía de la fuente:
Ejemplo:
Calcular la entropía asociada a un dado, cuando:
•El dado es “correcto”
•Cuando el dado se manipula de manera de que salga un UNO o un SEIS es el doble de la probabilidad de
las otras caras.
Ejemplo:
Consideremos la información producida por una máquina de escribir de 26 letras y el espacio entre letras,
en otras palabras, la fuente produce 27 símbolos. Si los símbolos tuvieran la misma probabilidad
Redundancia
La mayoría de las fuentes de información producen mensajes que no consisten en una única elección
entre posibilidades de igual probabilidad, sino en elecciones sucesivas entre posibilidades de probabilidad
variable y dependiente. A este tipo de secuencias se les denomina procesos estocásticos.
El caso más típico son las letras y palabras que conforman el lenguaje. El escribir en español constituye un
proceso de elecciones dependientes. Por ejemplo, al formar una palabra se elige una primera letra de
todas las posibles primeras letras con diferentes probabilidades; luego, se elige la segunda letra cuya
probabilidad depende de la primera letra seleccionada, y así sucesivamente hasta formar la palabra
deseada.
Lo mismo ocurre en el caso de las palabras para formar oraciones.
Lo importante aquí es señalar el hecho de que, en la medida que se avanza en la formación de una
palabra u oración, el rango de posibles letras o palabras a ser seleccionadas va disminuyendo y la
probabilidad de que ciertas letras o palabras específicas sean seleccionadas va aumentando. Dicho de
otra forma, “tanto la incertidumbre como la información de las últimas letras de una palabra o de las últimas
palabras de una oración es menor comparada con las primeras”
1.- La mayoría de los mensajes se constituyen a partir de un número limitado de posibilidades, por
ejemplo, sólo 27 letras en el caso de nuestro idioma.
2.- La probabilidad de ocurrencia de una de estas posibilidades dentro de un mensaje depende de las
posibilidades seleccionadas previamente; por ejemplo, la probabilidad de que ocurra la letra "q" luego de
una "p" es O. Son estos dos hechos los que en conjunto determinan que todo mensaje contenga cierto
grado de redundancia. En otras palabras, la redundancia se refiere a que las posibilidades dentro de un
mensaje se repiten, y se repiten de una cierta manera predecible. Mientras mayor sea, entonces, la
redundancia de un mensaje, menor será su incertidumbre y menor la información que contenga
Redundancia de una Fuente
Se dice que una fuente es redundante cuando produce símbolos dependientes, es decir símbolos
adicionales generados que no son necesarios en forma absoluta para producir información. Por ejemplo un
texto en ingles tiene una redundancia de alrededor del 50%, es decir que la mitad de los símbolos son
innecesarios. La redundancia de una fuente puede expresarse como:
Ejemplo: calcular la redundancia de una fuente binaria que tiene P(0)=1/4 y P(1)=3/4.
Rd = [(1-0.8)/1]*100= 20%.
Si P(0)=P(1), Rd = 0%
Entropía: Conceptos
Cuando todos los símbolos son igualmente probables (distribución de probabilidad plana), todos
aportan información relevante y la entropía es máxima.
La entropía también se puede considerar como la cantidad de información promedio que contienen
los símbolos usados.
La entropía puede ser considerada como una medida de la incertidumbre y de la información
necesaria para, en cualquier proceso, poder acotar, reducir o eliminar la incertidumbre
Redundancia es aquello que es predecible o convencional en un mensaje, su opuesto es la
Entropía.
La redundancia es el resultado de una alta probabilidad y la entropía de una baja probabilidad
Un mensaje con baja predecibilidad es entrópico y tiene alto contenido informático
Un mensaje con alta predecibilidad esredundante y tiene bajo contenido informático
Tasa de Información
Supongamos que dos fuentes tienen la misma entropía, pero una es mas rápida que la otra, es decir
produce mas símbolos por unidad de tiempo.
En un periodo dado, mas información será transferida de la fuente mas rápida lo cual coloca necesidades
mayores sobre el sistema de comunicación. Por lo tanto la descripción de una fuente no solo es su
entropía (bit/símbolos), sino también (o mas bien..) su TASA DE INFORMACION media en bits/segundo
(bps).
La tasa de Información de una fuente discreta se define como:
Donde σ es la duración promedio del símbolo:
Por lo tanto 1/σ es igual al número promedio de símbolos por unidad de tiempo
Tasa de Información: Ejemplo
Tasa de Información: Ejemplo
Una fuente produce cuatro símbolos A, B, C y D cuyas probabilidades son:
PA = 0,5, PB = 0,25 PC = 0,125, PD = 0,125
La Entropía de la fuente será:
H = 0,5log2 + 0,25log4 + 0,125log8 + 0,125log8 = 1,75 bit/simbolo
Si los símbolos fueran equiprobables, o sea Pi=1/4, entonces:
H = log4 = 2 bit/simbolo
Ahora los símbolos se producen a una velocidad de r=1000 símbolos/seg, entonces la tasa de información
R será:
D Si los símbolos tienen diferentes probabilidades:
Si los símbolos son equiprobables:
O sea la velocidad R es máxima cuando los símbolos son equiprobables
CONCLUSION???
Codificación de los Mensajes
La Fuente discreta genera, aleatoriamente, mensajes digitales arbitrariamente largos, es decir, secuencias
arbitrariamente largas de símbolos de un cierto alfabeto (alfabeto de la fuente). Es un dispositivo que emite
con regularidad y de forma aleatoria símbolos pertenecientes a un cierto conjunto discreto y finito llamado
alfabeto de la fuente.
El Codificador transforma los mensajes generados por la fuente; es decir, convierte una secuencia de
símbolos dada en otra distinta (en general, con símbolos de un alfabeto también distinto del alfabeto de la
fuente, que se denomina alfabeto de codificación, y que habrá de ser necesariamente igual que el alfabeto
de entrada del canal). Esta transformación, cuyo objetivo es la transmisión fiel y eficiente de los mensajes
de la fuente dada, utilizando el canal dado, deberá hacerse teniendo en cuenta tanto las características
estadísticas de los mensajes de la fuente (es decir, de la fuente) como las del ruido que se produce en el
canal.
El Canal discreto ruidoso realiza, aleatoriamente, una transformación indeseable sobre los mensajes que
lo atraviesan, de forma que el mensaje que recibe el decodificador no es, en general, el mismo que ha
generado el codificador
El Decodificador tiene que adivinar qué mensaje de la fuente corresponde al mensaje recibido, conocidas
las reglas de transformación que aplica el codificador
Codificación de la Fuente
Ahora bien, en la práctica, resulta conveniente aislar el efecto que tiene la fuente en el sistema del efecto
que tiene el canal, descomponiendo el codificador/decodificador.
Un Codificador de Fuente, cuya construcción ha de adaptarse a las características de la fuente de forma
que consiga representar los mensajes de la fuente con el menor número posible de símbolos de un cierto
alfabeto de codificación (típicamente los símbolos que se pueden transmitir por el canal dado)
Un Codificador de Canal, cuya construcción ha de adaptarse a las características del canal de forma que
permita la consecución de una transmisión fiable sobre un canal ruidoso con un coste mínimo.
La descomposición del proceso de codificación en dos subprocesos independientes, codificación de fuente
y codificación de canal, facilita el análisis del sistema, por una parte; y, por otra parte, proporciona una gran
flexibilidad en la implementación, porque hace virtualmente independientes los diseños del codificador de
canal y del codificador de fuente
Conceptos de códigos: El codificador óptimo
Un codificador óptimo es aquel que utiliza el mínimo número de bits para codificar un mensaje de la fuente.
Un codificador óptimo usará:
D Códigos cortos para codificar mensajes frecuentes
D Códigos de mayor longitud para aquellos mensajes que sean menos frecuentes.
De esta forma se optimiza el rendimiento del canal o zona de almacenamiento y el sistema es eficiente en
términos del número de bits para representar los mensajes.
Por ejemplo, el código Morse se aprovecha de este principio para optimizar el número de caracteres a
transmitir a partir del estudio de las letras más frecuentes del alfabeto inglés.
“El código Morse no es un codificador óptimo pero sí asigna a las letras más frecuente código más cortos,
justamente para optimizar su eficiencia”
Entropía: Ejemplos
LA ENTROPÍA DE UNA VARIABLE ALEATORIA ES EL NÚMERO MEDIO DE BITS QUE SE
NECESITARÁN PARA CODIFICAR C/U DE LOS ESTADOS DE LA VARIABLE:
SI SE QUIERE REPRESENTAR (CODIFICAR) LOS DIEZ DÍGITOS DECIMALES USANDO SECUENCIAS
DE BITS:
CON 3 DIGITOS BINARIOS NO ES SUFICIENTE, SE NECESITA MÁS.
SI SE USAN 4 DIGITOS BINARIOS TAL VEZ SEA DEMASIADO.
LA ENTROPÍA DE 10 SUCESOS EQUIPROBABLES ES:
EL VALOR CALCULADO ES EL LÍMITE TEÓRICO, QUE NORMALMENTE NO SE PUEDE
ALCANZAR.
SE PUEDE DECIR QUE NO EXISTE NINGUNA CODIFICACIÓN QUE EMPLEE LONGITUDES
PROMEDIO DE MENSAJE INFERIORES AL NÚMERO CALCULADO.
Podemos construir un codificador óptimo basándonos en la entropía de una variable aleatoria de
información x. En efecto, la entropía nos da el número medio de bits necesarios para codificar el mensaje a
través de un codificador óptimo y por tanto nos determina el límite máximo al que se puede comprimir un
mensaje usando un enfoque símbolo a símbolo sin ninguna pérdida de información (demostrado
analíticamente por Shannon), el límite de compresión (en bits) es igual a la entropía multiplicada por el
largo del mensaje. Reescribiendo la ecuación de cálculo de la entropía podemos decir:
por tanto la información que aporta un determinado símbolo xi,
Esta expresión representa el número necesario de bits para codificar el mensaje xi en el codificador óptimo
y por tanto la entropía también se puede considerar como una medida de la información promedio
contenida en cada símbolo del mensaje.
Supongamos que el número de estados de un mensaje es igual a 3 [M1, M2 y M3], donde la probabilidad
de M1 es 50%, la de M2 25% y la de M3 25%.
Por tanto el codificador óptimo necesita de media 1,5 bits para codificar cualquier valor de X.
Por ejemplo podríamos codificar M1 con "0", M2 con "10" y M2 con "11". Usando este convenio para
codificar el mensaje M1M2M1M1M3M1M2M3 usaríamos "010001101011" y por tanto 12 bits. La longitud
promedio del código seria: ??
Conceptos de códigos: El codificador óptimo
Supongamos que el número de estados de un mensaje es igual a 3 [M1, M2 y M3], donde la probabilidad
de M1 es 50%, la de M2 25% y la de M3 25%.
Por tanto el codificador óptimo necesita de media 1,5 bits para codificar cualquier valor de X.
Por ejemplo podríamos codificar M1 con "0", M2 con "10" y M2 con "11". Usando este convenio para
codificar el mensaje M1M2M1M1M3M1M2M3 usaríamos "010001101011" y por tanto 12 bits. La longitud
promedio del código seria:
L(código) = 0,5 ∗ 1 + 0,25 ∗ 2 + 0,25 ∗ 2 = 1,5 bit
El Algoritmo de Huffman
Supongamos que se dispone de una fuente continua que discretizamos empleando un cuantificador
uniforme con 8 niveles. A continuación codificamos sus salidas, asignándole a cada muestra de entrada un
símbolo compuesto por tres bits. Las probabilidades de cada uno de estos símbolos son: P(000) =0.2,
P(001) =0.01, P(010) =0.4, P(011) =0.04, P(100) =0.1, P(101) =0.02, P(110) =0.07 y P(111) =0.16.
En consecuencia, la entropía de esta fuente es
que es significativamente inferior a los 3 bits por muestra que estamos empleando si tomamos
directamente la salida del codificador. La codificación de Huffman le va asignar a cada cadena de 3 bits
una cadena de longitud variable que minimice el número de bits medio por símbolo.