Redes de telecomunicações

Elementos de Teoria da Informa¸˜o ca

M´rio A. T. Figueiredo a

Departamento de Engenharia Electrot´cnica e de Computadores e Instituto Superior T´cnico e 1049-001 Lisboa Portugal

Vers˜o 1.5 a

Novembro de 2007

2

Conte´do u
1 Introdu¸˜o ` Teoria da Informa¸˜o ca a ca 1.1 Fontes de Informa¸˜o sem Mem´ria . . . . . . . . . . . . . . . . . . ca o 1.2 Medida de Informa¸˜o: a Entropia . . . . . . . . . . . . . . . . . . ca 1.3 Propriedades Elementares da Entropia e Quantidades Relacionadas 1.3.1 Limites Superior e Inferior para a Entropia . . . . . . . . . 1.3.2 Entropia Conjunta . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Entropia Condicional e Lei de Bayes para Entropias . . . . 1.3.4 Informa¸˜o M´tua . . . . . . . . . . . . . . . . . . . . . . . ca u 1.4 Desigualdade da Informa¸˜o . . . . . . . . . . . . . . . . . . . . . . ca 1.5 Corol´rios da Desigualdade da Informa¸˜o . . . . . . . . . . . . . . a ca 1.6 A Desigualdade do Processamento de Dados . . . . . . . . . . . . . 2 Codifica¸˜o de Fontes Discretas Sem Mem´ria ca o 2.1 C´digos . . . . . . . . . . . . . . . . . . . . . . . . . . o 2.1.1 Defini¸˜es e Nota¸˜o . . . . . . . . . . . . . . . co ca 2.1.2 C´digos N˜o Singulares . . . . . . . . . . . . . o a 2.1.3 C´digos Univocamente Descodific´veis . . . . . o a 2.1.4 C´digos Instantˆneos . . . . . . . . . . . . . . . o a 2.2 Desigualdade de Kraft-McMillan . . . . . . . . . . . . ´ 2.3 C´digos Ideais e C´digos Optimos . . . . . . . . . . . o o ´ 2.4 Limites para os C´digos Optimos . . . . . . . . . . . . o 2.5 Extens˜es de Fonte . . . . . . . . . . . . . . . . . . . . o 2.6 Codifica¸˜o com Modelo Errado . . . . . . . . . . . . . ca 2.7 Codifica¸˜o de Huffman . . . . . . . . . . . . . . . . . ca 2.7.1 Algoritmo de Huffman . . . . . . . . . . . . . . 2.7.2 Escrita Recursiva do Algoritmo de Huffman . . 2.7.3 Demonstra¸˜o de Optimalidade . . . . . . . . . ca 2.7.4 Algoritmo de Huffman para Alfabetos D-´rios . a 2.8 Codifica¸˜o de Shannon-Fano-Elias . . .