Compressão de Dados Parte 2 - Aula de Introdução à Multimídia

Prévia do material em texto

IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 1
INTRODUÇÃO À MULTIMÍDIA
Compressão de Dados – Parte 2
Prof. Daniel Cunha
dcunha@cin.ufpe.br
2 / 13
Roteiro
� Introdução
� Codificação de Fonte
� Comprimento médio de um código
� Eficiência de um código
� Entropia: uma nova abordagem
� Codificação de Entropia
� Codificação de Shannon-Fano
� Conclusões
3 / 13
Introdução
� Última aula
� Importância da compressão de dados em sistemas
multimídia.
� Teoria da informação (conceitos básicos).
� Fonte de informação discreta.
� Entropia de uma fonte discreta.
� Extensão de uma fonte discreta.
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 2
4 / 13
Codificação de Fonte
� Princípio da codificação de fonte
� Reduzir a redundância da informação da fonte.
5 / 13
Codificação de Fonte
� Telégrafo elétrico
� Código Morse (código de tamanho variável)
� Sequências curtas: letras mais frequentes.
� Sequências longas: letras menos prováveis.
Samuel Morse (1791-1872)
Invenção do código Morse e do telégrafo.
6 / 13
Codificação de Fonte
� Código Morse
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 3
7 / 13
Comprimento Médio de um Código
1
q
i i
i
L p
=
=∑ ℓ
(COMPRIMENTO MÉDIO DE UM CÓDIGO)
8 / 13
Eficiência de um Código
( ) 1H S
L
η = ≤
(EFICIÊNCIA DE UM CÓDIGO)( )1d L H SR
L
η −= − =
(REDUNDÂNCIA DE UM CÓDIGO)
9 / 13
Entropia: outra abordagem
� X, V.A. discreta
Uma urna contém 64 bolas, sendo 16 rotuladas com “1”, 16
rotuladas com “2”, 8 rotuladas com “3”, 8 rotuladas com “4”, 4
rotuladas com “5”, 4 rotuladas com “6”, 4 rotuladas com “7” e 4
rotuladas com “8”. Chico seleciona uma bola da urna ao acaso e
anota o número. Que estratégias Maria pode usar para
descobrir o número da bola por meio de perguntas dirigidas a
Chico, as quais levem a respostas do tipo sim/não? Relacione o
número médio de perguntas com a entropia.
Objetivo: Caracterizar o nº mínimo de perguntas requeridas
para identificar X.
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 4
10 / 13
Codificação de Entropia
� Identificação dos símbolos mais frequentes no fluxo de dados
que são bons candidatos para palavras-código curtas no fluxo
de bits obtido no processo de compressão de dados.
� O projeto de um código de tamanho variável tal que o
comprimento médio da palavra-código se aproxima da
entropia da fonte sem memória é chamado codificação de
entropia.
11 / 13
Codificação de Entropia
� Código de Shannon-Fano
1. Listar os símbolos da fonte em ordem decrescente de
probabilidade;
2. Particionar o conjunto em dois subconjuntos que tenham as
probabilidades mais próximas possíveis. Associe o bit “0” ao
subconjunto superior e o bit “1” ao subconjunto inferior;
3. Continuar o processo, cada vez particionando os
subconjuntos em outros subconjuntos que tenham
probabilidades mais próximas até que não possa ser
realizado nenhum outro particionamento.
12 / 13
Codificação de Shannon-Fano
� Exercício 1
Seja a fonte discreta S={s1,s2,s3,s4,s5,s6} com probabilidades
{p1=0,08;p2=0,05;p3=0,3;p4=0,25;p5=0,2;p6=0,12}. Obtenha um
código de Shannon-Fano. Calcule a entropia da fonte, o
comprimento médio do código e sua eficiência.
� Exercício 2
Faça o mesmo para a fonte discreta S={s1,s2,s3,s4} com
probabilidades {p1=0,2;p2=0,4;p3=0,2;p4=0,2}.
É possível obter outro código com o algoritmo de Shannon-
Fano no Exercício 2?
IF687 - Introdução à Multimídia
Prof. Daniel Cunha - CIn/UFPE 5
13 / 13
Conclusões
� Introdução
� Codificação de Fonte
� Comprimento médio de um código
� Eficiência de um código
� Entropia: uma nova abordagem
� Codificação de Entropia
� Codificação de Shannon-Fano