Baixe o app para aproveitar ainda mais
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
Compartilhar