Prueba Teoría de Información y Codificación

Prueba Acumulativa N°1

IEE4A3 – Teoría de Información y Codificación

Nombre: Fecha:

El examen tiene una valoración de 150 puntos. El examen consta de 3 secciones, una sección con preguntas, una sección de afirmaciones y una sección con problemas. La sección de preguntas consta de 20 preguntas con una valoración 2 puntos cada uno. La sección de verdadero y falso consta de 10 afirmaciones con una valoración de 1 punto cada una, y cada afirmación incorrecta anulará a una afirmación correcta. La sección de problemas consta de 5 problemas con una valoración de 20 puntos cada uno. Las respuestas pueden contestarse usando un lápiz, excepto las respuestas a las preguntas de verdadero y falso, las cuales deben contestarse usando esferográfico. Duración: 2 horas.

Sección Preguntas:

1. Explique qué entiende por entropía?

2. Para qué se realiza la codificación de fuente? Para qué se realiza la codificación de canal?

3. Explique qué es un bit de información?

4. Qué implica que el valor de la entropía de una fuente sea 0? Qué implica que el valor de la entropía de una fuente sea máxima?

5. Es la probabilidad de un símbolo importante con respecto a la longitud de la palabra código asignada a ese símbolo?

6. Qué es una fuente de memoria nula (FIMN)?

7. Qué es una fuente de Markov?

8. Exponga qué es la función entropía. Grafique la función entropía.

9. Qué relación existe entre la entropía de una extensión de orden n de una FIMN y la entropía de la FIMN?

10. Exponga de forma clara qué significan los siguientes elementos en las fuentes de Markov: estado, probabilidad condicional, probabilidad del suceso simultáneo, probabilidad de estado.

11. Presente el diagrama de estados para una fuente de Markov de segundo orden, con alfabeto {0, 1} y probabilidades condicionales:

( | ) ( | ) ( | ) ( | ) ( | ) ( | ) ( | ) ( | )

12. Qué es una fuente afín? Qué relación tiene la entropía de una fuente de Markov con respecto a la entropía de su fuente afín?

13. Qué es un código?

14. Cuál es la condición para que un código bloque sea unívoco?

15. Explique qué es la longitud de una palabra código? Explique qué es la longitud media de un código?

16. Explique qué es un código compacto?

17. Explique qué debe hacer en caso de que se quiera codificar los símbolos de una fuente, pero sus probabilidades no se pueden expresar como una potencia (codificación de Shannon)?

18. Explique en qué consiste la codificación RLE?

19. Explique por qué un código de Huffman es compacto?

20. En qué se diferencian la compresión con pérdidas de la compresión sin pérdidas?

Conteste Verdadero (V) o Falso (F) según corresponda:

1. Los símbolos de una fuente con mayor probabilidad son los que aportan mayor información ( )

2. En una fuente de Markov no ergódica se tienen secuencias típicas de estados ( )

3. En un código bloque, se asigna a cada símbolo de la fuente una palabra código ( )

4. Un código Singular es aquel en el que todas las palabras códigos son diferentes ( )

5. En un código instantáneo, para decodificar se requiere conocer de las siguientes palabras código ( )

6. Para que un código sea instantáneo se requiere que ninguna palabra coincida con el prefijo de otra ( )

7. La inecuación de Kraft proporciona las condiciones cuantitativas para la existencia de un código instantáneo ( )

8. La compresión con pérdidas es reversible ( )

9. Los métodos estadísticos comprimen usando las propiedades estadísticas de la fuente ( )

10. En la codificación diferencial se codifican las diferencias entre las muestras ( )

Problemas:

1. Dos fuentes de memoria nula y tienen y símbolos respectivamente. Los símbolos de se presentan con probabilidad ; y los de se presentan con probabilidad , las entropías de las fuentes son y respectivamente. Se define una nueva fuente compuesta de y , formada por símbolos. Los primeros símbolos tienen probabilidad y los últimos símbolos tiene probabilidad ̅ . Siendo ̅ .

1. Demostrar que:

( ) ̅ ( )

2. Obtener el , que haga máximo a ( ).

2. El diagrama de estados de una fuente de Markov viene dado por la figura:

1. Calcular las probabilidades estacionarias (de estado).

2. Calcular la entropía de la fuente.

3. Calcular la entropía de la fuente afín.

4. Si p=q, Calcular y dibujar la función entropía.

5. Calcular la entropía de la fuente afín cuando p=q.

q

p

3. Dada la siguiente tabla:

Símbolo

Probabilidad

0,50

0,10

0,10

0,15

0,03

0,01

0,04

0,02

0,05

1. Calcular ( ).

2. Encontrar un código de Shannon-Fano usando un alfabeto

...