Compressão e Codificação de Dados - 2004/2005 Docente: José M. Bioucas Dias Instituto de Telecomunicações Tel.: 218418466 (2466) Secção:Telecomunicações
· Exame de época especial no dia 16 de Setembro (quinta-feira), às 9:30. · · Notas dos trabalhos e notas finais de 2003/2004 NOVO: já com as notas de todos os trabalhos (09/09/2004) · · A aula teórica de segunda passou da sala E3 para a FA1 · · Aulas práticas: Segunda 13:30-15:30, sala E4; Quinta 11:00-13:00, sala V114 · · Início das aulas práticas: 27/07/2004 · · Aula prática extraordinária: dia 6/11/2004, sexta feita, no C11 das 10:00 às 12:00 · · · Informações úteis sobre o trabalho · · Notas do 1º exame de 2004/2005 · · Notas do 2º exame de 2004/2005 · · Horário
Avaliação · Exame (50 %) + Trabalho (50%) · · Grupos de trabalho · Licenciatura - até dois alunos · · Mestrado - um aluno ·
Bibliografia: Livros fundamentais: - Introduction to Data Compression, K. Sayood, Morgan Kaufman Publishers, 2000. - Elements of Information Theory, T. Cover and J. Thomas, John Wiley & Sons, 1991. Outros livros recomendados: - Vector Quantization and Signal Compression, A. Gersho and R. Gray, Kluwer Academic Publishers, 1992. - Basic Concepts in Information Theory and Coding, S. Golomb, R. Peile, and R. Scholtz, Plenum Press, 1994. - Communication Theory, C. Gold and R. Pinch, Cambridge University Press, 1991. - Digital Coding of Waveforms, N. Jayant and P. Noll, Prentice-Hall, 1984. - Digital Image Compression: Algorithms and Standards, W. Kou, Kluwer Academic Publishers, 1995. PROGRAMA: Introdução aos elementos fundamentais. Compressão com e sem perdas (lossy/lossless); redundância; irrelevância e aspectos psico-físicos; fontes discretas e contínuas; quantização; noções de codificação de fonte e de canal. Conceitos básicos de teoria da informação. Informação de um evento; fontes discretas sem memória; entropia; entropia condicional, conjunta e relativa (ou divergência de Kullback-Leiber); informação mútua. Desigualdade Gibbs e suas consequências: desigualdade do processamento de dados (data processing inequality). Regras de cadeia (chain rules). Compressão entrópica de fontes discretas sem memória. Códigos descodificáveis e instantâneos; desigualdade de Kraft-McMillan; códigos óptimos (teorema da codificação de fonte, de Shannon); código de Huffman; optimalidade do código de Huffman; codificação de Huffman adaptativa. Codificação de Shannon-Fano-Elias; codificação aritmética. O teorema da equipartição assimptótica e a sua relação com a codificação óptima de Shannon. Conceitos de teoria da informação para processos estocásticos. Fontes não necessariamente sem memória. Taxa de entropia; taxa de entropia condicional; particularização para fontes (processos) estacionários; particularização para fontes (processos) de Markov estacionários. Compressão baseada em dicionários. Conceitos básicos; parsing; greedy parsing; parsing óptimo; técnicas intermédias. Algoritmo de Ziv-Lempel e suas variantes. Compressão predictiva. Exploração da redundância temporal (ou espacial no caso de imagens) como técnica de compressão; noções elementares de estimação/predição óptima; predição linear óptima. Referência à compressão fractal enquanto técnica de compressão predictiva. Codificação/compressão (com perdas) de sinais. Quantização; quantização regular; quantização uniforme; ruído de quantização; quantização óptima. Algoritmos de desenho de quantizadores (algoritmo de Lloyd I). Codificaçao predictiva de sinais (differential pulse code modulation - DPCM; modulação delta); teorema fundamental da codificação predictiva. Quantização vectorial (vector quantization). Quantização regular e politopal. Equivalência entre os quantizadores vectoriais e outros tipos de estruturas. Desempenho de quantizadores vectoriais. Regiões de Voronoi. Algoritmos de desenho de quantizadores vectoriais (algoritmo de Lloyd II). Compressão por transformada. Formulação geral: o problema da alocação de bits, algoritmo de Fox. Transformadas ortogonais. Transformada de Karhunen-Loeve e transformadas sub-óptimas (transformada discreta de coseno - DCT, transformada de Walsh-Hadamard). Transformada de wavelets, representações multi-resolução e em sub-bandas. Exemplos práticos. Codificação/compressão de sinais de voz. Compressão de imagens e de sequências de imagens, as normas JPEG e MPEG como implementações de técnicas de compresão por transformada, compressão predictiva e compressão entrópica. Exames de anos anteriores: Exames de 1998/1999 (primeiro): ps ou pdf , (segundo): ps ou pdf
Resumos:
Última alteração: 13/10/1994 |