Unidad Ii-Formateada
Unidad Ii-Formateada
Unidad Ii-Formateada
TEORIA DE LA INFORMACION
Cuantificación de la Información.
Los Aportes de Claude Shannon.
Teoría de la información – Concepto-Elementos
Información y Certidumbre.
Información Mutua.
Binit y Bit.
Entropía.
Fuentes Continuas.
Máxima capacidad de transferencia de un canal.
Ley de Shannon-Hartley.
CUANTIFICACIÓN DE LA INFORMACIÓN
TEORIA DE LA INFORMACION
CONCEPTO-ELEMENTOS
P(A) = k/N.
Aplicando la fórmula para el caso mencionado decimos:
N= población de 100 pacientes
K= 5 de los cuales son diabéticos
¿Cuál sería la probabilidad de padecer diabetes?
INFORMACION Y CERTIDUMBRE
La medida de la información.
La capacidad de un canal o sistema de transmisión para transferir
información.
La codificación como un medio de utilizar los sistemas a máxima capacidad.
Estos conceptos pueden ser enlazados por el teorema fundamental de la teoría de
la información que dice:
Letras Código
binario
A 000
B 001
C 010
D 011
E 100
F 101
G 110
H 111
Para enviar una letra deberá enviarse tres variables binarias, así, por ejemplo, si
se quiere emitir la letra " A", deberá transmitirse el código "000", si se quiere enviar
la letra "B", se hará a través del código "001", y así sucesivamente, hasta la "H"
que corresponde al código "111".
Si además, convenimos que se comenzará la transmisión desde el dígito más
significativo (el más a la izquierda), el receptor, a medida que van llegando, irá
disminuyendo la interesa, por cuanto aumenta la probabilidad de arribo de una
determinada letra. Para ello veamos el siguiente ejemplo:
Antes de comenzar la transmisión, el receptor tiene una incertidumbre total de cuál
será el mensaje a recibir. Como la fuente tiene "8" elementos (letras A a la H), y
como todas tienen la misma probabilidad de emitirse (sistema equiprobable), la
incertidumbre tiene una probabilidad de:
A = 000
B = 001
C = 010
D = 011
P = 1/4 = 0,25 = 25 %
Si en el segundo periodo, medimos y nos encontramos que existe una tensión
eléctrica, estamos ante la presencia de un "1", con lo cual se reduce la
incertidumbre por cuanto solo hay dos posibilidades:
C = 010
D = 011
La probabilidad aumenta a:
P = 1/2 = 0,5 = 50 %
C = 010
En este caso la probabilidad será:
P = 1/1 = 1 = 100 %
2n = 24 = 16
Para codificar más símbolos, como ser las letras más los números (0 al 9), y
algunos otros códigos de control se utilizan "n = 7" ó "n = 8" elementos,
dependiendo del tipo de código.
Como podemos apreciar, que ahora los mensajes contienen mayor "cantidad de
información", ya que para letra debemos transmitir 7 u 8 elementos.
Generalizando, si tenemos una fuente con "N = 2n" mensajes posibles a trasmitir,
se requerirá combinar un número mínimo "n" de elementos binarios para codificar
cada uno de los "N". Conocido "N", por definición de logaritmo será:
n = log2 N
O sea:
I = n = log2 N
P = 1/N
Resulta que:
N = 1/P
O sea que:
El caso de la moneda lanzada al aire es: N = 2 (las dos alternativas, cara y cruz) y
E = 1 (la moneda).
A los fines del ejemplo y para facilitar su entendimiento, vamos a realizar algunas
simplificaciones. Para ello vamos a considerar una pantalla compuesta por 500
líneas y 600 columnas, tal como se aprecia en la figura.
Supongamos que cada punto puede tomar 10 valores distintos entre el negro y el
blanco pasando por 8 grises intermedios.
De esta forma, vamos a tener NE = 10300.000 imágenes distintas, que son las
combinaciones de los 300.000 puntos variando entre los 10 valores. Si todas son
igualmente probables, la cantidad de información será, aplicando la formula ( 1):
IA = f(PA)
Donde la función "PA" debe ser determinada. Para encontrar f(PA), es intuitivo
suponer los siguientes requerimientos:
Existen muchas funciones que satisfacen las tres anteriores, pero la decisión final
se obtiene al considerar la transmisión de mensajes independientes.
Cuando el mensaje "A" es entregado al usuario, este recibe "IA" unidades de
información.
Cuando es entregado un segundo mensaje, la información total recibida debería
ser la suma de las informaciones mutuas: IA + IB.
Esto es fácil de ver si consideramos que "A" y "B" vienen de diferentes fuentes.
Pero supongamos que "A" y "B" provienen de la misma fuente: podemos hablar
entonces del mensaje compuesto: C = AB.
Hay una sola ecuación que satisface las condiciones anteriores, y es la función
logarítmica "f(x) = logb (x)". Donde "b" es la base del logaritmo.
IA = logb 1/PA
Lo más usual es tomar "b = 2" denominándose la unidad así determinada como
[bit], como ya habíamos determinado anteriormente. Si PA = PB = 1/2, entonces:
IA = IB = log2 2 = 1 [bit]
IA = IB = Ln 1/PA = 1 [NAT]
Es evidente que:
BINIT Y BIT
Por ejemplo:
Entonces:
IA = log2 4 = 2 [bit]
IB = log2 4/3 = 0,414 [bit]
Ejemplo 1:
Calcular la información asociada a la caída de una moneda ( suceso
estadísticamente independiente).
Ejemplo 2:
Calcular la información entregada por la aparición de una letra entre 32
equiprobable posibles.
Ejemplo 3:
Supongamos que una fuente produce los símbolos A, B, C y D, con probabilidades
1/2, 1/4, 1/8, y 1/8 respectivamente.
Calcular:
La información en cada caso.
Si los símbolos son independientes, calcular los bits de información del mensaje
BACA.
Ejemplo 4:
Calcular la probabilidad de que aparezcan 3 caras consecutivamente en la tirada
de una moneda y su información asociada.
Ejemplo 5:
En un naipe de barajas españolas se extrae una carta. Si me informan que es de
"ORO". ¿Cuántos bits de información ha recibido?. ¿Que información adicional es
necesaria para especificar la carta?
Ejemplo 6:
Supongamos una imagen formada por 400 líneas horizontales, y cada línea con
300 puntos discretos, con una posibilidad de variación de su brillo de 8 niveles
distintos. ¿Cuántas imágenes distintas se podrán formar, y qué cantidad de
información proveerán?
ENTROPIA
Entropía de una fuente
Ya hablamos del concepto de información. De acuerdo a la teoría de la
información, el nivel de información de una fuente se puede medir según la
entropía de la misma. Los estudios sobre la entropía son de suma importancia en
la teoría de la información y se deben principalmente a Shannon, existen a su vez
un gran número de propiedades respecto de la entropía de variables aleatorias
debidas a Kolmogorov.
Dada una fuente "F" que emite mensajes, resulta frecuente observar que los
mensajes emitidos no resulten equiprobables, sino que tienen una cierta
probabilidad de ocurrencia dependiendo del mensaje. Para codificar los mensajes
de una fuente intentaremos utilizar menor cantidad de bits para los mensajes más
probables y mayor cantidad de bits para los mensajes menos probables de forma
tal que el promedio de bits utilizados para codificar los mensajes sea menor a la
cantidad de bits promedio de los mensajes originales. Esta es la base de la
compresión de datos.
Un mundo de 8 bits
Como sabemos un archivo en una computadora es una secuencia de BITS, sin
embargo en nuestras definiciones de entropía y longitud ideal de los caracteres
estamos considerando la probabilidad de ocurrencia de caracteres es decir
bloques de 8 bits, podríamos pensar si los resultados cambiarían considerando
bytes de 9 o 7 bits, por ejemplo. La respuesta es afirmativa, pero la entropía
tendería a aumentar a medida que nos alejamos del valor de 8 bits por byte. El
motivo por el cual ocurre esto reside en que en cualquier archivo almacenado en
una computadora los elementos que pueden ser dependientes unos de otros son
los bytes y no los bits. A medida que nos alejamos del valor de 8 bits para nuestro
concepto de byte perdemos estructura en nuestra fuente y la misma cada vez se
vuelve más aleatoria por lo que podremos comprimirla en menor medida. De aquí
surge que tomemos siempre bytes de 8 bits, tarea que puede sonar obvia pero
que merece más de una reflexión.
Ejemplo:
H * 17 = 47.96 bits.
FUENTES CONTINUAS
Son aquellas cuyos mensajes son funcionales que varían continuamente con el
tiempo. La definición de entropía para fuentes continuas es muy compleja y
escapa a los conceptos de esta materia, no obstante, por razones de simplicidad,
en la mayoría de los casos se aplica la presentación discreta, ya que por razones
de limitaciones físicas fundamentales, los sistemas de computación y de
comunicaciones son procesos discretos sin consideración de la fuente. A título de
ejemplo, veremos una aplicación sobre el idioma:
La información que disponemos en este caso son palabras, es decir una sucesión
de letras que constituyen un texto coherente. Supongamos que utilizamos 27
letras y un espacio, por lo tanto tengo 28 símbolos distintos.
Primer modelo
Suposiciones:
Segundo modelo
Suposiciones:
P(espacio) = 0,1858
P(A) = 0,05642
P(B) = 0,0127
P(Z) = 0,0005
Tercer modelo:
Suposiciones:
H = 3,32 bit/símbolo
Cuarto modelo:
Suposiciones:
H = 3,10 bit/símbolo
Quinto modelo
Suposiciones:
a) Conozco todo el texto anterior.
b) Probabilidades reales.
H = 1 bit/símbolo.
Es decir, que si el sistema es muy eficiente, debo enviar solo 1 bit. Este
último modelo es el más eficiente, ya que debe manejar menor información.
Por lo visto, el primer modelo debe estar preparado para manejar 5 bit/letra, y este
último modelo solo debe manejar 1 bit/letra, o sea, viéndolo de otra forma este
último modelo puede transformase 5 veces más información, o ser 5 veces más
rápido que el primer modelo.
En la práctica se aprovecha el estudio teórico de éstos modelo. El primer modelo
se utiliza normalmente en teletipos, ya que es el más económico. Normalmente se
utilizan cinco dígitos binarios por letras cuando solo sería necesario en promedio
un dígito binario por símbolo si se utilizara en el código morse de puntos y rayas.
Los modelos posteriores, (tercero y cuarto) se utilizan en sistemas muy
sofisticados de comunicaciones, como es el caso de comunicaciones espaciales.
En un futuro se espera poder usar el modelo número cinco.
Nyquist dedujo una ecuación que expresa la velocidad máxima de datos a través
de un canal sin ruido> con un ancho de banda finito.
Shannon lo amplió para el caso de un canal sujeto a ruido aleatorio (término).
Según Nyquist, si una señal arbitraria se la hace pasar a través de un canal con su
Ancho de Banda "H", la señal filtrada puede reconstruirse por completo mediante,
la obtención simple y sencilla de por lo menos "2H" muestras por segundo.
El llevar acabo muestreo de las líneas a frecuencias más altas no tiene sentido,
porque los componentes de frecuencias más altas no pueden recuperarse por
haber sido filtrada. Si la señal contiene "V" niveles discretos, el teorema de Nyquist
establece que:
Hay entonces un tiempo mínimo "t" que se requiere para que la energía cambie, y
una variación mínima detectable de la amplitud.
Por ejemplo, la figura anterior: t = 1 seg; y las variaciones de tensión son +- 1
voltio. Cuando la amplitud máxima es de 3V, solo existen 4 niveles detectables.
Si la señal varía menos de 1 voltio, no podrá ser distinguida entre las variaciones
indeseables del ruido.
NT/t
Sin embargo, inútilmente puede notarse que la información debe ser proporcional
al tiempo de transmisión. Al duplicar T se debería doblar el contenido de
información.
Veremos que existe una estrecha relación entre repuesta en el tiempo y respuesta
en frecuencia, lo que nos permite relacionar información con Ancho de Banda.
1 = superior.
0 = inferior.
De donde:
(n2 12 S + 1) / a 2
Reemplazando n2 tendremos:
C = B log2 [(1 + 12 S) / a2] [bits/seg]
En última instancia esto depende del ruido al tratar de decodificar las señales
recibidas. La elección de "a" depende de la variancia " " y de probabilidad de
error Pe.
El esparcimiento debe ser K veces el ruido (rms) .
C = B log2 [(1 + 12 s)/K2 N][bits/seg]
Veamos un ejemplo:
Un canal telefónica de Ancho de Banda de 3000 Hz, y una S/N = 3 - db
(parámetros típico del sistema) tienen una capacidad teórica de:
C = 3000 log2 ( 1 + 1000) [bits/seg]
log2 1001 = 1/ log10 2 * log 1000 = 1/0,30103 * 3 = 9,9657