Tmp 25050 Lista4870082511

Universidade Federal do ABC
Disciplina: Natureza da Informação
Lista de Exercícios 04 – Códigos Eficientes
Prof. João Henrique Kleinschmidt
A lista é individual e deve ser escrita à mão.

1) Considere um dado de 8 lados cujas faces estão escritas as letras de A até
H. As probabilidades de sair cada face são: A (1/2), B (1/4), C (1/8), D (1/16), E
(1/32), F (1/64), G (1/128) e H (1/128).
a) Encontre as codificações de Shannon-Fano e de Huffman dos símbolos emitidos por essa fonte
b) Calcule a entropia da fonte e compare com o comprimento médio das codificações obtidas no item a (ou seja, determine as eficiências das codificações Shannon-Fano e Huffman)
2) Um dado viciado de 5 faces possui probabilidade 1/8 de sair a face A e 1/8 de sair a face B. As outras três faces C, D e E possuem ¼ de probabilidade de sair cada uma.
a) Encontre as codificações de Shannon-Fano e de Huffman dos símbolos emitidos por essa fonte.
b) Calcule a entropia da fonte e compare com o comprimento médio dos códigos obtidos no item a (ou seja, determine as eficiências das codificações Shannon-Fano e Huffman).
3) Construa os códigos de Shannon-Fano e de Huffman para o conjunto de símbolos abaixo e compare os comprimentos médios dos códigos obtidos com a entropia H(X), determinando suas eficiências:
Símbolo Probabilidade x1 0,2 x2 0,18 x3, x4, x5 0,1 cada x6 0,061 x7 0,059 x8, x9, x10, x11 0,04 cada x12 0,03 x13 0,01
4) Você deseja transmitir a seguinte frase para um receptor: “esta lista e muito facil”. Para transmitir esta frase, você utiliza o padrão ASCII para mapear os caracteres em sequências de bits (7 bits por caractere).
a) Quantos bits serão necessários para codificar a sequência acima?

b) Como ficaria esta sequência após a aplicação da codificação de ShannonFanno? Qual é o comprimento médio do código gerado?
c) Como ficaria esta sequência após a aplicação da codificação de Huffman?
Qual é o comprimento médio do código gerado?
d) Calcule a entropia da fonte e as eficiências das