Grupo 2 -Trabalho Pedido 1 Seminário de Codificação da Fonte

Prévia do material em texto

.
Grupo 2 – Código Estatístico de
Huffman
Comunicações Digitais
Professor: João Matos Pinheiro Filho
Curso: Engenharia Elétrica
.
Grupo 2 – Código Estatístico de
Huffman
Grupo 2 – Integrantes
Edicarlos Silva Fernandes - 1322081056
Clever Mendez Escobedo - 1912081022 
Eduardo Vinicius Cabral - 1512081037
Felipe do Nascimento Tavares - 2122081004
Dárvin Cassiano Posselt - 2112081020
.
Grupo 2 – Código Estatístico de
Huffman
Sumário
● Objetivos Pretendidos
● Introdução
● Realização de codificação de Huffman
● Exemplo de aplicação
● Aplicações na Comunicação Digital
● Energy Efficient in Data Centers
● Conclusão
● Referências Bibliográficas
.
Grupo 2 – Código Estatístico de
Huffman
OBJETIVOS PRETENDIDOS
b.1) Explanar sua importância histórica; 
b.2) Explicar como realizar a codificação por meio de um exemplo;
 
b.3) Listar aplicações em comunicações digitais. 
.
Grupo 2 – Código Estatístico de
Huffman
Introdução
David Albert Huffman
● 09/08/1925, Ohio - 07/10/1999, Santa Cruz. 
● Câncer, final de 1998.
● Engenharia elétrica, Ohio, 1944, mestrado em 1949. Doutorado, 1953, MIT.
● Pioneiro da Ciência da Computação.
● Máquina de estados finitos, comutação de circuitos, processos de síntese e projetos de 
sinais.
.
Grupo 2 – Código Estatístico de
Huffman
Introdução
O Código Estatístico de Huffman, ou Codificação de Huffman.
● Método de compressão.
● Surgiu em 1952, MIT, trabalho final de disciplina.
● Árvore binária de grande eficiência.
● Superou seu professor, Claude Shannon.
● Fortemente utilizado em compactação de fotos e arquivos gerais.
● Método não patenteado, utilizado em “open-source”.
.
Grupo 2 – Código Estatístico de
Huffman
● Realização de codificação de Huffman
Formação do código de Huffman:
1) Árvore tenha sua raiz associada a um símbolo do alfabeto com seu respectivo peso;
2) Remover quaisquer duas árvores cujas raízes tenham menor peso;
3) Repetir o passo anterior até que exista somente uma árvore na floresta.
Edicarlos e Clever- Pág.27 - Tese de doutorado, Compressão de código de programa Usando Fatoração de Operandos. 
.
Grupo 2 – Código Estatístico de
Huffman
● Exemplo de aplicação
Edicarlos e Clever - Pág.27 - Tese de doutorado, Compressão de código de programa Usando Fatoração de Operandos. 
Fig.1 - Dados dos símbolos e dos respectivos pesos/probabilidades iguais a 1.
.
Grupo 2 – Código Estatístico de
Huffman
● Exemplo de aplicação
 Fig.1 - Constrição inicial da árvore de Huffman. 
Edicarlos e Clever - Pág.28 - Tese de doutorado, Compressão de código de programa Usando Fatoração de Operandos.
.
Grupo 2 – Código Estatístico de
Huffman
● Exemplo de aplicação
Fig.2 - Atualização da lista de símbolos.
Edicarlos e Clever - - Pág.28 - Tese de doutorado, Compressão de código de programa Usando Fatoração de Operandos.
.
Grupo 2 – Código Estatístico de
Huffman
● Exemplo de aplicação
 Fig.3 - Árvore de Huffman.
Edicarlos e Clever - Pág.29 - Tese de doutorado, Compressão de código de programa Usando Fatoração de Operandos.
.
Grupo 2 – Código Estatístico de
Huffman
Edicarlos e Clever - Pág.29 - Tese de doutorado, Compressão de código de programa Usando Fatoração de Operandos.
.
Grupo 2 – Código Estatístico de
Huffman
Edicarlos e Clever - Pág.29 - Tese de doutorado, Compressão de código de programa Usando Fatoração de Operandos.
.
Grupo 2 – Código Estatístico de
Huffman
Edicarlos e Clever - Pág.29 - Tese de doutorado, Compressão de código de programa Usando Fatoração de Operandos.
.
Grupo 2 – Código Estatístico de
Huffman
● Aplicações na Comunicação Digital
 
Eduardo e Felipe
Este método de codificação tem uma ampla utilização nas tecnologias multimídia. Sendo um 
algoritmo que permite otimizar a informação sem qualquer tipo de perdas, e é 
extremamente empregado como “passo” final do processamento de dados na compressão de 
imagens, vídeos e ficheiros. Entre os formatos utilizados estão:
JPEG, MPEG, GZIP, FAX E MP3.
Huffman é de utilização livre (não patenteado), sendo uma vantagem em comparação com 
outros métodos de codificação sem perdas, como a codificação aritmética.
É extremamente simples e simultaneamente muito eficaz na codificação de entropia, 
permitindo reduzir significativamente a quantidade de bits necessários para codificar 
qualquer bloco de informação.
.
Grupo 2 – Código Estatístico de
Huffman
Técnica de compressão de imagem (sem perda) 
 
Eduardo e Felipe
.
Grupo 2 – Código Estatístico de
Huffman
Técnica de compressão de imagem (sem perda) 
 
Eduardo e Felipe
.
Grupo 2 – Código Estatístico de
Huffman
● Conclusões da aplicação de Huffman 
 
Eduardo e Felipe
.
Grupo 2 – Código Estatístico de
Huffman
 
Eduardo e Felipe
Energy Efficient in Data Centers
.
Grupo 2 – Código Estatístico de
Huffman
 
Eduardo e Felipe
The amount of data produced in the world is increasing rapidly, and so does the storage needed to 
accommodate all that data. Data centers can be bigger than football fields and require electrical power 
enough to power a whole city.
As data centers are increasingly focused on energy efficiency, it becomes important to develop 
low power implementations of the various applications that run on them. Data compression plays a 
critical role in data centers to mitigate storage and communication costs. This work focuses on 
building a low power, high performance implementation for canonical Huffman encoding.
Data centers are one of the biggest users of data encoding for efficient storage and networking, 
which is typically run on high-end multi-core processors. 
.
Grupo 2 – Código Estatístico de
Huffman
 
Eduardo e Felipe
● Conclusão
A codificação de Huffman tem como principal utilidade à compactação de arquivos, visando 
diminuir o espaço ocupado. 
A sua não patenteação torna o procedimento mais acessível.
Na eficiência energética, o código de Huffman possui várias utilizações, visto que novos 
pensamentos e necessidades sustentabilidade surgem diariamente.
.
Grupo 2 – Código Estatístico de
Huffman
● Referências Bilbiográficas
[1] D. A. Huffman. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the 
IRE, 40(9):1098-1101, setembro 1952.
[2] Fabíola G. P. de Souza. Métodos Universais de Compressão de Dados. Tese de Mestrado, 
IC-UNICAMP, dezembro de 1991.
[3] A Kilo of Data 
https://louridas.github.io/rwa/assignments/a-kilo-of-data/
[4] Energy Efficient Canonical Huffman Encoding - 
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1047.3116&rep=rep1&type=pdf