2024
Compressão e Codificação de Dados
Nome: Compressão e Codificação de Dados
Cód.: INF13263M
6 ECTS
Duração: 15 semanas/156 horas
Área Científica:
Informática
Língua(s) de lecionação: Português
Língua(s) de apoio tutorial: Português
Objetivos de Desenvolvimento Sustentável
Objetivos de Aprendizagem
Adquirir uma visão geral dos problemas de compressão de dados sem perdas e codificação em canais de comunicação.
Compreender os fundamentos da teoria de informação de Shannon e os limites teóricos aplicáveis à compressão de dados e à capacidade de um canal de comunicação.
Conhecer vários algoritmos comuns de compressão de dados sem perdas e de codificação de canal.
Compreender de que modo os conceitos de teoria da informação podem ser aplicados noutras áreas de conhecimento.
Compreender os fundamentos da teoria de informação de Shannon e os limites teóricos aplicáveis à compressão de dados e à capacidade de um canal de comunicação.
Conhecer vários algoritmos comuns de compressão de dados sem perdas e de codificação de canal.
Compreender de que modo os conceitos de teoria da informação podem ser aplicados noutras áreas de conhecimento.
Conteúdos Programáticos
Introdução à teoria da informação de Shannon.
Modelo fonte-canal-receptor.
Modelos de fontes de informação: fonte discreta sem e com memória.
Cadeias de Markov. Probabilidades estacionárias.
Definição de entropia, entropia condicional e informação mútua. Propriedades.
Teorema de codificação da fonte.
Algoritmos de compressão entrópicos.
Códigos de Shannon, Shannon-Fano e Huffman.
Códigos Shannon-Fano-Elias, Codificação Aritmética.
Algoritmos de compressão universais.
Código de Huffman adaptativo.
Códigos Lempel-Ziv: LZ77, LZ78 e LZW.
Definição de capacidade de um canal discreto sem memória. Algoritmo de Blahut e Arimoto.
Teorema de codificação de canal de Shannon.
Algoritmos de codificação de canal. Detecção e correcção de erros.
Paridade.
Código de repetição e de Hamming.
Turbo códigos e LDPC.
Introdução à compressão de dados com perdas e teoria rate-distortion.
Modelo fonte-canal-receptor.
Modelos de fontes de informação: fonte discreta sem e com memória.
Cadeias de Markov. Probabilidades estacionárias.
Definição de entropia, entropia condicional e informação mútua. Propriedades.
Teorema de codificação da fonte.
Algoritmos de compressão entrópicos.
Códigos de Shannon, Shannon-Fano e Huffman.
Códigos Shannon-Fano-Elias, Codificação Aritmética.
Algoritmos de compressão universais.
Código de Huffman adaptativo.
Códigos Lempel-Ziv: LZ77, LZ78 e LZW.
Definição de capacidade de um canal discreto sem memória. Algoritmo de Blahut e Arimoto.
Teorema de codificação de canal de Shannon.
Algoritmos de codificação de canal. Detecção e correcção de erros.
Paridade.
Código de repetição e de Hamming.
Turbo códigos e LDPC.
Introdução à compressão de dados com perdas e teoria rate-distortion.
Métodos de Ensino
As aulas dividem-se em aulas teóricas, em que é exposta a matéria letiva ao nível da teoria e dos algoritmos, e aulas práticas, onde são resolvidos problemas concretos quer de aplicação da teoria, quer de aplicação prática dos algoritmos em papel e computador.
A avaliação é realizada através da elaboração de trabalhos práticos e de testes escritos ao longo do semestre ou, em alternativa, de um exame final.
Além do ensino presencial referido acima, a unidade curricular está organizada e suportada numa plataforma de ensino electrónica, de modo a ser compatível com a aprendizagem nos regimes tutorial e e-Learning.
A avaliação é realizada através da elaboração de trabalhos práticos e de testes escritos ao longo do semestre ou, em alternativa, de um exame final.
Além do ensino presencial referido acima, a unidade curricular está organizada e suportada numa plataforma de ensino electrónica, de modo a ser compatível com a aprendizagem nos regimes tutorial e e-Learning.
Bibliografia
Livros/Books:
Elements of Information Theory, Cover and Thomas, Wiley.
Information Theory, Inference and Learning Algorithms, MacKay, Cambridge.
Artigos/Papers:
C. Shannon, A Mathematical Theory of Communication, The Bell System Technical Journal, Vol. 27, pp. 379--423, 623--656, July, October, 1948.
R. E. Blahut, Computation of Channel Capacity and Rate-Distortion Functions, IEEE Transactions on Information Theory, Vol. 18, No. 4, July 1972.
Elements of Information Theory, Cover and Thomas, Wiley.
Information Theory, Inference and Learning Algorithms, MacKay, Cambridge.
Artigos/Papers:
C. Shannon, A Mathematical Theory of Communication, The Bell System Technical Journal, Vol. 27, pp. 379--423, 623--656, July, October, 1948.
R. E. Blahut, Computation of Channel Capacity and Rate-Distortion Functions, IEEE Transactions on Information Theory, Vol. 18, No. 4, July 1972.
Equipa Docente (2023/2024 )
- Miguel José Simões Barão [responsável]
