Siguiente: Programas Arriba: Primeras listas Anterior: Primeras listas

Ejercicios

1. Diseñe un código instantáneo para un alfabeto llano de $n$ símbolos, de manera que las longitudes de cada uno de los códigos de los símbolos coincidan. Indique cuál es el número $k$, en términos de $n$, de símbolos necesarios en el alfabeto código.

2. Decida si el código definido por la siguiente tabla es de decodificación única:

1	01	3	10	5	1100
2	011	4	1000	6	0111

Si no lo fuera, localice dos palabras distintas que produzcan un mismo código.

3. Decida si el código definido por la siguiente tabla es de decodificación única:

0	aa	2	abbbb	4	abbaa	6	bbbab	8	aaaaba
1	aabab	3	ababa	5	babba	7	aaaabb	9	aaaaab

Si no lo fuera, localice dos palabras distintas que produzcan un mismo código.

4. Sea $A=\left(a_{\nu}\right)_{\nu=0}^{n-1}$ un alfabeto de $n$ símbolos. Sea $\sigma\in A^*$ una palabra tal que, para cada $\nu$ tal que $1\leq \nu \leq n-1$ el símbolo $a_{\nu}$ aparece el doble de veces que $a_{\nu-1}$. Describa cómo ha de ser el código de Huffman binario.

5. Sea $A=\left(a_{\nu}\right)_{\nu=0}^{n-1}$ un alfabeto de $n$ símbolos. Sea $\sigma\in A^*$ una palabra tal que todos los símbolos aparecen un mismo número de veces en $\sigma$. Describa cómo ha de ser el código de Huffman binario. Trate por separado el caso en que long($\sigma$) es una potencia de 2 y el caso complementario.

6. Dé un ejemplo de una tabla de frecuencias para un alfabeto de 5 símbolos de manera que el código binario de Huffman tenga una longitud promedio 1.8.

7. En un mensaje $\sigma$ sobre un alfabeto de 4 símbolos, $A=\{a_0,a_1,a_2,a_3\}$, se tiene que el primero, $a_0$ aparece siete veces más que cualquiera de los otros. Construya un código binario que tenga una longitud promedio 1.4.

8. Suponga que se tiene un alfabeto de 256 símbolos de ocurrencias equiprobables. ¿Cuál es el valor de su entropía? ¿Cuántos deben ser los símbolos en el alfabeto para que en ocurrencias equiprobables se tenga una entropía de 50 bits?

9. La efectividad $\Phi:{\bf p}\mapsto\Phi({\bf p})$ de una distribución ${\bf p}$ se define como la razón entre la entropía $H({\bf p})$ y la longitud promedio del código binario de Huffman $\ell_H({\bf p})$ que determina. Encuentre los valores extremos de la efectividad e indique a cuáles distribuciones corresponden.

10. Aplique el teorema de Shannon de Códigos sin Ruido 3.1 a la situación descrita en el ejemplo 3.2 y calcule estimativos, en términos de $k$ y de $p$, de la tasa de compresión esperada.

Siguiente: Programas Arriba: Primeras listas Anterior: Primeras listas