Lista5 CodigosEficientesCompressao

Prévia do material em texto

Lista 5 – Códigos eficientes e compressã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, determinando assim 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 Shannon-
Fano? 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 codificações obtidas nos 
itens a, b e c. 
 
 
5) Você está desenvolvendo um novo computador, com memória baseada em 
moléculas de DNA. Você utilizará as 4 bases disponíveis para armazenar 
dados. 
 
a) Quantas bases serão necessárias para armazenar 1 Terabyte de dados? 
 
b) Você deseja armazenar um arquivo contendo apenas 8 tipos de símbolos, 
que aparecem em cada posição respectivamente com probabilidades: (10%, 
20%, 20%, 15%, 15%, 10%, 5% e 5%). Proponha uma codificação auto-
pontuável utilizando as bases A, C, T e G que seja a mais enxuta possível e 
determine a eficiência dessa codificação. 
 
 
6) Foi pedido para que você codifique um trava línguas em inglês 
compactamente. Essa é a sentença: “peter piper picked a peck of pickled 
peppers”. A distribuição de frequência dos símbolos é: 
 
 
 
a) Uma forma de codificar essa sequência seria usar um código de tamanho 
fixo, com cada palavra de código minimamente longa para codificar 14 
símbolos diferentes. Quantos bytes seriam necessários para transmitir essa 
frase de 44 caracteres em uma codificação de tamanho fixo? 
 
b) Determine o número mínimo de bits requerido para codificar a frase inteira 
(conteúdo de informação da frase), assumindo que cada caractere é 
independente do caractere em volta. 
 
c) Qual é a contribuição teórica de cada um dos 14 símbolos à informação 
média? 
 
d) Faça um dicionário de códigos para os 14 símbolos usando a codificação de 
Huffman. 
e) Usando a sequência de códigos do item d para codificar a frase: 
i. Quantos bits são necessários? 
ii. Como esse número se compara com o número de bits necessário na 
codificação com tamanho fixo do item a? 
iii) Como esse número se compara com o conteúdo de informação da frase 
calculado no item b? 
 
 
7) Considere uma fonte X com símbolos xi, para i= 1, 2, 3, 4. Sejam os códigos 
binários a seguir: 
 
 
 
a) Quais deles são códigos instantâneos? Explique. 
 
b) Quais deles são unicamente decodificáveis? Explique. 
 
 
8) Explique os códigos de cada coluna abaixo (porque a primeira coluna trata-
se de um código singular, porque a segunda trata-se de um código não-
singular mas não unicamente decodificável, e assim por diante...) 
 
 
 
 
9) Uma fonte X possui quatro símbolos x1, x2, x3 e x4 com p(x1) = ½, p(x2) = 
¼ e p(x3) = p(x4) = 1/8. Construa o código de Shannon-Fano para X. Mostre 
que esse código possui eficiência de 100%. 
 
 
10) Considere uma fonte X com m símbolos xi, i=1, ..., m de mesma 
probabilidade. Seja n o tamanho da palavra de um código de tamanho fixo. 
Mostre que, se n = log2m, então a eficiência do código é de 100%. 
 
 
11) Em uma cadeia de DNA, existem quatro tipos de bases: G, T, C e A.Qual a 
informação contida em uma sequência de DNA de tamanho 10 nos seguintes 
casos? 
 
a) A chance de ocorrência de cada base é igual 
 
b) As bases G e T têm o dobro de chance de ocorrência do que as bases C e A 
 
 
12) Considere os quatro códigos listados abaixo: 
 
 
 
a) Identifique os códigos de prefixo e construa suas árvores de decisão 
individuais. 
 
b) Decodifique a sequência 0011011111000 usando os códigos de prefixo 
identificados no item a. Tente repetir o mesmo procedimento para os códigos 
que não são de prefixo. 
 
 
13) Considere um dado de 8 lados cujas faces estão escritas as letras de A até 
H. Considerando que todas as faces possuem igual probabilidade de saírem, 
discuta se é possível ou não construir um código que seja mais eficiente do que 
o código de tamanho fixo para este caso. 
 
 
14) Uma fonte X possui cinco símbolos com probabilidades: p(x1) = 0,4, p(x2) = 
0,19, p(x3) = 0,16, p(x4) = 0,15 e p(x5) = 0,1. 
 
a) Construa o código de Shannon-Fano para X e calcule a eficiência do código. 
 
b) Repita para o código de Huffman e compare os resultados. 
 
 
15) Uma fonte X possui cinco símbolos de mesma probabilidade. 
 
a) Construa o código de Shannon-Fano para X e calcule a eficiência do código. 
 
b) Repita para o código de Huffman e compare os resultados. 
 
 
 
 
 
 
 
16) Dado viciado: Suponha que o dado está viciado, com as seguintes 
probabilidades: 1: 0.05; 6: 0.3; de 2 a 5: 0,1625. 
 
a) Determine as eficiências dos códigos abaixo 
 
 
 
b) Determine os códigos de Shannon-Fano e de Huffman e suas 
respectivas eficiências. 
 
 
17) Considere uma fonte discreta sem memória cujo alfabeto consiste de K 
símbolos equiprováveis. Que condições devem ser satisfeitas por K e pelo 
tamanho da palavra-código (de tamanho fixo) para que a eficiência de 
codificação seja 100%? 
 
 
18) Joãozinho afirma que é possível projetar um método que produza códigos 
mais eficientes que o de Huffman. Ele elaborou o seguinte método iterativo: 
 
- 1ª iteração: Para os 2 símbolos mais prováveis, atribua palavras-código de 1 
bit seguindo a ordenação binária 
- 2ª iteração: Para os próximos 4 símbolos mais prováveis, atribua palavras-
código de 2 bits seguindo a ordenação binária 
- 3ª iteração: Para os próximos 8 símbolos mais prováveis, atribua palavras-
código de 3 bits seguindo a ordenação binária 
 ... 
- Na iteração: Para os próximos 2N símbolos mais prováveis, atribua palavras-
código de N bits seguindo a ordenação binária 
 
a) Aplique o método descrito por Joãozinho para as seguintes probabilidades 
das seis faces de um dado viciado, obtendo seus códigos correspondentes: 
 
P(X = 1) = 1/4; P(X = 2) = 1/4; P(X = 3) = 1/4; P(X = 4) = 1/8; P(X = 5) = 1/16; P(X = 6) = 1/16 
b) Determine as eficiências do código desenvolvido por Joãozinho e do código 
de Huffman para o dado viciado do item a. Notou algo estranho na eficiência do 
código do Joãozinho? Caso afirmativo, explique o que há de estranho. 
 
19) Os códigos podem ser classificados em 4 tipos 
i – singular 
ii – não-singular,porém não unicamente decodificável 
iii – unicamente decodificável, porém não instantâneo 
iv – instantâneo 
 
a) Determine o tipo de cada um dos códigos a seguir e justifique 
 
a1) Código Morse: 
 
a2) A = 00, B = 01, C = 10, D = 11 
a3) A = 010, B = 100, C = 101, D = 100 
a4) A = 10, B = 11, C = 00, D = 110 
a5) A = 0, B = 011, C = 10, D = 01 
 
b) Por que, no código Morse, é necessária uma pausa (intervalo de tempo 
maior) entre a emissão de dois caracteres (letras ou números) e um intervalo 
de tempo ainda maior entre duas palavras? 
 
 
20) Dois dados não viciados são jogados por Alice e a soma de seus 
resultados é anotada por ela. Bob deve fazer uma sequência de perguntas do 
tipo sim/não para descobrir esse número. Descreva uma estratégia para ele 
fazer isso de maneira a tentar minimizar o número de questões feitas. Essa 
estratégia tem que ser melhor do que aquela obtida para o exercício 8 da 
lista anterior. 
 
21) Considere a mensagem “122121213”. Assumindo que cada caractere é um 
ASCII de 8 bits, como ela seria transmitida na codificação run-length? Qual é a 
taxa de compressão obtida? 
 
 
 
 
 
 
 
22) Consideremos a seguinte variante em versão portuguesa da famosa frase 
do político JFK: 
 
A pergunta de cada um de nós não deve ser o que o país pode fazer por nós; 
mas sim o que cada um de nós pode fazer pelo país 
 
a) Quantos bytes ocupa a frase? 
b) Que frequência tem cada uma das palavras? 
c) Monte um dicionário estático para essa frase com base na resposta da 
questão b. 
d) Quantos bytes ocupa o dicionário? 
 
 
23) Por que run-length pode ser considerado um exemplo de detecção de 
redundância? Esse algoritmo garante economia de espaço? Em que 
circunstâncias o algoritmo resulta num arquivo comprimido que é maior que o 
original? 
 
 
24) Como as sequências a seguir seriam codificadas com run-length? 
 
a) AAABBBBBBYYYYPPPPPPPPPTKKKKKKKK 
b) 111112223333312222221111111333333333 
 
 
25) Qual porcentagem de compressão foi conseguida em cada caso no 
exercício anterior? 
 
26) Em que casos se recomenda o uso de compressão com ou sem perda? 
Discuta. 
 
27) Elabore um método simples para quantizar uma imagem de 8 bits de níveis 
de cinza em outra imagem de 4 bits de níveis de cinza. Tal método pode ser 
facilmente estendido para imagens coloridas (RGB)? 
 
28) Sejam as duas mensagens seguintes: 
 
i) AAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBB 
 
ii) ABABABABABABABABABABABABABABABABABABABAB 
 
A codificação run-length teria um bom desempenho para comprimir a 
mensagem i? E com relação à compressão da mensagem ii? Justifique. 
 
 
 
 
29) Considere uma imagem da bandeira da Alemanha de resolução 30 X 40 no 
padrão RGB de 1 byte por canal, onde as 10 primeiras linhas correspondem à 
cor preta, as 10 linhas seguintes correspondem à cor vermelha e as últimas 10 
linhas correspondem à cor amarela. 
 
a) Qual é o tamanho de um arquivo contendo essa imagem (em bits e em 
bytes)? Justifique. 
 
b) Considere o método de compressão run-length no qual um conjunto de 
pixels consecutivos de mesma cor é codificado com o padrão binário da 
cor correspondente seguida por um valor entre colchetes [X], onde X é o 
número de repetições consecutivas da cor considerada. Suponha que os 
colchetes são representados por 1 byte (caracteres ASCII) e X é um 
número inteiro representado por 4 bytes. Além disso, o arquivo 
compactado deve conter um cabeçalho que informa a resolução do 
arquivo, sendo constituído por dois números inteiros representados por 2 
bytes cada. Qual é o tamanho do arquivo do item anterior após essa 
compressão (em bits e em bytes)? Qual é a taxa de compressão obtida 
em relação ao tamanho do arquivo obtido no item a? Justifique. 
 
c) Qual dos métodos de compressão seria mais adequado para comprimir 
a imagem da bandeira da Alemanha: run-length ou código de Huffman? 
Justifique.