Práctica 6: Teoría de la Información (Teoría de las Comunicaciones)

Archivo:Back.png Volver a la página de la materia

Ejercicio 01

Para cada una de las siguientes cadenas de caracteres:

• i) AAAAAAAAAA
• ii) AAABBBCCCDDD
• iii) AAAAAA
• iv) AAAAAAAABB
• v) AAAAABBBCC
• vi) AAABBBCCDD
• vii) AAAAABBBBB
• viii) AAAAAAAABC

Calcular la frecuencia de cada símbolo, hacer su histograma y calcular su entropía. Ordenar las secuencias de menor a mayor entropía. ¿ Qué observa ?

Entropía:$H=\sum _{i=1}^{n}P(Si)*log2(1/P(Si))=-\sum _{i=1}^{n}P(Si)*log2(P(Si))$

La entropía indica la cantidad de información en promedio que una fuente emite medida en bits por símbolo: ¿ Está de acuerdo a la luz de los resultados obtenidos ? ¿ Qué es más compresible: una secuencia con baja o con alta entropía ? ¿ Por qué ? Sacar conclusiones.

Rta:

• i) f(A) = 1, H = 0
• ii) f(s_i) = 1/4, H = 2
• iii) f(A) = 1, H = 0
• iv) f(A) = 4/5, f(B) = 1/5, H = 4/5 * log(3/4) + 7/5 * log(5)

(asi sucesivamente, son cuentas...)

La entropia sera mayor a medida que las probabilidades de aparecer de cada simbolo se parezcan. Es decir, a medida que la precedencia de cada uno sea mas "aleatoria".

Ejercicio 02

Sea una secuencia de números enteros grandes que cumplen la propiedad que dos números consecutivos están a lo sumo una distancia d uno del otro (d pequeño). Piense una forma de disminuir la cantidad de bits necesaria para representar la secuencia. Implemente para la secuencia: 81324, 81326, 81325, 81323, 81323, 81324 y saque conclusiones.

• ¿ Cómo reconstruiría la secuencia original ?
• ¿ Como es la entropía de la secuencia representada con respecto a la entropía de la secuencia original ? ¿ Por qué ?

Rta:

a) Represento poniendo el primer valor de la secuencia y luego para los siguientes codificando con longitud fija el valor de diferencia, usando log_2(d) digitos binarios mas uno que indique si se tiene que restar o sumar (este valor debera ser informado).

b) Como se debe cumplir en ambas representaciones que H <= L, y la nueva longitud L' <= L, entonces la nueva entropia H' <= H (ya se, es una falacia, pero es mas o menos lo que dice en las fotocopias... despues lo pienso mejor)

Ejercicio 03

En una transmisión de fax se necesitan 2.25*10^6 elementos cuadrados de imagen para obtener la resolución adecuada (1500 * 1500 puntos). ¿ Cuál es el máximo contenido de información que puede llegar a trasmitirse si se necesitan 12 niveles de luminosidad para una buena reproducción ?

Rta:

1500 * 1500 * 12 = #imagen

=> supongo que una imagen es un simbolo y son equiprobables

maxCantInf = log(#imagen)

cualquiera!!!! no debería ser maxCantInf = log( 12 ^ (1500 * 1500) ) ????????? así daría más o menos 8MB, lo cual tien más sentido que la otra cuenta, que da nada más que 24 bits!!!!!!!

Ejercicio 04

Un alfabeto consta de los símbolos A B C y D. Para transmitir cada letra se la codifica en una secuencia de dos pulsos binarios; cada pulso dura 5 milisegundos. Se pide:

• a) Calcular la velocidad promedio de transmisión de información si las letras son equiprobables.
• b) ¿ Cuál es dicha velocidad si las probabilidades de ocurrencia de cada letra (símbolo) son Pa = 1/5, Pb = Pc = 1/4 y Pd = 3/10 ?

Rta:

• a) Velocidad promedio

Las letras son equiprobables => H(S) = log2(#simbolos)
H(S) = log_2(4) = 2 bits/simbolo

r = #simbolos/seg
R = tasa de informacion = r * H(S)

10 ms ------- 1 simb
1 seg ------- r = 100 simb/seg

R = 100 simb/seg * 2 bits/simb = 200 bit/seg

• b) Nueva velocidad

H(S) = 1/5 * log2(5) + 1/4 * log2(4) + 1/4 * log2(4) + 3/10 * log2(10/3) ≈ 1.98

R = 100 simb/seg * 1.98 bits/simb = 198 bit/seg

Ejercicio 05

Suponer una sucesión de un millón de dígitos binarios de los cuales 700.000 son ceros. Calcular la información promedio (entropia) de cada dígito. ¿ Cuál es la relación que se debe cumplir para lograr la entropía máxima en el mensaje transmitido ?

Rta:

p(0) = 700000/1000000 = 0.7 p(1) = 0.3

H(S) = -0.7 * log2(0.7) - 0.3 * log2(0.3) = 0.88 bit/simb

Es maxima cuando los digitos son equiprobables (entonces H(S) = 1)

Ejercicio 06

Dados los siguientes símbolos emitidos por un fuente de información, codificados de la siguiente manera:

• S1 = 0
• S2 = 10
• S3 = 110
• S4 = 1110
• S5 = 1111

El código: ¿ Es unívocamente decodificable ? ¿ Es instantáneo ?

Rta:

Es instantáneo (no necesita mirar que simbolo/s siguen para entender a que simbolo codificado corresponde la secuencia actual) porque no tiene prefijos y es unívocamente decodificable por ser instantáneo.

Ejercicio 07

¿ Es posible codificar los símbolos en el caso del ejercicio 4 a) mediante un código binario unívoco de longitud media inferior a dos binits por símbolo ?

Rta:

Como se debe cumplir que H(S) <= L, y la H(S) = 2 entonces la menor longitud promedio posible del codigo es 2. Asique no es posible.

Ejercicio 08

Se transmite a través de un modem una imagen binaria codificada por medio del método Huffman. La imagen original tiene 9.600.000 pixels. Si la velocidad de modulación del modem es de 1200 baudios, calcular el tiempo necesario para transmitirla.

• El modem se ajusta a la norma V.22 bis, con modulación diferencial de fase (DPSK) usando cuatro cambios de fase.
• El código resultante tiene una longitud media de 0.5 binit/píxel.

Ejercicio 09

Un alfabeto consta de los símbolos A, B, C y D. Para transmitir cada letra se la codifica en una secuencia de pulsos binarios; cada pulso dura 10 milisegundos. Se pide:

• Definir un código unívocamente decodificable e instantáneo teniendo en cuenta que las probabilidades de ocurrencia de cada letra (símbolo) son Pa = 1/5, Pb = Pc = 1/4 y Pd = 3/10.
• Cuál es la velocidad de transmisión promedio ?

Respuesta:

Un buen codigo instantaneo y univoco lo da aplicar Huffman, entonces quedaria:

D = 0
B = 10
C = 110
A = 111

La velocidad de transmision promedio es

r = (1/5 * 1 + 1/4 * 2 + 1/4 * 3 + 3/10 * 3) / 10 = 0.235 simbolos/ms
H(S) = 1/5 * log 5 + 1/4 * log 4 + 1/4 * log 4 + 3/10 * log 10/3 = 1.9854753 bit
R = r * H(S) = 0.466586695 bit/ms

Ejercicio 10

Sea un archivo de texto codificado en ASCII. ¿ Qué mecanismo de compresión aplicaría ? ¿ Qué relaciones de la Teoría de la Información se deben cumplir ?

Ejercicio 11

Se tiene un microscopio electrónico conectado a una red de computadoras. El microscopio es capaz de tomar 16 imágenes por segundo a una resolución de 300x200 puntos en 8 colores. Se desean transmitir esas imágenes a través de la red. Se sabe que las imágenes tienen las siguientes proporciones de colores en promedio: Negro 30% - Blanco 21% - Rojo 16% - Amarillo 10% - Azul 8% - Verde 6% - Violeta 5% - Naranja 4%<

¿ Cómo las codificaría para aprovechar mejor el ancho de banda ? ¿ Qué ancho de banda se necesita para transmitir dichas imágenes con la codificación utilizada ? ¿ Y sin comprimir ?

Ejercicio 12

Se tiene una señal de voz de 20KHz digitalizada usando muestras de 16 bits. Se la quiere comprimir tomando en cuenta que la voz humana no varía mucho dentro de un rango pequeño de frecuencias. ¿ Cómo implementaría una compresión que permita enviar esa señal usando menos bits en el medio físico ?

Ejercicio 13

Se tienen los siguientes códigos para un mismo alfabeto de símbolos:

• S1=0 ; S2=10 ; S3=01 ; S4=11
• S1=00 ; S2=01 ; S3=10 ; S4=11

Indicar cuál de los dos es óptimo.

Respuesta:

El segundo, pues el primero no es univocamente decodificable, que es condicion necesaria para ser optimo. No es posible distinguir 0110 en el primero: puede ser S1 S4 S1 o S3 S2.

Ejercicio 14

¿ Un código unívocamente decodificable que no es instantáneo trae problemas de interpretación de la representación de los símbolos ?

Ejercicio 15

Indique si las siguientes afirmaciones son verdaderas o falsas:

• La unión (a nivel de símbolos) de dos códigos óptimos siempre forma un nuevo código óptimo.
• Puede existir un código instantáneo que no sea óptimo.
• La entropía de un alfabeto de símbolos es la cota máxima para la longitud promedio de cualquier codificación del mismo.
• Siempre existe un código instantáneo que no sea óptimo.

Ejercicio 16

Se tienen dos códigos diferentes para un mismo conjunto de símbolos. ¿ Pueden ser ambos óptimos ? ¿ Pueden ser ambos unívocamente decodificables ? ¿ Pueden ser ambos instantáneos ?

Respuesta:

Si, puede tratarse de dos codigos que utilicen la misma codificacion pero asignada a distintos simbolos; si su probabilidad coincide, entonces ambos son optimos.

Por ejemplo, si un codigo C codifica S1 como 01 y S2 como 10, y C' lo hace al reves (con todos los demas simbolos codificados igual), y vale que la probabilidad de S1 y S2 es la misma, entonces C es optimo sii C' lo es.

Como ambos pueden ser optimos, entonces tambien pueden ser univocamente decodificables e instantaneos.

Ejercicio 17

Se desea comprimir un archivo de texto en castellano. El modelo de fuente de información que asume:

• ¿ Afecta al diseño del algoritmo de compresión ?
• ¿ A la relación de compresión ?

Ejercicio 18

Indicar si la siguiente frase es verdadera o falsa: “Dado un conjunto de cantidad X de símbolos, se puede armar infinitos códigos unívocamente decodificables”

Ejercicio 19

Se tienen dos textos, uno escrito en español y el otro su traducción al ingles. Se los quiere codificar a ambos.

• ¿ La codificación puede estar basada en uno de ellos ?
• ¿ Cómo determina si su codificación es óptima ?

Ejercicio 20

Verdadero o falso:

• ¿ Puede haber un código instantáneo que no sea unívocamente decodificable ?
• ¿ Puede haber un código unívocamente decodificable que no sea instantáneo ?

Rta:

• No. Todo código instantáneo es univocamente decodificable. Es más, es univocamente decodificable sin necesidad de conocer símbolos anteriores o siguientes.
• Si. Ejemplo:

S1 ~> 0
S2 ~> 01
S3 ~> 011
S4 ~> 111

S1S4S4 = 0|111|111

Cuando leemos el 0 tenemos que ver que es lo que sigue para poder saber si es S1 o no, todavia puede ser cualquiera de las extenciones (01, 011). Cuando leo el primer uno tengo que seguir pues todavía podría ser 011. Cuando leo 011 tengo que seguir para sacarme las dudas. Al tener 0111, todavía tengo que seguir mirando para saber si es un 0|111 o un 01|111. Y así sucesivamente voy descartando las opciones. Un código de mierda.

Ejercicio 21

Basado en binits, decidir si son verdaderas o falsas las siguientes afirmaciones:

• Dado un conjunto de X símbolos, se pueden crear infinitos códigos instantáneos.
• Dado un conjunto de X símbolos, se pueden crear infinitos códigos óptimos.

Ejercicio 22

Se tiene un archivo de texto en idioma Feudalio el cual tiene un alfabeto que consta únicamente de cuatro símbolos: T (strínguix), P (pórsula), S (sapicá) y el espacio en blanco. Se desea codificarlo en un código binario con los símbolos (binits) 1 (uno) y 0 (cero).

• ¿ Cómo codificaría modelando como una fuente de memoria nula, asumiendo que la entropía

de la fuente es máxima ?

• ¿ Cómo codificaría luego que de analizar el archivo de texto y hallar que la distribución de símbolos sobre 800.000, es de 100.000 para la T, 100.000 para la P, 200.000 para la S y 400.000 para el espacio en blanco ?
• Escriba en binario con cada una de las dos codificaciones anteriores el siguiente texto en Feudalio. ¿ Qué codificación resultó más eficiente ?

ST TS S S PS SP T S SP TS S  P S

Ejercicio 24

Decidir si la siguiente frase es verdadera o falsa: “Dado un código unívocamente decodificable, se pueden obtener infinitos códigos unívocamente decodificables a partir de él”

Ejercicio 25

Decidir si la siguiente frase es verdadera o falsa: “Dado un código instantáneo, se puede obtener infinitos códigos unívocamente decodificables a partir de él”

Rta:

Verdadero. Si se tiene un codigo instantaneo cualquiera se sabe que va a estar libre de prefijos. Por lo tanto, si yo le agrego un mismo bit (ej 1) a todos los codigos tengo otro codigo instantaneo, por lo tanto univocamente decodificable.

Ejercicio 26

Un compresor es un programa que toma una entrada (que podemos considerar formada por un alfabeto de 256 símbolos, ASCII) y la codifica con el objetivo de lograr una salida de longitud promedio inferior a 8 binits/símbolo (reduciendo el tamaño de archivo en el proceso).

Buscando un algoritmo de compresión sin pérdida, un proveedor ofrece un algoritmo capaz de reducir en 20% el tamaño de cualquier archivo de entrada. ¿ Es esto posible ? Justifique su respuesta usando la teoría de la información.

Rta: (que alguien la mire a ver que le parece)

No. Para que un código sea "entendible" debe cumplir que $H(s)\leq L$. En el caso de que nuestra fuente (el texto) aparezca de manera equiprobable los 256 símbolos entonces la entropía será máxima (8 bits/simbolo). El código en ese caso deberá tener una longitud de al menos 8 binits por símbolo.

Ejercicio 27

A qué se debe que existan distintos tipos de codificaciones (NRZ, NRZI, Manchester, 4B/5B) ?

Rta:

Que hace esta pregunta aca?

Ejercicio 28

Se tiene una Fuente de información “S“ de memoria nula que produce n símbolos cada uno con probabilidad asociada Pi, la entropía de dicha fuente es:

$H(S)=-\sum _{i=1}^{n}P_{i}*log_{2}(P_{i})$

1. ¿ Qué define la entropía ?
2. ¿ Cuándo la entropía es máxima ?
3. Dé un ejemplo de una fuente de H máxima = 1 bits/símbolo.

Rta:

1. La entropia define el desorden, la "confusion" que se obtiene a partir de una fuente de informacion. Tambien se puede ver como lo "impredecible" que es. Define la cantidad media de información por símbolo.
2. La entropia es maxima cuando manejamos una fuente de informacion equiprobable. Esto se debe a que no podemos saber ni asumir nada de antemano sobre lo que vamos a obtener de la fuente.
3. Un ejemplo claro de equiprobabilidad y entropia maxima es el resultado de lanzar una moneda al aire, ya que sabemos que las prob. para cada cara es de 1/2.