TEORIA DA INFORMAÇÃO E DA CODIFICAÇÃO

Código: 889

R$ 80,00 Adicionar ao Carrinho

Autor: Rioul, Olivier

Editora: Edu - Unb

Esta obra visa fornecer aos estudantes do segundo ciclo de universidades ou escolas de engenharia as noções essenciais de teoria da informação, para aplicações na codificação de fonte e de canal. Os estudantes aos quais a obra se destina devem possuir as bases da teoria das probabilidades (variáveis aleatórias), disciplina sobre a qual se apoia a teoria da informação. Poucos livros consagrados totalmente ou em grande parte à teoria da informação têm sido publicados em língua francesa, apesar da importância desse assunto para o ensino em universidades e escolas de engenharia. Há duas exceções notáveis: o terceiro volume de Introduction à la théorie de la communication, de Élie Roubine, publicado em 1970, e a monografia de Gérard Battail, Théorie de l’information: Application aux techniques de communication, publicada em 1997. Parece que a presente obra é provavelmente a única referência em francês que trata da teoria da informação a este nível de detalhe, desde a apresentação das ferramentas básicas da teoria (entropia, informação mútua) até a demonstração dos teoremas de Shannon (para a codificação de fonte e de canal). Diversas referências em inglês (ver a bibliografia no final desta obra) têm sido fontes de inspiração, entre elas o excelente The Theory of Information and Coding, de Robert J. McElice e o indiscutível Elements of Information Theory, de Thomas M. Cover e Joy A. Thomas. Algumas partes da presente obra resultam igualmente de trabalhos pessoais do autor, principalmente sobre o estabelecimento de uma ligação com informação de Fisher e sobre uma prova original da desigualdade da variância entrópica. Esta obra nasceu de cursos dados pelo autor na Escola Nacional Superior de Telecomunicações (ENST), na Escola Nacional Superior de Técnicas Avançadas (Ensta), na Universidade Pierre e Marie Curie (Paris VI) e na Universidade de Paris-Sud XI. Sua redação evoluiu regularmente por mais de dez anos. 9 10 Teoria da informação e da codificação Eu gostaria de agradecer aqui a todas as pessoas, colegas e amigos que, de uma maneira ou de outra, tornaram possível a organização dos cursos dos quais este livro provém, ajudaram na sua elaboração, ou me encorajaram a publicá-lo; agradeço em particular à Gerard Battail, Jean-Claude Bic, Maurice Charbit, Gérard Cohen, Pierre Duhamel, Philippe Gallion, Georges Rodriguez-Guisantes e Bruno Thedrez. Boa leitura! Olivier Rioul ficha catalográfica R479 Rioul, Olivier Teoria da informação e da codificação / Olivier Rioul; tradução José Carlos Magossi. – Campinas, sp: Editora da Unicamp; Brasília, df: Editora Universidade de Brasília, 2018. 1. Shannon, Claude E. 2. Teoria da informação. 3. Comunicação – Princípios matemáticos. 4. Sistemas de transmissão de dados. 5. Compressão de dados (Computação) 6. Entropia. I. Magossi, José Carlos. II. Título Sumário Nota Prévia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 PRIMEIRA PARTE. FERRAMENTAS DA TEORIA DA INFORMAÇÃO . . . . . 17 Capítulo 1. Entropia e entropia relativa . . . . . . . . . . . . . . . . . . . . . 19 1.1. Lembretes sobre variáveis aleatórias . . . . . . . . . . . . . . . . . . . 19 1.1.1. Variáveis aleatórias discretas . . . . . . . . . . . . . . . . . . . . . 19 1.1.2. Variáveis aleatórias contínuas . . . . . . . . . . . . . . . . . . . . 22 1.1.3. Notação unificada . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2. Entropia H(X) de uma variável aleatória . . . . . . . . . . . . . . . . 25 1.3. Entropia diferencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4. Entropia relativa ou divergência D(p, q) . . . . . . . . . . . . . . . . . 32 Capítulo 2. Tratamento e informação . . . . . . . . . . . . . . . . . . . . . . 37 2.1. Tratamentos e canais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.1. Tratamentos e canais discretos . . . . . . . . . . . . . . . . . . . . 39 2.1.2. Tratamentos e canais contínuos . . . . . . . . . . . . . . . . . . . 44 2.1.3. Tratamentos e canais recíprocos . . . . . . . . . . . . . . . . . . . 46 2.2. Informação mútua I(X, Y ) . . . . . . . . . . . . . . . . . . . . . . . . 48 Capítulo 3. Informação e entropia . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1. Informação mútua e entropias . . . . . . . . . . . . . . . . . . . . . . . 53 3.2. Informação e incerteza . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3. Diagramas de Venn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4. Informação transmitida sobre canais discretos . . . . . . . . . . . . . . 60 3.5. Informação e entropias diferenciais . . . . . . . . . . . . . . . . . . . . 62 5 Capítulo 4. Concavidade e entropia máxima . . . . . . . . . . . . . . . . . . 69 4.1. Propriedades de concavidade e de convexidade . . . . . . . . . . . . . 69 4.2. Desigualdade de Gibbs e limite de Shannon . . . . . . . . . . . . . . . 73 4.3. Desigualdades de Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Capítulo 5. Cadeias de tratamento e perda de informação . . . . . . . . . . 85 5.1. Cadeias de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 5.1.1. Dois tratamentos sucessivos X ? Y ? Z . . . . . . . . . . . . . 85 5.1.2. Vários tratamentos sucessivos X1 ? X2 ? · · · ? Xn . . . . . . 90 5.2. Desenvolvimento da informação sobre várias v.a. . . . . . . . . . . . . 93 5.3. Tratamento de dados e informação mútua . . . . . . . . . . . . . . . . 99 5.4. Tratamento de dados e divergência . . . . . . . . . . . . . . . . . . . . 104 Capítulo 6. Informação de Fisher e e.q.m. mínimo . . . . . . . . . . . . . . 107 6.1. Informação de Fisher paramétrica J?(X) . . . . . . . . . . . . . . . . 107 6.2. Desigualdade de Cramér-Rao . . . . . . . . . . . . . . . . . . . . . . . 112 6.3. Tratamento de dados e informação de Fisher . . . . . . . . . . . . . . 115 6.4. Erro quadrático médio mínimo Var(?|X) . . . . . . . . . . . . . . . . 118 6.5. Tratamento de dados e e.q.m. mínimo . . . . . . . . . . . . . . . . . . 121 6.6. Informação de Fisher não paramétrica e e.q.m.m. . . . . . . . . . . . . 122 Capítulo 7. Variância entrópica e identidade de Bruijn . . . . . . . . . . . . 127 7.1. Entropia e mistura de variáveis aleatórias . . . . . . . . . . . . . . . . 127 7.2. Variância entrópica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 7.3. Desigualdade da informação de Fisher . . . . . . . . . . . . . . . . . . 135 7.4. Informações de Fisher e de Shannon . . . . . . . . . . . . . . . . . . . 139 7.5. Identidade de Bruijn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 SEGUNDA PARTE. LIMITES E TEOREMAS DE SHANNON . . . . . . . . . . 147 Capítulo 8. Fontes e canais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8.1. Modelos de fontes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8.2. Modelos de canais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 8.3. Entropia e informação mútua dos componentes . . . . . . . . . . . . . 161 Capítulo 9. Codificação de fonte e de canal . . . . . . . . . . . . . . . . . . . 167 9.1. O problema geral de codificação . . . . . . . . . . . . . . . . . . . . . 167 9.2. Codificação de fonte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 9.3. Codificação de canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 9.4. Codificação de fonte/canal conjunta . . . . . . . . . . . . . . . . . . . 176 Capítulo 10. Limites de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . 179 10.1. A desigualdade fundamental da codificação: OPTA . . . . . . . . . . 179 10.2. Codificação de fonte: Função taxa-distorção R(D) . . . . . . . . . . . 182 10.3. Codificação de canal: Função capacidade-custo C(P) . . . . . . . . . 184 10.4. Aspecto das funções R(D) e C(P) . . . . . . . . . . . . . . . . . . . . 186 10.5. Influência da dimensão . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 10.6. Influência da memória . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 Capítulo 11. Cálculo teórico dos limites de Shannon . . . . . . . . . . . . . 199 11.1. R(D) para uma fonte sem memória . . . . . . . . . . . . . . . . . . . 199 11.2. C(P) para um canal aditivo sem memória . . . . . . . . . . . . . . . . 204 11.3. Diversos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 Capítulo 12. Sequências típicas . . . . . . . . . . . . . . . . . . . . . . . . . . 213 12.1. Sequências típicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 12.2. Sequências conjuntamente típicas . . . . . . . . . . . . . . . . . . . . . 216 12.3. Desigualdades de dependência típica . . . . . . . . . . . . . . . . . . . 217 Capítulo 13. Teoremas de Shannon . . . . . . . . . . . . . . . . . . . . . . . . 219 13.1. Codificação de fonte sem perdas . . . . . . . . . . . . . . . . . . . . . 219 13.2. Codificação de canal sem restrição de custo . . . . . . . . . . . . . . . 223 13.3. Codificação de canal: Caso geral . . . . . . . . . . . . . . . . . . . . . 227 13.4. Codificação de fonte com perdas (caso geral) . . . . . . . . . . . . . . 229 13.5. Comentários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 13.6. Codificação fonte/canal . . . . . . . . . . . . . . . . . . . . . . . . . . 234 13.7. O discurso da preguiça . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Anexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 A. Exercícios para a primeira parte . . . . . . . . . . . . . . . . . . . . . . . 241 B. Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 B.1. Codificação ótima para o canal com apagamento . . . . . . . . . . 257 B.2. Capacidade de Hartley do canal uniforme . . . . . . . . . . . . . . 258 B.3. Cálculo da capacidade de canais simétricos . . . . . . . . . . . . . 259 B.4. Enquadramento da função taxa-distorção . . . . . . . . . . . . . . 261 B.5. Enquadramento da capacidade . . . . . . . . . . . . . . . . . . . . 262 B.6. Algoritmo de Blahut-Arimoto . . . . . . . . . . . . . . . . . . . . 262 B.7. Capacidade com via de retorno . . . . . . . . . . . . . . . . . . . . 265 B.8. Capacidade de um canal com estados . . . . . . . . . . . . . . . . 266 B.9. Capacidade de um canal com estados conhecidos . . . . . . . . . 268 B.10. Capacidade do canal gaussiano com desvanecimentos . . . . . . . 269 B.11. Capacidade do canal de Gilbert-Elliott . . . . . . . . . . . . . . . 270 B.12. Entropia de uma fonte estacionária . . . . . . . . . . . . . . . . . . 271 B.13. Capacidade de um canal binário com memória . . . . . . . . . . . 272 B.14. Sistemas seguros em criptografia com chave secreta . . . . . . . . 273 B.15. Codificação fonte-canal em separado no caso gaussiano . . . . . . 275 B.16. Região de capacidade de um canal com acesso múltiplo . . . . . . 276 Bibliografia comentada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Índice remissivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

ISBN:

9788523013103

Ano:

2018

Edição:

1

Formato:

2,00 x 16,00 x 26,00cm

Nº Páginas:

288

Peso:

424g