Compressão e Codificação de Dados - 2004/2005

Docente: José M. Bioucas Dias
                

Instituto de Telecomunicações
Instituto Superior Técnico
Torre Norte, Piso 10
Av. Rovisco Pais
1049-001  Lisboa
PORTUGAL

Tel.:  218418466 (2466)
E-mail: 
bioucas@lx.it.pt

Secção:Telecomunicações

 

 


                          

 

           

Text Box: Informações Gerais

· 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

·  

· Enunciado do trabalho

·  

· Informações úteis sobre o trabalho

·  

· Notas do 1º exame de 2004/2005

·  

· Notas do 2º exame de 2004/2005

·  

· Notas finais de 2004/2005

·  

· Notas de Época Especial

 

 

 

Horário

 

Teóricas

Segunda 9:30-11:00 (FA1); Sexta 8:00-9:30 (EA5)

Práticas

Segunda 13:30-15:30 (E4); Quinta 11:00-13:00 (V 114)

Dúvidas

Sexta 11:00-13:00 (LT1)

 

 

 

 


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.  
    Cap.'s: 1, 2, 4, 5, 9, 13.

- Elements of Information Theory, T. Cover and J. Thomas, John Wiley & Sons, 1991.  
    Cap.'s: 5, 7, 8, 9, 10, 11, 12.

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
Exames de 1999/2000 (primeiro):
ps  ou  pdf ,  (segundo):ps  ou  pdf
Exames de  2000/2001 (primeiro):
ps  ou  pdf,   (segundo):ps  ou  pdf
Exames de  2001/2002 (primeiro):
ps  ou  pdf    (segundo):ps  ou  pdf
Exames de  2002/2003 (primeiro):
ps  ou  pdf    (segundo):ps  ou  pdf
Exames de  2003/2004 (primeiro):
ps  ou  pdf
Exames de  2004/2005 (primeiro):
pdf

 

 


Resumos:

Capítulo 2

 


Última alteração: 13/10/1994