Secção de Análise de Sinais

Compressão e Codificação de Dados (CCD)

Programa Detalhado

Revisões da Teoria das Probabilidades e Variáveis Aleatórias [Carlson]. Exercícios de aplicação na análise estatística dum sistema criptográfico [Stinson].

Teoria da Informação: estudo dos conceitos básicos - entropia, capacidade de canal e codificação.

Conceito de quantidade de informação média ou Entropia [Cover]: dualidade Incerteza-Informação. Definição de Informação Própria da concretização da variável aleatória. Definição de Entropia duma variável aleatória. Entropia Conjunta dum par de variáveis aleatórias; Entropia Condicionada e Entropia Condicionada média. Divergência de Kullback-Leibler. Exemplos de aplicação. Informação mútua a duas variáveis aleatórias. Aplicação do conceito de Entropia no domínio da Criptografia: estudo da segurança do sistema criptográfico de Vernam; análise dos Equívocos da Chave e da Mensagem. O sistema de cifra por substituição e referência a outras técnicas de cifra clássicas [Stinson].

Codificação de Fonte [Salomon]: conceito de redundância; definição e exemplos. Redundância numa linguagem natural e a estimação da entropia da linguagem. Estudo da relação entre características estatísticas da fonte, a entropia e a possibilidade de compressão. Métodos de compressão Ad Hoc: codificação de Repetições (Run Length Coding) e codificação Move To Front. Modelo da fonte sem memória e modelo genérico da codificação de fonte. Definição de código fonte e comprimento médio do código. Teorema da Codificação de Fonte de Shannon. Classes de códigos; características dos códigos prefixos; comprimento médio dum código prefixo; Desigualdade de Kraft. Extensão de fonte e código prefixo estendido. Codificação de Shannon-Fano e codificação de Huffman. Exemplos. Codificação de Shannon-Fano-Elias e Codificação Aritmética. Exemplos. Transformadas como pré-processamento para a compressão: Burrows-Wheeler (BWT) e Move To Front (MTF). Análise de resultados de testes. Modelos de fontes discretas com memória e modelos de Markov. Entropia de fontes com memória. Codificação de fontes com memória: codificação preditiva e outros exemplos. O paradigma moderno da compressão: tipos de modelos e tipos de compressores. Análise dos recursos de memória necessários às implementações dos compressores estatísticos. Introdução às técnicas de codificação baseadas em dicionário. A codificação de Ziv e Lempel (LZ) e seu enquadramento histórico. Máquina de gerar sequências com instruções LZ. Codificação LZ77 e suas variantes: estudo do LZSS. Aspectos de implementação. Análise e estudo de variantes do LZSS com codificação de Huffman na saída. Codificação LZ78 e suas variantes. Comparação da eficácia de compressão das técnicas de compressão estudadas, usando o Calgary e o Canterburry Corpus. Referência a técnicas de codificação com perdas: MPEG e JPEG.

Conceito de capacidade de transferência de informação sobre canais discretos e sem memória [Carlson]: análise do canal com entrada binária e saída ternária. Informação mútua e equívocos no canal. Definição de Capacidade do Canal discreto e sem memória: estudo do Canal Binário Simétrico. Teorema da Codificação de Canal de Shannon. Exemplo de codificação dum canal com ruído.

Codificação de Canal [Roman]: conceito de distância de Hamming; distribuição binomial e Probabilidade de erro média de símbolo. Estudo do código de repetição (3,1) e do código de bit de paridade (3,2). Revisões sobre estruturas algébricas: conceito de Espaço Vectorial e aplicação deste conceito nos códigos Lineares. Estudo de códigos de Bloco Lineares: códigos com 1 bit de paridade; códigos de organização em matriz, com linha e coluna de bits de paridade; codificação e descodificação de blocos com 4 bits de dados e 3 bits de paridade. Codificação de Hamming: a geração do código; a matriz geradora, a descodificação por síndroma e padrões de erro; a matriz verificadora de paridade; a distância mínima dos códigos de Hamming. Conceito de Código Dual. Extensão e Redução dos códigos de bloco lineares. Estudo de códigos de bloco Cíclicos: palavras do código como polinómios; operações com polinómios e polinómio gerador. Códigos Cíclicos Sistemáticos: geração do código de Hamming cíclico; cálculo de síndromas; implementação da divisão de polinómios; exemplos de códigos cíclicos: CRC, Golay e BCH. Códigos Convolucionais: geração do código e polinómio gerador; árvore do código, "code trellis" e diagrama de estados como formas de representação do codificador; descodificação dos códigos convolucionais: o algoritmo de Viterbi.

Entropia para fontes contínuas: estudo da máxima entropia. Informação mútua e capacidade de canais contínuos: lei de Hartley-Shannon [Carlson].

Textos de Apoio

	[Carlson]        A. Carlson, Communications Systems (third edition), McGraw-Hill
	[Stinson]         D. Stinson, Cryptography - Theory and Practice, CRC Press
	[Cover]           T. Cover, J. Thomas, Elements of Information Theory, Wiley
	[Salomon]      D. Salomon, Data Compression: the complete reference, Springer

[Roman]      S. Roman, Introduction to Coding and Information Theory, Springer