Docente: Mário A. T. Figueiredo
Secção:Telecomunicações
NOVO: notas
do exame de época
especial, 2004 (exame de 16 de Setembro).
Notas dos trabalhos e notas finais de
2003/2004
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.
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.
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 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